python/ecc.py at master · cepheidxa/python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#!/usr/bin/python3

import prime
import logging

"""Test ECC curve in ECC cryption algorithm."""

class Point:
    def __init__(self, x = 0, y= 0):
        self.__x = x
        self.__y = y
    @property
    def x(self):
        return self.__x
    @x.setter
    def x(self, value):
        self.__x = value
    @x.deleter
    def x(self):
        pass
    @property
    def y(self):
        return self.__y
    @y.setter
    def y(self, value):
        self.__y = value
    @y.deleter
    def y(self):
        pass
    def __str__(self):
        return ''.join(['(', str(self.__x), ',', str(self.__y), ')'])

class ZeroPoint(Point):
    def __init__(self):
        pass
    @property
    def x(self):
        pass
    @x.setter
    def x(self, value):
        pass
    @x.deleter
    def x(self):
        pass
    @property
    def y(self):
        pass
    @y.setter
    def y(self, value):
        pass
    @y.deleter
    def y(self):
        pass
    def __str__(self):
        return 'ZeroPoint'

class ECC:
    """Elliptic curve is y^2 = x^3 - ax - b (mod p)."""
    def __init__(self, a = 27397, b = 92791, p = 697967):
        self._a = a
        self._b = b
        self._p = p
        self._logger = logging.getLogger('test.ecc')
        self._G = None
    @property
    def G(self):
        if not self._G:
            return self.basePoint()
        else:
            return self._G
    @G.setter
    def G(self, value):
        pass
    @G.deleter
    def G(self):
        pass
    def add(self, p, q):
        r = Point()
        if isinstance(p, ZeroPoint):
            r = q
        elif isinstance(q, ZeroPoint):
            r = p
        elif p.x != q.x:
            s = (p.y - q.y) * prime.inv(p.x - q.x, self._p)
            r.x = (s ** 2 - p.x - q.x) % self._p
            r.y = ((p.y + s * (r.x - p.x)) * -1) % self._p
            if r.x < 0:
                r.x = r.x + self._p
            if r.y < 0:
                r.y = r.y + self._p
        elif (p.y + q.y) % self._p == 0:
            r = ZeroPoint()
        else:
            if p.y == 0:
                p, q = q, p
            s = (3 * p.x * p.x - self._a) * prime.inv(2 * p.y, self._p)
            r.x = (s ** 2 - 2 * p.x) % self._p
            r.y = ((p.y + s * (r.x - p.x)) * -1) % self._p
            if r.x < 0:
                r.x = r.x + self._p
            if r.y < 0:
                r.y = r.y + self._p
        return r
    def listPointGenerator(self):
        for i in range(self._p):
                y2 = (i ** 3 - self._a * i  - self._b) % self._p
                y = prime.sqrtmod(y2, self._p)
                if y:
                    p = Point(i, y)
                    yield p
                    p = Point(i, self._p - y)
                    yield p
    def basePoint(self, start = None):
        if not start:
            start = self._p // 2
        for i in range(start, self._p):
                y2 = (i ** 3 - self._a * i  - self._b) % self._p
                y = prime.sqrtmod(y2, self._p)
                if y:
                    return Point(i, y)
        return None
    def isInCurve(self, point):
        if isinstance(point, ZeroPoint):
            return True
        y2 = (point.y ** 2) % self._p
        t = (point.x ** 3 - self._a * point.x - self._b) % self._p
        return (y2 - t) % self._p == 0