Questions tagged [montgomery-multiplication]
A modular multiplication algorithm invented by Montgomery that allows modular arithmetic to be performed efficiently when the modulus is large (typically several hundred bits).
4
questions
7
votes
2answers
953 views
RSA Timing Attack on “Extra” Montgomery Reduction
In "A practical implementation of the timing attack", the authors take advantage of a timing difference that stems from "extra reductions" that occur when multiplying numbers in the Montgomery form. ...
4
votes
1answer
138 views
How does Montgomery reduction work?
I want to reduce a multi-precision integer $x$ modulo a prime $p$, very fast. Performing the traditional Euclidean division for only calculating the modulo, is inefficient and modular reduction is at ...
4
votes
1answer
545 views
What is a u-coordinate within Elliptic Curve Diffie-Hellman using the Montgomery ladder
I am trying to understand the below paragraph.
Elliptic curve Diffie-Hellman is often calculated using the Montgomery
ladder. This gives a simple and efficient calculation that is
naturally ...
0
votes
1answer
431 views
Confused about final subtraction of modulus in Montgomery Multiplication, during modular exponentiation
I'm confused about how one might supposedly bypass the final subtraction of the modulus in radix-2 montgomery modular multiplication, when used in a modular exponentiation algorithm. The following two ...