# Exercise 1
# Input k: an integer
# Output: (p,q,g) with a k bits prime q, p-1=2q, p prime and g an element modulo p of order q
def gen(k):
r = 2^(k-1) + ZZ.random_element(2^(k-1))
q = next_prime(r)
p = 2*q+1
while not is_prime(p):
r = 2^(k-1) + ZZ.random_element(2^(k-1))
q = next_prime(r)
p = 2*q+1
'''g of order q: elements of (Z/pZ)* are of order 1,2,q or p-1=2q
Let c in (Z/pZ)^*, we can have c^2 = 1 (the order of c divides 2) so c=1 or -1, or g=c^2 has order q as g^q = c^(2q) = c^(p-1) = 1
With c=2, we have g=4. If p=2*2+1=5, q=2, and g=4=-1 has order q. If p>5, 4 is not 1 or -1, and is of order q '''
g = Integers(p)(4)
return p,q,g
k = 20
p,q,g = gen(k)
print "\nExercise 1\n"
print "k =",k
print "p =",p," prime: ",is_prime(p)
print "q =",q," prime: ",is_prime(q), " of ",len(q.binary())," bits"
# multiplicative_order : order of an element, be cautious on the size of p : this method must factor p-1 (relatively easy in this case as p-1=2q)
print "g = ",g," of order q : ",g.multiplicative_order() == q
# Exercise 2
# Input (p,q,g) returned by gen and h in the group generated by g
# Output: the Discrete logarithm of h in basis g
def naive(p,q,g,h):
f = Integers(p)(1)
x = 0
while h!=f:
x = x+1
f = f*g
return x
print "\nExercise 2\n"
x = ZZ.random_element(q)
print "We look for x = ",x
h = g^x
print "With the naive method, we find ",naive(p,q,g,h)
print "With the .log method of Sage, we find ",h.log(g)
# Exercise 5
# Baby Step Giant Step
# Input (p,q,g) returned by gen and h in the group generated by g
# Output: the Discrete logarithm of h in basis g
def Shanks(p,q,g,h):
m = ceil(sqrt(q))
gm = g^m
# Giant steps L = [g^(mi),i]
L = {} # dictionary
aux = 1
for i in range(1,m):
aux = aux * gm # gm^i
L[aux]=i
# Baby steps
ginv = g^(-1)
f = h
i = 0
while not L.has_key(f):
f = f * ginv
i = i +1
return i+L[f]*m
print "\nExercise 5\n"
xx = Shanks(p,q,g,h)
print "With BSGS, we find ",xx
k = 30
p,q,g = gen(k)
print "\nWith q of ",k," bits"
x = ZZ.random_element(q)
print "We look for x = ",x
h = g^x
xx = Shanks(p,q,g,h)
print "With BSGS, we find ",xx
# Exercise 11
# Iterating function for Pollard rho
# Input: X,i,j,g,h,q, with X,g,h in the group generated by g of order q, and X=g^ih^j
# Output: f(X),ii,jj s.t f(X)=g^iih^jj
def iteration(X,i,j,g,h,q):
val=ZZ(X)
if val%3 == 0:
return X^2,(2*i)%q,(2*j)%q
if val%3 == 1:
return X*h,i,(j+1)%q
if val%3 == 2:
return X*g,(i+1)%q,j%q
# Pollard rho
# Input (p,q,g) returned by gen and h in the group generated by g
# Output: the Discrete logarithm of h in basis g
def Pollard(p,q,g,h):
ix = ZZ.random_element(q)
jx = ZZ.random_element(q)
X = g^ix*h^jx
X,ix,jx = iteration(X,ix,jx,g,h,q)
Y,iy,jy = iteration(X,ix,jx,g,h,q)
while X!=Y: # One could bound the number of iterations
X,ix,jx = iteration(X,ix,jx,g,h,q)
Y,iy,jy = iteration(Y,iy,jy,g,h,q)
Y,iy,jy = iteration(Y,iy,jy,g,h,q)
if gcd(jy-jx,q)!=1:
return(-1) # Failure
return (ix-iy)/(jy-jx)%q
print("\nExercise 11\n")
xxx = Pollard(p,q,g,h)
print "With Pollard, we find ",xxx
k = 40
p,q,g = gen(k)
print "\nWith q of ",k," bits"
x = ZZ.random_element(q)
print "We look for ",x
h = g^x
#xx = Pollard(p,q,g,h)
print "With Pollard, we find ",xx
# Exercise 12
# Input: kp and kq, two integers
# Output: p,E,q,g where p is a random kp bits prime, E a random elliptic curve over F_p, g is a point of E(F_p) of order q with q a kq bits prime
def gen_ec(kp,kq):
r = 2^(kp-1) + ZZ.random_element(2^(kp-1))
p = next_prime(r) # p a random kp bits prime
print "\np =",p
notGood = 1
Fp = GF(p)
c = 0
while notGood:
a = Fp.random_element()
b = Fp.random_element()
c = c +1;
if 4*a^3+27*b^2!=0:
E = EllipticCurve([a,b])
print "\niteration",c
print E
n = E.cardinality()
print "Number of points :",n
M = factor(n) # inefficient for large parameters !
q = M[-1][0] # largest prime factor
lq = len(q.binary())
print "Largest prime factor of the order found: ",q
print "Size",lq," bits"
if lq >= kq:
notGood = 0
print E.abelian_group() # E(F_p) generated by P1,P2 isomorphic to Z/n1Z ⊕ Z/n2Z with n2 dividing n1 and p − 1. In general n2 small so E is almost cyclic and q divides n1.
P1 = (E.abelian_group().gens()[0]).element() # element() to cast v[0] has an element of E and not of an abstract abelian_group
l = ZZ(P1.order()/q) # n1/q
P = l*P1 # (n1/q).P1 // of order q
return p,E,q,P
print("\nExercise 12\n")
kp = 34
kq = 30
print "We look for an elliptic curve over Fp, with p of size ", kp," bits with a prime order subgroup of size at least ", kq, " bits\n"
p,E,q,P = gen_ec(kp,kq)
print "\n\np =",p, " of", len(p.binary())," bits"
print "E:",E
print "number of points:",E.cardinality()
print "Subgroup of order q =", q," of ",len(q.binary())," bits"
print "cofactor : ", E.cardinality()/q
print "order of P correct :", P.order() == q
# iteration function of Pollard Rho. Similar to the one above. Changes: branches are decided with respect to the value mod 3 of the x-coordinate of the point ; we also use the addive notation to compute in the group
def iteration(X,i,j,g,h,q):
val=ZZ(X.xy()[0]) # .xy() to get affine coordinates
if val%3 == 0:
return 2*X,(2*i)%q,(2*j)%q
if val%3 == 1:
return X+h,i,(j+1)%q
if val%3 == 2:
return X+g,(i+1)%q,j%q
# main function of Pollard Rho. Similar to the one above, with additive notation
def Pollard(p,q,g,h):
ix = ZZ.random_element(q)
jx = ZZ.random_element(q)
X = ix*g + jx*h
X,ix,jx = iteration(X,ix,jx,g,h,q)
Y,iy,jy = iteration(X,ix,jx,g,h,q)
while X!=Y: # One could bound the number of iterations
X,ix,jx = iteration(X,ix,jx,g,h,q)
Y,iy,jy = iteration(Y,iy,jy,g,h,q)
Y,iy,jy = iteration(Y,iy,jy,g,h,q)
if gcd(jy-jx,q)!=1:
return(-1) # Failure
return (ix-iy)/(jy-jx)%q
x = ZZ.random_element(q)
print "We look for ",x
Q = x*P
xx = Pollard(p,q,P,Q)
print "With Pollard, we find ",xx
print ".discrete_log method of Sage, we find ", P.discrete_log(Q)