New Cryptanalytic Attack on RSA Modulus N = pq Using Small Prime Difference Method

Cryptography

Kamel Ariffin, MuhammadRezal¹ 

关键词: RSA modulus;    primes difference;    cryptanalysis;    short decryption exponent;    attacks;    continued fraction;   

DOI  :  10.3390/cryptography3010002

学科分类：工程和技术（综合）

来源: mdpi

【 摘 要 】

This paper presents new short decryption exponent attacks on RSA, which successfully leads to the factorization of RSA modulus N = p q in polynomial time. The paper has two parts. In the first part, we report the usage of the small prime difference method of the form| b 2p −a 2 q | < N γwhere the ratio of q p is close tob 2 a 2 , which yields a bound d < 3 2N 3 4− γ from the convergents of the continued fraction expansion of eN − ⌈a 2+b 2a bN⌉ + 1 . The second part of the paper reports four cryptanalytic attacks on t instances of RSA moduliN s=p s q sfor s = 1 , 2 , … , t where we use N − ⌈a 2+b 2a bN⌉ + 1 as an approximation of ϕ ( N ) satisfying generalized key equations of the shapee sd −k sϕ(N s)= 1,e s d s− k ϕ(N s)= 1,e sd −k sϕ(N s)=z s , ande s d s− k ϕ(N s)=z sfor unknown positive integers d , k s, d s, k s , and z s, where we establish that t RSA moduli can be simultaneously factored in polynomial time using combinations of simultaneous Diophantine approximations and lattice basis reduction methods. In all the reported attacks, we have found an improved short secret exponent bound, which is considered to be better than some bounds as reported in the literature.

【 授权许可】

CC BY