# ECDH implementation in python (part 2)

I worked a while on my code I posted here to make it more flexible and hopefully a little bit more secure. My goal is to implement a secure library for elliptic curve cryptography.

# coding: utf-8

MERSENNE_EXPONENTS = [
2, 3, 5, 7, 13, 17, 19, 31, 61, 89,
107, 127, 521, 607, 1279, 2203, 2281,
3217, 4253, 4423
]

def ext_euclidean(a, b):

t = u = 1
s = v = 0
while b:
a, (q, b) = b, divmod(a, b)
u, s = s, u - q*s
v, t = t, v - q*t
return a, u, v

def legendre(x, p)

return pow(x, p >> 1, p)

def W(n, r, x, m):

if n == 1:
inv = ext_euclidean(x, m)[1]
return (r*r*inv - 2) % m
if n & 1:
w0 = W(n >> 1, r, x, m)
w1 = W((n+1) >> 1, r, x, m)
return (w0*w1 - W(1, r, x, m)) % m
return (W(n >> 1, r, x, m)**2 - 2) % m

class Point:

def __init__(self, x, y):

self.x = x
self.y = y

def __str__(self):

return '(' + str(self.x) + ', ' + str(self.y) + ')'

def __eq__(self, p):

if type(p) != type(self):
return False
return self.x == p.x and self.y == p.y

class EllipticCurve:
"""Provides functions for
calculations on finite elliptic
curves.
"""
def __init__(self, a, b, m, warning=True):
"""Constructs the curve.
a and b are parameters of the
short Weierstraß equation:
y^2 = x^3 + ax + b

m is the order of the finite field,
so the actual equation is
y^2 = x^3 + ax + b (mod m)
"""
self.a = a
self.b = b
self.m = m
if warning:
if m & 3 == 3 and b == 0:
raise Warning
if m % 6 == 5 and a == 0:
raise Warning

def mod_sqrt(self, v):

l = legendre(v, self.m)
if l == (-1) % self.m:
return None
if l == 0:
return 0
if l == 1:
if self.m & 3 == 1:
r = 0
while legendre(r*r - 4*v, self.m) != (-1) % self.m:
r += 1
w1 = W(self.m >> 2, r, v, self.m)
w3 = W((self.m+3) >> 2, r, v, self.m)
inv_r = ext_euclidean(r, self.m)[1]
inv_2 = (self.m+1) >> 1
return (v * (w1+w3) * inv_2 * inv_r) % self.m
if self.m & 3 == 3:
return pow(v, (self.m+1) >> 2, self.m)
raise ValueError
raise ValueError

def generate(self, x):
"""
Generate Point with given x coordinate
"""
x %= self.m
v = (x**3 + self.a*x + self.b) % self.m
y = self.mod_sqrt(v)
if y is None:
return None
return Point(x, y)

"""
None is the neutral element.
"""
if p is None:
return q
if q is None:
return p
numerator = (q.y - p.y) % self.m
denominator = (q.x - p.x) % self.m
if denominator == 0:
if p == q:
if p.y == 0:
return None
inv = ext_euclidean(2 * p.y, self.m)[1]
slope = inv * (3*p.x**2 + self.a) % self.m
else:
return None  # p == -q
else:
inv = ext_euclidean(denominator, self.m)[1]
slope = inv * numerator % self.m
xr = (slope**2 - (p.x + q.x)) % self.m
yr = (slope * (p.x - xr) - p.y) % self.m
return Point(xr, yr)

def mul(self, p, n):
"""binary multiplication.
"""
if p is None:
return None
if n < 0:
p = Point(p.x, self.m - p.y)
n = -n
r = None
for b in bin(n)[2:]:
if b == '1':
return r

class MersenneCurve(EllipticCurve):
"""Elliptic Curve where the
curve order is a Mersenne prime.
"""
def __init__(self, a, b, p, warning=True):

if p not in MERSENNE_EXPONENTS:
raise ValueError
if b == 0 and warning:
raise Warning
self.a = a
self.b = b
self.p = p  # prime exponent
self.m = ~((~0) << p)


Notes:

• the algorithms for ext_euclidean(a, b) and W(n, r, x, m) are derived from the descriptions on the german Wikipedia, I didn't find these algorithms I use on the english one, just don't be confused about it.
• you should never use b = 0 for a MersenneCurve. In this case, it needs 2 * p multiplications on the curve to break the encryption. I'll post my code for this attack another time.
• the function is_generator of the first post only works on a MersenneCurve with b = 0, the same issue that made the function work leads to the attack mentioned above.

I'd like to re-iterate one of Ashwini Chaudhary's points, from your previous post:

Use better meaningful variable names than u, v, t, m etc.

Your code is incredibly hard to read. WTF does p mean? One second it's a "# prime exponent", the next it's a "Point(p.x, self.m - p.y)".

Your reason to not write self documenting code, and to not even put comments in your code, comes down to 'Wikipedia didn't', and it might confuse someone:

to the variable names: I used u, v, s and t because this letters are also used in the wikipedia description of the extended euclidean algorithm. m could be named module or similar but I don't want to get confused with modules you can import. Good answer though, thanks!

First, the Wikipedia article is written for mathematicians. And so uses single letter variables to adhere to standards in mathematics. These are not the same standards in computer science. And since you're writing code, you should adhere to computing standards, not standards for mathematics.

As to not wanting to name it module, because someone may think it's something you import is ridiculous. Currently your variables can mean any and every word. m, for example, could mean 'module', 'math', 'mean', 'mountain', 'motorbike', which is far more confusing.

• "motorbike" +1 for that only ;) – Ludisposed Oct 24 '17 at 10:20
• basicly you're right, code variables should have self-explaining names. OTOH, did you even try to find better names for numbers of mathematic formulas? It's just extremely hard, the best name I found for one is slope. I already try to name my variables after what they do, but often times I can't even tell exactly what they do. I agree with you that the multiple use of p is confusing, I'll try to fix that. On the other side, I don't see much hope for most of the other variable names. Have a nice day and thanks for your response. – Aemyl Oct 24 '17 at 10:27
• @Aemyl With all due respect, it sounds like you don't know what your code is doing. And so you're finding scapegoats, rather than learning what the code is actually doing. – Peilonrayz Oct 24 '17 at 10:48
• well, that's really half-true: I know what the functions do, but I don't know completely how they work (except the mul-function, that's easy to understand) – Aemyl Oct 24 '17 at 10:52