11 votes
Accepted

Advantages of Montgomery Ladder-based Scalar Multiplication

Synthetically, the advantages of the Montgomery ladder are that it is simple and fast. If you look at X25519, the Diffie-Hellman algorithm applied to Curve25519 and described in RFC 7748, you will see ...
user avatar
7 votes
Accepted

How does Montgomery reduction work?

In 1985, Montgomery introduced a new clever way to represent the numbers $\mathbb{Z}/n \mathbb{Z}$ such that arithmetic, especially the modular multiplications become easier. Peter L. Montgomery; ...
user avatar
  • 43.1k
5 votes
Accepted

Questions about the Curve25519-donna implementation

You have 5 limbs because it is based on DJB's papers and as the Ed25519 paper mentions, it's using a $2^{51}$ radix representation for performance reasons. It does so in order to avoid carries when ...
user avatar
  • 7,163
5 votes

RSA Timing Attack on "Extra" Montgomery Reduction

Montgomery multiplication Theorem (Montgomery, 1985). For any odd integer $N$ and any integer $0 \le T < N2^k$, one has: $$T 2^{-k} \equiv \frac{T + UN}{2^k} \pmod N$$ where $U = T N' \bmod 2^k$ ...
user avatar
  • 1,679
4 votes

RSA Timing Attack on "Extra" Montgomery Reduction

What a coincidence, I implemented this attack yesterday! I'm executing it right now and I can tell you that the difference at each step is around 1 reduction (as the paper suggests). See for example ...
user avatar
  • 4,822
3 votes

Where to apply Montgomery Multiplication in GF(2^n)

The usual motivation for using Montgomery multiplication is that it significantly reduces the cost of modular reduction by changing the representation of elements. In the Montgomery ring the ...
user avatar
  • 9,671
3 votes

Meaning of pseudocode "$(C, S):=$"

I believe that the meaning is "compute the $2n$-bit value $a[j]*b[0] + C$, and then assign the top $n$ bits to $C$ and the bottom $n$ bits into $S$
user avatar
  • 131k
2 votes

What happens if no final subtraction is done in Montgomery multiplication?

Theorem 2 in [Dussé et al. 1991] states that, if we skip the final subtraction, then, for $N < R / 4$ and $0 \leq A, B < 2 N$, we have $0 \leq C = \text{MonMul}(A B) < 2 N$, while keeping $C \...
user avatar
  • 21
2 votes

Montgomery multiplication without final subtraction

Brett just asked & answered this question : Confused about final subtraction of modulus in Montgomery Multiplication, during modular exponentiation You should increase $R$ exponent by $2$. If you ...
user avatar
  • 21
2 votes
Accepted

Understanding Montgomery's parameterization of elliptic curves

Write $(x_i, y_i) = (X_i : Y_i : Z_i)$, so that $x_i = X_i/Z_i$ and $y_i = X_i/Z_i$, where $Z_i \ne 0$ is arbitrary. (If you are not familiar with projective coordinates or you like visuals, see an ...
user avatar
2 votes

Where to apply Montgomery Multiplication in GF(2^n)

Where to apply Montgomery Multiplication in $GF(2^n)$? This answer really depends on how you constructed the binary extension field $GF(2^n)$. If the irreducible polynomial is trinomial or ...
user avatar
  • 43.1k
2 votes
Accepted

Montgomery Multiplication with CRT

The issue is, the message length is now longer than the modulus $p$ and $q$ That's not true. In the $p$ track, you are raising $M \bmod p$ to the power $d \bmod p-1$; we have $M \bmod p < p$; ...
user avatar
  • 131k
2 votes
Accepted

Montgomery Algorithm

The confusion comes from the choice of representation. I'd a quick look to the referenced paper, where the autors use a 2-radix representation. Then you shoud initialise $e=\frac{m+15}{w}$ instead of $...
user avatar
1 vote

Why is Montgomery Ladder fast on Montgomery Curves?

Elliptic curves can be represented in different form. The most basic equation, in which every elliptic curve can be represented is the Weierstraß equation: $$ y^2 = x^3 + ax + b$$ For a Montgomery ...
user avatar
  • 1,482
1 vote

Where to apply Montgomery Multiplication in GF(2^n)

The key to Montgomery Multiplication is the prescaling of one or two of the inputs by $r^k$ as stated in this answer by kelalaka to How Does Montgomery Reduction Work. In the case of polynomial ...
user avatar
1 vote
Accepted

Montgomery Ladder with affin/projective Coordinates

Maybe one day someone finds this Post again and has the same questions. To you: I hope you're having a great day! Questions: The projective Arithmetic is faster, because there are only ...
user avatar
  • 1,482
1 vote
Accepted

What scalars produce the wrong values with X25519's montgomery ladder?

Actually, the answer is none. Everything works, and produces the correct results. Potential problems arise when converting back to Twisted Edwards space, and that's a different question.
user avatar
1 vote
Accepted

Question about using Montgomery form for elliptic curve operations on bls12-381

I figured this out, the best approach is to use either Montgomery or Barrets algorithm for modulo reduction, Barrets requires a slightly higher bit multiplication but not pre-transformation, while ...
user avatar
1 vote
Accepted

montgomery reduction multiplicative identity

The additive identity is $0$, as usual. The multiplicative identity is the Montgomery representative for $1$, namely $1\cdot R \bmod N = R \bmod N$, just like the Montgomery representative for any ...
user avatar
1 vote
Accepted

Montgomery Reduction - Conditions on R

First of all, The Montgomery's Reduction algorithm requires that $\operatorname{GCD}(n,R)=1$ . This requirement is satisfied iff $n$ is odd. The $R$ is chosen as $2^l$ where $ 2^{l-1} \leq n < 2^{...
user avatar
  • 43.1k
1 vote
Accepted

Confused about final subtraction of modulus in Montgomery Multiplication, during modular exponentiation

The problem was that there was one additional thing I left out....if I'm increasing the loop iteration count and the number of bits from 2048 to 2050, then I had to choose a new R to satisfy the ...
user avatar
  • 161
1 vote

Montgomery multiplication without final subtraction

The above mentioned work is focused on a hardware implementation (I have this work as a PDF). I'd suggest you to search for: Colin D. Walter. Montgomery Exponentiation Needs no Final Subtractions. ...
user avatar
  • 286
1 vote

Why should $a,b < N$ for Montgomery Reduction?

Looks like misunderstanding to me: you are asking about Montgomery reduction but your example is about Montgomery multiplication. Montgomery reduction inputs a number in range $[0..NR-1]$ and outputs ...
user avatar
  • 716
1 vote

Montgomery Reduction

Consult the transcript from the class, there is an example he works through which is very similar to this problem. Fundamentally you're trying to solve the problem c = (T + T(-N^-1) (mod R)N)/R (mod N)...
user avatar
  • 11
1 vote
Accepted

Montgomery and Galois fields

I've already replied to the question posted some days before. Montgomery multiplication is another way to perform modular multiplication in the residue system representation. The operation induced is ...
user avatar
1 vote

Montgomery Algorithm

@haster8558 I know this is late, but I am struggling with the same problem. I do have a few answers for you though... I dont understand why I the number of the word are linked to the width of the ...
user avatar
  • 161

Only top scored, non community-wiki answers of a minimum length are eligible