On (unknowingly) using near-square RSA primes
The invention in 1978 of the first practical asymmetric cryptosystem known as RSA was a breakthrough within the long history of secret communications. Since its inception, the RSA cryptosystem has become embedded in millions of digital applications with the objectives of ensuring confidentiality, in...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Published: |
MDPI AG
2022
|
| Online Access: | http://psasir.upm.edu.my/id/eprint/102393/ |
| _version_ | 1848863791674032128 |
|---|---|
| author | Ruzai, Wan Nur Aqlili Abd Ghafar, Amir Hamzah Salim, Nur Raidah Kamel Ariffin, Muhammad Rezal |
| author_facet | Ruzai, Wan Nur Aqlili Abd Ghafar, Amir Hamzah Salim, Nur Raidah Kamel Ariffin, Muhammad Rezal |
| author_sort | Ruzai, Wan Nur Aqlili |
| building | UPM Institutional Repository |
| collection | Online Access |
| description | The invention in 1978 of the first practical asymmetric cryptosystem known as RSA was a breakthrough within the long history of secret communications. Since its inception, the RSA cryptosystem has become embedded in millions of digital applications with the objectives of ensuring confidentiality, integrity, authenticity, and disallowing repudiation. However, the generation of the RSA modulus, N=pq which requires p and q to be random primes, may accidentally entail the choice of a special type of prime called a near-square prime. This structure of N may be used unknowingly en masse in real-world applications since no current cryptographic implementation prevents its generation. In this study, we show that use of this type of prime will potentially lead to total destruction of RSA. We present three cases of near-square primes used as RSA primes, set in the form of (i) N=pq=(am−ra)(bm−rb); (ii) N=pq=(am+ra)(bm−rb) ; and (iii) N=pq=(am−ra)(bm+rb). Although (ii) and (iii) are quite similar, p and q must be within the same size range of n-bits, which results in different conditions for both cases. We formulate attacks using three different algorithms to better understand their feasibility. We also provide an efficient countermeasure that it is recommended is adopted by current cryptographic libraries with RSA implementation. |
| first_indexed | 2025-11-15T13:38:32Z |
| format | Article |
| id | upm-102393 |
| institution | Universiti Putra Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-15T13:38:32Z |
| publishDate | 2022 |
| publisher | MDPI AG |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | upm-1023932023-05-22T03:06:55Z http://psasir.upm.edu.my/id/eprint/102393/ On (unknowingly) using near-square RSA primes Ruzai, Wan Nur Aqlili Abd Ghafar, Amir Hamzah Salim, Nur Raidah Kamel Ariffin, Muhammad Rezal The invention in 1978 of the first practical asymmetric cryptosystem known as RSA was a breakthrough within the long history of secret communications. Since its inception, the RSA cryptosystem has become embedded in millions of digital applications with the objectives of ensuring confidentiality, integrity, authenticity, and disallowing repudiation. However, the generation of the RSA modulus, N=pq which requires p and q to be random primes, may accidentally entail the choice of a special type of prime called a near-square prime. This structure of N may be used unknowingly en masse in real-world applications since no current cryptographic implementation prevents its generation. In this study, we show that use of this type of prime will potentially lead to total destruction of RSA. We present three cases of near-square primes used as RSA primes, set in the form of (i) N=pq=(am−ra)(bm−rb); (ii) N=pq=(am+ra)(bm−rb) ; and (iii) N=pq=(am−ra)(bm+rb). Although (ii) and (iii) are quite similar, p and q must be within the same size range of n-bits, which results in different conditions for both cases. We formulate attacks using three different algorithms to better understand their feasibility. We also provide an efficient countermeasure that it is recommended is adopted by current cryptographic libraries with RSA implementation. MDPI AG 2022-09-11 Article PeerReviewed Ruzai, Wan Nur Aqlili and Abd Ghafar, Amir Hamzah and Salim, Nur Raidah and Kamel Ariffin, Muhammad Rezal (2022) On (unknowingly) using near-square RSA primes. Multidisciplinary Digital Publishing Institute MDPI, 14 (9). art. no. 1898. pp. 1-18. ISSN 2073-8994 https://www.mdpi.com/2073-8994/14/9/1898 10.3390/sym14091898 |
| spellingShingle | Ruzai, Wan Nur Aqlili Abd Ghafar, Amir Hamzah Salim, Nur Raidah Kamel Ariffin, Muhammad Rezal On (unknowingly) using near-square RSA primes |
| title | On (unknowingly) using near-square RSA primes |
| title_full | On (unknowingly) using near-square RSA primes |
| title_fullStr | On (unknowingly) using near-square RSA primes |
| title_full_unstemmed | On (unknowingly) using near-square RSA primes |
| title_short | On (unknowingly) using near-square RSA primes |
| title_sort | on (unknowingly) using near-square rsa primes |
| url | http://psasir.upm.edu.my/id/eprint/102393/ http://psasir.upm.edu.my/id/eprint/102393/ http://psasir.upm.edu.my/id/eprint/102393/ |