离散对数

在整数中,离散对数(Discrete logarithm, DL)是一种基于同余运算和原根的一种对数运算。

在任何群 $G$ 中可为所有整数 $k$ 定义一个幂数为 $b^k$,而离散对数 $\log_ba$ 是指使得 $b^k = a$ 的整数 $k$。 离散对数在一些特殊情况下可以快速计算。然而,通常没有具非常效率的方法来计算它们。公钥密码学中几个重要算法的基础,是假设寻找离散对数的问题解,在仔细选择过的群中,并不存在有效率的求解算法。

基本定义

生成元

在一个群 $G$ 中,如果 $g$ 是 $G$ 的生成元,即所有 $G$ 中的所有元素都可以被表示成 $y=g^x$,此时的 $x$ 称为 $y$ 在 $G$ 中的对数。

设 $m \ge 1,\gcd(a,m)=1$,使得 $a^d \equiv 1 \pmod m$ 成立的最小正整数 $d$ 称为 $a$ 对模 $m$ 的指数或者阶。一般将其计为 $\delta_m(a)$。

满足 $a^d \equiv 1 \pmod m$ 的 $d$ 一定满足 $d \mid \varphi(m)$。

原根

当 $\delta_m(a)=\varphi(m)$ 时,称 $a$ 是模 $m$ 的原根,简称 $m$ 的原根。

只有 $m=2,4,p^\alpha,2p^\alpha$($p$ 为奇素数,$\alpha$ 为正整数)时,模 $m$ 的剩余系存在原根。(充要条件)

常规Sage函数

参数说明:求解以base为底,a的对数;ordbase的阶,可以缺省,operation可以是+*,默认为*bounds是一个区间(ld,ud),需要保证所计算的对数在此区间内。

  • discrete_log(a,base,ord,operation)

    通用的求离散对数的方法。

  • discrete_log_rho(a,base,ord,operation)

    求离散对数的Pollard-Rho算法。

  • discrete_log_lambda(a,base,bounds,operation)

    求离散对数的Pollard-kangaroo算法(也称为lambda算法)。

  • bsgs(base,a,bounds,operation)

    小步大步法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#生成64位的素数p作为模数,int为32位,超过int要在数字后加L
p=random_prime(2L**64)

#定义有限域GF(p)
G=GF(p)

#找一个模p的原根
gp ('znprimroot('+str(p)+')')
#输出Mod(rt,p),则x是模p的原根
g=G(rt)

#生成私钥
x=G(ZZ.random_element(p-1))

#公钥y=g^x mod p,由于已经定义在GF(p)上,因此g**x就是g^x mod p
y=g**x

#计算离散对数的通用方法
discrete_log(y,g)==x

#计算离散对数的lambda方法
discrete_log_lambda(y,g,(floor(ZZ(x)/2),2*ZZ(x)))==x

#小步大步法计算离散对数
bsgs(g,y,(floor(ZZ(x)/2),2*ZZ(x)))==x

大步小步算法(BSGS)

大步小步算法常用于求解用于解决解高次同余方程的问题,问题形式如:有同余方程$a^x \equiv b \pmod p$,$p$ 为质数,求最小非负整数解 $x$ 使得原方程成立。这类问题也称为离散对数问题。该算法的复杂度可以达到$O(\sqrt{p}\log{n})$甚至更低。

1
2
#Sage
bsgs(base,a,bounds,operation)

Pollard Rho算法

Pollard Rho算法是一种随机性的概率型算法,基于PR算法我们可以加速大整数的因子分解,这也是1975年Pollard提出该算法时的应用方面,这可以用来攻击RSA的公钥密码体制,之后在1978年Pollard又利用循环群 $ρ$ 形的特点提出了用于解决离散对数问题的PR算法,后来也扩展到了椭圆曲线上,这样PR算法便成功威胁到了整个公钥密码体系。

解决离散对数问题的Pollard Rho算法,可以帮助我们在有限的循环群上解决离散对数问题。简单来看我们取一个大素数 $P$,设 $G$ 为一个乘法的循环群,其生成元为 $g$,则该群的阶就是 $N=P-1$。此时在 $G$ 上的离散对数问题就是对于 $G$ 中的元素 $q$,找到 $x$ 使得 $g^x=q$,而Pollard Rho算法主要就是利用了循环群的生成序列呈现一个 $ρ$ 字形状。

使用Pollard Rho算法后可以将求解的时间复杂度降到 $O(\sqrt{N})$,至于空间复杂度则可以忽略不计,因为该算法是个概率型算法,每次只随机选取一对进行比较,所以不会占用存储,这与大步小步算法相反,其实PR算法也可以看作是大步小步算法的随机化版本,继承令时间复杂度的有点,同时还减少了空间的消耗,因为大步小步算法需要占用大量的存储空间。

此算法适用于生成元的阶的素因子都是大数的情形。

参考:https://xz.aliyun.com/t/2780

1
2
#Sage
discrete_log_rho(a,base,ord,operation)

Pohlig-Hellman算法

Pohig-Hellman算法是一种求解光滑阶循环群上的离散对数的方法。

Pohlig-Hellman算法的复杂度在一般情况下比BSGS算法高,但是在特殊情况下(循环群的阶是光滑数,即可以因子分解成较小的数的乘积),使用Pohlig-Hellman能取得好的效果。而且有些时候,尽管BSGS能够将复杂度降至$\sqrt{p}$,但是这个数依然很大,所以不能用。这时可以考虑Pohlig-hellman方法能不能起作用。

  • 算法思想

    考虑DLP问题:$a^x \equiv b \pmod p$,因为 $p$ 是大素数,模 $p$ 的循环群的阶是 $p−1$。假设模 $p$ 的最小的本原元是 $g$(本原元是可以求的),那么有

    $\left\{\begin{array}{c} a \equiv g^{a’} \pmod p \\ b \equiv g^{b’} \pmod p \end{array}\right.$

    进一步有 $a^x \equiv b \pmod p \Longleftrightarrow g^{a’x} \equiv g^{b’} \pmod p$,

    有 $a’x \equiv b’ \pmod {p-1}$,

    如果求出了满足上式的 $a’$ 和 $b’$ ,通过扩展gcd方法可以求一次同余方程的解得到 $x$ 。

    问题归结成如何求 $a’$ 和 $b’$ ,即原本的一个离散对数问题,现在变成两个离散对数问题:

    $\left\{\begin{array}{c} a \equiv g^{a’} \pmod p \\ b \equiv g^{b’} \pmod p \end{array}\right.$

    以求 $a’$ 为例,解DLP问题:$g^x \equiv a \pmod p$:

    1. 将 $p-1$ 进行标准的素因子分解,即 $p-1=\prod\limits_{i=1}^{m} p_i^{k_i}=p_1^{k_1}p_2^{k_2}p_3^{k_3} \cdots p_m^{k_m}$;

    2. 对每个素因子 $p_i$,将 $x$ 表示成 $p_i$ 进制,有

      $x=a_0+a_1p_1+a_2p_2^2+a_3p_3^3+\dots+a_{k_i-1}p_i^{k_i-1} \pmod {p_i^{k_i}}$,

      这样的 $p_i$ 进制表示,系数 $a_i$ 自然是小于 $p_i$;

    3. 令 $r=1$,有 $(g^x)^{\frac{p-1}{p_i^r}} \equiv a^{\frac{p-1}{p_i^r}} \pmod p$,展开 $x$ 有

      $(g^{a_0+a_1p_1+a_2p_2^2+a_3p_3^3+\dots+a_{k_i-1}p_i^{k_i-1}})^{\frac{p-1}{p_i^r}} \equiv a^{\frac{p-1}{p_i^r}} \pmod p$

      $g^{a_0{\frac{p-1}{p_i}}} \cdot g^{a_1(p-1)} \cdot g^{a_2(p-1)p_i} \cdots g^{a_{k_i-1}(p-1)p_i^{k_i-2}} \equiv a^{\frac{p-1}{p_i}} \pmod p$

      注意从第二项开始,每一项指数都包含 $p−1$(由费马小定理知 $g^{p-1} \equiv 1 \pmod p$),所以式子变成

      $g^{a_0{\frac{p-1}{p_i}}} \equiv a^{\frac{p-1}{p_i}} \pmod p$

      这个式子中只有 $a_0$ 是未知的,因为 $a_0 \in [0,p_i−1]$,所以可以穷举得到 $a_0$ 的值。

    4. 再令 $r=2,3,4,\cdots,k_i$,重复步骤3,依次穷举求出 $a_1,a_2,\cdots,a_{k_i-1}$,整个的时间复杂度是 $\mathrm{O}(p_ik_i)$。可以得到

      $x=a_0+a_1p_1+a_2p_2^2+a_3p_3^3+\dots+a_{k_i-1}p_i^{k_i-1} \pmod {p_i^{k_i}}$

    5. 重复上述过程,得到 $m$ 个关于 $x$ 的式子,利用中国剩余定理(CRT),可以计算出 $x$ 的值。

    利用这个方法求出 $a’$ 和 $b’$ 后,就可以得到原DLP问题的解。

    注:

    Pohlig-Hellman算法最重要的点是利用了原根的性质,它只能解决 $a \equiv g^x \pmod p$($g$ 是原根)的问题,对于 $g$ 不是原根的情况,需要利用原根将原方程转化成两个关于原根的离散对数问题。

    注意Pohlig-hellman只能用于求解光滑阶群,也就是 $p-1$ 可以分解成小的素因子乘积。否则,穷举 $a_i$ 的时间复杂度依旧很高。另外可以考虑在穷举 $a_i$ 时利用小步大步算法,进一步优划算法复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from Crypto.Util.number import *
from gmpy2 import *
import time

# g^x = h (mod p)
def PohligHellmanDLP(g,h,p):
Lq=pollard_rho_Factor(p-1)
assert reduce(lambda x,y: x*y, Lq) == p-1
print(Lq)
Lg=[pow(g,(p-1)//i,p) for i in Lq]
Lh=[pow(h,(p-1)//i,p) for i in Lq]
length=len(Lq)
La=[]
for i in range(length):
La.append(ForceDLP(Lg[i],Lh[i],p))
X=CRT(Lq,La)
if pow(g,X,p)==h:
print("Found x! x =",X)
return X
else:
print("Error!")

p=
g=
h=
start_time=time.time()
x = PohligHellmanDLP(g,h,p)
print(x)
print("it takes",time.time()-start_time,"seconds",)

多项式DLP

参考:InCTF 2020 - DLPoly

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#Sage
def brute_dlp(gi, ci, n, lim):
bi = gi
for i in range(1, lim+1):
if bi == ci:
return i
bi = (bi * gi) % n
print("[-] NOT in the range")
print("[-] Something's Wrong, you gotta check the range", lim)

def pohlig_hellman(g, c, s, n, factors):
res = []
modulus = []
for q, e in factors:
assert pow(g, s//(q**e), n) != 1
gi = pow(g, s//(q**e), n)
ci = pow(c, s//(q**e), n)
dlogi = brute_dlp(gi, ci, n, q**e)
print("[+] dlog modulo {0} == {1}".format(q**e, dlogi))
res.append(dlogi)
modulus.append(q**e)
print("\n[*] res = ", res)
print("[*] modulus = ", modulus)
dlog = CRT(res, modulus)
print("\n[+] dlog modulo {0} == {1}".format(prod(modulus), dlog))
return dlog

p =
P = PolynomialRing(Zmod(p), name='x')
x = P.gen()
n =
g =
nfactors = n.factor()
s = 1
for i in nfactors:
s *= p**(i[0].degree()) - 1

print(s)
print(factor(s))
qe =
dlog = pohlig_hellman(g, c, s, n, qe)

flag = bytes.fromhex(hex(dlog)[2:])
print("\n[*] flag = ", flag.decode())

Okamoto-Uchiyama加密算法

1998年由Tatsuaki Okamoto和Shigenori Uchiyama提出的公钥加密算法。

条件:$n=p^2q$

  • 密钥生成

    1. 生成两个大素数 $p$ 和 $q$;
    2. 计算 $n=p^2q$;
    3. 选择一个随机整数 $g \in \{2, \cdots ,n-1\}$ 满足 $g^{p-1} \not\equiv 1 \pmod {p^2}$;
    4. 计算 $h=g^n \bmod n$。

    公钥为 $(n,g,h)$,私钥为 $(p,q)$。

  • 加密

    明文 $m<p$ 可以通过公钥 $(n,g,h)$ 加密:

    1. 选择一个随机整数 $r \in \{1,\cdots,n-1\}$;
    2. 计算 $c=g^m h^r \bmod n$。

    $c$ 即为 $m$ 的密文。

  • 解密

    密文 $c$ 可以通过私钥 $(p,q)$ 解密:

    1. 计算 $a=\cfrac{(c^{p-1} \bmod {p^2})-1}{p}$;
    2. 计算 $b=\cfrac{(g^{p-1} \bmod {p^2})-1}{p}$;
    3. 使用扩展欧几里得算法计算 $b$ 的模 $p$ 逆元 $b’=b^{-1} \bmod p$;
    4. 计算 $m=ab’ \bmod p$。

    $m$ 即为 $c$ 的明文。

参考:PoseidonCTF 1st Edition 2020 - discrete log