Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- __author__ = 'Mr.DangThu_KMA'
- # Basics of Elliptic Curve Cryptography implementation on Python
- import collections
- def inv(n, q):
- for i in range(q):
- if (n * i) % q == 1:
- return i
- pass
- assert False, "unreached"
- pass
- def sqrt(n, q):
- assert n < q
- for i in range(1, q):
- if i * i % q == n:
- return (i, q - i)
- pass
- Coord = collections.namedtuple("Coord", ["x", "y"])
- class EC(object):
- """System of Elliptic Curve"""
- def __init__(self, a, b, q):
- 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
- 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):
- 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):
- 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
- """
- 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):
- 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) and g != self.zero
- for i in range(1, self.q + 1):
- if self.mul(g, i) == self.zero:
- return i
- pass
- pass
- if __name__=='__main__':
- print "Welcome to EC calculator"
- #input EC
- print "Please input p a b:"
- e = raw_input(">")
- e = e.split(" ")
- q = int(e[0])
- a = int(e[1])
- b = int(e[2])
- E = EC(a,b,q)
- #input P
- print "Please input P(x1,y1): "
- x1 = int(raw_input("x1="))
- y1 = int(raw_input("y1="))
- p1 = Coord(x1, y1)
- answer = raw_input("1: Add\n2: Multiplication\n")
- if (answer not in ['1','2']):
- answer = raw_input("1: Add\n2: Multiplication\n")
- if (answer=='1'):
- print "Please input Q(x2,y2)"
- x2 = int(raw_input("x2="))
- y2 = int(raw_input("y2="))
- p2 = Coord(x2, y2)
- kq = E.add(p1,p2)
- print "P + Q = ", kq
- if (answer == '2'):
- print "Please input k:"
- k = int(raw_input(">"))
- kq = E.mul(p1,k)
- print "%dP = " % k, kq
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement