OLD | NEW |
---|---|
(Empty) | |
1 # Author: Google | |
2 # See the LICENSE file for legal information regarding use of this file. | |
davidben
2015/04/02 00:20:36
FYI, Adam, I reindented and changed a few names on
| |
3 | |
4 import os | |
5 | |
6 p = ( | |
7 1157920892103562487626974469494075735300861434152903141955336313088670978539 51) | |
8 order = ( | |
9 1157920892103562487626974469494075735299969552241357603424222590610685120443 69) | |
10 p256B = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b | |
11 | |
12 baseX = 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296 | |
13 baseY = 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5 | |
14 basePoint = (baseX, baseY) | |
15 | |
16 | |
17 def _pointAdd(a, b): | |
18 Z1Z1 = (a[2] * a[2]) % p | |
19 Z2Z2 = (b[2] * b[2]) % p | |
20 U1 = (a[0] * Z2Z2) % p | |
21 U2 = (b[0] * Z1Z1) % p | |
22 S1 = (a[1] * b[2] * Z2Z2) % p | |
23 S2 = (b[1] * a[2] * Z1Z1) % p | |
24 if U1 == U2 and S1 == S2: | |
25 return pointDouble(a) | |
26 H = (U2 - U1) % p | |
27 I = (4 * H * H) % p | |
28 J = (H * I) % p | |
29 r = (2 * (S2 - S1)) % p | |
30 V = (U1 * I) % p | |
31 X3 = (r * r - J - 2 * V) % p | |
32 Y3 = (r * (V - X3) - 2 * S1 * J) % p | |
33 Z3 = (((a[2] + b[2]) * (a[2] + b[2]) - Z1Z1 - Z2Z2) * H) % p | |
34 | |
35 return (X3, Y3, Z3) | |
36 | |
37 | |
38 def _pointDouble(a): | |
39 delta = (a[2] * a[2]) % p | |
40 gamma = (a[1] * a[1]) % p | |
41 beta = (a[0] * gamma) % p | |
42 alpha = (3 * (a[0] - delta) * (a[0] + delta)) % p | |
43 X3 = (alpha * alpha - 8 * beta) % p | |
44 Z3 = ((a[1] + a[2]) * (a[1] + a[2]) - gamma - delta) % p | |
45 Y3 = (alpha * (4 * beta - X3) - 8 * gamma * gamma) % p | |
46 | |
47 return (X3, Y3, Z3) | |
48 | |
49 | |
50 def _square(n): | |
51 return (n * n) | |
52 | |
53 | |
54 def _modpow(a, n, p): | |
55 if n == 0: | |
56 return 1 | |
57 if n == 1: | |
58 return a | |
59 r = _square(_modpow(a, n >> 1, p)) % p | |
60 if n & 1 == 1: | |
61 r = (r * a) % p | |
62 return r | |
63 | |
64 | |
65 def _scalarMult(k, point): | |
66 accum = (0, 0, 0) | |
67 accumIsInfinity = True | |
68 jacobianPoint = (point[0], point[1], 1) | |
69 | |
70 for bit in range(255, -1, -1): | |
71 if not accumIsInfinity: | |
72 accum = _pointDouble(accum) | |
73 | |
74 if (k >> bit) & 1 == 1: | |
75 if accumIsInfinity: | |
76 accum = jacobianPoint | |
77 accumIsInfinity = False | |
78 else: | |
79 accum = _pointAdd(accum, jacobianPoint) | |
80 | |
81 if accumIsInfinity: | |
82 return (0, 0) | |
83 | |
84 zInv = _modpow(accum[2], p - 2, p) | |
85 return ((accum[0] * zInv * zInv) % p, (accum[1] * zInv * zInv * zInv) % p) | |
86 | |
87 | |
88 def _scalarBaseMult(k): | |
89 return _scalarMult(k, basePoint) | |
90 | |
91 | |
92 def _decodeBigEndian(b): | |
93 return sum([ord(b[len(b) - i - 1]) << 8 * i for i in range(len(b))]) | |
94 | |
95 | |
96 def _encodeBigEndian(n): | |
97 b = [] | |
98 while n != 0: | |
99 b.append(chr(n & 0xff)) | |
100 n >>= 8 | |
101 | |
102 if len(b) == 0: | |
103 b.append(0) | |
104 b.reverse() | |
105 | |
106 return "".join(b) | |
107 | |
108 | |
109 def _zeroPad(b, length): | |
110 if len(b) < length: | |
111 return ("\x00" * (length - len(b))) + b | |
112 return b | |
113 | |
114 | |
115 def _encodePoint(point): | |
116 x = point[0] | |
117 y = point[1] | |
118 if (y * y) % p != (x * x * x - 3 * x + p256B) % p: | |
119 raise "point not on curve" | |
120 return "\x04" + _zeroPad(_encodeBigEndian(point[0]), 32) + _zeroPad( | |
121 _encodeBigEndian(point[1]), 32) | |
122 | |
123 | |
124 def _decodePoint(b): | |
125 if len(b) != 1 + 32 + 32 or ord(b[0]) != 4: | |
126 raise "invalid encoded ec point" | |
127 x = _decodeBigEndian(b[1:33]) | |
128 y = _decodeBigEndian(b[33:65]) | |
129 if (y * y) % p != (x * x * x - 3 * x + p256B) % p: | |
130 raise "point not on curve" | |
131 return (x, y) | |
132 | |
133 | |
134 def generatePublicPrivate(): | |
135 """generatePublicPrivate returns a tuple of (X9.62 encoded public point, | |
136 private value), where the private value is generated from os.urandom.""" | |
137 private = _decodeBigEndian(os.urandom(40)) % order | |
138 return _encodePoint(_scalarBaseMult(private)), private | |
139 | |
140 | |
141 def generateSharedValue(theirPublic, private): | |
142 """generateSharedValue returns the encoded x-coordinate of the | |
143 multiplication of a peer's X9.62 encoded point and a private value.""" | |
144 return _zeroPad( | |
145 _encodeBigEndian(_scalarMult(private, _decodePoint(theirPublic))[0]), | |
146 32) | |
147 | |
148 if __name__ == "__main__": | |
149 alice, alicePrivate = generatePublicPrivate() | |
150 bob, bobPrivate = generatePublicPrivate() | |
151 | |
152 if generateSharedValue(alice, bobPrivate) != generateSharedValue( | |
153 bob, alicePrivate): | |
154 raise "simple DH test failed" | |
155 | |
156 (x, _) = _scalarBaseMult(1) | |
157 | |
158 for i in range(1000): | |
159 (x, _) = _scalarBaseMult(x) | |
160 | |
161 if x != 24282819652575985690405863180348125017294379467208082890495344928336 35302706: | |
162 raise "loop test failed" | |
OLD | NEW |