RSA型公钥密码体制的研究
详细信息    本馆镜像全文|  推荐本文 |  |   获取CNKI官网全文
摘要
本文对RSA型公钥密码体制进行了研究。第一章介绍了公钥密码学的研究背景、意义、现状以及公钥密码体制的基本概念和标准RSA体制;第二章对TauyoshiTakagi关于n-adic多块RSA型公钥体制的工作做了详细介绍;在第三章里详细介绍了标准RSA低指数攻击方面的研究成果,包括D.Coppersmith等提出的对低指数相关消息RSA的攻击及最新的由Dan Boneh与Glenn Durfee证明的私钥d     本文的主要结果如下:
     1.指出了D.Coppersmith在文[31]中存在的一些错误和混乱,证明了环Zn上两个加密多项式在Zn上只有唯一公共根,这虽然不能说明用Euclidean算法求环Zn上两个加密多项式的最大公因式从而恢复明文的方法的确定性,但也反映了问题的一个方面。
     2.改进了曹珍富在文[50]中提出的模拟RSA型公钥密码体制,解决了其中存在的密文扩展问题,并讨论了新体制的安全性;提出了一个新的模拟RSA型公钥密码体制,该体制无密文数据扩展,而且在概念上更接近于标准RSA。
This thesis mainly has a study on the RSA-type public key
    cryptosystems. In
    Chapter One, the research background, significance and state of
    public-key cryptology
    are introduced along with the introduction to elementary concepts
    of public-key
    cryptosystems and the standard RSA scheme. In Chapter Two, the
    n-adic multi-block
    RSA-type public key cryptosystem presented by Tauyoshi Takagi in
    Crypto'97 has been
    introduced. In Chapter Three, the achievements on the
    low-exponent attack of the
    standard RSA scheme are introduced, including the low-exponent
    attack with related
    massages presented by D.Coppersmith and the new important result
    finished by Dan
    Boneh and Glenn Durfee that the standard RSA scheme with private
    key d less than
    N is insecure, a remark on D.Coppersmith's analysis is also given
    in this chapter. In
    
    Chapter Four, the work on construction of the RSA analogue over
    polynomial rings by
    SunQi and CaoZhenfu is introduced, and the author's related work
    is also included in
    this chapter.
    
    
     The main results of this thesis are as follows:
    
    
    1 .Sonie mistakes and confusion made by D.Coppersmith in [31] are
    pointed out; a proof
    that the two encryption polynomials only have one common root
    over Z~ is given,
    which may reflect one aspect of the problem though cannot
    sufficiently demonstrate the
    definity of the attack using Euclidean algorithm to find the
    greatest common divisor of
    the two encryption polynomials over Zn.
    
    
    2.A modification of the RSA analogue presented by CaoZhenfu in
    [50] is made, vhich
    has solved the ciphertext extension problem in the above
    analogue, and the security of
    the new scheme is also discussed; another new RSA analogue has
    been proposed, which
    has no ciphertext extension and is much similar to the standard
    RSA scheme in
    conception.
