Post-quantum RSA

被引:21
作者
Bernstein, Daniel J. [1 ,2 ]
Heninger, Nadia [3 ]
Lou, Paul [3 ]
Valenta, Luke [3 ]
机构
[1] Univ Illinois, Dept Comp Sci, Chicago, IL 60607 USA
[2] Tech Univ Eindhoven, Dept Math & Comp Sci, POB 513, NL-5600 MB Eindhoven, Netherlands
[3] Univ Penn, Comp & Informat Sci Dept, Philadelphia, PA 19103 USA
来源
POST-QUANTUM CRYPTOGRAPHY, PQCRYPTO 2017 | 2017年 / 10346卷
基金
美国国家科学基金会; 欧盟地平线“2020”;
关键词
Post-quantum cryptography; RSA scalability; Shor's algorithm; ECM; Grover's algorithm; Make RSA Great Again; DISCRETE LOGARITHMS; PRIME; FACTORIZATION; ALGORITHMS;
D O I
10.1007/978-3-319-59879-6_18
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
This paper proposes RSA parameters for which (1) key generation, encryption, decryption, signing, and verification are feasible on today's computers while (2) all known attacks are infeasible, even assuming highly scalable quantum computers. As part of the performance analysis, this paper introduces a new algorithm to generate a batch of primes. As part of the attack analysis, this paper introduces a new quantum factorization algorithm that is often much faster than Shor's algorithm and much faster than pre-quantum factorization algorithms. Initial pqRSA implementation results are provided.
引用
收藏
页码:311 / 329
页数:19
相关论文
共 56 条
[1]  
Abdalla M, 2010, LNCS, V6212, DOI [10.1007/978-3-642- 14712-8. See [11], DOI 10.1007/978-3-642-14712-8.SEE[11]]
[2]  
[Anonymous], 2012, KERNEL BUG MM HUGE M
[3]  
[Anonymous], 2014, P 23 USENIX SEC S SA
[4]  
[Anonymous], 2015, GNU MP GNU MULTIPLE
[5]  
[Anonymous], 2008, 2 INT C QUANT NAN MI
[6]  
[Anonymous], 1979, Technical Report
[7]  
[Anonymous], 2008, MATH SCI RES I PUBLI
[8]  
[Anonymous], 2001, IACR e-Print Arch.
[9]  
[Anonymous], 2011, LNCS, DOI DOI 10.1007/978-3-642-22792-9
[10]  
Barbulescu R., 2013, Open Book Series, P63, DOI [10.2140/obs.2013.1.63, DOI 10.2140/OBS.2013.1.63]