微信服务号

微信订阅号

2025年3月24日 8:10 星期一
首页 > 过刊浏览>2016年第27卷第3期 >760-767. DOI:10.13328/j.cnki.jos.004922
PDF HTML阅读 XML下载 导出引用 引用提醒
公钥密码分析简介
作者:

Introduction to Public Key Cryptanalysis
Author:
  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [50]
    • |
  • 相似文献
    • |
  • 引证文献
    • | |
  • 文章评论
    摘要:

    对公钥密码体制的密码分析历史的形成,给出一些重要结果的描述和重要文献的历史发展线索,同时对2010年~2014年有限域和椭圆曲线的离散对数问题的突破性进展给予了简单介绍.自公钥密码学1976年诞生以来,公钥密码体制的密码分析已经发展成为非常庞大的多学科交叉研究领域,希望可以给同行和学习密码学的研究生进入该领域起到帮助作用.

    Abstract:

    In this paper the historic development of public-key cryptanalysis and important literature are surveyed.In particular the breakthroughs during 2010~2014 about the discrete logarithm problems for finite fields and elliptic curves are described.Since the birth of public key cryptography, public key cryptanalysis has been developed to be an inter discipline research with tools from mathematics, algorithmic science and experimental simulations.This survey intents to help the young researchers in Chinese cryptologic community to enter this active research field.

    参考文献
    [1] Diffie W, Hellman ME. New directions in cryptography. IEEE Trans. on Information Theory, 1976,22(6):644-654.[doi:10.1109/TIT.1976.1055638]
    [2] Merkle RC. Secure communications over insecure channels. Communications of the ACM, 1978,21(4):294-299.[doi:10.1145/359460.359473]
    [3] Gardner M. A new kind of cipher that would take millions of years to break. Scientific American, 1977,237:120-224.[doi:10. 1038/scientificamerican0877-120]
    [4] Rivest RL, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 1978,21(2):120-126.[doi:10.1145/359340.359342]
    [5] Adleman LM. On distinguishing prime numbers from composite numbers. In:Proc. of the 21st Annual Symp. on Foundations of Computer Science. New York:IEEE, 1980. 387-406.[doi:10.1109/SFCS.1980.28]
    [6] Jr Lenstra HW. Factoring Integers with Elliptic Curves. Annals of Mathematics, 1987,126:649-673.
    [7] Coppersmith D. Fast evaluation of logarithms in fields of characteristic two. IEEE Trans. on Information Theory, 1984,30(4):587-594.[doi:10.1109/TIT.1984.1056941]
    [8] Koblitz N. Elliptic curve cryptosystems. Mathematics of Computation, 1987,48(177):203-209.[doi:10.1090/S0025-5718-1987-0866109-5]
    [9] Miller VS. Use of elliptic curves in cryptography. In:Williams HC, ed. Proc. of the Advances in Cryptology-CRYPTO'85. Berlin, Heidelberg:Springer-Verlag, 1986. 417-426.[doi:10.1007/3-540-39799-X_31]
    [10] Kleinjung T, Aoki K, Franke J, Lenstra AK, Thome E, Bos JW, Gaudry P, Kruppa A, Montgomery PL, Osvik DA, te Riele H, Timofeev A, Zimmermann P. Factorization of a 768-bit RSA modulus. In:Rabin T, ed. Proc. of the Advances in Cryptology-CRYPTO 2010. Berlin, Heidelberg:Springer-Verlag, 2010. 333-350.[doi:10.1007/978-3-642-14623-7_18]
    [11] Barbulescu R, Gaudry P, Joux A, Thome E. A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic. In:Nguyen PQ, Oswald E, eds. Proc. of the Advances in Cryptology-EUROCRYPT 2014. Berlin, Heidelberg:Springer-Verlag, 2014. 1-16.[doi:10.1007/978-3-642-55220-5_1]
    [12] Cheng Q, Wan D, Zhuang J. Traps to the BGJT-algorithm for discrete logarithms. LMS Journal of Computation and Mathematics, 2014,17(A):218-229.[doi:10.1112/S1461157014000242]
    [13] Diffie W. The first ten years of public-key cryptography. Proc. of the IEEE, 1988,76(5):560-577.[doi:10.1109/5.4442]
    [14] McEliece RJ. A public-key cryptosystem based on algebraic coding theory. DSN Progress Report, 1978,42(44):114-116.
    [15] Merkle R, Hellman ME. Hiding information and signatures in trapdoor knapsacks. IEEE Trans. on Information Theory, 1978,24(5):525-530.[doi:10.1109/TIT.1978.1055927]
    [16] Minder L, Shokrollahi A. Cryptanalysis of the Sidelnikov cryptosystem. In:Naor M, ed. Proc. of the Advances in Cryptology-EUROCRYPT 2007. Berlin, Heidelberg:Springer-Verlag, 2007. 347-360.[doi:10.1007/978-3-540-72540-4_20]
    [17] Shamir A. A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem. In:Chaum D, Rivest RL, Sherman AT, eds. Proc. of the Advances in Cryptology. Springer-Verlag, 1983. 279-288.[doi:10.1007/978-1-4757-0602-4_27]
    [18] Shamir A. A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem. IEEE Trans. on Information Theory, 1984,30:699-704.[doi:10.1109/TIT.1984.1056964]
    [19] Lenstra AK, Lenstra HW, Lovász L. Factoring polynomials with rational coefficients. Mathematische Annalen, 1982,261(4):515-534.[doi:10.1007/BF01457454]
    [20] Matsumoto T, Imai H. A class of asymmetric crypto-systems based on polynomials over finite rings. In:Proc. of the IEEE Int'l Symp. on Information Theory. 1983. 131-132.
    [21] Delsarte P, Desmedt Y, Odlyzko A, Piret P. Fast cryptanalysis of the Matsumoto-Imai public key scheme. In:Beth T, Cot N, Ingemarsson I, eds. Proc. of the Advances in Cryptology. Berlin, Heidelberg:Springer-Verlag, 1985. 142-149.[doi:10.1007/3-540-39757-4_14]
    [22] Matsumoto T, Imai H. Public quadratic polynomial-tuples for efficient signature-verification and message-encryption. In:Barstow W, ed. Proc. of the Advances in Cryptology-EUROCRYPT'88. Berlin, Heidelberg:Springer-Verlag, 1988. 419-453.[doi:10. 1007/3-540-45961-8_39]
    [23] Patarin J. Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt'88. In:Coppersmith D, ed. Proc. of the Advances in Cryptology-CRYPT0'95. Berlin, Heidelberg:Springer-Verlag, 1995. 248-261.[doi:10.1007/3-540-44750-4_20]
    [24] Patarin J. Asymmetric cryptography with a hidden monomial. In:Koblitz. N, ed. Proc. of the Advances in Cryptology-CRYPTO'96. Berlin, Heidelberg:Springer-Verlag, 1996. 45-60.[doi:10.1007/3-540-68697-5_4]
    [25] Boneh D. Twenty years of attacks on the RSA cryptosystem. Notices of the AMS, 1999,46(2):203-213.
    [26] Wiener MJ. Cryptanalysis of short RSA secret exponents. IEEE Trans. on Information Theory, 1990,36(3):553-558.[doi:10.1109/18.54902]
    [27] Boneh D, Durfee G. Cryptanalysis of RSA with private key d less than N0.292. IEEE Trans. on Information Theory, 2000,46(4):1339-1349.[doi:10.1109/18.850673]
    [28] Coppersmith D. Small solutions to polynomial equations, and low exponent RSA vulnerabilities. Journal of Cryptology, 1997,10(4):233-260.[doi:10.1007/s001459900030]
    [29] Halderman JA, Schoen SD, Heninger N, Clarkson W, Paul W, Calandrino JA, Felten EW. Lest we remember:Cold-boot attacks on encryption keys. Communications of the ACM, 2009,52(5):91-98.[doi:10.1145/1506409.1506429]
    [30] Heninger N, Shacham H. Reconstructing RSA private keys from random key bits. In:Halevi S, ed. Proc. of the Advances in Cryptology-CRYPTO 2009. Berlin, Heidelberg:Springer-Verlag, 2009. 1-17.[doi:10.1007/978-3-642-03356-8_1]
    [31] Menezes AJ, Okamoto T, Vanstone SA. Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Trans. on Information Theory, 1993,39(5):1639-1646.[doi:10.1109/18.259647]
    [32] Frey G, Rück HG. A remark concerning-divisibility and the discrete logarithm in the divisor class group of curves. Mathematics of computation, 1994,62(206):865-874.[doi:10.2307/2153546]
    [33] Semaev I. Evaluation of discrete logarithms in a group of P-torsion points of an elliptic curve in characteristic. Mathematics of Computation of the American Mathematical Society, 1998,67(221):353-356.[doi:10.1090/S0025-5718-98-00887-4]
    [34] Smart NP. The discrete logarithm problem on elliptic curves of trace one. Journal of Cryptology, 1999,12(3):193-196.[doi:10. 1007/s001459900052]
    [35] Satoh T. Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves. Commentarii mathematici Universitatis Sancti Pauli, 1998,47(1):81-92.
    [36] Gaudry P, Hess F, Smart NP. Constructive and destructive facets of Weil descent on elliptic curves. Journal of Cryptology, 2002, 15(1):19-46.[doi:10.1007/s00145-001-0011-x]
    [37] Hess F. Generalizing the GHS attack on the elliptic curve discrete logarithm problem. LMS Journal of Computation and Mathematics, 2004,7:167-192.[doi:10.1112/S146115700000108X]
    [38] Menezes A, Qu M. Analysis of the Weil descent attack of Gaudry, Hess and Smart. In:Naccache D, ed. Proc. of the Topics in Cryptology-CT-RSA 2001. Berlin, Heidelberg:Springer-Verlag, 2001. 308-318.[doi:10.1007/3-540-45353-9_23]
    [39] Menezes A, Teske E. Cryptographic implications of Hess' generalized GHS attack. Applicable Algebra in Engineering, Communication and Computing, 2006,16(6):439-460.[doi:10.1007/s00200-005-0186-8]
    [40] Semaev I. Summation polynomials and the discrete logarithm problem on elliptic curves. IACR Cryptology ePrint Archive, 2004, 2004:31.
    [41] Gaudry P. Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem. Journal of Symbolic Computation, 2009,44(12):1690-1702.[doi:10.1016/j.jsc.2008.08.005]
    [42] Diem C. On the discrete logarithm problem in elliptic curves. Compositio Mathematica, 2011,147(1):75-104.[doi:10.1112/S0010437X10005075]
    [43] Faugère JC, Perret L, Petit C, Renault G. Improving the complexity of index calculus algorithms in elliptic curves over binary fields, In:Pointcheval D, Johansson T, eds. Proc. of the Advances in Cryptology-EUROCRYPT 2012. Berlin, Heidelberg:Springer-Verlag, 2012. 27-44.[doi:10.1007/978-3-642-29011-4_4]
    [44] Shantz M, Teske E. Solving the elliptic curve discrete logarithm problem using Semaev polynomials, Weil descent and Gröbner basis methods-An experimental study. In:Fischlin M, Katzenbeisser S, eds. Proc. of the Number Theory and Cryptography. Berlin, Heidelberg:Springer-Verlag, 2013. 94-107.[doi:10.1007/978-3-642-42001-6_7]
    [45] Coppersmith D, Shamir A. Lattice attacks on NTRU. In:Fumy W, ed. Proc. of the Advances in Cryptology-EUROCRYPT'97. Berlin, Heidelberg:Springer-Verlag, 1997. 52-61.[doi:10.1007/3-540-69053-0_5]
    [46] Howgrave-Graham N, Nguyen PQ, Pointcheval D, Proos J, Silverman JH, Singer A, Whyte W. The impact of decryption failures on the security of NTRU encryption. In:Boneh D, ed. Proc. of the Advances in Cryptology-CRYPTO 2003. Berlin, Heidelberg:Springer-Verlag, 2003. 226-246.[doi:10.1007/978-3-540-45146-4_14]
    [47] Gentry C, Szydlo M. Cryptanalysis of the revised NTRU signature scheme. In:Knudsen LR, ed. Proc. of the Advances in Cryptology-EUROCRYPT 2002. Berlin, Heidelberg:Springer-Verlag, 2002. 299-320.[doi:10.1007/3-540-46035-7_20]
    [48] Howgrave-Graham N. A hybrid lattice-reduction and meet-in-the-middle attack against NTRU. In:Menezes A, ed. Proc. of the Advances in Cryptology-CRYPTO 2007. Berlin, Heidelberg:Springer-Verlag, 2007. 150-169.[doi:10.1007/978-3-540-74143-5_9]
    [49] Stehlé D, Steinfeld R. Making NTRU as secure as worst-case problems over ideal lattices. In:Paterson KG, ed. Proc. of the Advances in Cryptology-EUROCRYPT 2011. Berlin, Heidelberg:Springer-Verlag, 2011. 27-47.[doi:10.1007/978-3-642-20465-4_4]
    [50] Perlner RA, Cooper DA. Quantum resistant public key cryptography:A survey. In:Proc. of the 8th Symp. on Identity and Trust on the Internet. New York:ACM Predd, 2009. 85-93.[doi:10.1145/1527017.1527028]
    相似文献
    引证文献
引用本文

肖人毅.公钥密码分析简介.软件学报,2016,27(3):760-767

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2015-03-09
  • 最后修改日期:2015-05-20
  • 录用日期:2015-06-13
  • 在线发布日期: 2015-11-12
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19727196位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号