兩種算法的理論分析

李 梅

(西南大學 數(shù)學與統(tǒng)計學院，重慶 400715)

如今，密碼體制的安全性已被人們所重視，在生活中變得尤為重要，而一些密碼體制可能會因為密文而泄露明文的部分信息，Oracle RSA Decryption(n，b，y) 算法卻證實了RSA密碼體制在一類此種類型的攻擊下是安全的.同樣的，Elgamal密碼體制的安全性也是基于離散對數(shù)logαβ的難解性，L2Oracle-Discrete-Logarithm(p，α，β)算法也證明了在已知β的情況下，離散對數(shù)的比特安全性.

1 算法Oracle RSA Decryption(n，b，y)

設(shè)n=pq，p，q為素數(shù)，P=C=Zn，定義K={(n，p，q，a，b)：ab≡1(modφ(n))}.對K=(n，p，q，a，b)，定義ek(x)=xbmodn，dk(y)=yamodn，(x，y∈Zn)，其中n，b為公鑰，p，q，a為私鑰.

external Half

k←[log2n]

fori←0 tok

l0←0

hi←n

fori←0 tok

return ([hi])

2 算法L2 Oracle-Discrete-Logarithm(p，α，β)

2.1 離散對數(shù)

(G，·)為一乘法群，α∈G，其階為n，β∈<α>，若αx=β，0≤x≤n-1，則記x=logαβ，稱其為β的離散對數(shù).

2.2 算法L2 Oracle-Discrete-Logarithm(p，α，β)

externalL1，OracleL2

x0←L1(β)

β←β/αx0modp

i←1

Whileβ≠1

return(xi-1，xi-2，…，x0)

3 算法分析

1) Oracle RSA Decryption(n，b，y)算法中，因為y=ek(x)=xbmodn，所以ek(x1)ek(x2)=ek(x1x2).因此在算法的第一個for循環(huán)中，hi=half(y×(ek(2))i)=half(ek(x·2i))，又

(1)

(2)

(3)

…

(4)

4 總 結(jié)

對這兩種算法作出了分析，使得算法的成立性顯得更加自然合理，兩種算法均證明了明文的安全性，Oracle RSA Decryption(n，b，y)算法從明文x的所屬區(qū)間出發(fā)從而得到x，而L2Oracle-Discrete-Logarithm(p，α，β)算法則是從明文信息比特的角度出發(fā)得到x，從以上算法的分析中，也可以看出信息比特安全的重要性，在今后密碼學的發(fā)展過程中，更加值得重視.

參考文獻：

[1] DOUGLAS R S.密碼學原理與實踐[M].北京：電子工業(yè)出版社，2009

[2] GOLDWASSER S，MICALI S，TONG P. Why and How to Establish a Private Code on a Public Network[A]. Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (FOCS’82)[C].Chicago，Illinois，1982：134-144

[3] 陳笑偉.關(guān)于離散對數(shù)比特問題的一個新發(fā)現(xiàn)[J].科技創(chuàng)新導報，2009(3)：231-233

[4] 斯·廷森D R.密碼學原理與實踐[M].2版.馮登國，譯.北京：電子工業(yè)出版社，2009

[5] 劉玉君.信道編碼[M].鄭州：河南科學技術(shù)出版社，1992

[6] PERALTA R. Simultaneous Security of Bits in the Discrete Log[A]. Proceedings Eurocrypt’85[C].Springer LNCS，1986(219)：62-72

[7] 離散對數(shù)的比特安全性[J].浙江大學學報：工學版，2013，30(8)：23-27

[8] LONG D L，WIGDERSON A.The discrete log hides O(log n) bits[J]. SIAMJ Computing，1988(17)：363-372