具有有限域 GF(2^5) 的 Diffie-Hellman 密鑰交換協議
在 Diffie-Hellman 密鑰交換協議中，系統參數如下： 有限域 $ GF(2^5) $ 用不可約多項式定義 $ f(x) = x^5 + x^2 + 1 $ 和原始元素 $ \alpha= x $ 在該領域。
假設 Alice 選擇了隨機數 $ a = 5 $ 和鮑勃選擇 $ b = 6 $ ，顯示 Alice 和 Bob 為獲取他們的共享密鑰所執行的步驟。關鍵是什麼？
對於愛麗絲：
$ α^a = α^5 = x^5 = (x^2 + 1) $
對於鮑勃：
$ α^b = α^6 = x*x^5 = x(x^2 + 1) = x^3 + x $
愛麗絲的共享密鑰：
$ α^{ab} = (x^2 + 1)^b = (x^2 + 1)^6\ldots $
Bob 的共享密鑰：
$ α^{ab} = (x^3 + x)^a = (x^3 + x)^5\ldots $
答案是 $ x^4 + x $ 但我不確定如何從 Alice 或 Bob 雙方簡化到這個答案，它們應該具有相同的共享密鑰
三個詞有限域算術。有限域（伽羅瓦域）的元素可以用多項式表示，就像在這種情況下一樣。我們更喜歡它，因為它為我們提供了良好的計算性能。
$ \rm GF(2^5) $ 是二進製欄位擴展，具有基本欄位 2，二進製欄位。為了構造這個域，我們需要一個不可約的二元多項式$$ * $$5 級$$ ‡ $$. 在你的情況下 $ f(x)=x^5+x^2+1 $ . 該欄位可以由 $ \operatorname{GF} (2)[x]/f(x) $ $$ + $$. 5次不可約二元多項式不必唯一，構造的可能性只有 6 種 $ \operatorname{GF}(2^5) $ $$ # $$.
- $ f(x)=1+x^2+x^5 $ ,
- $ f(x)=1+x+x^2+x^3+x^5 $ ,
- $ f(x)=1+x^3+x^5 $ ,
- $ f(x)=1+x+x^3+x^4+x^5 $ ,
- $ f(x)=1+x^2+x^3+x^4+x^5 $ ， 和
- $ f(x)=1+x+x^2+x^4+x^5 $
對於二元域擴展，我們更喜歡具有小度單項式和較少單項式的那些。所以， $ f(x)=1+x^2+x^5 $ 是一個不錯的選擇。
加法是多項式加法，係數減少到基域。乘法有點棘手，我們需要用不可約多項式進行模約簡。在你的情況下，每當你看到 $ x^5 $ 將其替換為 $ x^2+1 $ . 在這個網站上，你可以看到加法和乘法的表格。對於小型情況，生成表並將其硬編碼到表中可能會有所幫助，但是請注意記憶體攻擊。
一種方法是一次全部相乘然後減少 $$ \begin{align} (x^2 + 1)^6 &= x^{12} + 6 x^{10} + 15 x^8 + 20 x^6 + 15 x^4 + 6 x^2 + 1 \ &= x^{12} + x^8 + 15 x^4 + 1 \ \vdots &= \vdots\ \end{align} $$
這不是首選方法，因為它可以縮放太多，尤其是對於大型有限域。更好的方法是下面的乘法和減法範式。
$$ \begin{align} (x^2 + 1)^6 &= ((x^2 + 1)^2)^2 (x^2 + 1)^2 &&,\text{expand one level } \ &= (x^4 + \color{red}{2} x^2 + 1)^2 (x^4 + \color{red}{2} x^2 + 1) && , \color{red}{2=0} \text{ in } \mathbb{F}_2\ &= (x^4 + 1)^2 (x^4 + 1) &&,\text{work on left} \ &= (x^8 + \color{red}{2}x + 1) (x^4 + 1) && , \color{red}{2=0} \text{ in } \mathbb{F}_2\ &= (x^8 + 1) (x^4 + 1) && , \text{use } x^5 = x^2+1\ &= ((x^5)x^3 + 1) (x^4 + 1) \ &= ((x^2+1)x^3 + 1) (x^4 + 1) \ &= (x^5 + x^3 + 1 ) (x^4 + 1)&& , \text{use } x^5 = x^2+1\ &= (x^2+ \color{red}{1} + x^3 + \color{red}{1} ) (x^4 + 1)&& , \color{red}{2=0} \text{ in } \mathbb{F}_2\ &= (x^3 + x^2 ) (x^4 + 1) &&, \text{multiply}\ &= x^7 + x^6 + x^3 + x^2 &&,\text{use } x^5 = x^2+1\ &= (x^2+1)x^2 + (x^2+1)x + x^3 + x^2 &&,\text{expand } \ &= x^4 + \color{red}{2} x^3 + \color{red}{2} x^2 + x &&,\text{use }\color{red}{2=0} \text{ in } \mathbb{F}_2\ &= x^4+ x && \end{align} $$
而且，對於另一個等式，您可以通過以下方式看到它們的相等性；$$ (x^3+x)^5=x^5(x^2+1)^5=(x^2+1)(x^2+1)^5=(x^2+1)^6 $$
實際上，我們使用位向量來處理二進制多項式：
$ (x^2+1)= [00101] $ ，我們可以用 5 位表示，因為有限域 $ GF(2^5) $ .
每當我們看到 5 中的 1 時，我們都會減少它。
- $ (x^5)= [1|00000] = [00101] $ ，減少是移位和x-or。我們可以說，用位置 5 替換 1 $ [0|00101] $ 和 x 或。同樣，我們可以寫出公式
- $ x^6 = (x^5)x = [01001] $ 和
- $ x^7 = (x^5)x^2 = [10100] $ ， 等等。在您的情況下，如果您一一相乘，則 6 應該足夠了。
$$ \begin{align} [00101]^6 &= [00101]\cdot [00101]\cdot [00101]^4 \ &= [10001]\cdot [00101]\cdot [00101]^3 \ &= [10|10001]\cdot [00101]^3 \tag{use $x^6$}\ &= [11000] \cdot [00101] \cdot [00101]^2\ &= [11|11000] \cdot [00101]^2\ \vdots &= \vdots \end{align} $$
$$ * $$如果多項式不能分解為同一域上的非平凡多項式，則稱該多項式是不可約的。（Wolfram 定義。）
$$ # $$該列表也來自 Wolfram。
$$ ‡ $$有一個關於次數的二進制多項式的序列；OEIS A059912
$$ + $$一般情況下；為了一個素數 $ p $ 主要力量 $ q=p^n $ , $ n \in \mathbb Z^+ $ , 與不可約多項式 $ f $ 學位 $ n $ , 商環
$$ {\operatorname{GF}}(q)={\operatorname{GF}}(p)[X]/(f(x)) $$ 多項式環的 $ \operatorname{GF}(p)[X] $ 由產生的理想 $ f(x) $ 是一個有限的有序域 $ q $ .