Elliptic_Curves_and_ElGamal

3682 days ago by alex

 
       
################################## # # Choose a random 9-bit prime # ################################## b = 9 x = randrange(2^(b-1),2^b) p = next_prime(x); p 
       
####################################################### # # Coefficients for a random elliptic curve over GF(p) # ####################################################### a, b = randrange(p), randrange(p) while (4*a^3 + 27*b^2) % p == 0: a, b = randrange(p), randrange(p) a,b 
       
E = EllipticCurve(GF(p), [a,b]); E 
       
###################################################### # # If the group of E is not cyclic (that is, if it is # isomorphic to a group Z/n x Z/r, go back two cells # and generate new (a,b). # # This script needs the Abelian group of E to be # isomorphic to some Z/n. # ###################################################### E.abelian_group() 
       
E.points? 
       
# Make a list of the points on E and verify that # its length is the order of the group. Epts = E.points() len(Epts) 
       
 
       
########################################################## # # ELGAMAL CRYPTOSYSTEM # # Public Key consists of # E Elliptic Curve # P Point on E of large order # Q Multiple of P by # Secret Key # d Integer 
       
E.gens? 
       
######################################################## # # We chose the parameters a,b to make the # group of E be some Z/n, so it is cyclic. # # This means that there is a point P on the curve so # that every point on the curve is a multiple of P. # ######################################################## P = E.gens()[0]; P 
       
n = P.additive_order(); n 
       
##################### # # THE SECRET KEY # ##################### d = randrange(n); d 
       
Q = d*P; Q 
       
Q in E 
       
 
       
######################################## # # Message # # Puzzle: how to encode message as a # string of points on elliptic curve E? # ######################################## msg = "April is the cruelest month." 
       
# Utility functions. def str2num(s): return ZZ(map(ord,s),256) def num2str(n): nl = n.digits(256) return join(map(chr,nl),'') 
       
############################################### # # Here is the message encoded (not encrypted) # Each character is a byte (8 bits) treated as # a single digit to base 256. # plain = str2num(msg); plain 
       
#################################################################### # # Encoding of message: # # (1) Represent plaintext as a string of digits # to base n (=order of P) # (2) Represent each such digit m by the m-th # point in the list of points of E. # #################################################################### plnd = plain.digits(n); plnd 
       
############################################# # # ElGamal Encryption # ############################################# k = randrange(n) C = [] for i in range(len(plnd)): m = plnd[i] M = E.points()[m] C.append([k*P, M + k*Q]) 
       
C 
       
 
       
#################################### # # Decryption followed by decoding # #################################### Mdec = [] for i in range(len(C)): Mdec.append(C[i][1] - d*C[i][0]) # Look up points in table to get # base-n digits. mdec = [Epts.index(Mdec[i]) for i in range(len(Mdec))] 
       
mdec == plnd 
       
ZZ(mdec,n) == plain 
       
num2str(ZZ(mdec,n))