Problem #7: ElGamal Encryption
Here are the parameters for the ElGamal cryptosystem in the problem.
{{{id=1|
p = 2^192-2^64-1; p
///
6277101735386680763835789423207666416083908700390324961279
}}}
{{{id=2|
is_prime(p)
///
True
}}}
{{{id=3|
B = int('64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1',16); B
///
2455155546008943817740293915197451784769108058161191238065L
}}}
{{{id=4|
E = EllipticCurve(GF(p),[-3,B])
///
}}}
{{{id=5|
is_prime(E.count_points())
///
True
}}}
{{{id=6|
x0 = int('188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012',16); x0
///
602046282375688656758213480587526111916698976636884684818L
}}}
{{{id=7|
y0 = int('07192b95ffc8da78631011ed6b24cdd573f977a11e794811',16); y0
///
174050332293622031404857552280219410364023488927386650641L
}}}
{{{id=8|
P = E([x0,y0])
///
}}}
$Q = [a]P$ where $a$ is the secret key:
{{{id=11|
Q = E([3663963113969291544469926280538612298367383514202028986922,1042131040378490833378905612228666552957404825004815884320])
///
}}}
Conversion functions
{{{id=12|
def str_to_int(string):
'''Takes a string consisting of letters and numbers and interprets it as an integer base 36.
The function is case insensitive.
'''
return ZZ(int(string,36))
///
}}}
{{{id=13|
def int_to_str(integer):
'''Takes an integer and returns the base 36 representation.
'''
return integer.str(36)
///
}}}
Testing the functions:
{{{id=14|
str_to_int('homework')
///
1385788861280
}}}
{{{id=15|
int_to_str(314159265358979324)
///
'2dxc5y3uvjzw'
}}}
{{{id=16|
int_to_str(str_to_int('CS259c'))
///
'cs259c'
}}}
Converting between integers and points on $E(\mathbb{F}_p)$.
(a) Write the following function.
{{{id=17|
def int_to_point(n,E):
'''Takes an integer n and encodes it as a unique point on the elliptic curve E.
'''
return E([0,1,0]) # replace this with the point you compute
///
}}}
(b) Write the following function.
{{{id=18|
def point_to_int(P):
'''Takes a point P on an elliptic curve and encodes it as an integer.
'''
return 0 # replace this with the integer you compute
///
}}}
Here's a procedure to test whether the functions behave appropriately. Note that the procedure takes functions as arguments.
{{{id=19|
def test_inverses(f,g,E,n):
'''Tests whether the functions f and g are inverses of each other on n random inputs.
f takes as input an integer t and an elliptic curve E.
g takes as input the output of f.
'''
for i in range(n):
t = randint(0,36^25)
if g(f(t,E)) != t:
return False
return True
///
}}}
We define a squaring function $f$ and a square root function $g$. (For more on lambda forms, see Python documentation.)
Here $f$ and $g$ are inverses because test_inverses only gives positive inputs to $f$, and the sqrt function always returns the positive square root.
{{{id=26|
f = lambda x,E : x^2 # E does nothing here
g = lambda y : sqrt(y)
test_inverses(f,g,E,1000)
///
True
}}}
Over a finite field, sqrt(x^2) may not be equal to $x$.
{{{id=27|
f = lambda x,E : GF(123457)(x)^2
test_inverses(f,g,E,1000)
///
False
}}}
Use test_inverses to test your functions above.
{{{id=34|
test_inverses(int_to_point,point_to_int,E,1000)
///
}}}
(c) Write an ElGamal encryption function.
{{{id=20|
def encrypt(P,Q,s):
'''Compute the ElGamal encryption of the string s using the public key (P,Q).'''
///
}}}
(d) Use this function to encrypt your name (or the first 25 characters thereof).
{{{id=25|
///
}}}