论文研究-Analyze the security of REESSE1 Public Key Cryptosystem.pdf

所需积分/C币:8 2019-08-14 17:07:43 324KB .PDF

REESSE1 公钥密码的安全性分析,顾海华,谷大武,2006年,Shenghui Su 设计了一个公钥密码,命名为REESSE1 。2010年中国密码学会年会上,Shenghui Su发布悬赏以鼓励更多的人分析REESSE1 。我们针对第�
国利技论文在线 http://www.paper.edu.cn 1 Background In this section, we introduce the reessel+ public key cryptosystem. To be simplicity we only copy the key generation algorithm, the digital signature algorithm and the identity verification algorithm The Key Generation Algorithm Let p1, .. pn be the first n primes in the set N A=2, 3,. . 1201] and 2=(1, 3, .., 2n-1, where Q2 be all odd set. Assune that d, D, T, S are four pairwise coprime integers, where dE 5, 216), and D, T>2n Sl: Randomly generate coprime A1,.. An with AiEA S2: Find prime M >(LiSn Ai)" making dDT)M, gcd(S,M)=1, and ke:M,where k meets i ⊥0 an d S3: Pick w,6∈(1,M) making gcd(6,n)=1,‖=dDm‖and≥2-20 S4: Compute a←6(6”-0W-),←67,h←(WI1A)-1%M S5: Randomly produce pairwise distinct l(1), .. l(n) with l(i)EQ S6: Compute C2←(AW()°% M for i=1 At last,(Ci, a, B) is a public key. (Ai, l(i). W, 8, D,d, h) is a private key and S,T,M are in common The Digital Signature algorithm Assume that (A:,l(i],w,8, D, d, h) is a private key, F is a file or message which will be signed, and hash is a one-way compression function S1:LetH←hash(F), whose binary form is b1…bn S2:Setk←6∑=1b1(1)%M,C←(I1=14)5%M S3: VaE 1, M) making dT fa, dwQ%M, where Q=(aD+WH8%M S4: Compute←(Q(6h)-1)15C1,U←(BW-)Q,9←6D%M, 5〈∑=0(0Q)-1=2(HW)%M S5: Vr E[1, d216 making d(rUS+s)%M, where U=U9(M) S6: If d((wQ)n-+&+rUS)%M, goto $5 At last, the signature( Q, U) on the file F is obtained, and sent to a receiver with F The identity verification algorithm Assume that (Ci, a, B)is the public key, F is the file or message, and(Q, U)is a signature on it S1:LetH〈hash(F), whose binary form is b1…bn S2: Compute g←In1Ch%M S3: Compute X←(aQ1)?ra°%M,Y+(GU-1)s+%M. S4: If X= Y, the identity is valid and F intact; else the identity is invalid or F modified 国利技论文在线 http://www.paper.edu.cn 2 Analysis of REESSE1+ Assume that we have a signature( Q, 0) signed by the correct private key. Since the digital signature should be open to the public, every one can easily get it. This means our assumption Is reasonable algorithm Input: M, Ci, S, T and a signature(@, 0) signed by the correct private key, Output: private key(Ai, l(i),W,8, D, d, h) 1. Since l(i)∈{1,3,5, 1},∑}=1l() 2. Compute Ili-1 Ci(nod M) 3. Calculate the generator g of GF(M) 4. Given I- Ci(mod M) and 9, compute the discrete logarithm in finite field GF(M). Suppose c is the output, i.e. ge=llis ci(mod M 5. for every case of Ili-l Ai where Ai E 2, 3, 4-., 1201) 5.1 Given I;- Ai and g, Compute the discrete logarithm in GF(M Suppose a is the output,i..9=ll=Ai(mod M) 52 Suppose e∈[1,M-1] satisfies g?≡W(modM). We have c=(a+en)8(mod M-1) 53forl()∈{1,3,5,…,2-1} 531 for Ai∈{2,3,4,,1201} 5.3.1.1 Let C1=(Ai Wl(2))o(mod M) Suppose g≡C1(modM)andg≡A;(modM) we have ci=(ai+el(i))8(mod M-1) 5.3.1.2 By Ey. (1)and Eq (2), we can get e and S 513 Compute w←g°(modM) 531.4 Compute a←6(6”+W)T,B<6W"T 5.3.1.5 Calculate h<(WI= Air-o(as-l)(mod M) 5.3.1.6 for every permutation of l(1), l(2), .. l(n)) where ()∈{ 2 5.3.1.6.1 for i from 1 to m Compute A; by Ci=(A; Wl@)(mod M) IfA2∈{2,3 1201, break Ol om 5 to 216 Calculate D-8/(Td) Now sign by the digital signature algorithm and suppose the output is(Q,,U) if(Q, U)==(Q, 0), print (A],l(i), W,S, D, d, h) 国利技论文在线 http://www.paper.edu.cn Suppose the time of computing discrete logarithm in GF(M) is T. It follows that step 4 costs T; the time of loop in step 5 is Cl 200: step 5.1 costs T; the time of loop in step 5.3 with step 5.3. 1 is 1200 n; step 5.3. 1.1 costs T while cost in other steps can be neglect compared with T. This means our algorithm needs about T+ Cl200(T+ 1200nT)in total. Recall that n is a constant suggested by 80.96, 112 or 128 and constants can be ignored in time complexity analysis. Therefore, the time complexity of our algorithm is O(T). Since the cost of computing discrete logarithm in finite field is in subexponential time 5, 6, it follows that we can get the private key definitely from the public key in subexponential time 参考文献( References) 1 Shenghui Su, The REESSE1 Public-key Cryptosystem, Computer Engineering Science (in Chinese), vol. 25, no5, pp 13-16, Sep. 2003 2S. Liu, F. Zhang, and K. Chen, Cryptanalysis of REESSEl Digital Signature Algorithm, in Proc. CCICS 2005, Xi'an, China, May 2005, pp 200-205 3 Shenghui Su, and Shuwang Lii,The REESSE1+ Public Key Cryptosystem Version 2.2 http://eprint.iacr.org/2006/420.pdf 4Shenghui Su, and Shuwang Li, Design and Analysis of the REESSEl+ Public Key Cryp- tosystem,availablehttp://arxiv.org/pdf/cs/0702046.pdf 5 Leonard M. Adleman, Ming-Deh A. Huang: Function Field Sieve Method for Discrete Logarithms over Finite Fields. Information and Compuation151(1-2): 5-16 1999 6 A Odlyzko. Discrete logarithms: The past and the future, Designs, Codes and Cryptogra hy,19:129-145,2000

...展开详情
img

关注 私信 TA的资源

上传资源赚积分,得勋章
最新资源