DLP学习

离散对数问题 DLP（Discrete Logarithm Problem）

做题时又被打爆了，记录一下
DLP就是离散对数问题，离散对数是基于群之上的概念，先简单说下群

群

定义

假设有一个非空集合 $ G $ ，以及一个二元运算 $ \times $ 所构成的集合 $ (G, \times) $ ，如果满足以下条件就是一个群：

• 封闭性：$\forall a,b \in G , a \times b = c \in G $
• 结合律：$\forall a,b,c \in G , a \times (b \times c) = (a \times b) \times c$
• 单位元：$\exists e \in G,\forall a \in G , a \times e = e \times a = a$
• 逆元：$\forall a \in G,\exists b \in G , a \times b = b \times a = e$

此外，如果一个群还满足 $\forall a,b \in G,a \times b = b \times a$ 则称 $ G $ 为交换群或者阿贝尔群

有限群

当一个群 $ G $ 中的元素只有有限个的时候，称其为有限群，其中群 $ G $ 的元素个数被称为群的阶或者基，记为 $|G|$

例如：$ (\mathbb{Z_n},+) $ 就是由集合 $ \mathbb{Z_n} = {0,1,…,n-1} $ 与整数模 n 加法构成的群，它的阶为 n

元素的阶

群 $ (G,\times) $ 内某个元素 $ a $ 的阶 ord(a) 是指满足以下条件的最小正整数 k

$$
a^k = a \times a \times a \ldots \times a = e
$$

e 是该群的单位元，值得注意的是 a^k 在群中不表示 a 的 k 次幂，而是将 a 进行 k 次群的二元运算

循环群

对于群 $ G ,a \in G $ 则 $ \langle a \rangle = {a^z|z \in \mathbb{Z}} $ 是由 $ a $ 生成的 $ G $ 的子群
若 $ g \in G,G = \langle g \rangle $ ,则称 $ G $ 是循环群， $ g $ 是生成元（ $ G $ 是阿贝尔群）

定理

• 对于每一个素数 $ p $ ，$(\mathbb{Z_p},*)$ 都是阿贝尔有限循环群
• 假设 $G$ 是一个有限循环群，则对于每一个 $a \in G$ 都有：
  • $a^{|G|} = e$
  • ord(a)是 $G$ 的因子
• 拉格朗日定理：对于有限群 $G$ ，$H$ 是 $G$ 的任意子群，则 $|H|$ 是 $|G|$ 的因子
• n阶有限循环群 <g>， $\forall k \in \mathbb{Z}$ ，有 $g^k$ 的阶是 $\frac{n}{\gcd(n,k)}$

DLP

简单来说就是给定大素数 $p$ ，$g \in \mathbb{Z_p^*}$ 求解以下问题

$$y \equiv g^{x} \pmod{p}$$

DHKE

Diffle-Hellman 密钥协商算法

1. 系统参数建立
   1. 选择大素数 $p$ ，满足 $p-1$ 含有大素因子 $q$
   2. 选取整数 $g(1<g<p)$ ，满足 $g$ 模 $p$ 的阶为 $q$
2. 双方秘钥协商
   1. Alice 随机秘密选取 $a(0<a<p-1)$ ，并计算
      $$A \equiv g^{a} \pmod{p}$$
   2. Bob 随机秘密选取 $b(0<b<p-1)$ ，并计算
      $$B \equiv g^{b} \pmod{p}$$
   3. Alice 将 $A$ 传送给 Bob，Bob 将 $B$ 传送给 Alice
   4. Alice 计算 $K \equiv B^{a} \pmod{p}$，Bob 计算 $K \equiv A^{b} \pmod{p}$

双方以 $K$ 为协商秘钥进行保密通信
事实上，有
$$K \equiv A^{b} \equiv B^{a} \equiv g^{ab} \pmod{p}$$

DDH（判定性离散对数问题）

