离散对数

学习参考：
1、harry0597师傅
2、lazzaro

在整数中，离散对数（DL）是一种基于同余运算和原根的一种对数运算

在任何群G中可为所有整数k定义一个幂数为$b^k$,而离散对数$log_{b^{a}}$使得$b^k=a$的整数k。

离散对数在一些特殊情况下可以快速计算，公钥密码学中几个重要算法的基础，是假设寻找离散对数的问题解，在仔细选择过的群中，并不存在有效率的求解算法。

基本定义

生成元

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

阶

设 𝑚≥1,gcd(𝑎,𝑚)=1，使得 𝑎^𝑑≡1(mod𝑚) 成立的最小正整数 𝑑 称为 𝑎 对模 𝑚 的指数或者阶。一为𝛿_𝑚(𝑎)。满足 𝑎^𝑑≡1(mod𝑚) 的 𝑑 一定满足 𝑑∣𝜑(𝑚)。

原根

当𝛿_𝑚(𝑎)=𝜑（𝑚）时，称a是模m的原根，简称m的原根

常规sage函数

参数：

  • 求解以base为底
  • a的对数
  • ord为base的阶，可忽略
  • operation可以是+或者*，默认*
  • bounds是一个区间(ld,ud),需要保证所计算的对数在此区间内

函数使用：

-

  • discrete_log(a,base,ord,operation)

    通用的求离散对数的方法。（Pohlig-Hellman+?BSGS）

    没有bounds

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

    • 要求中 g必须是原根 （对于 g 不是原根的情况，需要利用原根将原方程转化成两个关于原根的离散对数问题。
    • 要求阶是光滑的（p-1可拆为多个素数相乘）

  • discrete_log_rho(a,base,ord,operation)

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

    • 主要解决循环群上的离散对数问题
    • Pollard Rho算法主要利用循环群的生成序列呈现一个 ρ子形状
    • 适用于生成元的阶的素因子都是大数的情形

    Pollard Rho算法是一种随机性的概率型算法

    理论基础是生日悖论：

    在 $n$ 个元素的集合中随机选取元素，期望只需 $O(\sqrt{n})$ 次就能选到两个相同的元素（碰撞）。

    ρ子形状由来：

    算法生成的序列 $x_0, x_1, x_2, \dots$ 在有限群中必然会进入一个循环，画出轨迹后形状像希腊字母 ρ（一条尾巴 + 一个环）

    算法流程

    目标求解$g^x\equiv h \pmod p$中的x

    1. 划分群元素将群G分成三个大小相近的子集S0,S1,S2（通常按mod3划分）

    2. 定义迭代函数

      • 构造序列（$a_i,b_i,x_i$）其中$x_i=g^{a_i}\cdot h^{b_i}$

        因为 $h = g^x$，代入得：

        $$ x_i = g^{a_i} \cdot (g^x)^{b_i} = g^{a_i + x \cdot b_i} $$

        关键来了——这里 $x$ 和 $a_i, b_i$ 的关系是线性的：$a_i + x \cdot b_i$。

        这样当碰撞发生时 $x_i = x_j$，我们得到：

        $$ g^{a_i + x \cdot b_i} = g^{a_j + x \cdot b_j} \quad\Longrightarrow\quad a_i + x \cdot b_i \equiv a_j + x \cdot b_j \pmod{n} $$

        移项就是一个一元一次方程：

        $$ x \cdot (b_i - b_j) \equiv a_j - a_i \pmod{n} $$

        $$ x \equiv \frac{a_j - a_i}{b_i - b_j} \pmod{n} $$

    3. 使用Floyd找碰撞

      维护两个指针

      • 乌龟：每次一步
      • 兔子：每次两步

      当乌龟兔子相遇（$x_{slow}=x_{fast}$）找到

    4. 解出离散对数

      将 $h = g^x$ 代入上式：

      $$ g^{a_{\text{slow}}} \cdot g^{x \cdot b_{\text{slow}}} \equiv g^{a_{\text{fast}}} \cdot g^{x \cdot b_{\text{fast}}} \pmod{p} $$

      $$ g^{a_{\text{slow}} + x \cdot b_{\text{slow}}} \equiv g^{a_{\text{fast}} + x \cdot b_{\text{fast}}} \pmod{p} $$

      因此指数相等（模 $n$，$n$ 为 $g$ 的阶）：

      $$ a_{\text{slow}} + x \cdot b_{\text{slow}} \equiv a_{\text{fast}} + x \cdot b_{\text{fast}} \pmod{n} $$

      $$ x \cdot (b_{\text{slow}} - b_{\text{fast}}) \equiv a_{\text{fast}} - a_{\text{slow}} \pmod{n} $$

      令 $\Delta b = b_{\text{slow}} - b_{\text{fast}}$，$\Delta a = a_{\text{fast}} - a_{\text{slow}}$：

      $$ x \cdot \Delta b \equiv \Delta a \pmod{n} $$

      这是一个线性同余方程。当 $\gcd(\Delta b, n) = 1$ 时，直接求逆元即可：

      $$ x \equiv \Delta a \cdot (\Delta b)^{-1} \pmod{n} $$

      若 $\gcd(\Delta b, n) = d > 1$，则有 $d$ 个候选解，逐一检验即可

  • discrete_log_lambda(a,base,bounds,operation)

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

    • 适用于题目给出bounds

  • bsgs(base,a,bounds,operation)

    大步小步法。

    1
    from sage.groups.genertic import bsgs
    • 用于解高次同余方程问题
    • 适用于模p为质数的情况
    • 适用于题目给出bound

    原理介绍

