Cryptanalysis of RSA Variants with Primes Sharing Most Significant Bits

被引：5

作者：

Cherkaoui-Semmouni, Meryem ^{[1
]}

Nitaj, Abderrahmane ^{[2
]}

Susilo, Willy ^{[3
]}

Tonien, Joseph ^{[3
]}

机构：

[1] Mohammed V Univ Rabat, ENSIAS, ICES Team, Rabat, Morocco

[2] Normandie Univ, LMNO, CNRS, UNICAEN, F-14000 Caen, France

[3] Univ Wollongong, Sch Comp & Informat Technol, Inst Cybersecur & Cryptol, Wollongong, NSW, Australia

来源：

INFORMATION SECURITY (ISC 2021) | 2021年 / 13118卷

关键词：

RSA variants; Continued fractions; Coppersmith's method; Lattice reduction; KEY; EQUATIONS;

D O I：

10.1007/978-3-030-91356-4_3

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

We consider four variants of the RSA cryptosystem with an RSA modulus N = pq where the public exponent e and the private exponent d satisfy an equation of the form ed - k (p(2) - 1) (q(2) - 1) = 1. We show that, if the prime numbers p and q share most significant bits, that is, if the prime difference vertical bar p-q vertical bar is sufficiently small, then one can solve the equation for larger values of d, and factor the RSA modulus, which makes the systems insecure.

引用

页码：42 / 53

页数：12

共 22 条

[1]

[Anonymous], 2018, Lecture Notes in Computer Science

[2]

Boneh D, 1999, LECT NOTES COMPUT SC, V1592, P1

[3]

Boneh D., 1999, Notices Amer. Math. Soc., V46, P203

[4]

Bunder Martin, 2016, Information Security and Privacy. 21st Australasian Conference, ACISP 2016. Proceedings: LNCS 9723, P258, DOI 10.1007/978-3-319-40367-0_16

[5] A generalized attack on RSA type cryptosystems [J].

Bunder, Martin ;

Nitaj, Abderrahmane ;

Susilo, Willy ;

Tonien, Joseph .

THEORETICAL COMPUTER SCIENCE, 2017, 704 :74-81

[6] An efficient probabilistic public-key cryptosystern over quadratic fields quotients [J].

Castagnos, Guilhem .

FINITE FIELDS AND THEIR APPLICATIONS, 2007, 13 (03) :563-576

[7]

Collins T., 1997, US Patent, Patent No. [5,848,159, 5848159]

[8] Small solutions to polynomial equations, and low exponent RSA vulnerabilities [J].

Coppersmith, D .

JOURNAL OF CRYPTOLOGY, 1997, 10 (04) :233-260

[9] Cryptanalysis of RSA with small prime difference [J].

de Weger, B .

APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING, 2002, 13 (01) :17-28

[10]

Elkamchouchi H, 2002, ICCS 2002: 8TH INTERNATIONAL CONFERENCE ON COMMUNICATIONS SYSTEMS, VOLS 1 AND 2, PROCEEDINGS, P91, DOI 10.1109/ICCS.2002.1182444

← 1 2 3 →