假如说 Alice 和 Bob 执行如上所述的 Diffie-Hellman 密钥协议,那么 $ G,g,g^a,g^b $ 都是公共的, $ g^{ab} $ 是密钥.直观上,DDH问题就是是否对手能够从随机的 $ G $ 中的元素区分出 Alice 和 Bob 的密钥 $ g^{ab} $
正式来说:给定 $ G,g,g^a,g^b $ 和 $ T_x $ 使得 $ T_0 $ 是 $ G $ 中随机的一个元素, $T_1 = g^{ab} $ 同时 $ x $ 被随机均匀的从{0,1}中选择,找出 $x$

贴道例题，悄悄从别的平台上面修改过来的

from Crypto.Util.number import *
import random

FLAG = "flag{this_is_a_test_flag}"

def DDHgame(m, p):
    g = 2
    a = random.randint(1, p-1)
    b = random.randint(1, p-1)
    c = a*b%(p-1)
    ga = pow(g, a, p)
    gb = pow(g, b, p)
    gc = pow(g, c, p)
    if m:
        return (ga, gb, gc)
    else:
        return (ga, gb, random.randint(0, p-1))
    
p = getPrime(512)
m = bin(bytes_to_long(FLAG))[2:]
challenge = []
for i in m:
    challenge.append(DDHgame(int(i), p))

print(f"{p = }")
print(f"{challenge = }")

这道例题简单的实现了DDH加密，在这里就是需要辨别gc和一个大小(0,p-1)的随机数哪一个是属于群内的，从而推断出m的二进制位

Elgamal

我们假设 A 发消息 m 给 B

加密过程

• 随机选择一个满足要求的大素数 $p$ ，并生成有限域 $\mathbb{Z_p}$ 的一个生成元 $g \in \mathbb{Z_p^*}$
• 选择一个随机数 $k(1<k<p-2)$ ，计算 $y \equiv g^{k} \pmod{p}$
• 其中私钥为 $k$ 公钥为 $p,g,y$
• $A$ 选取随机数 $r \in \mathbb{Z_{p-1}}$ ，对明文加密 $E_k(m,r) = (y_1,y_2)$ 。其中 $y_1 \equiv g^r \pmod{p}，y_2 \equiv my^r \pmod{p}$

解密过程

$D_k(y_1,y_2) = y_2 (y_1^k)^{-1} \pmod{p} \equiv m(g^k)^r(g^{rk})^{-1} \equiv m \mod{p}$

贴道题，这个类型的题目好像经常出现（？）
2018 Code Blue lagalem（感谢CTF Wiki，每次例题都是上面扒下来的还有解析嘿嘿）

from Crypto.Util.number import *
from key import FLAG

