Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Basic Montgomery ladder implementation. In the test it works with just numbers, but you can plug in any operation.
#!/usr/bin/python3 -O
from math import floor, log
def montgomery_ladder(x, n, op, select):
k = floor(log(n, 2)) + 1
x1 = x
x2 = op(x, x)
for i in range(k - 2, -1, -1):
bit = 1 if n & (1 << i) else 0
q = select(bit, x2, x1)
qq = op(q, q)
x1x2 = op(x1, x2)
x1 = select(bit, x1x2, qq)
x2 = select(bit, qq, x1x2)
return x1
def const_time_select(bit, a, b):
mask = bit - 1
return mask & b | ~mask & a
if __name__ == "__main__":
import dis
for instr in dis.Bytecode(const_time_select):
assert not instr.is_jump_target
for x in range(0, 10):
for n in range(1, 10):
assert montgomery_ladder(x, n, lambda a, b: a + b, const_time_select) == x*n
assert montgomery_ladder(x, n, lambda a, b: a * b, const_time_select) == x**n
print("self test passed")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.