Partial Key Attack Given MSBs of CRT-RSA Private Keys

Amir Hamzah Abd Ghafar, Muhammad Rezal Kamel Ariffin, Sharifah Md Yasin and Siti Hasana Sapar
Additional contact information
Amir Hamzah Abd Ghafar: Institute for Mathematical Research, Universiti Putra Malaysia (UPM), Serdang 43400, Selangor Darul Ehsan, Malaysia
Muhammad Rezal Kamel Ariffin: Institute for Mathematical Research, Universiti Putra Malaysia (UPM), Serdang 43400, Selangor Darul Ehsan, Malaysia
Sharifah Md Yasin: Institute for Mathematical Research, Universiti Putra Malaysia (UPM), Serdang 43400, Selangor Darul Ehsan, Malaysia
Siti Hasana Sapar: Institute for Mathematical Research, Universiti Putra Malaysia (UPM), Serdang 43400, Selangor Darul Ehsan, Malaysia

Mathematics, 2020, vol. 8, issue 12, 1-20

Abstract: 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 | d p − d ˜ p | , | p − p ˜ | < N 1 − α 2 and has determined the largest prime of p − 1 e , it will enable the adversary to factor the RSA modulus N = p q . 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 .

Keywords: CRT-RSA cryptosystem; cryptanalysis; partial-key exposure attack; prime counting function; Dickman’s function (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/12/2188/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/12/2188/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:8:y:2020:i:12:p:2188-:d:458907

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().