DL 离散对数 ¶

https://ctf-wiki.org/crypto/asymmetric/discrete-log/discrete-log/#_2

DLP 指的是离散对数问题（Discrete Logarithm Problem）。它是一个数学问题，描述了在给定的群体中，找到一个整数 k，使得 $b^k≡a\pmod p$ 成立，其中 b 是群体中的一个生成元，a 是群体中的另一个元素，p 是一个素数。

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

即：$base^k≡a\pmod p$

In [26]:

Copied!





p = 17
F = GF(p)
g = F.multiplicative_generator()
print("g:", g)
c = 13
# g^x = c mod p
discrete_log(c, g), discrete_log(mod(c,p), mod(g,p)), 3^4%17
p = 17
F = GF(p)
g = F.multiplicative_generator()
print("g:", g)
c = 13
# g^x = c mod p
discrete_log(c, g), discrete_log(mod(c,p), mod(g,p)), 3^4%17

g: 3

Out[26]:

(4, 4, 13)

k = discrete_log(a,base,ord,operation) or k = discrete_log(mod(a, p), mod(base, p)) or y = Zmod(p)(a); k = y.log(base,p)
- 通用的求离散对数的方法。
discrete_log_rho(a,base,ord,operation)
- 求离散对数的 Pollard-Rho 算法。
discrete_log_lambda(a,base,bounds,operation)
- 求离散对数的 Pollard-kangaroo 算法（也称为 lambda 算法）。
bsgs(base,a,bounds,operation)
- 小步大步法。

practice

In [20]:

Copied!





p = 7
F = GF(p)
a = 4
g = F.multiplicative_generator()
# 求解 g^x = a mod p
x = discrete_log(a, g)
discrete_log(mod(a, p), mod(g, p)), discrete_log(a, g), a.log(g)
p = 7
F = GF(p)
a = 4
g = F.multiplicative_generator()
# 求解 g^x = a mod p
x = discrete_log(a, g)
discrete_log(mod(a, p), mod(g, p)), discrete_log(a, g), a.log(g)

Out[20]:

(4, 4, 2*log(2)/log(3))

In [40]:

Copied!

n = 2*2*3*5*7*31*41
factors , exps = zip(*factor(n))
factor(n), factors, exps
n = 2*2*3*5*7*31*41
factors , exps = zip(*factor(n))
factor(n), factors, exps

Out[40]:

(2^2 * 3 * 5 * 7 * 31 * 41, (2, 3, 5, 7, 31, 41), (2, 1, 1, 1, 1, 1))

Pohlig_Hellman¶

如果群的阶数（即群元素个数）可被因式分解（称为光滑的），则可使用 Pohlig-Hellman 算法求解，其复杂度被降到了最大的那个因数上；由于最后使用中国剩余定理求解离散对数问题，在部分情况下，可以舍弃最后一两个极大的数，尝试缩短攻击时间。

In [ ]:

Copied!





def Pohlig_Hellman_DLP(g, a, p):
    # Get the order of multiplicative group
    order = p - 1
    # Factor the order
    factors, exponents = zip(*factor(order))
    # Calculate prime powers
    primes = [factors[i] ^ exponents[i] for i in range(len(factors))]
    dlogs = []
    
    print(f"Group order: {order}")
    print(f"Prime factors: {factors}")
    print(f"Prime powers: {primes}")
    
    for fac in primes:
        # Calculate t = order/fac
        t = int(order // fac)
        # Calculate subgroup elements
        gt = power_mod(g, t, p)
        at = power_mod(a, t, p)
        # Solve DLP in subgroup
        dlog = discrete_log(at, gt, p)
        dlogs.append(dlog)
        print(f"factor: {fac}, Discrete Log: {dlog}")
    
    # Use Chinese Remainder Theorem to get final result
    return crt(dlogs, primes)
def Pohlig_Hellman_DLP(g, a, p):
    # Get the order of multiplicative group
    order = p - 1
    # Factor the order
    factors, exponents = zip(*factor(order))
    # Calculate prime powers
    primes = [factors[i] ^ exponents[i] for i in range(len(factors))]
    dlogs = []
    
    print(f"Group order: {order}")
    print(f"Prime factors: {factors}")
    print(f"Prime powers: {primes}")
    
    for fac in primes:
        # Calculate t = order/fac
        t = int(order // fac)
        # Calculate subgroup elements
        gt = power_mod(g, t, p)
        at = power_mod(a, t, p)
        # Solve DLP in subgroup
        dlog = discrete_log(at, gt, p)
        dlogs.append(dlog)
        print(f"factor: {fac}, Discrete Log: {dlog}")
    
    # Use Chinese Remainder Theorem to get final result
    return crt(dlogs, primes)