size = 2048
rand_state = getRandomInteger(size // 2)


def keygen(size):
    q = getPrime(size)
    k = 2
    while True:
        p = q * k + 1
        if isPrime(p):
            break
        k += 1
    g = 2
    while True:
        if pow(g, q, p) == 1:
            break
        g += 1
    A = getRandomInteger(size) % q
    B = getRandomInteger(size) % q
    x = getRandomInteger(size) % q
    h = pow(g, x, p)
    return (g, h, A, B, p, q), (x,)


def rand(A, B, M):
    global rand_state
    rand_state, ret = (A * rand_state + B) % M, rand_state
    return ret


def encrypt(pubkey, m):
    g, h, A, B, p, q = pubkey
    assert 0 < m <= p
    r = rand(A, B, q)
    c1 = pow(g, r, p)
    c2 = (m * pow(h, r, p)) % p
    return (c1, c2)

# pubkey, privkey = keygen(size)

m = bytes_to_long(FLAG)
c1, c2 = encrypt(pubkey, m)
c1_, c2_ = encrypt(pubkey, m)

print pubkey
print(c1, c2)
print(c1_, c2_)

可以看出，该算法就是一个 ElGamal 加密，给了同一个明文两组加密后的结果，其特点在于使用的随机数 r 是通过线性同余生成器生成的，则我们知道

$$
c_2 \equiv (m \cdot h^r) \mod p \
c_{2’} \equiv m \cdot h^{(Ar + B) \mod q} \equiv m \cdot h^{(Ar + B)} \pmod{p}
$$

则

$$
\frac{c_2^A*h^B}{c_{2’}} \equiv m^{A-1} \pmod{p}
$$

其中 $c_2,c_{2’},A,B,h$ 都知道，则我们知道

$$
m^{A-1} \equiv t \pmod{p}
$$

我们假设已知 p 的一个原根 g，则我们可以假设

$$
g^x \equiv t \
g^y \equiv m
$$

则

$$
g^{y(A-1)} \equiv g^x \pmod{p}
$$

则

$$
y(A-1) \equiv x \pmod{p-1} \
y(A-1) - k(p-1) = x
$$

这里我们知道 A，p，x，则我们可以利用扩展欧几里得定理求得

$$
s(A−1)+w(p−1)=gcd(A−1,p−1)
$$

如果 gcd(A-1,p-1)=d，则我们直接计算

$$
t^s \equiv m^{s(A-1)} \equiv m^d \pmod{p}
$$

如果 d = 1 ，就可以直接计算 m ，不为1计算就有点困难，在这里恰好为1

import gmpy2
data = open('./transcript.txt').read().split('\n')
g, h, A, B, p, q = eval(data[0])

c1, c2 = eval(data[1])
c1_, c2_ = eval(data[2])

tmp = gmpy2.powmod(c2, A, p) * gmpy2.powmod(h, B, p) * gmpy2.invert(c2_, p)
tmp = tmp % p

print 't=', tmp
print 'A=', A
print 'p=', p
gg, x, y = gmpy2.gcdext(A - 1, p - 1)
print gg

m = gmpy2.powmod(tmp, x, p)
print hex(m)[2:].decode('hex')

Schnorr

1. 密钥生成
   • 选择一个大的素数 $p$ 和 $p-1$ 的一个大素数因子 $q$
   • 选择一个模 $p$ 的阶为 $q$ 的元素 $g$
   • 选择一个私钥 $x$ ，它是比 $q$ 小的随机数
   • 计算 $y = g^x \mod p$ ， $y$ 就是对应的公钥
2. 签名生成
   • 选择一个随机数 $k < q$ ，然后计算 $r = g^k \mod p$ 和 $e = H(r || M)$
   • 计算 $s = k - xe \mod q$
   • 签名结果就是 $(s, e)$
3. 签名验证
   • 对于收到的签名 $(s, e)$ ，验证者执行以下过程
   • 计算 $r_v = g^sy^e \mod p$
   • 计算 $e_v = H(r_v || M)$
   • 如果 $e_v == e$ ，那么验证通过，否则失败
   • 验证过程正确性：$r_v = g^sy^e = g^{s+xe} = g^k = r$
   • 所以 $e_v = H(r_v||M) = H(r||M) = e$
4. Schnorr群
   • 上述计算过程要求在一个有限群上进行，这个群的阶是 $q$, $q$ 如何得来？这就是Schnorr群的算法。
   • 构造Schnorr群首先选择两个大素数：$p,q$ 满足：$p = q*r + 1$
   • $r$ 是大于1的整数，明显 $q$ 是 $p-1$ 的大素因子
   • 然后在 $(0,q)$ 之间找到一个 $h$ ，使得 $h^r \neq 1 \mod p$
   • 那么 $g = h^r \neq 1 \mod p$ 是 $q$ 阶子群的生成元
   • 为什么以 $g$ 为生成元的群会有 $q$ 的阶呢？看下式：
   • $g^q \equiv h^{rq} \equiv h^{p-1} \equiv 1 \mod p$
   • 这里用了费马小定理，表明了 $g$ 的阶只能是 $q$ 或者 $q$ 的因数，但因为 $h^r \neq 1 \mod p$ 并且 $q$ 是素数，所以 $g$ 的阶必定是 $q$
   • 这样生成的群就叫做Schnorr群，特点是 $q$ 素数阶，可以避免小子群攻击，且素数阶群必为循环群

DSA

1. 密钥生成
   • 选择一个合适的哈希函数，目前一般选择SHA1，也可以选择强度更高的其他哈希函数
   • 选择秘钥的长度 $L$ 和 $N$ ，这两个值决定了签名的安全程度
   • 选择 $N$ 比特的素数 $q$ 和 $L$ 比特的素数 $p$ ，使得 $q$ 为 $p-1$ 的大素因子
   • 选择满足 $g^k = 1 \mod p$ 的最小正整数 $k$ 为 $q$ 的 $g$ ，即在模 $p$ 下，$ord(g) = q$ 的 $g$ 。即 $g$ 在模 $p$ 下，其指数次幂可以生成具有 $q$ 个元素的子群。这里可以计算 $g \equiv h^{\frac{p-1}{q}} \mod p$ 来得到 $g$ ，其中 $h \in (1,p-1)$
   • 选择私钥 $x \in (0,q)$ ，计算 $y \equiv g^x \pmod{p}$
   • 公钥为 $(p,q,g,y)$ ，私钥为 $(x)$
2. 签名生成
   • 随机选择整数 $k \in (0,q)$
   • 计算 $r \equiv g^k \pmod{p} \pmod{q}$
   • 计算 $s \equiv (H(m) + xr)k^{-1} \pmod{q}$
   • 签名结果为 $(r,s)$
3. 签名验证
   • 计算辅助值 $w \equiv s^{-1} \pmod{q}$
   • 计算辅助值 $u_1 \equiv H(m) \cdot w \pmod{q} $
   • 计算辅助值 $u_2 \equiv r \cdot w \pmod{q} $
   • 计算 $v = g^{u_1}y^{u_2} \pmod{q} \pmod{q}$
   • 如果 $v == r$ 那么验证通过
4. 攻击
   • $k$ 复用
   • 如果在两次签名的过程中共享了 $k$ ，就可以进行攻击
   • 假设两次签名的消息为 $m_1$ 和 $m_2$ ，显然两个的 $r$ 一样，此外
   • $s_1 = (H(m_1) + xr)k^{-1} \pmod{q}$
   • $s_2 = (H(m_2) + xr)k^{-1} \pmod{q}$
   • 这里除了 $x$ 和 $k$ 不知道剩下的都知道，联立有 $k(s_1 - s_2) \equiv (H(m_1) - H(m_2)) \pmod{q}$
   • 此时可以解出 $k$ ，可以进一步解出 $x$

离散对数求解方法

常规sage函数

参数说明：求解以base为底，a的对数；ord为base的阶，可以缺省，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算法）
• sage.groups.generic.bsgs(a, b, bounds, operation='*') 小步大步法

BSGS算法

这一方法通常被称为小步大步法，这一方法使用了中间相遇攻击的思想

我们可以令 $x = im + j$ ,其中 $m = \lceil \sqrt{n} \rceil$ 那么整数 $i$ 和 $j$ 都在 $0$ 到 $m$ 的范围内，因此

$$
y = g^x = g^{im + j}
$$

也就是

$$
y(g^{-m})^i = g^j
$$

那么我们就可以枚举所有的 $j$ 进行计算，并将其存储到一个集合 $S$ 中，然后我们再次枚举 $i$ 计算 $y(g^{-m})^i$ ，一旦我们发现计算的结果在集合 $S$ 中，则说明我们得到了一个碰撞，进而得到了 $i$ 和 $j$

其中

• 每一次 $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

拓展BSGS算法

还是同样的问题，求解 $a^x \equiv b \mod p$ ,但是 $p$ 非质数怎么办呢，也就是说可能 $a,p$ 可能不互质，那么我们就需要想办法转换成为互质的，然后使用普通BSGS求解

将同余式转换： $sa^x + tp = b$

令 $d_1 = gcd(a,p)$ ，即 $d_1(sa^{x-1}\frac{a}{d_1} + t\frac{p}{d_1}) = b$

此时，若 $d_1 \nmid b$ 那么无整数解

我们在能够整除的情况下继续研究，即

$$
sa^{x-1}\frac{a}{d_1} + t\frac{p}{d_1} = \frac{b}{d_1} \
a^{x-1}\frac{a}{d_1} \equiv \frac{b}{d_1} \pmod{\frac{p}{d_1}}
$$

此时若 $a$ 与 $\frac{p}{d_1}$ 仍不互质，那么继续上述的转换，令 $d_2 = gcd(a,\frac{p}{d_1})$

$$
\frac{a}{d_1d_2}\cdot a^{x-2} \equiv \frac{b}{d_1d_2} \pmod{\frac{p}{d_1d_2}}
$$

同理不断处理，直到 $gcd(a,\frac{p}{d_1d_2\dots d_k}) = 1$

记 $D = \prod_{i=1}^{k} d_i $

$$
\frac{a}{D^k}\cdot a^{x-k} \equiv \frac{b}{D} \pmod{\frac{p}{D}}
$$

这样，把 $\frac{a^k}{D}$ 通过逆元丢到方程右边就可以用普通BSGS求解了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
inline int gcd(int a,int b){
    if(!b)
        return a;
    else{
        while(int i=a%b){
            a=b;
            b=i;
        }
        return b;
    }
}
 
inline int qpow(ll a,int n,int m) {
    //这个快速幂保证p不是1，少模一次是一次
    ll s=1;
    while(n) {
        if(n&1)
            s=s*a%m;
        a=a*a%m;
        n>>=1;
    }
    return s;
}
 
unordered_map<int,int> M;
//要求a,n互质 a^x=b mod n .k,t是留给exbsgs调用的
int bsgs(int a,int b,int n,int k=1,int t=0) {
    if(b==1)
        return 0;
    M.clear();
    int m=ceil(sqrt(n));
    ll s=b;//BS
    for(int i=0; i<m; i++,s=s*a%n)
        M[s]=i;
 
    s=k;//GS
    k=qpow(a,m,n);
    for(ll i=1; i<=m; i++) {
        s=s*k%n;
        if(M.count(s))
            return i*m-M[s]+t;  //这样就保证找到的是最小解了
    }
    return -1;
}
 
//a^x=b mod n
int exbsgs(int a,int b,int n) {
    if(b==1) {
        return 0;
    }
    int d=gcd(a,n),k=1,t=0;
    while(d^1) {
        if(b%d) {
            return -1;
        }
        ++t;
        b/=d;
        n/=d;
        k=(ll)k*(a/d)%n;
        if(b==k) {
            return t;
        }
        d=gcd(a,n);
    }
    return bsgs(a,b,n,k,t);
}
 
int main() {
    int a,b,n;
    while(1) {
        scanf("%d%d%d",&a,&n,&b);
        if(!a&&!n&&!b)
            break;
        a%=n;
        b%=n;
        int ans=exbsgs(a,b,n);
        if(ans==-1)
            puts("No Solution");
        else
            printf("%d\n",ans);
    }
    return 0;
}

Pollard Rho算法

原理和RSA里面的那个素数分解的Pollard Rho算法差不多，也是一个概率型的算法，适用于生成元的阶的素因子都是大数的情形

def pollard_rho(g, y, p):
    q = (p-1) // 2
    def new_xab(x, a, b,  g, y, p, q):
        subset = x % 3
        if subset == 0:
            return ((x*x) % p, (a*2) % q, (b*2) % q)
        if subset == 1:
            return ((x*g) % p, (a+1) % q, b        )
        if subset == 2:
            return ((x*y) % p, a        , (b+1) % q)
    x, a, b = 1, 0, 0
    X, A, B = x, a, b
    for i in range(1, p):
        x, a, b = new_xab(x, a, b,  g, y, p, q)
        X, A, B = new_xab(X, A, B,  g, y, p, q)
        X, A, B = new_xab(X, A, B,  g, y, p, q)
        if x == X:
            break
    res = ((a - A) * pow(B - b, -1, q)) % q
    if pow(g, res, p) == y:
        return res
    if pow(g, res + q, p) == y:
        return res + q
    return None

g = 
y = 
p = 
x = pollard_rho(g, y, p)
print(x)
print(pow(g, x, p) == y)

Pollard’s kangaroo algorithm算法

如果我们知道 $x$ 的范围为 $a \leq x \leq b$ 那么我们可以以 $O(\sqrt{b-a})$ 的时间复杂度解决问题

• discrete_log_lambda(a,base,bounds,operation) sage里调用

Pohlig-Hellman算法

只能用于求解光滑阶（即可以因子分解成较小的数的乘积）循环群上的离散对数

对于DLP问题 $a^x \equiv b \pmod{p}$ ，因为 $p$ 是大素数，模 $p$ 的循环群的阶是 $p-1$ ，假设模 $p$ 的最小的本原元是 $g$ ，那么有

$$
a \equiv g^{a’} \pmod{p} \
b \equiv g^{b’} \pmod{p}
$$

就有 $a’x \equiv b’ \pmod{p-1}$ ，如果求出了 $a’$ 和 $b’$ 就可以通过拓展gcd来求出 x ，现在问题就变成了怎么求解

$$
a \equiv g^{a’} \pmod{p} \
b \equiv g^{b’} \pmod{p}
$$

以求解 $a’$ 为例，解DLP问题： $g^x \equiv a \pmod{p}$

将 $p-1$ 分解为素因子 $p-1 = \prod_{i=1}^{m} p_i^{k_i} = p_1^{k_1}p_2^{k_2} \dots p_m^{k_m}$

对于每一个素因子 $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$

令 $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^r}} \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^r}} \pmod{p}
$$

