具有中等欄位的數字簽名算法 (DSA)
當我們必須解決離散對數問題時，我明白了 $ a^x\equiv b\pmod p $ ， 在哪裡 $ a $ 和 $ b $ 給定整數，我們必須找到秘密整數 $ x $ 這使得等式對於某些給定的模數為真 $ p $ .
我不明白什麼時候 $ a $ 和 $ b $ 是多項式，我們不僅要對整數取模，還要對另一個多項式取模。
- 你能給我一個明確的適用於這種情況的 DSA 的工作範例嗎？
- 已知對它的哪些攻擊？
編輯：在原始標準中，有限域具有特徵 2。“中等”域是指域 GF(p^n)，其中素數 $ p $ 更大。代替 $ p=2 $ 它在附近 $ 10^{10} $ 和 $ n=17 $ 或者。
編輯2：我自己的例子： $$ a=4 x^6+10 x^5+11 x^4+3 x^3+x^2+15 x+7 $$ $$ b=12 x^6+4 x^5+8 x^4+4 x^3+9 x^2+6 x+7 $$ $$ m_1=x^7-2 $$ $$ m_2=17 $$
尋找 $ e $ 那 $$ a^e\equiv b\pmod{m_1}\pmod{m_2} $$
我不確定我的例子是否相關，選擇多項式有一些標準 $ m_1 $ 和素數 $ m_2 $ . 我隨意選擇了它們。但我可以說 $ e=103 $ 是一個解決方案，因為我強行使用它。
問題涉及有限域 $ \mathrm{GF}(p^n) $ . 它想研究/攻擊該領域（的乘法子組）中的DSA變體，而不是 $ \mathrm{GF}(p) $ . 無論 DSA 變體是什麼，都可以通過解決離散對數問題來攻擊它 $ \mathrm{GF}(p^n) $ .
的乘法子群 $ \mathrm{GF}(p^n) $ 有訂單 $ p^n-1 $ ，並且任何元素的順序都會將其分開。如果順序 $ a $ 沒有大的素因數，那麼Pohlig-Hellman方法可以簡化為更簡單的子問題，而像Baby-Step Giant Step或Pollard’s rho這樣的一般 DLP 算法可以解決。DSA 通過在大素數的乘法子群中工作來阻止此類攻擊 $ q $ （例如，至少 256 位）。這也將簽名大小保持在最小（位大小的兩倍 $ q $ ).
設想的參數是 $ p\approx10^{10} $ 和 $ n=17 $ ， 因此 $ p^n $ 大約 565 位，使得這樣的子組是合理的。如果我們想要 $ p $ 略低於 $ 2^{32} $ 和 $ x^{17}-2 $ 不可約模 $ p $ （這簡化了計算），我們可以使用 32 位 $ p=\mathtt{ffe083f1}\text{h} $ ， 和 $ p^{17}-1 $ 以 262 位為最高素數 $ q=\mathtt{2a92bc16243adf3264304adf2adc292c32e64b569a5abfbd7be71d7a1816e3d8c1}\text{h} $ . 獲取有序元素 $ q $ ，我們可以選擇幾乎任何任意多項式 $ u $ ; 找到訂單 $ r $ 的 $ u $ （我們劃分 $ p^{17}-1 $ 由素數在其因式分解，同時提高 $ u $ 到那個功率產量 $ 1 $ ); 並使用 $ g=u^{r/q} $ 作為順序子群的生成器 $ q $ .
從中建構 DSA 模擬和 SHA-512 很容易。唯一的困難是當原件進行取模時 $ p $ 後跟一個減少模 $ q $ . 在眾多方法中，與之並行的一種選擇是使取冪取模 $ x^{17}-2\pmod p $ ，然後在 $ \Bbb Z $ 在這一點上 $ x=2^{32} $ （即連接表示為 32 位整數的係數），然後減少模 $ q $ .
這將使一個有效的 DSA 免受上述所有算法的影響 $ q $ . 但這仍然是不安全的，因為其他 DLP 方法適用於手頭的情況。Razvan Barbulescu 和 Cécile Pierrot 的The Multiple Number Field Sieve for Medium and High Characteristic Finite Fields中最近的結果總結在LMS Journal of Computation and Mathematics , 2014。
暫定：攻擊 DSA 模擬的選擇算法可能是 Antoine Joux、Reynald Lercier、Nigel P. Smart 和 Frederik Vercautere 的The number field sieve in the medium prime case，在Crypto 2006 的程序中。
在問題的末尾用一個小例子思考試圖在 $ \mathrm{GF}(17^7) $ , 但使用多項式 $ m_1=x^7-2 $ 這不是不可約模 $ p=17=m_2 $ ， 自從$$ (x+8)(x^6+9x^5+13x^4+15x^3+16x^2+8x+4)\\quad\equiv x^7-2\pmod{17} $$
它遵循 $ (x+8) $ 是不可逆的，我們得到一個環而不是一個場。
如果我們改為 $ p=29 $ 這使得 $ x^7-2 $ 不可約。我在下面假設這一點。
的乘法子群 $ \mathrm{GF}(p^n) $ 有訂單 $ p^n-1 $ ， 這裡 $ 29^7-1 $ . 這因素為 $ 2^2\cdot7^2\cdot88009573 $ . 的順序 $ a $ 必然是它的除數。通過計算 $ a^{(29^7-1)/2}=-1\ne1 $ , $ a^{(29^7-1)/7}=-5\ne1 $ ， 和 $ a^{(29^7-1)/88009573}\ne1 $ ，我們明白了 $ a $ 是完全乘法群的生成器。 $ b\ne0 $ ， 所以 $ a^e=b $ 有解決辦法。