Efficient CRT-RSA Decryption for Small Encryption Exponents

被引:0
作者
Maitra, Subhamoy [1 ]
Sarkar, Santanu [1 ]
机构
[1] Indian Stat Inst, Appl Stat Unit, Kolkata 700108, India
来源
TOPICS IN CRYPTOLOGY - CT-RSA 2010, PROCEEDINGS | 2010年 / 5985卷
关键词
RSA; CRT-RSA; Key Generation; Efficient Decryption; Primes; Exponents; KEY EXPOSURE ATTACKS; CRYPTANALYSIS;
D O I
暂无
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Consider CRT-RSA with the parameters p,q,e, d(p), d(q), where p,g are secret primes, e is the public encryption exponent and d(p), d(q) are the private decryption exponents. We present an efficient method to select CRT-RSA parameters in such a manner so that the decryption becomes faster for small encryption exponents. This is the most frequently used situation for application of RSA in commercial domain. Our idea is to choose e and the factors (with low Hamming weight) of d(p), d(q) first and then applying the extended Euclidean algorithm, we obtain p, q of same bit size. For small e, we get an asymptotic reduction of the order of 1/3 in the decryption time compared to standard CRT-RSA parameters for large N = pq. In case of practical parameters, with 1024 bits N and e = 2(16) + 1, we achieve a reduction of more than 27%. Extensive security analysis is presented for our selected parameters and benchmark examples are also provided.
引用
收藏
页码:26 / 40
页数:15
相关论文
共 50 条
[41]   Small CRT-Exponent RSA Revisited [J].
Atsushi Takayasu ;
Yao Lu ;
Liqiang Peng .
Journal of Cryptology, 2019, 32 :1337-1382
[42]   On the uniformity of distribution of the decryption exponent in fixed encryption exponent RSA [J].
Shparlinski, IE .
INFORMATION PROCESSING LETTERS, 2004, 92 (03) :143-147
[43]   基于DPA对Gauss形式CRT-RSA的选择明文攻击 [J].
李增局 ;
史汝辉 ;
王建新 ;
李超 ;
李海滨 ;
石新凌 .
密码学报, 2016, 3 (02) :202-210
[44]   Information Encryption and Decryption Analysis, Vulnerabilities and Reliability Implementing the RSA Algorithm in Python']Python [J].
Rodriguez G, Rocio ;
Castang M, Gerardo ;
Vanegas, Carlos A. .
APPLIED INFORMATICS (ICAI 2021), 2021, 1455 :391-404
[45]   Comment on "Efficient and Secure Outsourcing Scheme for RSA Decryption in Internet of Things" [J].
Vergnaud, Damien .
IEEE INTERNET OF THINGS JOURNAL, 2020, 7 (11) :11327-11329
[46]   Cryptanalysis of Variants of RSA with Multiple Small Secret Exponents [J].
Peng, Liqiang ;
Hu, Lei ;
Lu, Yao ;
Sarkar, Santanu ;
Xu, Jun ;
Huang, Zhangjie .
PROGRESS IN CRYPTOLOGY - INDOCRYPT 2015, 2015, 9462 :105-123
[47]   一种改进的CRT-RSA防御侧信道攻击算法 [J].
李子木 .
无线电通信技术, 2013, 39 (06) :60-63
[48]   The Implementation of the 1024-bit RSA Encryption/Decryption Algorithms Based on FPGA [J].
Qu, Yingjie ;
Zhao, Qing .
2009 INTERNATIONAL SYMPOSIUM ON INTELLIGENT INFORMATION SYSTEMS AND APPLICATIONS, PROCEEDINGS, 2009, :420-423
[49]   一种关于CRT-RSA算法的差分错误注入攻击 [J].
李增局 .
密码学报, 2016, 3 (06) :546-554
[50]   A polynomial time attack on RSA with private CRT-Exponents smaller than N0.073 [J].
Jochemsz, Ellen ;
May, Alexander .
ADVANCES IN CRYPTOLOGY - CRYPTO 2007, PROCEEDINGS, 2007, 4622 :395-+