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.

• Ludisposed: "motorbike" +1 for that only ;)
• Aemyl: 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.
• Peilonrayz: @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.
• Aemyl: 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)