離散對數¶
基本定義¶
在瞭解離散對數時,我們先來瞭解幾個基本定義。
定義1
在羣 G 中,g 爲 G 的生成元,也就是說羣 G 中每一個元素都可以寫成 y=g^k,我們稱 k 爲 y 在羣 G 中的對數。
定義2
設 m\geq 1,(a,m)=1 ,使得 a^d \equiv 1\pmod m 成立的最小正整數 d 稱爲 a 對模 m 的指數或者階,我們一般將其記爲 \delta_m(a)。
定義3
當 \delta_m(a)=\varphi(m) 時,稱 a 是模 m 的原根,簡稱 m 的原根。
一些性質¶
性質1
使得 a^d \equiv 1\pmod m 成立的最小正整數 d ,必有d\mid\varphi(m)。
性質2
模 m 剩餘系存在原根的充要條件是 m=2,4,p^{\alpha},2p^{\alpha} ,其中 p 爲奇素數, \alpha 爲正整數。
離散對數問題¶
已知 g,p,y ,對於方程 y\equiv g^x \pmod p ,求解 x 是一個難解問題。但是當 p 具有一定的特性時就可能可以求解,比如,這個羣的階是一個光滑數。
正是上述這個問題構成了目前很大一部分現代密碼學,包括 Diffie–Hellman 密鑰交換, ElGamal 算法,ECC 等。
離散對數求解方式¶
暴力破解¶
給定 y\equiv g^x \pmod p,我們可以暴力枚舉 x 從而得到真正的 x 的值。
Baby-step giant-step¶
這一方法通常被稱爲小步大步法,這一方法使用了中間相遇攻擊的思想。
我們可以令 x=im+j,其中 m= \lceil \sqrt n\rceil ,那麼整數 i 和 j 都在 0 到 m 的範圍內。
因此
也就是
那麼我們就可以枚舉所有的 j 並進行計算,並將其存儲到一個集合 S 中,然後我們再次枚舉 i,計算 y(g^{-m})^i,一旦我們發現計算的結果在集合 S 中,則說明我們得到了一個碰撞,進而得到了 i 和 j。
這顯然是一個時間與空間的折中的方式,我們將一個 O(n) 的時間複雜度,O(1) 空間複雜度的算法轉換爲了一個O(\sqrt n)的時間複雜度和O(\sqrt n) 的空間複雜度的算法。
其中
- 每一次 j 的增加表示“baby-step”,一次乘上 g。
- 每一次 i 的增加表示“giant-step”,一次乘上 g^{-m} 。
def bsgs(g, y, p):
m = int(ceil(sqrt(p - 1)))
S = {pow(g, j, p): j for j in range(m)}
gs = pow(g, p - 1 - m, p)
for i in range(m):
if y in S:
return i * m + S[y]
y = y * gs % p
return None
Pollard’s ρ algorithm¶
我們可以以O(\sqrt n)的時間複雜度和O(1) 的空間複雜度來解決上述問題。具體原理請自行谷歌。
Pollard’s kangaroo algorithm¶
如果我們知道 x 的範圍爲 a \leq x \leq b,那麼我們可以以O(\sqrt{b-a}) 的時間複雜度解決上述問題。具體原理請自行谷歌。
Pohlig-Hellman algorithm¶
不妨假設上述所提到的羣關於元素 g 的階爲 n, n 爲一個光滑數: n=\prod\limits_{i=1}^r p_i^{e_i}。
- 對於每個 i \in \{1,\ldots,r\} :
- 計算 g_i \equiv g^{n/p_i^{e_i}} \pmod m。根據拉格朗日定理, g_i 在羣中的階爲 p_i^{e_i} 。
- 計算 y_i \equiv y^{n/p_i^{e_i}} \equiv g^{xn/p_i^{e_i}} \equiv g_i^{x} \equiv g_i^{x \bmod p_i^{e_i}} \equiv g_i^{x_i} \pmod m,這裏我們知道 y_i,m,g_i,而x_i 的範圍爲[0,p_i^{e_i}),由 n 是一個光滑數,可知其範圍較小,因此我們可以使用 Pollard’s kangaroo algorithm 等方法快速求得x_i。
- 根據上述的推導,我們可以得到對於 i \in \{1,\ldots,r\} ,x \equiv x_i \pmod{p_i^{e_i}} ,該式可用中國剩餘定理求解。
上述過程可用下圖簡單描述:
其複雜度爲O\left(\sum\limits _i e_i\left(\log n+\sqrt{p_i}\right)\right),可以看出複雜度還是很低的。
但當 n 爲素數,m=2n+1,那麼複雜度和 O(\sqrt m) 是幾乎沒有差別的。
2018 國賽 crackme java¶
代碼如下
import java.math.BigInteger;
import java.util.Random;
public class Test1 {
static BigInteger two =new BigInteger("2");
static BigInteger p = new BigInteger("11360738295177002998495384057893129964980131806509572927886675899422214174408333932150813939357279703161556767193621832795605708456628733877084015367497711");
static BigInteger h= new BigInteger("7854998893567208831270627233155763658947405610938106998083991389307363085837028364154809577816577515021560985491707606165788274218742692875308216243966916");
/*
Alice write the below algorithm for encryption.
The public key {p, h} is broadcasted to everyone.
@param val: The plaintext to encrypt.
We suppose val only contains lowercase letter {a-z} and numeric charactors, and is at most 256 charactors in length.
*/
public static String pkEnc(String val){
BigInteger[] ret = new BigInteger[2];
BigInteger bVal=new BigInteger(val.toLowerCase(),36);
BigInteger r =new BigInteger(new Random().nextInt()+"");
ret[0]=two.modPow(r,p);
ret[1]=h.modPow(r,p).multiply(bVal);
return ret[0].toString(36)+"=="+ret[1].toString(36);
}
/* Alice write the below algorithm for decryption. x is her private key, which she will never let you know.
public static String skDec(String val,BigInteger x){
if(!val.contains("==")){
return null;
}
else {
BigInteger val0=new BigInteger(val.split("==")[0],36);
BigInteger val1=new BigInteger(val.split("==")[1],36);
BigInteger s=val0.modPow(x,p).modInverse(p);
return val1.multiply(s).mod(p).toString(36);
}
}
*/
public static void main(String[] args) throws Exception {
System.out.println("You intercepted the following message, which is sent from Bob to Alice:");
BigInteger bVal1=new BigInteger("a9hgrei38ez78hl2kkd6nvookaodyidgti7d9mbvctx3jjniezhlxs1b1xz9m0dzcexwiyhi4nhvazhhj8dwb91e7lbbxa4ieco",36);
BigInteger bVal2=new BigInteger("2q17m8ajs7509yl9iy39g4znf08bw3b33vibipaa1xt5b8lcmgmk6i5w4830yd3fdqfbqaf82386z5odwssyo3t93y91xqd5jb0zbgvkb00fcmo53sa8eblgw6vahl80ykxeylpr4bpv32p7flvhdtwl4cxqzc",36);
BigInteger r =new BigInteger(new Random().nextInt()+"");
System.out.println(r);
System.out.println(bVal1);
System.out.println(bVal2);
System.out.println("a9hgrei38ez78hl2kkd6nvookaodyidgti7d9mbvctx3jjniezhlxs1b1xz9m0dzcexwiyhi4nhvazhhj8dwb91e7lbbxa4ieco==2q17m8ajs7509yl9iy39g4znf08bw3b33vibipaa1xt5b8lcmgmk6i5w4830yd3fdqfbqaf82386z5odwssyo3t93y91xqd5jb0zbgvkb00fcmo53sa8eblgw6vahl80ykxeylpr4bpv32p7flvhdtwl4cxqzc");
System.out.println("Please figure out the plaintext!");
}
}
基本功能爲計算
r_0=2^r \bmod p
r_1 =b*h^r \bmod p
可以發現,r 的範圍爲 [0,2^{32}),所以我們可以使用 BSGS 算法,如下
from sage.all import *
c1 = int(
'a9hgrei38ez78hl2kkd6nvookaodyidgti7d9mbvctx3jjniezhlxs1b1xz9m0dzcexwiyhi4nhvazhhj8dwb91e7lbbxa4ieco',
36
)
c2 = int(
'2q17m8ajs7509yl9iy39g4znf08bw3b33vibipaa1xt5b8lcmgmk6i5w4830yd3fdqfbqaf82386z5odwssyo3t93y91xqd5jb0zbgvkb00fcmo53sa8eblgw6vahl80ykxeylpr4bpv32p7flvhdtwl4cxqzc',
36
)
print c1, c2
p = 11360738295177002998495384057893129964980131806509572927886675899422214174408333932150813939357279703161556767193621832795605708456628733877084015367497711
h = 7854998893567208831270627233155763658947405610938106998083991389307363085837028364154809577816577515021560985491707606165788274218742692875308216243966916
# generate the group
const2 = 2
const2 = Mod(const2, p)
c1 = Mod(c1, p)
c2 = Mod(c2, p)
h = Mod(h, p)
print '2', bsgs(const2, c1, bounds=(1, 2 ^ 32))
r = 152351913
num = long(c2 / (h**r))
print num