-
-
Save cigler/4f2f5d9bffe3e58dfc637e9849fc4aa8 to your computer and use it in GitHub Desktop.
[python]basics of elliptic curve cryptography
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # 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): | |
| """<add> of elliptic curve: negate of 3rd cross point of (p1,p2) line | |
| >>> c = ec.add(a, b) | |
| >>> assert ec.is_valid(c) | |
| >>> assert ec.add(c, ec.neg(b)) == a | |
| >>> assert ec.add(a, ec.neg(a)) == ec.zero | |
| """ | |
| if p1 == self.zero: return p2 | |
| if p2 == self.zero: return p1 | |
| if p1.x == p2.x and (p1.y != p2.y or p1.y == 0): | |
| # p1 + -p1 == 0 | |
| return self.zero | |
| if p1.x == p2.x: | |
| # p1 + p1: use tangent line of p1 as (p1,p1) line | |
| l = (3 * p1.x * p1.x + self.a) * inv(2 * p1.y, self.q) % self.q | |
| pass | |
| else: | |
| l = (p2.y - p1.y) * inv(p2.x - p1.x, self.q) % self.q | |
| pass | |
| x = (l * l - p1.x - p2.x) % self.q | |
| y = (l * (p1.x - x) - p1.y) % self.q | |
| return Coord(x, y) | |
| def mul(self, p, n): | |
| """n times <mul> of elliptic curve | |
| >>> m = ec.mul(p, n) | |
| >>> assert ec.is_valid(m) | |
| >>> assert ec.mul(p, ec.q) == ec.zero | |
| """ | |
| r = self.zero | |
| m2 = p | |
| # O(log2(n)) add | |
| while 0 < n: | |
| if n & 1 == 1: | |
| r = self.add(r, m2) | |
| pass | |
| n, m2 = n >> 1, self.add(m2, m2) | |
| pass | |
| # [ref] O(n) add | |
| #for i in range(n): | |
| # r = self.add(r, p) | |
| # pass | |
| return r | |
| def order(self, g): | |
| assert self.is_valid(g) | |
| for i in range(2, self.q + 1): | |
| if self.mul(g, i) == self.zero: | |
| return i | |
| pass | |
| raise Exception("Invalid order") | |
| pass | |
| class ElGamal(object): | |
| """ElGamal Encryption | |
| pub key encryption as replacing (mulmod, powmod) to (ec.add, ec.mul) | |
| - ec: elliptic curve | |
| - g: (random) a point on ec | |
| """ | |
| def __init__(self, ec, g): | |
| assert ec.is_valid(g) | |
| self.ec = ec | |
| self.g = g | |
| pass | |
| def gen(self, priv): | |
| """generate pub key | |
| - priv: priv key as (random) int < ec.q | |
| - returns: pub key as points on ec | |
| """ | |
| return self.ec.mul(g, priv) | |
| def enc(self, plain, pub, r): | |
| """encrypt | |
| - plain: data as a point on ec | |
| - pub: pub key as points on ec | |
| - r: randam int < ec.q | |
| - returns: (cipher1, ciper2) as points on ec | |
| """ | |
| assert self.ec.is_valid(plain) | |
| assert self.ec.is_valid(pub) | |
| return (self.ec.mul(g, r), self.ec.add(plain, self.ec.mul(pub, r))) | |
| def dec(self, cipher, priv): | |
| """decrypt | |
| - chiper: (chiper1, chiper2) as points on ec | |
| - priv: private key as int < ec.q | |
| - returns: plain as a point on ec | |
| """ | |
| c1, c2 = cipher | |
| assert self.ec.is_valid(c1) and ec.is_valid(c2) | |
| return self.ec.add(c2, self.ec.neg(self.ec.mul(c1, priv))) | |
| pass | |
| class DiffieHellman(object): | |
| """Elliptic Curve Diffie Hellman (Key Agreement) | |
| - ec: elliptic curve | |
| - g: a point on ec | |
| """ | |
| def __init__(self, ec, g): | |
| self.ec = ec | |
| self.g = g | |
| self.n = ec.order(g) | |
| pass | |
| def gen(self, priv): | |
| """generate pub key""" | |
| assert 0 < priv and priv < self.n | |
| return self.ec.mul(self.g, priv) | |
| def secret(self, priv, pub): | |
| """calc shared secret key for the pair | |
| - priv: my private key as int | |
| - pub: partner pub key as a point on ec | |
| - returns: shared secret as a point on ec | |
| """ | |
| assert self.ec.is_valid(pub) | |
| assert self.ec.mul(pub, self.n) == self.ec.zero | |
| return self.ec.mul(pub, priv) | |
| pass | |
| class DSA(object): | |
| """ECDSA | |
| - ec: elliptic curve | |
| - g: a point on ec | |
| """ | |
| def __init__(self, ec, g): | |
| self.ec = ec | |
| self.g = g | |
| self.n = ec.order(g) | |
| pass | |
| def gen(self, priv): | |
| """generate pub key""" | |
| assert 0 < priv and priv < self.n | |
| return self.ec.mul(self.g, priv) | |
| def sign(self, hashval, priv, r): | |
| """generate signature | |
| - hashval: hash value of message as int | |
| - priv: priv key as int | |
| - r: random int | |
| - returns: signature as (int, int) | |
| """ | |
| assert 0 < r and r < self.n | |
| m = self.ec.mul(self.g, r) | |
| return (m.x, inv(r, self.n) * (hashval + m.x * priv) % self.n) | |
| def validate(self, hashval, sig, pub): | |
| """validate signature | |
| - hashval: hash value of message as int | |
| - sig: signature as (int, int) | |
| - pub: pub key as a point on ec | |
| """ | |
| assert self.ec.is_valid(pub) | |
| assert self.ec.mul(pub, self.n) == self.ec.zero | |
| w = inv(sig[1], self.n) | |
| u1, u2 = hashval * w % self.n, sig[0] * w % self.n | |
| p = self.ec.add(self.ec.mul(self.g, u1), self.ec.mul(pub, u2)) | |
| return p.x % self.n == sig[0] | |
| pass | |
| if __name__ == "__main__": | |
| # shared elliptic curve system of examples | |
| ec = EC(1, 18, 19) | |
| g, _ = ec.at(7) | |
| # ElGamal enc/dec usage | |
| eg = ElGamal(ec, g) | |
| # mapping value to ec point | |
| # "masking": value k to point ec.mul(g, k) | |
| # ("imbedding" on proper n:use a point of x as 0 <= n*v <= x < n*(v+1) < q) | |
| mapping = [ec.mul(g, i) for i in range(ec.q)] | |
| plain = mapping[7] | |
| priv = 5 | |
| pub = eg.gen(priv) | |
| cipher = eg.enc(plain, pub, 15) | |
| decoded = eg.dec(cipher, priv) | |
| assert decoded == plain | |
| assert cipher != pub | |
| # ECDH usage | |
| dh = DiffieHellman(ec, g) | |
| apriv = 11 | |
| apub = dh.gen(apriv) | |
| bpriv = 3 | |
| bpub = dh.gen(bpriv) | |
| cpriv = 7 | |
| cpub = dh.gen(cpriv) | |
| # same secret on each pair | |
| assert dh.secret(apriv, bpub) == dh.secret(bpriv, apub) | |
| assert dh.secret(apriv, cpub) == dh.secret(cpriv, apub) | |
| assert dh.secret(bpriv, cpub) == dh.secret(cpriv, bpub) | |
| # not same secret on other pair | |
| assert dh.secret(apriv, cpub) != dh.secret(apriv, bpub) | |
| assert dh.secret(bpriv, apub) != dh.secret(bpriv, cpub) | |
| assert dh.secret(cpriv, bpub) != dh.secret(cpriv, apub) | |
| # ECDSA usage | |
| dsa = DSA(ec, g) | |
| priv = 11 | |
| pub = eg.gen(priv) | |
| hashval = 128 | |
| r = 7 | |
| sig = dsa.sign(hashval, priv, r) | |
| assert dsa.validate(hashval, sig, pub) | |
| pass |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment