0
\$\begingroup\$

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.
\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ "motorbike" +1 for that only ;) \$\endgroup\$ – Ludisposed Oct 24 '17 at 10:20
  • \$\begingroup\$ 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. \$\endgroup\$ – Aemyl Oct 24 '17 at 10:27
  • \$\begingroup\$ @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. \$\endgroup\$ – Peilonrayz Oct 24 '17 at 10:48
  • \$\begingroup\$ 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) \$\endgroup\$ – Aemyl Oct 24 '17 at 10:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.