离散对数

在整数中，离散对数（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)

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

  • discrete_log_rho(a,base,ord,operation)

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

  • discrete_log_lambda(a,base,bounds,operation)

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

  • bsgs(base,a,bounds,operation)

    小步大步法。

Elgamal密钥生成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#生成64位的素数p作为模数，int 32位
p=random_prime(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

求解DLP

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）

解决高次同余方程的问题

example:同余方程a^x≡b (mod p)，p为质数，求解最小非负整数解x使得原方程成立离散对数问题

复杂度较低

原理

求解g^x ≡ y (mod p)

拆分x

x = q·m + r

（m = ⌈√(p-1)⌉为什么呢？根据费马小定理x的范围要在0p-2之间，但因为q，r的范围都是0m-1所以m*m>=p-1）

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

所以将方程变为

g^(q·m + r) ≡ y (mod p)
↓
g^r ≡ y · g^(-q·m) (mod p)

左边与r相关，右边与q相关。分别枚举再来碰撞得到结果

脚本

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)