DLP
from Crypto.Util.number import *
from sage.all import *
def gen_weak_prime(size, smooth):
"""
generate approximately size-bit prime p
which p-1 factorized to p_1 * p_2 * ... * p_n and p_n is up to smooth-bit
(it means that p-1 is <smooth>-smooth number)
"""
p = 2
while True:
if p.bit_length() + smooth >= size:
p *= getPrime(size - p.bit_length())
if isPrime(p + 1):
return p +1
p = 2
else:
p *= getPrime(smooth + 1)
# generate params
p = gen_weak_prime(512, 512-32)
print("[+] p: {}".format(p))
factors = [f[0]**f[1] for f in factor(p-1)]
assert len(factors) == 3
g = getRandomRange(2, p)
g = Mod(g, p) ** (2*factors[2])
x = getRandomRange(2, p) # this is secret
h = g ** x
print("[+] secret: {}".format(x))
dlog = discrete_log(h, g)
print("[+] discrete-log: {}".format(dlog))
print("[+] check1: {}".format(g ** dlog))
print("[+] check2: {}".format(h))
