GF(p)上離散對數(shù)問題GNFS算法實現(xiàn).pdf

1、公鑰密碼體制的安全性都是基于一些難解的數(shù)學(xué)問題，Diffie-Hellman密鑰交換體制作為三大公鑰密碼體制之一，它的安全性基礎(chǔ)是離散對數(shù)的計算困難性問題。離散對數(shù)計算問題最初作為一個數(shù)學(xué)問題，在數(shù)論中具有較長的歷史；但是，隨著移位寄存器序列在密碼學(xué)中的應(yīng)用，尤其是Diffie-Hellman密鑰交換體制的誕生和廣泛使用，離散對數(shù)計算問題引起了廣泛興趣。在Diffie-Hellman體制誕生后的三十多年時間里，離散對數(shù)計算問題在理論、方

2、法和實現(xiàn)上都取得了一系列的進(jìn)展。 針對不同的循環(huán)群，離散對數(shù)問題的計算方法也不盡相同。按計算離散對數(shù)的時間復(fù)雜度可以分為指數(shù)算法和亞指數(shù)算法兩大類。在指數(shù)算法中，Shanks’的大步小步法、pollard rho方法和Pollard lambda方法這三種算法對任意的循環(huán)群都適用，都需要進(jìn)行O（√ng）次群運(yùn)算（其中ng為元素g的階）；亞指數(shù)算法起源于1986年Coppersmith等發(fā)表的高斯整數(shù)法（COS），它通過引入數(shù)域的

3、知識來解決有限域上的離散對數(shù)問題。在亞指數(shù)算法中，目前最有效的計算方法為數(shù)域篩法。 數(shù)域篩法計算離散對數(shù)一般都需要三個基本計算步驟： 1通過篩法篩選關(guān)系對，用關(guān)系對構(gòu)造因子基對數(shù)的線性方程組； 2求解線性方程，求得因子基離散對數(shù)； 3利用解得的因子基對數(shù)求單個的離散對數(shù)。 而在數(shù)域篩法中，目前認(rèn)為的較好方法為Joux與Lercier數(shù)域篩法。Joux與Lercier數(shù)域篩法在篩法部分與一般的數(shù)域篩

4、法是相同的，它的精妙之處在于先利用篩選得到得光滑關(guān)系對建立因子基對數(shù)方程組，然后求解線性方程組得到因子基對數(shù)，在此基礎(chǔ)上再計算單個對數(shù)。對一個固定的模數(shù)p，采用Joux與Lercier數(shù)域篩法計算離散對數(shù)，只需要解一次方程，從而計算單個對數(shù)的時間相對較短。 數(shù)域篩法計算離散對數(shù)問題包含較深的數(shù)學(xué)理論，涉及到抽象代數(shù)、代數(shù)數(shù)論和計算代數(shù)等數(shù)學(xué)學(xué)科的基礎(chǔ)知識。同時，在公開討論Joux與Lercier數(shù)域篩法的文獻(xiàn)中，大都缺少Joux

5、與Lercie數(shù)域篩法具體的實現(xiàn)細(xì)節(jié)和參數(shù)；而數(shù)域篩法的實現(xiàn)也是一項十分復(fù)雜的工程，包括了大數(shù)運(yùn)算、整數(shù)分解、篩法、稀疏方程求解、代數(shù)數(shù)域和代數(shù)整數(shù)環(huán)的一些基本性質(zhì)的計算等許多工作。本文主要討論Joux與Lercier數(shù)域篩法的軟件實現(xiàn)問題。文中首先詳細(xì)地介紹了Joux與Lercier數(shù)域篩法的基本原理，重點通過一個規(guī)模為70位（約為231比特）的挑戰(zhàn)數(shù) p=「1070π」+25507 =3141592653589793

6、2384626433832795028 84197169399375105820974944592333323為模數(shù)的離散對數(shù)計算實例，討論在素域Fp上用Joux與Lercier數(shù)域篩法計算離散對數(shù)實現(xiàn)的一些具體問題。在AMD的Dual Core AMD Opteron（tm）Processor875處理器上，用標(biāo)準(zhǔn)C語言和部分匯編語言，實現(xiàn)了素域Fp上用Joux與Lercier域篩法計算離散對數(shù)，并且在813分鐘內(nèi)，完成了實例