Cryptanalysis of RSA with two decryption exponents

作     者：Sarkar, Santanu Maitra, Subhamoy 

作者机构：Indian Stat Inst Appl Stat Unit Kolkata 700108 India 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：2010年第110卷第5期

页      面：178-181页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Council of Scientific and Industrial Research (CSIR)  India 

主　　题：Cryptography RSA Cryptanalysis Factorization Lattice LLL algorithm 

摘      要：In this paper, we consider RSA with N = pq, where p, q are of same bit size, i.e., q p 2q. We study the weaknesses of RSA when multiple encryption and decryption exponents are considered with same RSA modulus N. A decade back, Howgrave-Grahann and Seifert (CQRE 1999) studied this problem in detail and presented the bounds on the decryption exponents for which RSA is weak. For the case of two decryption exponents, the bound was N-0.357. We have exploited a different lattice based technique to show that RSA is weak beyond this bound. Our analysis provides improved results and it shows that for two exponents, RSA is weak when the RSA decryption exponents are less than N-0.416. Moreover, we get further improvement in the bound when some of the most significant bits (MSBs) of the decryption exponents are same (but unknown). (C) 2009 Elsevier B.V. All rights reserved.