这个式子中只有 $a_0$ 是未知的，因为 $a_o \in [0,p_i-1]$ 所以可以枚举出 $a_0$ 的值

再令 $r = 2,3,4, \cdots ,k_i$ 重复上面的方法，枚举求出 $a_1,a_2,\cdots,a_{k_i-1}$ 可以得到

$$
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}}
$$

对于每一个素因子都有上述过程，最后可以得到 m 个关于 $x$ 的式子，用CRT就可以计算出 $x$ 的值，利用这个方法就可以求出 $a’$ 和 $b’$

# Baby-step Giant-step法
def babystep_giantstep(g, y, p, q=None):
    if q is None:
        q = p - 1
    m = int(q**0.5 + 0.5)
    # Baby step
    table = {}
    gr = 1  # g^r
    for r in range(m):
        table[gr] = r
        gr = (gr * g) % p
    # Giant step
    try:
        gm = pow(g, -m, p)  # gm = g^{-m}
    except:
        return None
    ygqm = y                # ygqm = y * g^{-qm}
    for q in range(m):
        if ygqm in table:
            return q * m + table[ygqm]
        ygqm = (ygqm * gm) % p
    return None

# Pohlig–Hellman法
def pohlig_hellman_DLP(g, y, p):
    crt_moduli = []
    crt_remain = []
    for q, _ in factor(p-1):
        x = babystep_giantstep(pow(g,(p-1)//q,p), pow(y,(p-1)//q,p), p, q)
        if (x is None) or (x <= 1):
            continue
        crt_moduli.append(q)
        crt_remain.append(x)
    x = crt(crt_remain, crt_moduli)
    return x

g = 
y = 
p = 
x = pohlig_hellman_DLP(g, y, p)
print(x)
print(pow(g, x, p) == y)

---

参考:
区块链中的数学-Schnorr 离散对数签名及素数阶群构造（Schnorr 群）
crypto常用算法
离散对数(by Lazzaro)
离散对数(by CTF-Wiki)
算法学习笔记(10): BSGS算法及其扩展算法