1、關(guān)于區(qū)間上離散對數(shù)問題的改進(jìn)算法 報(bào)告人：王瑤 2015年10月23號王瑤，呂克偉研究內(nèi)容研究內(nèi)容 在群G上區(qū)間大小為N 的離散對數(shù)問題為：給定群元素g，h以及大整數(shù)N，找到整數(shù)n ( )，使得 。 通常對于該問題的求解主要是對Pollards kangaroos method的改進(jìn),嘗試通過減少跳躍次數(shù)來優(yōu)化算法，目前解決這一問題的最優(yōu)低存儲(chǔ)算法是van Oorschot和 Wiener 版本的Pollards kangaroos method，其平均情況下的時(shí)間代價(jià)是 次群運(yùn)算。 文中對經(jīng)典Pollards kangaroos method進(jìn)行改進(jìn)，得到新的求解算法。新算法是通過利用多次小

2、整數(shù)乘法代替一次完整的大整數(shù)乘法來減少kangaroos每次跳躍的時(shí)間代價(jià)實(shí)現(xiàn)算法效率的提高。進(jìn)一步，文章中通過增加kangaroos的數(shù)量使得算法在跳躍次數(shù)和每次跳躍的時(shí)間代價(jià)兩方面都得到改進(jìn)，從而得到區(qū)間上離散對數(shù)問題的更有效的求解算法。Nn0ngh No )1 (2( 研究背景研究背景 經(jīng)典離散對數(shù)問題（DLP）是許多密碼系統(tǒng)和協(xié)議的安全性基礎(chǔ)，但隨著密碼學(xué)的發(fā)展，出現(xiàn)了一些特殊的離散對數(shù)問題用于解決實(shí)際中的密碼學(xué)問題，比如在某個(gè)區(qū)間上的離散對數(shù)問題。該問題的出現(xiàn)是由于在實(shí)際應(yīng)用中，如果沒有進(jìn)行有效的保護(hù)措施，敵手可能通過某些側(cè)信道攻擊的手段獲取關(guān)于離散對數(shù)的某些比特位信息，從而推斷出待

3、求解離散對數(shù)所在的區(qū)間范圍，之后敵手在進(jìn)行離散對數(shù)求解時(shí)只需要在該區(qū)間范圍內(nèi)求解即可。 目前用Baby-step Giant-step method解決區(qū)間上的離散對數(shù)問題，需要執(zhí)行 次群運(yùn)算、需要 空間。因此該算法需要較大的存儲(chǔ)空間并且查表的速度對算法的影響很大，最快變體在平均情況下的時(shí)間代價(jià)為 次群運(yùn)算。 直到2010年，Galbraith等人通過增加kangaroos的只數(shù)實(shí)現(xiàn)總的跳躍次數(shù)的減少，從而對經(jīng)典Pollards kangaroos method給予改進(jìn)，使得算法的代價(jià)從 次群運(yùn)算降低到 次群運(yùn)算。并說明，當(dāng)四只kangaroos同時(shí)跳躍時(shí)算法的效率最高。)( nO)( nOn

4、34no )1 (2 ( no )1 (714. 1 (相關(guān)算法相關(guān)算法p 經(jīng)典經(jīng)典Pollards kangaroos算法算法 給定循環(huán)群G，群中元素g，h，大整數(shù)N，計(jì)算n使得 選擇一個(gè)正整數(shù)的小集合S作為kangaroos的跳躍步集合，從群G中隨機(jī)均勻選取一些元素構(gòu)成可區(qū)分集合D，定義一個(gè)從群G到集合S的隨機(jī)映射f： 。 一只kangaroo跳躍就對應(yīng)一個(gè)G中的序列： ，i=0,1,2, 從給定的 開始。同時(shí)定義一序列 , 令 ，i=0,1,2, 因此，是kangaroo前i次跳躍的距離和，那么， ，i=0,1,2,ngh)0 (NnSG相關(guān)算法相關(guān)算法 Pollards kangaro

5、os是基于隨機(jī)步的算法，每只kangaroo每次跳躍一步。定義兩只kangaroos分別為T和W。T從區(qū)間中點(diǎn)開始向區(qū)間右側(cè)跳躍，W從群元素h開始（即未知離散對數(shù)的群元素）向區(qū)間右側(cè)跳躍，兩者使用同樣的隨機(jī)步集合。在串行計(jì)算機(jī)上對T和W交替操作，無論何時(shí)只要kangaroos的跳躍落地點(diǎn)的群元素屬于可區(qū)分點(diǎn)集合D，記錄此時(shí)的落地點(diǎn)。當(dāng)某個(gè)落地點(diǎn)值被不同類型（T或者W）kangaroos訪問時(shí)即發(fā)生碰撞，算法終止。 經(jīng)典的Pollards kangaroos method針對每只kangaroo，每次跳躍都需要計(jì)算一次大整數(shù)乘法，但只有當(dāng)其滿足可區(qū)分點(diǎn)條件時(shí)才將該跳躍點(diǎn)存儲(chǔ)下來以備碰撞檢測，否則

6、丟棄該點(diǎn)值不進(jìn)行存儲(chǔ)。因此存儲(chǔ)操作不是每次都進(jìn)行，故每次跳躍都花費(fèi)很大的時(shí)間代價(jià)計(jì)算一次完整大整數(shù)乘法并沒有必要，這是經(jīng)典Kangaroos算法的一個(gè)不足。相關(guān)算法相關(guān)算法 p Cheon-Hong-Kim算法算法 經(jīng)典Pollards rho method是通過迭代找到碰撞來求出離散對數(shù)，2008年Jung HeeCheon等人提出利用預(yù)定義的可區(qū)分點(diǎn)的條件通過減少每次迭代的計(jì)算量來降低Pollards rho算法的時(shí)間代價(jià)。主要通過定義合適的函數(shù)，計(jì)算簡單的函數(shù)值，判斷預(yù)先定義的可區(qū)分點(diǎn)條件，只有滿足可區(qū)分點(diǎn)條件時(shí)才計(jì)算一次完全乘法得到對應(yīng)的群元素，存入表中，并與表中已有元素進(jìn)行碰撞檢測，

7、而不滿足條件時(shí)只需要進(jìn)行簡單的運(yùn)算得到下次迭代需要的索引下標(biāo)s即可。 Cheon等人改進(jìn)的算法通過一定量的預(yù)計(jì)算，把每次迭代中計(jì)算兩個(gè)群元素乘積轉(zhuǎn)換成多次小整數(shù)乘積，使得算法的運(yùn)行時(shí)間至少比原始算法快10倍。但其只是減少了每次迭代的計(jì)算量，并沒有考慮減少迭代次數(shù)（可類比為kangaroos算法中的跳躍次數(shù)），而迭代次數(shù)過分依賴于迭代函數(shù)的選取。改進(jìn)的改進(jìn)的Pollards kangaroos算法算法p 主要思想主要思想 嘗試在減少跳躍次數(shù)的基礎(chǔ)上再減少每次跳躍的時(shí)間代價(jià)，這樣可以從兩方面提升經(jīng)典算法的運(yùn)行時(shí)間。經(jīng)典算法中，每次群運(yùn)算的時(shí)間代價(jià)主要是迭代過程中計(jì)算兩個(gè)大整數(shù)的乘積，但該計(jì)算并不是

8、每次都必需的。所以，我們通過設(shè)計(jì)合適的迭代函數(shù)，做一定量的預(yù)計(jì)算，每次用多次小整數(shù)乘積代替一次大整數(shù)乘積計(jì)算，只有需要進(jìn)行存儲(chǔ)操作時(shí)才進(jìn)行一次大整數(shù)乘法，從而減少大整數(shù)乘積的計(jì)算次數(shù)，使得計(jì)算效率得到提高。p 算法描述算法描述 固定索引集合S=0,1,2，k-1，k是一小整數(shù)。選擇小的正整數(shù)集合S = 作為跳躍步長集合，令 M= 。固定一個(gè)小正整數(shù)l，并且預(yù)計(jì)算集合 中值 ，即為至多個(gè)M中元素乘積的集合。標(biāo)簽集合T=0,1,.,T-1，T=kb，b是一小整數(shù)。改進(jìn)的改進(jìn)的Pollards kangaroos算法算法 定義集合T=0,1,2,t-1，定義下面四個(gè)函數(shù)： 索引函數(shù)s： 輔助索引函數(shù)

9、 標(biāo)簽函數(shù) 輔助標(biāo)簽函數(shù) 定義 ， ，使其滿足下面兩點(diǎn)：1. 是滿射并且原象近似均勻，也就是說群G中的元素對應(yīng)的S下的象點(diǎn)將群G劃分成大小相近的子集。2. 我們設(shè)計(jì)函數(shù) ，定義函數(shù) ： 給定， 總可以寫成下列形式：改進(jìn)的改進(jìn)的Pollards kangaroos算法算法 定義輔助標(biāo)簽函數(shù) ， 函數(shù)是將一次大整數(shù)乘法轉(zhuǎn)換為多次小整數(shù)乘法的關(guān)鍵?？蓞^(qū)分點(diǎn)條件定義為： 。 一只kangaroo就是一個(gè)G中的序列： ， 不用計(jì)算 的乘積，可利用 得到下次索引值 ， 同樣，不用計(jì)算出 就可得到 。依次計(jì)算索引值，每次迭代都不用計(jì)算完全乘法，只有滿足可區(qū)分點(diǎn)的條件時(shí)才計(jì)算一次完全乘法,獲得此時(shí)對應(yīng)的 ，其

10、中 已預(yù)計(jì)算，可通過查表得到。 定義兩只kangaroos ，分別為T和W，T、W從區(qū)間中點(diǎn)和h開始向區(qū)間右側(cè)跳躍，交替執(zhí)行上述算法，當(dāng)滿足可區(qū)分點(diǎn)條件時(shí)，計(jì)算出此時(shí)的跳躍點(diǎn)值進(jìn)行存儲(chǔ)，當(dāng)某個(gè)值被不同類型（T或者W）kangaroos訪問時(shí)即發(fā)生碰撞，算法終止。 算法再優(yōu)化算法再優(yōu)化 為了從跳躍次數(shù)上再優(yōu)化kangaroos算法，可將kangaroos的只數(shù)取為四只，相應(yīng)的對原始算法做一定的修改即可。設(shè)置兩只wild kangaroos，起始點(diǎn)分別為h和 。為了更快得到wild-wild碰撞，我們應(yīng)將S集合中的元素均取為偶數(shù)，即每次的跳躍步長均為偶數(shù)。為了保證wild-tame碰撞，需要設(shè)置兩

11、只tame kangaroos，起始點(diǎn)取為相鄰兩點(diǎn)（一奇一偶），可取區(qū)間中點(diǎn) 。這樣取值還有一點(diǎn)好處就是不會(huì)出現(xiàn)無用的tame-tame碰撞，但會(huì)發(fā)生我們需要的tame-wild碰撞。 這樣的改變可以使得區(qū)間寬度減半，發(fā)生碰撞時(shí)每只kangaroos的跳躍步數(shù)減少，這樣，相比原始的kangaroos算法，既減少了跳躍步數(shù)，又減少了每次跳躍的時(shí)間代價(jià)，使得算法的總體運(yùn)行時(shí)間代價(jià)減少。改進(jìn)前后算法代價(jià)對比改進(jìn)前后算法代價(jià)對比算法算法跳躍次數(shù)跳躍次數(shù)一次跳躍時(shí)間代價(jià)一次跳躍時(shí)間代價(jià)一次跳躍時(shí)間代一次跳躍時(shí)間代價(jià)價(jià)（p是是1024bits）經(jīng)典 two kangaroos1次1024比特乘法（1048576次比特運(yùn)算）改進(jìn)的 two kangaroos64次16比特與32比特比特乘法（32768次比特運(yùn)算）four kangaroos1次1024比特乘法（1