Baby-Step Giant-Step Algorithm

1. Discrete Logarithm problem:

目的：求x的值，也就是generator相乘的次数。在prime很大的时候求解困难，因为brute-force的时间复杂度是O(prime)

应用：在DH key exchange中，中间人如果需要从已知条件阿尔法(generator), A(public key), p(prime)破解获得两方的密钥a,b，就需要解决DLP问题。

2. Baby-Step Giant-Step Algorithm

是一种利用空间来有效减少DLP时间复杂度的计算，时间复杂度为O(m * log(m)), m = ceil(sqrt(p))，空间复杂度为O(sqrt(p))。由于时间复杂度是sqrt级别的下降，为了保证安全性prime的bits一定要长

思路：分解x = mq + r, m = sqrt(p), 使用hashtable减少重复计算。也就是已知target, g，计算g^r ≡ target * g^(-mq) (mod p)(然后所有计算出来的数字都要mod p)。其中r为baby step ,q为giant step，原因是b是逐一递增，q在hashtable中是m倍递增（是这样解释的8？）

• 计算m = sqrt(p)
• babystep: for r in range(m),在hashtable中记录{g^r mod p : r}，注意可以使用之前已经计算过的值
• 计算gm = g^(-m)，根据模反定义，也就是计算g^(m)的模反元素。使用pow和egcd计算inverse
• giantstep: for q in range(m), 计算index = gm^q mod p，并在hashtable中查找是否有对应的key，如果有直接返回x = mq + r，如果没有，在前一步计算的基础上再乘以一个gm，和babystep中复用一个思路。

代码大概是这样的8，不知道可不可以用位运算代替模运算，但是查了一下只有这个规律:当%和&互换：a % 2^n = a & (2^n - 1)，然而p是prime

import math
import time

# find the inverse of a in GF(p) with xGCD. gf_inv(31, 3**6) = 2
def gf_inv(p, a):
    r1 = p
    r2 = a
    c1 = 0
    c2 = 1

    while r1 > 1:
        q = r1 // r2
        r = r1 % r2
        c = c1 - c2 * q
        r1 = r2
        c1 = c2
        r2 = r
        c2 = c
    return c1 % p


# compute a * b in GF(p)
def gf_mul(p, a, b):
    return a * b % p


# compute a ** b in GF(p)
def gf_pow(p, a, b):
    if b == 0:
        return 1
    if b == 1:
        return a % p
    v = gf_pow(p, a, b // 2)
    if b % 2 == 0:
        return v * v % p
    else:
        return v * v * a % p


# compute a + b in GF(p)
def gf_add(p, a, b):
    return (a + b) % p


# The basic idea of this algorithm is to check if target * g ^(-mq) == g^r, return x = (r + mq)
def bsgs(p, gen, target):
    # 1. compute m
    m = math.ceil(math.sqrt(p))

    # 2. compute g^r
    # create a dictionary list_gr to store the index {gr:r}
    gr_list = {}
    gr = 1
    for r in range(m):
        gr_list[gr] = r
        gr = gen * gr % p  # reuse previous result of gr, or gf_mul(p, gen, gr)

    # 3. compute g^(-m) which is the inverse of g^m
    gm_inv = gf_inv(p, gf_pow(p, gen, m))

    # 4. compute hgmq: target * (g^-m)^q
    hgmq = target
    for q in range(m):
        if hgmq in gr_list:
            return q * m + gr_list[hgmq]
        else:
            hgmq = hgmq * gm_inv % p  # reuse precomputed hgmq, or hgmq = gf_mul(p, hgmq, gm)
    return "No result"


def brute_force(p, gen, target):
    x = 1
    product = gen
    while product != target:
        x += 1
        product = gf_mul(p, product, gen)
    return x


def measure_time(func, *args):
    p, gen, target = args
    start = time.time()
    x = func(p, gen, target)
    time_elapsed = time.time() - start
    print("secret key: {}, runtime: {:<15f}".format(x, time_elapsed))


def main():
    p_list = [31, 7919, 688889, 51539607551, 108086391056891903]
    gen_list = [3, 7, 13, 19, 19]
    target_list = [6, 854, 490760, 43511947506, 18733402164927303]

    print("Brute force algorithm:")
    for i in range(5):
        if i > 2:
            print("secret key: N/A, runtime: N/A")
        else:
            measure_time(brute_force, p_list[i], gen_list[i], target_list[i])

    print("Baby-Step Giant-Step algorithm:")
    for i in range(5):
        measure_time(bsgs, p_list[i], gen_list[i], target_list[i])


if __name__ == '__main__':
    main()

# example output
# Brute force algorithm:
# secret key: 25, runtime: 0.000020
# secret key: 234, runtime: 0.000169
# secret key: 676545, runtime: 0.308789
# secret key: N/A, runtime: N/A
# secret key: N/A, runtime: N/A
# Baby-Step Giant-Step algorithm:
# secret key: 25, runtime: 0.000035
# secret key: 234, runtime: 0.000049
# secret key: 676545, runtime: 0.000525
# secret key: 584050353, runtime: 0.124305
# secret key: 947234702, runtime: 677.787557

# Brute force algorithm:
# secret key: 25, runtime: 0.000017
# secret key: 234, runtime: 0.000138
# secret key: 676545, runtime: 0.292695
# secret key: N/A, runtime: N/A
# secret key: N/A, runtime: N/A
# Baby-Step Giant-Step algorithm:
# secret key: 25, runtime: 0.000063
# secret key: 234, runtime: 0.000060
# secret key: 676545, runtime: 0.000528
# secret key: 584050353, runtime: 0.126814
# secret key: 947234702, runtime: 687.591964

# check complexity
# https://cp-algorithms.com/algebra/discrete-log.html
# egcd.

3. Some small functions

• python计算bit length，可以用来计算prime的二进制长度，从而判断基本的时间复杂度

>>> a = 108086391056891903
>>> a.bit_length()
57
>>> len(bin(108086391056891903)[2:])
57

• 计算a的modular multiplicative inverse时，当p是质数时，根据fermat's little theorem的公式a^(p - 1) ≡ 1 (mod p)，在python中可以使用pow(a, p - 2, p)，在本例中为(3^6)^29 * (3^6) ≡ 1 (mod 31)得到pow(3**6, 29, 31)，因为(3^6)^29是3^6的inverse

其他

写位运算还是比较难，很难理解

inverse和egcd的理解