ECDH implementation in python (part 2)

Question

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) def add(self, p, q): """ point addition on this curve. 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. double and add instead of square and multiply. """ 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:]: r = self.add(r, r) if b == '1': r = self.add(r, p) 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.

Answer 1

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.