A New LSB Attack on Special-Structured RSA Primes

Symmetry

AmirHamzah Abd Ghafar¹  MuhammadRezal Kamel Ariffin¹  MuhammadAsyraf Asbullah¹ 

[1] Institute for Mathematical Research, Universiti Putra Malaysia, Serdang 43400, Selangor Darul Ehsan, Malaysia;

关键词: cryptography;    RSA cryptosystem;    RSA cryptanalysis;    partial key exposure attack;   

DOI  :  10.3390/sym12050838

来源: DOAJ

【 摘 要 】

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=a^m+r_p$ and $q=b^m+r_q$ for $a,b$ are positive integers and m is a positive even number. Second, we assume that the bits of $r_p$ and $r_q$ 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.

【 授权许可】

Unknown