OLD | NEW |
(Empty) | |
| 1 # Author: Google |
| 2 # See the LICENSE file for legal information regarding use of this file. |
| 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 |