Tag Info

Accepted

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 ...
• 85.7k
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; ...
• 45.5k
Accepted

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 ...
• 7,419

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$ ...
• 1,719

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 ...
• 4,862

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 ...
• 17.1k

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$
• 138k

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 ...
• 1,840
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 ...
1 vote
Accepted

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 ...
• 1,840
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.
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 ...
• 85
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 ...
• 46.8k
1 vote
Accepted

• 726
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)...
• 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 ...
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 ...
• 161

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