Clamping With Curve 25519 (X25519)
I has a problem to solve recently. In ECDH (Elliptic Curve Diffie-Hellman) with X25519 — and which uses Curve 25519 rather than NIST P256. With this, 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 they 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 to compute (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 bits are masked, so that the three least significant bits 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’
And it works! Ah, ha! If you want to read more, try here: