第三十六個知識點：Index Calculus算法

我們這篇部落格繼續描述一種數學攻擊，這種數學攻擊被叫做Index Calculus(IC)算法。

注意這裡Index Calculus算法沒有找到合适的中文翻譯。因為原文不是很通順，我加入了很多自己的話。

我們要做什麼

Index Calculus攻擊是一種企圖解決DLP（離散對數問題）的方法。簡單來說，算法把目标值寫成在因子基數上的元素幂的乘積，對數已知的元素，然後利用對數定律提取目标值。我們現在詳細的解釋剛才那句話是什麼意思。

算法工作原理

該算法能被用于在群\(G = \langle g \rangle\)中任何的元素\(h\)。我們将會依賴這樣的命題：如果\(x^ay^bz^c = 1\)，那麼\(a*\log_g{x}+b*\log_g{y}+c*\log_g{z} = \log_g{1} = 0\)。是以，如果我們能發現一些\(x_i\)，且\(L_i = \log_g{x_i}\)，\(h = x_1^{a_1}...x_r^{a_r}\)，然後我們有\(\log_gh = a_1*L_1+...+a_r*L_r\)。IC算法就是利用了這一點，攻擊的效率取決于各個階段的執行速度。為了上下文，除了一般的技術，我們還會用群\(Z/pZ\)上的離散對數問題作為例子。由于懶惰，我們将用詞彙離線計算和預計算都指的是每個群隻需要做一次的工作。類似的，線上的和每次的工作指的是每個DLP問題都需要做的。

（預計算，非常的快）選擇一個因子基數

因子基數是一些元素\(b_0 = g,b_1,...,b_r \in G\)。如何選擇它們和選擇多少取決于我們研究的群和後面的步驟運作的時間。實際上，簡單的選擇\(r\)通常導緻一個低效的線上計算(小\(r\))和離線(大\(r\))計算的效率權衡。在我們的例子中，我們通常選擇-1和前\(r\)個素數。因為這會讓我們的線上計算更有效率。這個\(r\)是我們選擇因子基數的數量。

最後得到的結果是這樣的：{−1,2,3,5,7,11,...,\(p_r\)}共r+1個因子基數。

（預計算，昂貴的但是可以并行）找出因子基數和DLP問題之間的關系

用一些技術（光滑數優化過的整數分解算法）來擷取這樣的關系：\(g^k \mod q = (-1)^{e_0}2^{e_1}3^{e_2}...p_r^{e_r}\)。我們找到了用不同的因子基數表示的方程它們互相關聯。通過取對數，我們可以轉換為線性關系。我們繼續搜尋直到找到r個關系，r越大我們需要的時間越多。也就是說，通過簡單地要求每個程序獨立搜尋，然後合并結果集，可以很容易地并行完成。我們的例子就是這樣工作的。說白了就是取不同的k，是以可以并行計算。

（預計算，相對有效率）求因子基數的DLP結果

我們對這\(r+1\)個因子基數解決離散對數問題。因為之前的矩陣，我們直接就知道了如何求解這個問題。因為\(log_g(g) = 1\)是預先知道的。我們有了r+1個等價關系。我們需要一個矩陣求解器即可。

（線上的，昂貴的）把\(h\)寫成因子基數的乘積

我們嘗試找到\(y\)和清單\(a_i\)使得\(hg^y = b_1^{a_1}...b_r^{a_r}\)。這個也可以并行的計算，通過嘗試\(y\)值。如果我們嘗試成功，我們立刻可以得到：

\[\log_g(h) = -y + L_1a_1 + \dots + L_r a_r

\]

現在，我們在前一個階段忽略了一個大問題，如何找到\(y\)？實際上我們的例子不算太壞。因為因子基數都是小素數，我們可以簡單的嘗試分解\(hg^y\)通過除法這樣的技術。然而在其它群中，這可能是困難的不切實際的。

一個簡要的總結

是以，Index Calculus算法通過離散對數轉化為和的形式找出離散對數的結果。它通過建立一個已知的表（因子基數庫）來解決這個問題，然後找到一個與目标相關的等式将目标寫成這種形式。是以，該算法非常通用，通過改變因子基數r的大小，可以恢複一些明顯的經典攻擊。然而選擇\(r\)的值使得每個階段都可以有效的完成通常是不可能的，是以要麼離線計算會很難，要麼線上計算會很難（或者都很難）。