Elliptic curve cryptography python github
# Basics of Elliptic Curve Cryptography implementation on Python
import collections
def inv(n, q):
"""div on PN modulo a/b mod q as a * inv(b, q) mod q
>>> assert n * inv(n, q) % q == 1
"""
for i in range(q):
if (n * i) % q == 1:
return i
pass
assert False, "unreached"
pass
def sqrt(n, q):
"""sqrt on PN modulo: returns two numbers or exception if not exist
>>> assert (sqrt(n, q)[0] ** 2) % q == n
>>> assert (sqrt(n, q)[1] ** 2) % q == n
"""
assert n < q
for i in range(1, q):
if i * i % q == n:
return (i, q - i)
pass
raise Exception("not found")
Coord = collections.namedtuple("Coord", ["x", "y"])
class EC(object):
"""System of Elliptic Curve"""
def __init__(self, a, b, q):
"""elliptic curve as: (y**2 = x**3 + a * x + b) mod q
- a, b: params of curve formula
- q: prime number
"""
assert 0 < a and a < q and 0 < b and b < q and q > 2
assert (4 * (a ** 3) + 27 * (b ** 2)) % q != 0
self.a = a
self.b = b
self.q = q
# just as unique ZERO value representation for "add": (not on curve)
self.zero = Coord(0, 0)
pass
def is_valid(self, p):
if p == self.zero: return True
l = (p.y ** 2) % self.q
r = ((p.x ** 3) + self.a * p.x + self.b) % self.q
return l == r
def at(self, x):
"""find points on curve at x
- x: int < q
- returns: ((x, y), (x,-y)) or not found exception
>>> a, ma = ec.at(x)
>>> assert a.x == ma.x and a.x == x
>>> assert a.x == ma.x and a.x == x
>>> assert ec.neg(a) == ma
>>> assert ec.is_valid(a) and ec.is_valid(ma)
"""
assert x < self.q
ysq = (x ** 3 + self.a * x + self.b) % self.q
y, my = sqrt(ysq, self.q)
return Coord(x, y), Coord(x, my)
def neg(self, p):
"""negate p
>>> assert ec.is_valid(ec.neg(p))
"""
return Coord(p.x, -p.y % self.q)
def add(self, p1, p2):
""" |