一個改進的離散對數問題攻擊算法

1、一個改良的離散對數問題攻擊算法很多密碼技術的平安性都建立在離散對數問題的困難性上 ,如 Diffie Hellman 密鑰協議 1 , EIGamal 密碼體制及其簽名 方案， 以及它們的變種等。 Diffie Hellman 問題2 ，模合數 n 乘群 Z*n 中的離散對數問題， 以及 n 的因子分解問題， 在密碼學上存 在 一定的關聯，它們的困難性存在著內在的等價性 1 。針對離散對數問題有許多攻擊方法，目前的有窮舉攻擊， Pohlig Hellman 攻擊 3 ，指數積分攻擊 3 ， Pollard 概 率 攻擊 3 ，小步大步攻擊 2 ， 4 ，袋鼠攻擊 5 和生日攻擊 6 等。 這些

2、攻擊方法往往在某些特定場合尤其有效， 如當 p-1 為形 如 2 的 冪次方 6 ， p-1 的因數都較小 3 或 p 的位數較短時。小 步大步 攻擊算法那么適合于包括橢圓曲線 2， 3在內的所有離散 對數問題，是 本文進行研究并加以改良的對象。對于小步大步攻擊算法， 在忽略對數因子的情況下， 其時 間 復雜度為 0(n) ，已接近于離散對數問題的任何通用算法的復雜性下界6 ，但仍留有值得優(yōu)化的余地。另一方面，空間復雜 度較大一直是小 步大步算法的缺乏之處。1 離散對數問題 離散對數的求解雖是困難的， 但其逆運算即指數運算， 可以 應用平方乘的方法有效地計算。 假設將指數用有符號的二進制數表

3、示，使 之具有較小的海明權重 7 ，那么可以進一步減少其中乘法 的次數，從 而提高運算速度。2 小步大步攻擊算法及分析小步一大步(Baby Step Gia nt Step)攻擊算法有時也稱 為 Shanks 算法4, 具體實現如下面的算法 1 所示。其中參數 n, a， B 的 意義與定義 1 中的定義相同。3 改良算法先給出改良后的算法描述 ,其中參數與算法 1 完全相同。4 改良算法的性能分析同樣以群乘法為根本運算單位， 分析改良算法的時間和空間 復 雜性。與算法 1 一樣，在第 1)步，要先預計算 a m 并緩存。雖時 間復雜 度仍為 O(logm) ，但在(1.2)步中將指數 m 采

4、取具有較小 海明權重 7 的 表示方式， 可以顯著減少其中乘法的次數， 從而 可以平均提高大致 11% 的運算速度 2 。由于平方運算最快可以 比兩個不同整數的乘法運算 快兩倍 1 ，所以這項措施的好處是 非常明顯的； 同時在 (1.3) 步中 采用多精度平方乘算法 1 ，可進 一步提高運算速度。5 兩算法的比照 由上面的分析，可歸納出兩個算法的主要不同之 處在于：1) 存貯表的數目。 算法 1 需要兩個表， 而算法 2 那么只需 1 個 , 從而存貯器開銷不同2)表元素的比擬時機。 算法 1 是兩組數據 (兩張表 )都計算完 成 后再進行比擬， 而算法 2 那么是只需在第一張表完成的根底上即

5、 可開 展比擬工作。5) 表排序與查表時間。 算法 1 需對兩張表都排序， 且查表時 間 與表的規(guī)模直接相關 (為 0(m) ) 。而算法 2 由于引入抗沖突 的哈希函數， 無須排序操作，且查表時間也降為O(1) 。6 進一步的改良措施 改良后的小步大步攻擊算法較原算法而言 進行了算法實 現上的多項優(yōu)化， 但這僅是針對算法本身的優(yōu)化， 兩 種算法所面 對的問題規(guī)模仍然是相同的。 可以嘗試通過降低問題的規(guī) 模來進 一步縮短攻擊算法的計算過程。 這一點對于比特位較長的素數 p 意義更加明顯。7 結語 本文將改良后的小步大步攻擊算法與原算法的性能進行 了比照分析， 說明上述改良措施均是正確而行之有效的。 如何減 少 存貯開銷， 盡量防止或減少求逆元運算， 如何有效應用多精度 算法， 以及通過變換指數表現形式來加速冪運算速度等， 都值得 在日益廣泛 應用的密碼系統和簽名方案的實現過程中加以充分 考慮和探討。努力提高攻擊算法的運算效率只是一個方面的工作， 延伸到 如 何降低算法的輸入規(guī)模將是一件非常有意義的工作。 本文僅討