UPM Institutional Repository

A new LSB attack on special-structured RSA primes


Abd Ghafar, Amir Hamzah and Kamel Ariffin, Muhammad Rezal and Asbullah, Muhammad Asyraf (2020) A new LSB attack on special-structured RSA primes. Symmetry, 12 (5). art. no. 838. pp. 1-13. ISSN 2073-8994


Asymmetric key cryptosystem is a vital element in securing our communication in cyberspace. It encrypts our transmitting data and authenticates the originality and integrity of the data. The Rivest–Shamir–Adleman (RSA) cryptosystem is highly regarded as one of the most deployed public-key cryptosystem today. Previous attacks on the cryptosystem focus on the effort to weaken the hardness of integer factorization problem, embedded in the RSA modulus, N=pq . The adversary used several assumptions to enable the attacks. For examples, p and q which satisfy Pollard’s weak primes structures and partial knowledge of least significant bits (LSBs) of p and q can cause N to be factored in polynomial time, thus breaking the security of RSA. In this paper, we heavily utilized both assumptions. First, we assume that p and q satisfy specific structures where p=am+rp and q=bm+rq for a,b are positive integers and m is a positive even number. Second, we assume that the bits of rp and rq are the known LSBs of p and q respectively. In our analysis, we have successfully factored N in polynomial time using both assumptions. We also counted the number of primes that are affected by our attack. Based on the result, it may poses a great danger to the users of RSA if no countermeasure being developed to resist our attack.

Download File

[img] Text
Restricted to Repository staff only

Download (283kB)
Official URL or Download Paper: https://www.mdpi.com/2073-8994/12/5/838

Additional Metadata

Item Type: Article
Divisions: Faculty of Science
Institute for Mathematical Research
Centre of Foundation Studies for Agricultural Science
DOI Number: https://doi.org/10.3390/sym12050838
Publisher: MDPI
Keywords: Cryptography; RSA cryptosystem; RSA cryptanalysis; Partial key exposure attack
Depositing User: Nabilah Mustapa
Date Deposited: 16 Jun 2020 06:38
Last Modified: 16 Jun 2020 06:38
Altmetrics: http://www.altmetric.com/details.php?domain=psasir.upm.edu.my&doi=10.3390/sym12050838
URI: http://psasir.upm.edu.my/id/eprint/36978
Statistic Details: View Download Statistic

Actions (login required)

View Item View Item