Elgamal密钥生成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#生成64位的素数p作为模数，int 32位
p=random_prime(2L**64)

#定义有限域GF(p)，伽瓦罗域
G=GF(p) 

#找到一个模p的原根
gp('znprimroot('+str(p)+')')

#输出Mod(rt,p),x是模p原根
g=G(rt)
#生成私钥[0,p-1]
x=G(ZZ.random_element(p-1))

#公钥y=g^x mod p,由于已经定义在GF(p)上所以g**x就是g^x mod p
y=g**x
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
g^x≡y(mod p)
#破解即可还原私钥


#通用方法
discrete_log(y,g)==x
#n为合数（Pohlig-Hellman）
x=discrete_log(mod(b,n),mod(a,n))
#n为质数(线性筛Index Caculus)
R=Integers(99)
a=R(4)
b=a^9
b.log(a)
#或者
x=int(pari(f"znlog({int(b),Mod({int(a)},{int(n)}}))"))
x=gp.znlog(b,gp.Mod(a,n))

#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

#GF(p)下计算DLP
F=GF(p)
ax=F(b+(a-1)*A)/F(a*s-s+b)
x=discrete_log(F(ax),F(a))

大步小步算法（BSGS）

解决高次同余方程的问题

为什么不直接暴力解$g^x\equiv y\pmod p$ ？(x的范围为0-p-2)暴力枚举需要O(p)

example:

同余方程$a^x\equiv b \pmod p$，p为质数，求解最小非负整数解x使得原方程成立离散对数问题

复杂度较低

原理

求解$g^x \equiv y \pmod p$

拆分x

x = q·m + r

设 $m = \lceil \sqrt{p-1} \rceil$，把 $x$ 写成带余除法的形式：

$$ x = \mathbf{q} \cdot m + \mathbf{r}, \quad 0 \le r < m $$

代入原方程：

$$ g^{qm + r} \equiv y \pmod{p} $$

移项（把含 $r$ 的放一边，含 $q$ 的放另一边）：

$$ g^r \equiv y \cdot g^{-qm} \pmod{p} $$

费马小定理：g^(p-1) ≡ 1 (mod p) 模p乘法群的阶为p-1

变量 取值范围 可能取值数量
左边 $g^r$ $r$ $0 \sim m-1$ $m$ 个
右边 $y \cdot g^{-qm}$ $q$ $0 \sim m-1$ $m$ 个

总共只有 $2m \approx 2\sqrt{p}$ 种可能，而不是原来的 $p$ 种。

Baby Step：枚举左边，建表

“小步”——每次指数只加 1，走得很慢：

$$ \begin{aligned} r=0&: \quad g^0 = 1 \ r=1&: \quad g^1 = g \ r=2&: \quad g^2 = g \cdot g \ &\vdots \end{aligned} $$

把每个 $g^r \to r$ 存入哈希表（用值查指数

Giant Step：枚举右边，查表

“大步”——每次乘 $g^{-m}$，相当于指数一步跨 $m$：

$$ \begin{aligned} q=0&: \quad y \cdot g^{0} = y \ q=1&: \quad y \cdot g^{-m} = y \cdot g^{-m} \ q=2&: \quad y \cdot g^{-2m} = y \cdot g^{-m} \cdot g^{-m} \ &\vdots \end{aligned} $$

每步算出一个值，就去哈希表里查：这个值出现过吗？对应的 $r$ 是多少？

一旦命中，直接拼出答案：

$$ x = q \cdot m + r $$

时空复杂度

暴力 BSGS
时间 $O(p)$ $O(\sqrt{p})$
空间 $O(1)$ $O(\sqrt{p})$（存哈希表）

脚本

1
2
#sage
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
26
def babystep_giantstep(g,y,p):
    #init m
    m=int((p-1)**0.5+0.5)
    #Baby step(建表)
    table={}
    gr=1    #g^0=1
    for r in range(m):
        table[gr]=r  #{g^r:r}
        gr=(gr*g)%p
    #Giant step(查表)
    #g^m · g^(p-1-m) = g^(p-1) ≡ 1 (mod p)
    #即模拟元g^(-m) ≡ g^(p-1-m) (mod p)
    gm=pow(g,-m,p)   
    ygqm=y  #初始值y*g^0=y
    for q in range(m):
        if ygqm in table:
            return q*m+table[ygqm]
        ygqm=(ygqm*gm)%p  #一步m，q加1
    return None

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