Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
Avatar for Foundations of Public Key Cryptography.
 Download
1852 views
ubuntu2004
Tweet
Share
Share

BABY STEP GIANT STEP ATTACK ON DISCRETE LOG PROBLEM

The BSGS procedure solves the DLP b=gxb=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=gxb=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=gxb=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=gxb=g^x using BSGS.

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