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

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

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

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

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

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

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