Partial key attack given MSBs of CRT-RSA private keys
The CRT-RSA cryptosystem is the most widely adopted RSA variant in digital applications. It exploits the properties of the Chinese remainder theorem (CRT) to elegantly reduce the size of the private keys. This significantly increases the efficiency of the RSA decryption algorithm. Nevertheless, an a...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Published: |
Multidisciplinary Digital Publishing Institute
2020
|
| _version_ | 1825952311411736576 |
|---|---|
| author | Abd Ghafar, Amir Hamzah Abd Kamel Ariffin, Muhammad Rezal Kamel Md Yasin, Sharifah Md Sapar, Siti Hasana |
| author_facet | Abd Ghafar, Amir Hamzah Abd Kamel Ariffin, Muhammad Rezal Kamel Md Yasin, Sharifah Md Sapar, Siti Hasana |
| author_sort | Abd Ghafar, Amir Hamzah Abd |
| collection | UPM |
| description | The CRT-RSA cryptosystem is the most widely adopted RSA variant in digital applications. It exploits the properties of the Chinese remainder theorem (CRT) to elegantly reduce the size of the private keys. This significantly increases the efficiency of the RSA decryption algorithm. Nevertheless, an attack on RSA may also be applied to this RSA variant. One of the attacks is called partially known private key attack, that relies on the assumption that the adversary has knowledge of partial bits regarding RSA private keys. In this paper, we mount this type of attack on CRT-RSA. By using partial most significant bits (MSBs) of one of the RSA primes, p or q and its corresponding private exponent, d, we obtain an RSA intermediate. The intermediate is derived from p−1 and RSA public key, e. The analytical and novel reason on the success of our attack is that once the adversary has obtained the parameters: approximation of private exponent d˜p, approximation of p, p˜ and the public exponent e where d˜p,p˜,e=Nα/2 where 0<α≤1/4 such that |dp−d˜p|,|p−p˜|<N1−α2 and has determined the largest prime of p−1e, it will enable the adversary to factor the RSA modulus N=pq. Although the parameter space to find the prime factor is large, we show that one can adjust its “success appetite” by applying prime-counting function properties. By comparing our method with contemporary partial key attacks on CRT-RSA, upon determining a suitable predetermined “success appetite” value, we found out that our method required fewer bits of the private keys in order to factor N. |
| first_indexed | 2024-09-25T03:35:21Z |
| format | Article |
| id | upm.eprints-87060 |
| institution | Universiti Putra Malaysia |
| last_indexed | 2024-09-25T03:35:21Z |
| publishDate | 2020 |
| publisher | Multidisciplinary Digital Publishing Institute |
| record_format | dspace |
| spelling | upm.eprints-870602024-05-16T02:29:28Z http://psasir.upm.edu.my/id/eprint/87060/ Partial key attack given MSBs of CRT-RSA private keys Abd Ghafar, Amir Hamzah Abd Kamel Ariffin, Muhammad Rezal Kamel Md Yasin, Sharifah Md Sapar, Siti Hasana The CRT-RSA cryptosystem is the most widely adopted RSA variant in digital applications. It exploits the properties of the Chinese remainder theorem (CRT) to elegantly reduce the size of the private keys. This significantly increases the efficiency of the RSA decryption algorithm. Nevertheless, an attack on RSA may also be applied to this RSA variant. One of the attacks is called partially known private key attack, that relies on the assumption that the adversary has knowledge of partial bits regarding RSA private keys. In this paper, we mount this type of attack on CRT-RSA. By using partial most significant bits (MSBs) of one of the RSA primes, p or q and its corresponding private exponent, d, we obtain an RSA intermediate. The intermediate is derived from p−1 and RSA public key, e. The analytical and novel reason on the success of our attack is that once the adversary has obtained the parameters: approximation of private exponent d˜p, approximation of p, p˜ and the public exponent e where d˜p,p˜,e=Nα/2 where 0<α≤1/4 such that |dp−d˜p|,|p−p˜|<N1−α2 and has determined the largest prime of p−1e, it will enable the adversary to factor the RSA modulus N=pq. Although the parameter space to find the prime factor is large, we show that one can adjust its “success appetite” by applying prime-counting function properties. By comparing our method with contemporary partial key attacks on CRT-RSA, upon determining a suitable predetermined “success appetite” value, we found out that our method required fewer bits of the private keys in order to factor N. Multidisciplinary Digital Publishing Institute 2020 Article PeerReviewed Abd Ghafar, Amir Hamzah Abd and Kamel Ariffin, Muhammad Rezal Kamel and Md Yasin, Sharifah Md and Sapar, Siti Hasana (2020) Partial key attack given MSBs of CRT-RSA private keys. Mathematics, 8 (12). art. no. 2188. pp. 1-20. ISSN 2227-7390 https://www.mdpi.com/2227-7390/8/12/2188 10.3390/math8122188 |
| spellingShingle | Abd Ghafar, Amir Hamzah Abd Kamel Ariffin, Muhammad Rezal Kamel Md Yasin, Sharifah Md Sapar, Siti Hasana Partial key attack given MSBs of CRT-RSA private keys |
| title | Partial key attack given MSBs of CRT-RSA private keys |
| title_full | Partial key attack given MSBs of CRT-RSA private keys |
| title_fullStr | Partial key attack given MSBs of CRT-RSA private keys |
| title_full_unstemmed | Partial key attack given MSBs of CRT-RSA private keys |
| title_short | Partial key attack given MSBs of CRT-RSA private keys |
| title_sort | partial key attack given msbs of crt rsa private keys |
| work_keys_str_mv | AT abdghafaramirhamzahabd partialkeyattackgivenmsbsofcrtrsaprivatekeys AT kamelariffinmuhammadrezalkamel partialkeyattackgivenmsbsofcrtrsaprivatekeys AT mdyasinsharifahmd partialkeyattackgivenmsbsofcrtrsaprivatekeys AT saparsitihasana partialkeyattackgivenmsbsofcrtrsaprivatekeys |