Baby Step Giant Step.sagews

BABY STEP GIANT STEP ATTACK ON DISCRETE LOG PROBLEM

The BSGS procedure solves the DLP $b=g^x$ where p is the prime number, g is a primitive root of p and b is the public value of the El Gamal public key.

def BSGS(g,b,p):
    N=p-1
    m=floor(sqrt(N))+1
    B=[]
    G=[]
    B.append(1)

    for j in range(1,m):
        B.append(power_mod(g,j,p))

    p2 = power_mod(g,m,p)
    for j in range(0,m-1):
        tempVal = b* power_mod(p2,-j,p) % p
        for i in range(len(B)):
            if(tempVal == B[i]):
                return (i+(m*j)) % (p-1)

    print("ERROR: didn't find private key")
    return -1

Example 1. Let p= 738443, g=23, b=293. Solve the DLP $b=g^x$ using BSGS.

p=738443
b=293
g=23
x=BSGS(g,b,p)
print("The recovered private key is " , x)
print("Using recovered private key we re-comptue the b value" , power_mod(g,x,p), "and compare it to the known value", b)

The recovered private key is 172388 Using recovered private key we re-comptue the b value 293 and compare it to the known value 293

Example 2. Let p= 5623571, g=2, b=2162125. Solve the DLP $b=g^x$ using BSGS.

p = 5623571
g = 2
b = 2162125
x = BSGS(g,b,p)
print("The recovered key is", x)
print("Using recovered private key we re-comptue the b value" , power_mod(g,x,p), "and compare it to the known value", b)

Example 3. Let p= 8989899007, g=17, b=7096854884. Solve the DLP $b=g^x$ using BSGS.

p = 8989899007
g = 17
b = 7096854884
x = BSGS(g,b,p)
print("stdout":"17\n"}