Curve 25519 is one of the most widely used ECC methods. It uses a curve of \(y^2 = x^3 + 486662 x^2 + x\) [plot], and which is a Montgomery curve. The prime number used is \(2^{255}-19\). This page implements ECDH, and which is the method used in Tor to exchange the key. In this case we will use Python to implement X25519 (and which uses Curve 25519), but only uses the x-axis point for the sharing of values. The base point \(G\) on Curve 25519 is (9,1478161944 ... 7755586237401)[here] and the paramaters based by on RFC 7748 [here]. We will illustrate the clamping method in X25519, and where the three least significant bits are set to zero.
X25519 with Clamping |
Method
In ECDH (Elliptic Curve Diffie-Hellman), Alice generates a and Bob generates b. Next Alice computes aG (and which is the point G added a times), and Bob computes bG. They pass these values and then Alice computes a(bG) and Bob computes b(aG), and the end up with abG, and have a shared key. Here is an example [here]:
Bob private (b): 10 Alice private (a): 9Bob public (bG): b'c288c2bc5d7953c290c2a25433c39e41c3a7c29e4a0368c2822b4e3cc383c3b13709c2a554c391005dc2ab467e' Alice public (aG): b'c3900b0269c3b66758c3b27ac2afc3833b33c28e0ac3ac21c39bc3be73c38128c2ba75c29fc2b4c3a043c2a10b2b54'Bob shared (b)aG: b'564521c2b742c3934b36c3adc3b4127b2bc29ec38dc2890fc39b510b53083bc3a004174860c39ec3ab5d1f' Alice shared (a)bG: b'564521c2b742c3934b36c3adc3b4127b2bc29ec38dc2890fc39b510b53083bc3a004174860c39ec3ab5d1f'
The code is here:
And so I tried by computing (ab) G, and where we multiply a by b, and then perform the multiplication:
print (“\n\nJust checking ...”) res=(bytes_to_int(a)*bytes_to_int(b)) k = base_point_mult(int_to_bytes(res,32)) print (“\n\nChecking shared (ab)G:\t”,binascii.hexlify(k.encode()))
And the answer is not the same as a(bG) and b(aG):
Just checking … Checking shared (ab)G: b’2fc3a57dc2a347c38d62431528c39ac2ac5fc2bb290730c3bfc3b6c284c2afc384c38fc382c3adc290c2995f58c38b3b74'
So what’s the problem? Well, it took me a while to realise, but it’s all to do with clamping, and where the least significant by is masked, so that the three last signifcant bytes are set to zero:
def clamp(n): n &= ~7 n &= ~(128 << 8 * 31) n |= 64 << 8 * 31 return n
Thus the value of 9 (1001) will be 8 (1000) and the value of 10 (1010) will also be 8 (1010). Thus we actually have 8 times 8 which is 64.
Bob private (b): 8 Alice private (a): 8Bob public (bG): b’0bc386c28f6872172fc29dc2a9c3835bc3a0c28276c2a636c2a804c29d4426c39cc2b5067c56c2b81138504d6a’ Alice public (aG): b’0bc386c28f6872172fc29dc2a9c3835bc3a0c28276c2a636c2a804c29d4426c39cc2b5067c56c2b81138504d6a’Bob shared (b)aG: b’c2ac54c3b0546711c2956fc2b2035ac2a4c2a531c2b1c293731d65c2916ac2b4c3aac287c2961714024fc392c2a17b’ Alice shared (a)bG: b’c2ac54c3b0546711c2956fc2b2035ac2a4c2a531c2b1c293731d65c2916ac2b4c3aac287c2961714024fc392c2a17b’Just checking …Checking shared (ab)G: b’c2af6c6bc3a037c38c0622c3a8c28a735ac298c3b77ac3806f372bc2adc28542c2bc0f65c380c385c280c2b0c295c2ae4e’
X25519 thus uses clamping.