https://www.rfc-editor.org/rfc/rfc7748 gives a simple implementation of scalar multiplication on curve25519. They have some Python code and some pseudocode, and I tried my best to connect all of it into a single Python application. There is also a piece of code which I had to write from scratch, and by that I mean exponentiation of big numbers modulo p. The final product doesn't seem to work. It fails on elementary stuff like multiplying the base element by 1 (that is X25519(1, 9) != 9), and on tests provided by the document itself. At first I thought that I may be passing incorrectly formatted input, but I tried many combinations of the test values and it seems like the issue isn't there. My current guess is that I got the modulo arithmetic wrong. Please help Here's my code:
p = 2**255 - 19
a24 = 121665
bits = 255
def power_mod_p(b, e):
powers = [b]
for i in range(1, 256):
powers.append((powers[i-1] ** 2) % p)
result = 1
for i in range(256):
if (e >> i) & 1:
result = (result * powers[i]) % p
return result
def cswap(swap, x_2, x_3):
dummy = (0 - swap) & (x_2 ^ x_3)
x_2 = x_2 ^ dummy
x_3 = x_3 ^ dummy
return (x_2, x_3)
def X25519(k, u):
x_1 = u
x_2 = 1
z_2 = 0
x_3 = u
z_3 = 1
swap = 0
for t in reversed(range(255)):
k_t = (k >> t) & 1
swap = swap ** k_t
(x_2, x_3) = cswap(swap, x_2, x_3)
(z_2, z_3) = cswap(swap, z_2, z_3)
swap = k_t
A = x_2 + z_2
AA = A*A
B = x_2 - z_2
BB = B*B
E = AA - BB
C = x_3 + z_3
D = x_3 - z_3
DA = D * A
CB = C * B
x_3 = ((DA + CB) ** 2) % p
z_3 = (x_1 * (DA - CB) ** 2) % p
x_2 = (AA * BB) % p
z_2 = (E * (AA + a24 * E)) % p
(x_2, x_3) = cswap(swap, x_2, x_3)
(z_2, z_3) = cswap(swap, z_2, z_3)
return (x_2 * (power_mod_p(z_2, p - 2))) % p
def main():
# this first test is from the document, and it produces a bad result
print(hex(X25519(31029842492115040904895560451863089656472772604678260265531221036453811406496, 34426434033919594451155107781188821651316167215306631574996226621102155684838)))
print(X25519(1, 9)) # should print 9 according to the theory, instead prints nonsense
if __name__ == "__main__":
main()
If you take a look at the end of the X25519 function, you will see that I added % p in some places. I assume that the pseudocode didn't explicitly include something like this, because it is mensioned in the document that all calculations are performed modulo p.
Another idea I just had is that maybe I interpreted some of the pseudocode incorrectly. For example, I assumed that the pseudocode's a ^= b is equivalent to Python's a = a ** b. I'm not 100% sure about it, because I see the '^' symbol used for XOR most of the times, but at some point in the document they explicitly do something like x XOR y to denote XOR, and I don't think that XORing with 2 makes the most sense. But I don't know anything at this point. I've spent much more time than I would like to admit trying to figure out what's wrong here. I will very fondly remember anyone who would be able to help me out.
