Cryptanalysis of RSA with a small parameter revisited

被引：5

作者：

Meng, Xianmeng ^{[1
]}

Zheng, Xuexin ^{[2
]}

机构：

[1] Shandong Univ Finance & Econ, Sch Math, Jinan 250014, Peoples R China

[2] China Acad Elect & Informat Technol, Beijing 100041, Peoples R China

来源：

INFORMATION PROCESSING LETTERS | 2015年 / 115卷 / 11期

关键词：

Algorithms; Cryptanalysis; RSA; The birthday attack; The baby-step giant-step method; EXPONENTS;

D O I：

10.1016/j.ipl.2015.06.013

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Let N = pq be an RSA modulus with balanced primes p and q. Suppose that the public exponent e and private exponent d satisfy ed - 1 = k phi(N). We revisit the birthday attack against short exponent RSA proposed by Meng and Zheng at ACISP 2012. We show that if e > root k(p + q), then N can be factored in both time and space complexity of (O) over tilde (root k). This improves the former result. We also give a detail explanation on how the baby-step giant-step method works. (C) 2015 Elsevier B.V. All rights reserved.

引用

页码：858 / 862

页数：5

共 12 条

[1]

Apostol T. M., 1995, INTRO ANAL NUMBER TH

[2]

Bach E., 1996, ALGORITHMIC NUMBER T

[3]

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

[4] Cryptanalysis of RSA with private key d less than N0.292 [J].

Boneh, D ;

Durfee, G .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2000, 46 (04) :1339-1349

[5]

Durfee G, 2000, LECT NOTES COMPUT SC, V1976, P14

[6]

Menezes A., 1997, HDB APPL CRYPTOGRAPH

[7]

Meng X.M., 2012, LECT NOTES COMPUT SC, V7372, P115

[8]

Nguyen P.Q., 2009, CONT MATH SER

[9]

RIVEST RL, 1978, COMMUN ACM, V21, P120, DOI 10.1145/357980.358017

[10]

Sun HM, 2005, LECT NOTES COMPUT SC, V3386, P199

← 1 2 →