引文
[1] Adleman,L.M. and McCurley,K.S.: Open Problems in Number Theoretic Compl-exity,II , Proc.of ANTS,LNCS,Springer-Verlag,pp.291-322(1995) .
    [2] Diffie,W. and Hellman,M.: New Directions in Cryptography, IEEE Trans. on Information Theory,IT-22,6,pp.644-654(1976) .
    [3] ElGamal,T: A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, IEEE Trans.on Information Theory,IT-31,4,pp.469-472(1985) .
    [4] Rivest,R., Shamir, A. and Adleman,L.: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Communications of the ACM, Vol.21,No.2,pp. 120-126(1978) .
    [5] Smith,P.and ennon,M.:LUC: A New Public Key System, Proc.of IFIP/SEC' 93, pp. 103-117, North-Holland(1993) .
    [6] Rabin,M.O.:Digital Signatures and Public-Key Encryptions as Intractable as Factorization,MIT,Technical Report,MIT/LCS/TR-212 1979.
    [7] Williams,H.C.:A Modification of the RSA Public Key Encrytion Procedure, IEEE Trans.on Information Theory,IT-26,6,pp.726-729(1980) .
    [8] Williams,H.C.:Some Public-Key Crypto-Functions as Intractable as Factorization, Proc.of Crypto'84,LNCS 196,Springer-Verlag,pp.66-70. (1985) .
    [9] Demytko,N.:A New Elliptic Curve Based Analogue of RSA, Proc.of Eurocrypt'93, LNCS 765,Springer-Verlag,pp.40-49(1994) .
    [10] Koyama,K.,Maurer,U.M.,Okamoto,T.and Vanstone,S.A.: New Public-Key Sche-mes based on Elliptic Curves over the Ring Zn, Proc.of Crypto'91, LNCS 576, Spring-r-Verlag,pp.252-266(1992) .
    [11] Kurosawa,K.,Ito,T.and Takeuchi,M.:Public Key Cryptosystem using a Reciprocal Number with the same Intractablity as Factoring a Large Number, Cryptologia, 12,4, pp.225-233(1988) .
    [12] Loxton,J.H.,Khoo,D.S.P.,Bird,G.J.and Seberry,J.:A Cubic RSA Code Equivalent to Factorization, Journal of Cryptology,5,2,pp.139-150(1992) .
    [13] Chao,J.,Matsuda,N and Tsujii,S.:Efficient construction of secure hyperelliptic discrete logarithm problems,Proc.of ICICS'97,LNCS 1334,Springer-Verlag pp.292-301(1997) .
    [14] Koblitz,N.: Elliptic Curve Cryptosystems,Math.Comp.,48,177,pp.203-209(1987) .
    [15] Miller,V.S.:Use of Elliptic Curves in Cryptography, Proc.of Crypt'85,LNCS218, Springer-Verlag;pp.417-426(1985) .
    
    
    [16] Goldwasser,S.and Micali,S.:Probabilistic Encryption, JCSS,28,2, pp.270-299, 1984.
    [17] Ajtai,M.and Dwork,C.:A Public-Key Cryptosystem with Worst-Case/Average Case Equivalence, Proc.of STOC'97,pp.284-293(1997) .
    [18] McEliece,R.J.:A Public-Key Cryptosystem Based on Algebraic Coding. Theory, DSN progress report 42-44,Jet Propulsion Laboratories,Pasadena(1978)
    [19] Chor,B.and Rivest,R.L.:A knapsack type public key cryptosystem based on arithmetic in finite fields,Proc.of Crypto'84,LNCS 196,Springer-Verlag,pp.54-65(1985) .
    [20] Merkle,R.C and Hellman ,M.E.:Hiding Information and Signatures in Trapdoor Knapsacks,IEEE Trans.on Information Theory,24,pp.525-530 1978.
    [21] Naccache,D.and Stern,J.:A New Public-Key Cryptosystem,Proc.of EuroCrypt'97 LNCS 1233,Springer-Verlag,pp.27-436(1997) .
    [22] Matsumoto,T.and Imai,H.:Public Quadratic Polynomial-Tuples for Efficient Signature-Verification and Message-Encryption,Proc.of Eurocrypt'88,LNCS 330,Springer-Verlag,pp.419-453(1988) .
    [23] Patarin,J.and Goubin,J.: Trapdoor one-way permutations and multivariate polyno-mials,Proc.of ICICS'97,LNCS 1334,Springer-Verlag,pp.369-380(1997) .
    [24] Patarin,J.and Goubin,J.: Asymmetric cryptography with S-Boxes, Proc.of ICICS' 97,LNCS 1334 ,Springer-Verlag,pp.369-380(1997) .
    [25] Alexi,W.,Chor,B.Z.,Goldreich,O.and Schnorr,C.P: RSA and Rabin Functions:Ce-rtion Parts Are as Hard as the Whole, SIAM Journal of Computing,17,2,pp.449-457. (1988) .
    [26] Blum,M. and Goldwasser,S.: An Efficient probabilistic public-key encrytion scheme which hides all partial information, Proc.of Crypto'84,LNCS 196, Springer-Verl-ag, pp.289-299(1985) .
    [27] Guang Gang and Lein Harn,:Public-Key Cryptosystems Based on Cubic Finite Field Extensions, IEEE Trans.on Information Theory,Vol.45,No.7,Novermber 1999.
    [28] Uchiyama S.:A New Public-Key Cryptosystem Secure as Factoring[A].Advances in Cryptology-Eurocrypt'98,LNCS1403[C].Springer-Verlag,pp.308-318. (1998) .
    [29] Coron J S, Naccache D, Paillier. Accelerating Okamoto-Uchiyama Public-Key Cryptosystem[J]. IEE Electronics Letters, Vol.35(4) :pp.291-292,(1999) .
    [30] Buclimann J,Williams.H.C, Quadratic Fields and Cryptography. Number Theory and Cryptography,Loxton J,H ed.Cambridge University Press, 1990,pp.9-25.
    [31] D.Coppersmith,M.Franklin,J.Patarin.: Low-Exponent RSA with related messages, Advances in Cryptology-Eurocrypt'96,LNCS 1070,(1996) ,pp.1-9.
    
    
    [32] D. Coppersmith, Finding a small root of a univariate modular equation, Advances in Cryptology-Eurocrypt' 96,LNCS 1070,(1996) ,pp. 155-165.
    [33] D.Boneh,:Twenty years of attacks on RSA cryptosystem. Notices of the American Mathematical Society, February 1999,pp.203-213.
    [34] D.Boneh, and G.Durfee, Cryptanalysis of RSA with private ked d less than N0. 292, IEEE Trans.on Information Theory,No.3,2000. (Or in Proc.of Eurocrypt'99,Vol.1592, LNCS,pp.1-11. IACR,Springer-Verlag,1999. ).
    [35] D.Boneh,G.Durfee,and Y.Frankel,An attack on RSA given a fraction of the priva-te key bits, AsiaCrypt'98, Lecture Notes in Compute Science,Springer-Verlag,Berlin and New York, 1998.
    [36] J.Hastad, Solving simultaneous modular equcations of low degree,SIAM J.Comp-t.17(1998) ,pp.336-341.
    [37] D.Bleichenbacher, On the security of the KMOV public key cryptosystem, in Cr-ypt' 97,Lecture Notes in Computer Science.Berlin,Germay: Springer-Verlag,1997. pp. 235-248.
    [38] D. Coppersmith, Small solutions to polynomial equations,and low exponent RSA vulnerabilities, J.Crypt.,Vol.10,pp.233-260,1997.
    [39] N.Howgrave-Graham, Finding small roots of univariate modular equations revisited, in Cryptography and Coding ,Lecture notes in Computer Science,Berlin,Ge-rmay:Springer-Verlag,1997,Vol.1355,pp.131-142.
    [40] A.Joux and J. Stern, Lattice reductions:A toolbox for the cryptanalyst, J.Cryptol. Vol.11,No.3,pp.161-185,1998.
    [41] C.Jutla, On finding small solutions of modular multivariate polynomial equations, in Eurocrypt'98,Lecture notes in Compute Science. Berlin, Germay: Springer-Verlag, 1998,Vol.1403,pp.158-170.
    [42] A.Lenstra,H.Lenstra,and L.Lovasz, Fatoring polynomials with rational coefficien-ts, Math.Annalen, Vol.261, pp.515-534, 1982.
    [43] L.Lovasz, An algorithmic theory of numbers,graphs,and convexity, in SIAM CBMS-NSF Regional Conf.Series in Applied Mathematics,Vol.50,1986.
    [44] M.Wiener, Cryptanalysis of short RSA secret exponents,IEEE Trans.on Inform. Theory,Vol.36,pp.553-558,May1990.
    [45] Number Theory Library(NTL),V.Shoup.[on line].Available:http://www.shoup.net/ntl/
    [46] A.Menezes,P.van Oorschot,and S.Vanstone, Handbook of Applied Cryptography, CRC,1996.
    
    
    [47]D.Boneh and R.Venkatesan, Breaking RSA may not be equivalent to factoring, in Eurocrypt'98,Vol. 1403 Lecture Notes in Computer Science,pp.59-71 ,Springer-Verlag,(1998).
    [48]Zhang Fangguo, Zhang Futai, Wang Changjie, Wang Yumin, Improved Cryptanalysis of RSA with Short Private Key, to appear, Journal of Computer Science and Technology.
    [49]Tsuyoshi Takagi, Fast RSA-Type Cryptosystems Using N-adic Expansion, in Crpto'97, Lecture Notes in Computer Science,pp.372-384, Springer-Verlag,(1997).
    [50]曹珍富,关于有限域F_p上的多项式RSA的安全性和RSA的新模拟.通信学报,1999,vol.20.No.9:pp.15~18。
    [51]胡予濮,冶继民,公钥体制OUPKC的变形及其应用,西安电子科技大学学报,Vol.28,No.2,Apr.2001,pp.190-192。
    [52]孙琦,关于一类陷门单向函数,四川大学学报(自然科学版),1985(4),33-35。
    [53]柯召,孙琦,数论讲义,高等教育出版社,1986。
    [54]王育民,刘建伟,通信网的安全——理论与技术,西安电子科技大学出版社,1999。
    [55]冯登国,裴定一,密码学导引,北京:科学出版社,1999。
    [56]冯登国,计算机通信网络安全,北京:清华大学出版社,2001。
    [57]D.R.斯廷森,密码学理论和实践,国防科学技术保密通信重点实验室,1997。

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址:北京市海淀区学院路29号 邮编:100083

电话:办公室:(+86 10)66554848;文献借阅、咨询服务、科技查新:66554700