5 files changed, 1074 insertions, 32 deletions

diff --git a/util/ec.py b/util/ec.py
new file mode 100644
index 0000000..4e3244a
--- /dev/null
+++ b/util/ec.py
@@ -0,0 +1,1010 @@
+"""
+This module is a collection of modules glued together, to provide basic
+elliptic curve arithmetic for curves over prime and binary fields. It consists of
+ - tinyec: https://github.com/alexmgr/tinyec (GPL v3 licensed)
+ - pyfinite: https://github.com/emin63/pyfinite (MIT licensed)
+ - modular square root from https://eli.thegreenplace.net/2009/03/07/computing-modular-square-roots-in-python
+ - and some of my own code: https://github.com/J08nY
+"""
+
+import abc
+import random
+from functools import reduce, wraps
+from os import path
+
+
+def legendre_symbol(a, p):
+    """ Compute the Legendre symbol a|p using
+        Euler's criterion. p is a prime, a is
+        relatively prime to p (if p divides
+        a, then a|p = 0)
+
+        Returns 1 if a has a square root modulo
+        p, -1 otherwise.
+    """
+    ls = pow(a, (p - 1) // 2, p)
+    return -1 if ls == p - 1 else ls
+
+
+def is_prime(n, trials=50):
+    """
+    Miller-Rabin primality test.
+    """
+    s = 0
+    d = n - 1
+    while d % 2 == 0:
+        d >>= 1
+        s += 1
+    assert (2 ** s * d == n - 1)
+
+    def trial_composite(a):
+        if pow(a, d, n) == 1:
+            return False
+        for i in range(s):
+            if pow(a, 2 ** i * d, n) == n - 1:
+                return False
+        return True
+
+    for i in range(trials):  # number of trials
+        a = random.randrange(2, n)
+        if trial_composite(a):
+            return False
+    return True
+
+
+def gcd(a, b):
+    """Euclid's greatest common denominator algorithm."""
+    if abs(a) < abs(b):
+        return gcd(b, a)
+
+    while abs(b) > 0:
+        q, r = divmod(a, b)
+        a, b = b, r
+
+    return a
+
+
+def extgcd(a, b):
+    """Extended Euclid's greatest common denominator algorithm."""
+    if abs(b) > abs(a):
+        (x, y, d) = extgcd(b, a)
+        return y, x, d
+
+    if abs(b) == 0:
+        return 1, 0, a
+
+    x1, x2, y1, y2 = 0, 1, 1, 0
+    while abs(b) > 0:
+        q, r = divmod(a, b)
+        x = x2 - q * x1
+        y = y2 - q * y1
+        a, b, x2, x1, y2, y1 = b, r, x1, x, y1, y
+
+    return x2, y2, a
+
+
+def check(func):
+    @wraps(func)
+    def method(self, other):
+        if isinstance(other, int):
+            other = self.__class__(other, self.field)
+        if type(self) is type(other):
+            if self.field == other.field:
+                return func(self, other)
+            else:
+                raise ValueError
+        else:
+            raise TypeError
+
+    return method
+
+
+class Mod(object):
+    """An element x of ℤₙ."""
+
+    def __init__(self, x: int, n: int):
+        self.x = x % n
+        self.field = n
+
+    @check
+    def __add__(self, other):
+        return Mod((self.x + other.x) % self.field, self.field)
+
+    @check
+    def __radd__(self, other):
+        return self + other
+
+    @check
+    def __sub__(self, other):
+        return Mod((self.x - other.x) % self.field, self.field)
+
+    @check
+    def __rsub__(self, other):
+        return -self + other
+
+    def __neg__(self):
+        return Mod(self.field - self.x, self.field)
+
+    def inverse(self):
+        x, y, d = extgcd(self.x, self.field)
+        return Mod(x, self.field)
+
+    def __invert__(self):
+        return self.inverse()
+
+    @check
+    def __mul__(self, other):
+        return Mod((self.x * other.x) % self.field, self.field)
+
+    @check
+    def __rmul__(self, other):
+        return self * other
+
+    @check
+    def __truediv__(self, other):
+        return self * ~other
+
+    @check
+    def __rtruediv__(self, other):
+        return ~self * other
+
+    @check
+    def __floordiv__(self, other):
+        return self * ~other
+
+    @check
+    def __rfloordiv__(self, other):
+        return ~self * other
+
+    @check
+    def __div__(self, other):
+        return self.__floordiv__(other)
+
+    @check
+    def __rdiv__(self, other):
+        return self.__rfloordiv__(other)
+
+    @check
+    def __divmod__(self, divisor):
+        q, r = divmod(self.x, divisor.x)
+        return Mod(q, self.field), Mod(r, self.field)
+
+    def __int__(self):
+        return self.x
+
+    def __eq__(self, other):
+        if type(other) is not Mod:
+            return False
+        return self.x == other.x and self.field == other.field
+
+    def __ne__(self, other):
+        return not self == other
+
+    def __repr__(self):
+        return str(self.x)
+
+    def __pow__(self, n):
+        if not isinstance(n, int):
+            raise TypeError
+        if n == 0:
+            return Mod(1, self.field)
+        if n < 0:
+            return (~self) ** -n
+        if n == 1:
+            return self
+        if n == 2:
+            return self * self
+
+        q = self
+        r = self if n & 1 else Mod(1, self.field)
+
+        i = 2
+        while i <= n:
+            q = (q * q)
+            if n & i == i:
+                r = (q * r)
+            i = i << 1
+        return r
+
+    def sqrt(self):
+        if not is_prime(self.field):
+            raise NotImplementedError
+        # Simple cases
+        if legendre_symbol(self.x, self.field) != 1 or self.x == 0 or self.field == 2:
+            raise ValueError("Not a quadratic residue.")
+        if self.field % 4 == 3:
+            return self ** ((self.field + 1) // 4)
+
+        a = self.x
+        p = self.field
+        s = p - 1
+        e = 0
+        while s % 2 == 0:
+            s /= 2
+            e += 1
+
+        n = 2
+        while legendre_symbol(n, p) != -1:
+            n += 1
+
+        x = pow(a, (s + 1) / 2, p)
+        b = pow(a, s, p)
+        g = pow(n, s, p)
+        r = e
+
+        while True:
+            t = b
+            m = 0
+            for m in range(r):
+                if t == 1:
+                    break
+                t = pow(t, 2, p)
+
+            if m == 0:
+                return Mod(x, p)
+
+            gs = pow(g, 2 ** (r - m - 1), p)
+            g = (gs * gs) % p
+            x = (x * gs) % p
+            b = (b * g) % p
+            r = m
+
+
+class FField(object):
+    """
+    The FField class implements a binary field.
+    """
+
+    def __init__(self, n, gen):
+        """
+        This method constructs the field GF(2^n).  It takes two
+        required arguments, n and gen,
+        representing the coefficients of the generator polynomial
+        (of degree n) to use.
+        Note that you can look at the generator for the field object
+        F by looking at F.generator.
+        """
+
+        self.n = n
+        if len(gen) != n + 1:
+            full_gen = [0] * (n + 1)
+            for i in gen:
+                full_gen[i] = 1
+            gen = full_gen[::-1]
+        self.generator = self.to_element(gen)
+        self.unity = 1
+
+    def add(self, x, y):
+        """
+        Adds two field elements and returns the result.
+        """
+
+        return x ^ y
+
+    def subtract(self, x, y):
+        """
+        Subtracts the second argument from the first and returns
+        the result.  In fields of characteristic two this is the same
+        as the Add method.
+        """
+        return x ^ y
+
+    def multiply(self, f, v):
+        """
+        Multiplies two field elements (modulo the generator
+        self.generator) and returns the result.
+
+        See MultiplyWithoutReducing if you don't want multiplication
+        modulo self.generator.
+        """
+        m = self.multiply_no_reduce(f, v)
+        return self.full_division(m, self.generator, self.find_degree(m), self.n)[1]
+
+    def inverse(self, f):
+        """
+        Computes the multiplicative inverse of its argument and
+        returns the result.
+        """
+        return self.ext_gcd(self.unity, f, self.generator, self.find_degree(f), self.n)[1]
+
+    def divide(self, f, v):
+        """
+        Divide(f,v) returns f * v^-1.
+        """
+        return self.multiply(f, self.inverse(v))
+
+    def exponentiate(self, f, n):
+        """
+        Exponentiate(f, n) returns f^n.
+        """
+        if not isinstance(n, int):
+            raise TypeError
+        if n == 0:
+            return self.unity
+        if n < 0:
+            f = self.inverse(f)
+            n = -n
+        if n == 1:
+            return f
+        if n == 2:
+            return self.multiply(f, f)
+
+        q = f
+        r = f if n & 1 else self.unity
+
+        i = 2
+        while i <= n:
+            q = self.multiply(q, q)
+            if n & i == i:
+                r = self.multiply(q, r)
+            i = i << 1
+        return r
+
+    def sqrt(self, f):
+        return self.exponentiate(f, (2 ** self.n) - 1)
+
+    def trace(self, f):
+        t = f
+        for _ in range(1, self.n):
+            t = self.add(self.multiply(t, t), f)
+        return t
+
+    def half_trace(self, f):
+        if self.n % 2 != 1:
+            raise ValueError
+        h = f
+        for _ in range(1, (self.n - 1) // 2):
+            h = self.multiply(h, h)
+            h = self.add(self.multiply(h, h), f)
+        return h
+
+    def find_degree(self, v):
+        """
+        Find the degree of the polynomial representing the input field
+        element v.  This takes O(degree(v)) operations.
+
+        A faster version requiring only O(log(degree(v)))
+        could be written using binary search...
+        """
+        if v:
+            return v.bit_length() - 1
+        else:
+            return 0
+
+    def multiply_no_reduce(self, f, v):
+        """
+        Multiplies two field elements and does not take the result
+        modulo self.generator.  You probably should not use this
+        unless you know what you are doing; look at Multiply instead.
+        """
+
+        result = 0
+        mask = self.unity
+        for i in range(self.n + 1):
+            if mask & v:
+                result = result ^ f
+            f = f << 1
+            mask = mask << 1
+        return result
+
+    def ext_gcd(self, d, a, b, a_degree, b_degree):
+        """
+        Takes arguments (d,a,b,aDegree,bDegree) where d = gcd(a,b)
+        and returns the result of the extended Euclid algorithm
+        on (d,a,b).
+        """
+        if b == 0:
+            return a, self.unity, 0
+        else:
+            (floorADivB, aModB) = self.full_division(a, b, a_degree, b_degree)
+            (d, x, y) = self.ext_gcd(d, b, aModB, b_degree, self.find_degree(aModB))
+            return d, y, self.subtract(x, self.multiply(floorADivB, y))
+
+    def full_division(self, f, v, f_degree, v_degree):
+        """
+        Takes four arguments, f, v, fDegree, and vDegree where
+        fDegree and vDegree are the degrees of the field elements
+        f and v represented as a polynomials.
+        This method returns the field elements a and b such that
+
+            f(x) = a(x) * v(x) + b(x).
+
+        That is, a is the divisor and b is the remainder, or in
+        other words a is like floor(f/v) and b is like f modulo v.
+        """
+
+        result = 0
+        mask = self.unity << f_degree
+        for i in range(f_degree, v_degree - 1, -1):
+            if mask & f:
+                result = result ^ (self.unity << (i - v_degree))
+                f = self.subtract(f, v << (i - v_degree))
+            mask = mask >> self.unity
+        return result, f
+
+    def coefficients(self, f):
+        """
+        Show coefficients of input field element represented as a
+        polynomial in decreasing order.
+        """
+
+        result = []
+        for i in range(self.n, -1, -1):
+            if (self.unity << i) & f:
+                result.append(1)
+            else:
+                result.append(0)
+
+        return result
+
+    def polynomial(self, f):
+        """
+        Show input field element represented as a polynomial.
+        """
+
+        f_degree = self.find_degree(f)
+        result = ''
+
+        if f == 0:
+            return '0'
+
+        for i in range(f_degree, 0, -1):
+            if (1 << i) & f:
+                result = result + (' x^' + repr(i))
+        if 1 & f:
+            result = result + ' ' + repr(1)
+        return result.strip().replace(' ', ' + ')
+
+    def to_element(self, l):
+        """
+        This method takes as input a binary list (e.g. [1, 0, 1, 1])
+        and converts it to a decimal representation of a field element.
+        For example, [1, 0, 1, 1] is mapped to 8 | 2 | 1 = 11.
+
+        Note if the input list is of degree >= to the degree of the
+        generator for the field, then you will have to call take the
+        result modulo the generator to get a proper element in the
+        field.
+        """
+
+        temp = map(lambda a, b: a << b, l, range(len(l) - 1, -1, -1))
+        return reduce(lambda a, b: a | b, temp)
+
+    def __str__(self):
+        return "F_(2^{}): {}".format(self.n, self.polynomial(self.generator))
+
+    def __repr__(self):
+        return str(self)
+
+
+class FElement(object):
+    """
+    This class provides field elements which overload the
+    +,-,*,%,//,/ operators to be the appropriate field operation.
+    Note that before creating FElement objects you must first
+    create an FField object.
+    """
+
+    def __init__(self, f, field):
+        """
+        The constructor takes two arguments, field, and e where
+        field is an FField object and e is an integer representing
+        an element in FField.
+
+        The result is a new FElement instance.
+        """
+        self.f = f
+        self.field = field
+
+    @check
+    def __add__(self, other):
+        return FElement(self.field.add(self.f, other.f), self.field)
+
+    @check
+    def __sub__(self, other):
+        return FElement(self.field.add(self.f, other.f), self.field)
+
+    def __neg__(self):
+        return self
+
+    @check
+    def __mul__(self, other):
+        return FElement(self.field.multiply(self.f, other.f), self.field)
+
+    @check
+    def __floordiv__(self, o):
+        return FElement(self.field.full_division(self.f, o.f,
+                                                 self.field.find_degree(self.f),
+                                                 self.field.find_degree(o.f))[0], self.field)
+
+    @check
+    def __truediv__(self, other):
+        return FElement(self.field.divide(self.f, other.f), self.field)
+
+    def __div__(self, *args, **kwargs):
+        return self.__truediv__(*args, **kwargs)
+
+    @check
+    def __divmod__(self, other):
+        d, m = self.field.full_division(self.f, other.f,
+                                        self.field.find_degree(self.f),
+                                        self.field.find_degree(other.f))
+        return FElement(d, self.field), FElement(m, self.field)
+
+    def inverse(self):
+        return FElement(self.field.inverse(self.f), self.field)
+
+    def __invert__(self):
+        return self.inverse()
+
+    def sqrt(self):
+        return FElement(self.field.sqrt(self.f), self.field)
+
+    def trace(self):
+        return FElement(self.field.trace(self.f), self.field)
+
+    def half_trace(self):
+        return FElement(self.field.half_trace(self.f), self.field)
+
+    def __pow__(self, power, modulo=None):
+        return FElement(self.field.exponentiate(self.f, power), self.field)
+
+    def __str__(self):
+        return str(int(self))
+
+    def __repr__(self):
+        return str(self)
+
+    def __int__(self):
+        return self.f
+
+    def __eq__(self, other):
+        if not isinstance(other, FElement):
+            return False
+        if self.field != other.field:
+            return False
+        return self.f == other.f
+
+
+class Curve(object):
+    __metaclass__ = abc.ABCMeta
+
+    def __init__(self, field, a, b, group, name=None):
+        self.field = field
+        if name is None:
+            name = "undefined"
+        self.name = name
+        self.a = a
+        self.b = b
+        self.group = group
+        self.g = Point(self, self.group.g[0], self.group.g[1])
+
+    @abc.abstractmethod
+    def is_singular(self):
+        ...
+
+    @abc.abstractmethod
+    def on_curve(self, x, y):
+        ...
+
+    @abc.abstractmethod
+    def add(self, x1, y1, x2, y2):
+        ...
+
+    @abc.abstractmethod
+    def dbl(self, x, y):
+        ...
+
+    @abc.abstractmethod
+    def neg(self, x, y):
+        ...
+
+    @abc.abstractmethod
+    def encode_point(self, point, compressed=False):
+        ...
+
+    @abc.abstractmethod
+    def decode_point(self, byte_data):
+        ...
+
+    def bit_size(self):
+        return self.group.n.bit_length()
+
+    def byte_size(self):
+        return (self.bit_size() + 7) // 8
+
+    @abc.abstractmethod
+    def field_size(self):
+        ...
+
+    def __eq__(self, other):
+        if not isinstance(other, Curve):
+            return False
+        return self.field == other.field and self.a == other.a and self.b == other.b and self.group == other.group
+
+    def __repr__(self):
+        return str(self)
+
+
+class CurveFp(Curve):
+    def is_singular(self):
+        return (4 * self.a ** 3 + 27 * self.b ** 2) == 0
+
+    def on_curve(self, x, y):
+        return (y ** 2 - x ** 3 - self.a * x - self.b) == 0
+
+    def add(self, x1, y1, x2, y2):
+        lm = (y2 - y1) / (x2 - x1)
+        x3 = lm ** 2 - x1 - x2
+        y3 = lm * (x1 - x3) - y1
+        return x3, y3
+
+    def dbl(self, x, y):
+        lm = (3 * x ** 2 + self.a) / (2 * y)
+        x3 = lm ** 2 - (2 * x)
+        y3 = lm * (x - x3) - y
+        return x3, y3
+
+    def mul(self, k, x, y, z=1):
+        def _add(x1, y1, z1, x2, y2, z2):
+            yz = y1 * z2
+            xz = x1 * z2
+            zz = z1 * z2
+            u = y2 * z1 - yz
+            uu = u ** 2
+            v = x2 * z1 - xz
+            vv = v ** 2
+            vvv = v * vv
+            r = vv * xz
+            a = uu * zz - vvv - 2 * r
+            x3 = v * a
+            y3 = u * (r - a) - vvv * yz
+            z3 = vvv * zz
+            return x3, y3, z3
+
+        def _dbl(x1, y1, z1):
+            xx = x1 ** 2
+            zz = z1 ** 2
+            w = self.a * zz + 3 * xx
+            s = 2 * y1 * z1
+            ss = s ** 2
+            sss = s * ss
+            r = y1 * s
+            rr = r ** 2
+            b = (x1 + r) ** 2 - xx - rr
+            h = w ** 2 - 2 * b
+            x3 = h * s
+            y3 = w * (b - h) - 2 * rr
+            z3 = sss
+            return x3, y3, z3
+        r0 = (x, y, z)
+        r1 = _dbl(x, y, z)
+        for i in range(k.bit_length() - 2, -1, -1):
+            if k & (1 << i):
+                r0 = _add(*r0, *r1)
+                r1 = _dbl(*r1)
+            else:
+                r1 = _add(*r0, *r1)
+                r0 = _dbl(*r0)
+        rx, ry, rz = r0
+        rzi = ~rz
+        return rx * rzi, ry * rzi
+
+    def neg(self, x, y):
+        return x, -y
+
+    def field_size(self):
+        return self.field.bit_length()
+
+    def encode_point(self, point, compressed=False):
+        byte_size = (self.field_size() + 7) // 8
+        if not compressed:
+            return bytes((0x04,)) + int(point.x).to_bytes(byte_size, byteorder="big") + int(
+                    point.y).to_bytes(byte_size, byteorder="big")
+        else:
+            yp = int(point.y) & 1
+            pc = bytes((0x02 | yp,))
+            return pc + int(point.x).to_bytes(byte_size, byteorder="big")
+
+    def decode_point(self, byte_data):
+        if byte_data[0] == 0 and len(byte_data) == 1:
+            return Inf(self)
+        byte_size = (self.field_size() + 7) // 8
+        if byte_data[0] in (0x04, 0x06):
+            if len(byte_data) != 1 + byte_size * 2:
+                raise ValueError
+            x = Mod(int.from_bytes(byte_data[1:byte_size + 1], byteorder="big"), self.field)
+            y = Mod(int.from_bytes(byte_data[byte_size + 1:], byteorder="big"), self.field)
+            return Point(self, x, y)
+        elif byte_data[0] in (0x02, 0x03):
+            if len(byte_data) != 1 + byte_size:
+                raise ValueError
+            x = Mod(int.from_bytes(byte_data[1:byte_size + 1], byteorder="big"), self.field)
+            rhs = x ** 3 + self.a * x + self.b
+            sqrt = rhs.sqrt()
+            yp = byte_data[0] & 1
+            if int(sqrt) & 1 == yp:
+                return Point(self, x, sqrt)
+            else:
+                return Point(self, x, self.field - sqrt)
+        raise ValueError
+
+    def __str__(self):
+        return "\"{}\": y^2 = x^3 + {}x + {} over {}".format(self.name, self.a, self.b, self.field)
+
+
+class CurveF2m(Curve):
+    def is_singular(self):
+        return self.b == 0
+
+    def on_curve(self, x, y):
+        return (y ** 2 + x * y - x ** 3 - self.a * x ^ 2 - self.b) == 0
+
+    def add(self, x1, y1, x2, y2):
+        lm = (y1 + y2) / (x1 + x2)
+        x3 = lm ** 2 + lm + x1 + x2 + self.a
+        y3 = lm * (x1 + x3) + x3 + y1
+        return x3, y3
+
+    def dbl(self, x, y):
+        lm = x + y / x
+        x3 = lm ** 2 + lm + self.a
+        y3 = x ** 2 + lm * x3 + x3
+        return x3, y3
+
+    def mul(self, k, x, y, z=1):
+        def _add(x1, y1, z1, x2, y2, z2):
+            a = x1 * z2
+            b = x2 * z1
+            c = a ** 2
+            d = b ** 2
+            e = a + b
+            f = c + d
+            g = y1 * (z2 ** 2)
+            h = y2 * (z1 ** 2)
+            i = g + h
+            j = i * e
+            z3 = f * z1 * z2
+            x3 = a * (h + d) + b * (c + g)
+            y3 = (a * j + f * g) * f + (j + z3) * x3
+            return x3, y3, z3
+
+        def _dbl(x1, y1, z1):
+            a = x1 * z1
+            b = x1 * x1
+            c = b + y1
+            d = a * c
+            z3 = a * a
+            x3 = c ** 2 + d + self.a * z3
+            y3 = (z3 + d) * x3 + b ** 2 * z3
+            return x3, y3, z3
+        r0 = (x, y, z)
+        r1 = _dbl(x, y, z)
+        for i in range(k.bit_length() - 2, -1, -1):
+            if k & (1 << i):
+                r0 = _add(*r0, *r1)
+                r1 = _dbl(*r1)
+            else:
+                r1 = _add(*r0, *r1)
+                r0 = _dbl(*r0)
+        rx, ry, rz = r0
+        rzi = ~rz
+        return rx * rzi, ry * (rzi ** 2)
+
+    def neg(self, x, y):
+        return x, x + y
+
+    def field_size(self):
+        return self.field.n
+
+    def encode_point(self, point, compressed=False):
+        byte_size = (self.field_size() + 7) // 8
+        if not compressed:
+            return bytes((0x04,)) + int(point.x).to_bytes(byte_size, byteorder="big") + int(
+                    point.y).to_bytes(byte_size, byteorder="big")
+        else:
+            if int(point.x) == 0:
+                yp = 0
+            else:
+                yp = int(point.y * point.x.inverse())
+            pc = bytes((0x02 | yp,))
+            return pc + int(point.x).to_bytes(byte_size, byteorder="big")
+
+    def decode_point(self, byte_data):
+        if byte_data[0] == 0 and len(byte_data) == 1:
+            return Inf(self)
+        byte_size = (self.field_size() + 7) // 8
+        if byte_data[0] in (0x04, 0x06):
+            if len(byte_data) != 1 + byte_size * 2:
+                raise ValueError
+            x = FElement(int.from_bytes(byte_data[1:byte_size + 1], byteorder="big"), self.field)
+            y = FElement(int.from_bytes(byte_data[byte_size + 1:], byteorder="big"), self.field)
+            return Point(self, x, y)
+        elif byte_data[0] in (0x02, 0x03):
+            if self.field.n % 2 != 1:
+                raise NotImplementedError
+            x = FElement(int.from_bytes(byte_data[1:byte_size + 1], byteorder="big"), self.field)
+            yp = byte_data[0] & 1
+            if int(x) == 0:
+                y = self.b ** (2 ** (self.field.n - 1))
+            else:
+                rhs = x + self.a + self.b * x ** (-2)
+                z = rhs.half_trace()
+                if z ** 2 + z != rhs:
+                    raise ValueError
+                if int(z) & 1 != yp:
+                    z += 1
+                y = x * z
+            return Point(self, x, y)
+        raise ValueError
+
+    def __str__(self):
+        return "\"{}\" => y^2 + xy = x^3 + {}x^2 + {} over {}".format(self.name, self.a, self.b,
+                                                                      self.field)
+
+
+class SubGroup(object):
+    def __init__(self, g, n, h):
+        self.g = g
+        self.n = n
+        self.h = h
+
+    def __eq__(self, other):
+        if not isinstance(other, SubGroup):
+            return False
+        return self.g == other.g and self.n == other.n and self.h == other.h
+
+    def __str__(self):
+        return "Subgroup => generator {}, order: {}, cofactor: {}".format(self.g, self.n, self.h)
+
+    def __repr__(self):
+        return str(self)
+
+
+class Inf(object):
+    def __init__(self, curve, x=None, y=None):
+        self.x = x
+        self.y = y
+        self.curve = curve
+
+    def __eq__(self, other):
+        if not isinstance(other, Inf):
+            return False
+        return self.curve == other.curve
+
+    def __ne__(self, other):
+        return not self.__eq__(other)
+
+    def __neg__(self):
+        return self
+
+    def __add__(self, other):
+        if isinstance(other, Inf):
+            return Inf(self.curve)
+        if isinstance(other, Point):
+            return other
+        raise TypeError(
+                "Unsupported operand type(s) for +: '%s' and '%s'" % (self.__class__.__name__,
+                                                                      other.__class__.__name__))
+
+    def __radd__(self, other):
+        return self + other
+
+    def __sub__(self, other):
+        if isinstance(other, Inf):
+            return Inf(self.curve)
+        if isinstance(other, Point):
+            return other
+        raise TypeError(
+                "Unsupported operand type(s) for +: '%s' and '%s'" % (self.__class__.__name__,
+                                                                      other.__class__.__name__))
+
+    def __str__(self):
+        return "{} on {}".format(self.__class__.__name__, self.curve)
+
+    def __repr__(self):
+        return str(self)
+
+
+class Point(object):
+    def __init__(self, curve, x, y):
+        self.curve = curve
+        self.x = x
+        self.y = y
+
+    def __eq__(self, other):
+        if not isinstance(other, Point):
+            return False
+        return self.x == other.x and self.y == other.y and self.curve == other.curve
+
+    def __ne__(self, other):
+        return not self.__eq__(other)
+
+    def __neg__(self):
+        return Point(self.curve, *self.curve.neg(self.x, self.y))
+
+    def __add__(self, other):
+        if isinstance(other, Inf):
+            return self
+        if isinstance(other, Point):
+            if self.curve != other.curve:
+                raise ValueError("Cannot add points belonging to different curves")
+            if self == -other:
+                return Inf(self.curve)
+            elif self == other:
+                return Point(self.curve, *self.curve.dbl(self.x, self.y))
+            else:
+                return Point(self.curve, *self.curve.add(self.x, self.y, other.x, other.y))
+        else:
+            raise TypeError(
+                    "Unsupported operand type(s) for +: '{}' and '{}'".format(
+                            self.__class__.__name__,
+                            other.__class__.__name__))
+
+    def __radd__(self, other):
+        return self + other
+
+    def __sub__(self, other):
+        return self + (-other)
+
+    def __rsub__(self, other):
+        return self - other
+
+    def __mul__(self, other):
+        if isinstance(other, int):
+            if other % self.curve.group.n == 0:
+                return Inf(self.curve)
+            if other < 0:
+                other = -other
+                addend = -self
+            else:
+                addend = self
+            if hasattr(self.curve, "mul") and callable(getattr(self.curve, "mul")):
+                return Point(self.curve, *self.curve.mul(other, addend.x, addend.y))
+            else:
+                result = Inf(self.curve)
+                # Iterate over all bits starting by the LSB
+                for bit in reversed([int(i) for i in bin(abs(other))[2:]]):
+                    if bit == 1:
+                        result += addend
+                    addend += addend
+                return result
+        else:
+            raise TypeError(
+                    "Unsupported operand type(s) for *: '%s' and '%s'" % (other.__class__.__name__,
+                                                                          self.__class__.__name__))
+
+    def __rmul__(self, other):
+        return self * other
+
+    def __str__(self):
+        return "({}, {}) on {}".format(self.x, self.y, self.curve)
+
+    def __repr__(self):
+        return str(self)
+
+
+def load_curve(file, name=None):
+    data = file.read()
+    parts = list(map(lambda x: int(x, 16), data.split(",")))
+    if len(parts) == 7:
+        p, a, b, gx, gy, n, h = parts
+        g = (Mod(gx, p), Mod(gy, p))
+        group = SubGroup(g, n, h)
+        return CurveFp(p, Mod(a, p), Mod(b, p), group, name)
+    elif len(parts) == 10:
+        m, e1, e2, e3, a, b, gx, gy, n, h = parts
+        poly = [m, e1, e2, e3, 0]
+        field = FField(m, poly)
+        g = (FElement(gx, field), FElement(gy, field))
+        group = SubGroup(g, n, h)
+        return CurveF2m(field, FElement(a, field), FElement(b, field), group, name)
+    else:
+        raise ValueError("Invalid curve data")
+
+
+def get_curve(idd):
+    cat, i = idd.split("/")
+    with open(path.join("..", "src", "cz", "crcs", "ectester", "data", cat, i + ".csv"), "r") as f:
+        return load_curve(f, i)
+
diff --git a/util/plot_dh.ipynb b/util/plot_dh.ipynb
index 950be6a..f43d631 100644
--- a/util/plot_dh.ipynb
+++ b/util/plot_dh.ipynb
@@ -82,7 +82,7 @@
     "style = \"ggplot\"\n",
     "\n",
     "# Color map to use, and what color to assign to \"bad\" values (necessary for log_scale)\n",
-    "color_map = plt.cm.plasma\n",
+    "color_map = plt.cm.viridis\n",
     "color_map_bad = \"black\"\n",
     "\n",
     "# What function to use to calculate number of histogram bins of time\n",
@@ -610,8 +610,8 @@
  ],
  "metadata": {
   "@webio": {
-   "lastCommId": "68bed3134fc443a3829779707f7e77b0",
-   "lastKernelId": "168cb4cf-3a36-4e98-a687-9a9f57b50354"
+   "lastCommId": "709d7f1e9dab427486f950933d243d24",
+   "lastKernelId": "cf0cea00-5a1b-4e6e-b81a-40a069517c67"
   },
   "hide_input": false,
   "kernelspec": {
@@ -629,7 +629,7 @@
    "name": "python",
    "nbconvert_exporter": "python",
    "pygments_lexer": "ipython3",
-   "version": "3.7.2"
+   "version": "3.7.4"
   },
   "latex_envs": {
    "LaTeX_envs_menu_present": true,
diff --git a/util/plot_dsa.ipynb b/util/plot_dsa.ipynb
index a542f9c..abd6531 100644
--- a/util/plot_dsa.ipynb
+++ b/util/plot_dsa.ipynb
@@ -27,7 +27,7 @@
     "import matplotlib.pyplot as plt\n",
     "from matplotlib import ticker, colors, gridspec\n",
     "from copy import deepcopy\n",
-    "from utils import plot_hist, moving_average, hw, time_scale, hist_size_func\n",
+    "from utils import plot_hist, moving_average, hw, time_scale, hist_size_func, recompute_nonces\n",
     "from binascii import unhexlify\n",
     "from IPython.display import display, HTML\n",
     "from ipywidgets import interact, interactive, fixed, interact_manual\n",
@@ -57,6 +57,13 @@
     "# File name with output from ECTesterReader or ECTesterStandalone signatures.\n",
     "fname = \"filename.csv\"\n",
     "\n",
+    "# A hash algorithm used\n",
+    "hash_algo = \"SHA1\" # e.g. \"SHA1\" or None for no hash, raw data signatures\n",
+    "\n",
+    "# A curve name or a path to curve file, used to recompute the random nonces used in signing, if they are not present\n",
+    "# in the file. (ECTester was not able to recompute them for some reason)\n",
+    "curve = None # e.g. \"secg/secp256r1\" or \"secp256r1.csv\" or None for no curve.\n",
+    "\n",
     "# The time unit used in displaying the plots. One of \"milli\", \"micro\", \"nano\".\n",
     "# WARNING: Using nano might lead to very large plots/histograms and to the\n",
     "#          notebook to freeze or run out of memory, as well as bad visualization\n",
@@ -83,7 +90,7 @@
     "style = \"ggplot\"\n",
     "\n",
     "# Color map to use, and what color to assign to \"bad\" values (necessary for log_scale)\n",
-    "color_map = plt.cm.plasma\n",
+    "color_map = plt.cm.viridis\n",
     "color_map_bad = \"black\"\n",
     "\n",
     "# What function to use to calculate number of histogram bins of time\n",
@@ -152,6 +159,9 @@
     "sign_disp_unit = time_scale(data[\"sign_time\"], orig_sign_unit, sign_unit, scaling_factor)\n",
     "verify_disp_unit = time_scale(data[\"verify_time\"], orig_verify_unit, verify_unit, scaling_factor)\n",
     "\n",
+    "if np.any(data[\"nonce\"] == None):\n",
+    "    recompute_nonces(data, curve, hash_algo)\n",
+    "\n",
     "# Trim times\n",
     "quant_low_bound = trim_low if 0 <= trim_low <= 1 else 0.01\n",
     "quant_high_bound = trim_high if 0 <= trim_high <= 1 else 0.95\n",
@@ -675,8 +685,8 @@
  ],
  "metadata": {
   "@webio": {
-   "lastCommId": "8be83dd299f244e7859686e690aa3254",
-   "lastKernelId": "4cf3b8b4-71ee-4bf5-aafc-ff6192e2d23c"
+   "lastCommId": "a38f080b9a044da08882846212c38d91",
+   "lastKernelId": "4cad5b27-583d-4c4e-947c-f47bdf2d4754"
   },
   "hide_input": false,
   "kernelspec": {
@@ -694,7 +704,7 @@
    "name": "python",
    "nbconvert_exporter": "python",
    "pygments_lexer": "ipython3",
-   "version": "3.7.2"
+   "version": "3.7.4"
   },
   "latex_envs": {
    "LaTeX_envs_menu_present": true,
diff --git a/util/plot_gen.ipynb b/util/plot_gen.ipynb
index 0b97e32..8e6913f 100644
--- a/util/plot_gen.ipynb
+++ b/util/plot_gen.ipynb
@@ -83,7 +83,7 @@
     "style = \"ggplot\"\n",
     "\n",
     "# Color map to use, and what color to assign to \"bad\" values (necessary for log_scale)\n",
-    "color_map = plt.cm.plasma\n",
+    "color_map = plt.cm.viridis\n",
     "color_map_bad = \"black\"\n",
     "\n",
     "# What function to use to calculate number of histogram bins of time\n",
@@ -697,8 +697,8 @@
  ],
  "metadata": {
   "@webio": {
-   "lastCommId": "654e0684d96844649d98c59269982aec",
-   "lastKernelId": "aa63ee10-ea6a-4bf0-9d7f-78e3bb9ee3a9"
+   "lastCommId": "62b9fbe51a4c472094fee49d62cdb7ec",
+   "lastKernelId": "a920ac21-57cb-406f-8aef-476c8b0e7df5"
   },
   "hide_input": false,
   "kernelspec": {
@@ -716,7 +716,7 @@
    "name": "python",
    "nbconvert_exporter": "python",
    "pygments_lexer": "ipython3",
-   "version": "3.7.2"
+   "version": "3.7.4"
   },
   "latex_envs": {
    "LaTeX_envs_menu_present": true,
diff --git a/util/utils.py b/util/utils.py
index 1c620ef..014c4c6 100644
--- a/util/utils.py
+++ b/util/utils.py
@@ -1,7 +1,9 @@
+import hashlib
 import numpy as np
 from matplotlib import ticker
 from math import sqrt, log
-
+import ec
+from asn1crypto.core import Sequence
 
 def hw(i):
     res = 0
@@ -18,19 +20,55 @@ def moving_average(a, n) :
 
 
 def time_scale(data, orig_unit, target_unit, scaling_factor):
+    if orig_unit == "instr":
+        return orig_unit
     units = {
         "milli": ("ms", 1000000),
         "micro": (r"$\mu s$", 1000),
         "nano":  ("ns", 1)
     }
-    upper = units[orig_unit][1]
-    lower = units[target_unit][1] * scaling_factor
+    upper = units[orig_unit][1] * scaling_factor
+    lower = units[target_unit][1]
     if upper > lower:
         data *= upper // lower
     elif lower > upper:
         np.floor_divide(data, lower // upper, data)
     return (r"$\frac{1}{" + str(scaling_factor) + "}$" if scaling_factor != 1 else "") + units[target_unit][0]
 
+def recompute_nonces(data, curve_name, hash_algo):
+    try:
+        curve = ec.get_curve(curve_name)
+    except:
+        curve = ec.load_curve(curve_name)
+    verified = False
+    for elem in data:
+        if elem["nonce"] is not None:
+            continue
+        if elem["index"] % (len(data)//10) == 0:
+            print(".", end="")
+        if hash_algo is None:
+            hm = int.from_bytes(elem["data"], byteorder="big") % curve.group.n
+        else:
+            h = hashlib.new(hash_algo, elem["data"])
+            hm = int(h.hexdigest(), 16)
+            if h.digest_size * 8 > curve.group.n.bit_length():
+                hm >> h.digest_size * 8 - curve.group.n.bit_length()
+            hm = hm % curve.group.n
+        r, s = Sequence.load(elem["signature"]).native.values()
+        r = ec.Mod(r, curve.group.n)
+        s = ec.Mod(s, curve.group.n)
+        rx = r * elem["priv"]
+        hmrx = hm + rx
+        nonce = s.inverse() * hmrx
+        if not verified:
+            res = int(nonce) * curve.g
+            if int(res.x) % curve.group.n != int(r):
+                print("Nonce recomputation couldnt verify!")
+                raise ValueError
+            else:
+                print("Nonce recomputation works")
+                verified = True
+        elem["nonce"] = int(nonce)
 
 def hist_size_func(choice):
     if choice == "sqrt":
@@ -71,19 +109,3 @@ def miller_correction(entropy, samples, bins):
     return entropy + (bins - 1)/(2*samples)
 
 
-def egcd(a, b):
-    if a == 0:
-        return b, 0, 1
-    else:
-        g, y, x = egcd(b % a, a)
-        return g, x - (b // a) * y, y
-
-
-def mod_inv(a, p):
-    if a < 0:
-        return p - mod_inv(-a, p)
-    g, x, y = egcd(a, p)
-    if g != 1:
-        raise ArithmeticError("Modular inverse does not exist")
-    else:
-        return x % p