Photo by Chris Briggs on Unsplash

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):  9
Bob 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): 8
Bob 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:

Cryptography Dispatches: Is X25519 Associative? Sometimes!