Coverage for /var/srv/projects/api.amasfac.comuna18.com/tmp/venv/lib/python3.9/site-packages/ellipticcurve/math.py: 21%

1from .point import Point 

2 

3 

4class Math: 

5 

6 @classmethod 

7 def modularSquareRoot(cls, value, prime): 

8 return pow(value, (prime + 1) // 4, prime) 

9 

10 @classmethod 

11 def multiply(cls, p, n, N, A, P): 

12 """ 

13 Fast way to multily point and scalar in elliptic curves 

14 

15 :param p: First Point to mutiply 

16 :param n: Scalar to mutiply 

17 :param N: Order of the elliptic curve 

18 :param P: Prime number in the module of the equation Y^2 = X^3 + A*X + B (mod p) 

19 :param A: Coefficient of the first-order term of the equation Y^2 = X^3 + A*X + B (mod p) 

20 :return: Point that represents the sum of First and Second Point 

21 """ 

22 return cls._fromJacobian( 

23 cls._jacobianMultiply(cls._toJacobian(p), n, N, A, P), P 

24 ) 

25 

26 @classmethod 

27 def add(cls, p, q, A, P): 

28 """ 

29 Fast way to add two points in elliptic curves 

30 

31 :param p: First Point you want to add 

32 :param q: Second Point you want to add 

33 :param P: Prime number in the module of the equation Y^2 = X^3 + A*X + B (mod p) 

34 :param A: Coefficient of the first-order term of the equation Y^2 = X^3 + A*X + B (mod p) 

35 :return: Point that represents the sum of First and Second Point 

36 """ 

37 return cls._fromJacobian( 

38 cls._jacobianAdd(cls._toJacobian(p), cls._toJacobian(q), A, P), P, 

39 ) 

40 

41 @classmethod 

42 def inv(cls, x, n): 

43 """ 

44 Extended Euclidean Algorithm. It's the 'division' in elliptic curves 

45 

46 :param x: Divisor 

47 :param n: Mod for division 

48 :return: Value representing the division 

49 """ 

50 if x == 0: 

51 return 0 

52 

53 lm = 1 

54 hm = 0 

55 low = x % n 

56 high = n 

57 

58 while low > 1: 

59 r = high // low 

60 nm = hm - lm * r 

61 nw = high - low * r 

62 high = low 

63 hm = lm 

64 low = nw 

65 lm = nm 

66 

67 return lm % n 

68 

69 @classmethod 

70 def _toJacobian(cls, p): 

71 """ 

72 Convert point to Jacobian coordinates 

73 

74 :param p: First Point you want to add 

75 :return: Point in Jacobian coordinates 

76 """ 

77 return Point(p.x, p.y, 1) 

78 

79 @classmethod 

80 def _fromJacobian(cls, p, P): 

81 """ 

82 Convert point back from Jacobian coordinates 

83 

84 :param p: First Point you want to add 

85 :param P: Prime number in the module of the equation Y^2 = X^3 + A*X + B (mod p) 

86 :return: Point in default coordinates 

87 """ 

88 z = cls.inv(p.z, P) 

89 x = (p.x * z ** 2) % P 

90 y = (p.y * z ** 3) % P 

91 

92 return Point(x, y, 0) 

93 

94 @classmethod 

95 def _jacobianDouble(cls, p, A, P): 

96 """ 

97 Double a point in elliptic curves 

98 

99 :param p: Point you want to double 

100 :param P: Prime number in the module of the equation Y^2 = X^3 + A*X + B (mod p) 

101 :param A: Coefficient of the first-order term of the equation Y^2 = X^3 + A*X + B (mod p) 

102 :return: Point that represents the sum of First and Second Point 

103 """ 

104 if p.y == 0: 

105 return Point(0, 0, 0) 

106 

107 ysq = (p.y ** 2) % P 

108 S = (4 * p.x * ysq) % P 

109 M = (3 * p.x ** 2 + A * p.z ** 4) % P 

110 nx = (M**2 - 2 * S) % P 

111 ny = (M * (S - nx) - 8 * ysq ** 2) % P 

112 nz = (2 * p.y * p.z) % P 

113 

114 return Point(nx, ny, nz) 

115 

116 @classmethod 

117 def _jacobianAdd(cls, p, q, A, P): 

118 """ 

119 Add two points in elliptic curves 

120 

121 :param p: First Point you want to add 

122 :param q: Second Point you want to add 

123 :param P: Prime number in the module of the equation Y^2 = X^3 + A*X + B (mod p) 

124 :param A: Coefficient of the first-order term of the equation Y^2 = X^3 + A*X + B (mod p) 

125 :return: Point that represents the sum of First and Second Point 

126 """ 

127 if p.y == 0: 

128 return q 

129 if q.y == 0: 

130 return p 

131 

132 U1 = (p.x * q.z ** 2) % P 

133 U2 = (q.x * p.z ** 2) % P 

134 S1 = (p.y * q.z ** 3) % P 

135 S2 = (q.y * p.z ** 3) % P 

136 

137 if U1 == U2: 

138 if S1 != S2: 

139 return Point(0, 0, 1) 

140 return cls._jacobianDouble(p, A, P) 

141 

142 H = U2 - U1 

143 R = S2 - S1 

144 H2 = (H * H) % P 

145 H3 = (H * H2) % P 

146 U1H2 = (U1 * H2) % P 

147 nx = (R ** 2 - H3 - 2 * U1H2) % P 

148 ny = (R * (U1H2 - nx) - S1 * H3) % P 

149 nz = (H * p.z * q.z) % P 

150 

151 return Point(nx, ny, nz) 

152 

153 @classmethod 

154 def _jacobianMultiply(cls, p, n, N, A, P): 

155 """ 

156 Multily point and scalar in elliptic curves 

157 

158 :param p: First Point to mutiply 

159 :param n: Scalar to mutiply 

160 :param N: Order of the elliptic curve 

161 :param P: Prime number in the module of the equation Y^2 = X^3 + A*X + B (mod p) 

162 :param A: Coefficient of the first-order term of the equation Y^2 = X^3 + A*X + B (mod p) 

163 :return: Point that represents the sum of First and Second Point 

164 """ 

165 if p.y == 0 or n == 0: 

166 return Point(0, 0, 1) 

167 

168 if n == 1: 

169 return p 

170 

171 if n < 0 or n >= N: 

172 return cls._jacobianMultiply(p, n % N, N, A, P) 

173 

174 if (n % 2) == 0: 

175 return cls._jacobianDouble( 

176 cls._jacobianMultiply(p, n // 2, N, A, P), A, P 

177 ) 

178 

179 return cls._jacobianAdd( 

180 cls._jacobianDouble(cls._jacobianMultiply(p, n // 2, N, A, P), A, P), p, A, P 

181 )