摘要
本文对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。