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).
47
questions
1
vote
0
answers
62
views
How to recover y-coordinates when using XZ montgomery curve
I am using Montgomery ladder with Montgomery curve $by^2=x^3+ax^2+x$ using XZ coordinates and I recovered the $X$ value using $X3=X1/Z1$, but I don't know how to recover the $Y$ coordinates.
for ...
- 209
2
votes
1
answer
69
views
What is the equation to get P-Q in Montgomery curve XZ coordinates
Based on Differentia-addition on P I can understand (Xp,Zp) which is the base point, (Xq,Zq) which comes from Doubling, but I ...
- 209
1
vote
0
answers
63
views
XZ coordinates for Montgomery curves
I am learning about Elliptic curve and I reached to Montgomery curve with XZ coordinates with this equation: b*y2=x3+a*x2+x and regarding the information from this ...
- 209
1
vote
0
answers
29
views
How does the Mongomery Algorithm work? [closed]
can someone please explain to me what's the role of montgomery reduction algorithm and how to implement it in python. I wrote the code below to calculate a*b mod m but it doesn't seem to work well.
...
- 11
3
votes
0
answers
134
views
Fast polynomial multiplication over finite field GF(2^n)
I wonder if there is a more efficient polynomial multiplication than Karatsuba over the finite field $\operatorname{GF}(2^n)$. Brief research on this topic gave me a few results on fast multiplication ...
- 31
0
votes
0
answers
73
views
Fast methods for adding the basepoint to an elliptic curve point?
Are there any clever (fast) methods for adding the basepoint (generator) to an arbitrary point on elliptic curve, finally ending in affine coordinates?
I.e. if G is ...
- 1
1
vote
0
answers
54
views
Montgomery algorithms for Lattice based schemes [closed]
Why most of Lattice based scheme use Montgomery Multiplication algorithm?
- 396
5
votes
1
answer
244
views
Why is Montgomery Ladder fast on Montgomery Curves?
When I look at the Montgomery Ladder algorithm, I don't find anything that is specific to the Montgomery curve. We are dealing with the points all the time i.e. we are either adding two points or ...
3
votes
0
answers
126
views
No Final subtraction in Word-level Montgomery Multiplication
I am trying to make an RSA module in VHDL, which in turn will be deployed to an FPGA. I am trying to implement a full Montgomery algorithm which means that I am working with the Montgomery ...
- 31
1
vote
0
answers
97
views
Is it possible to apply the El Gamal encryption/decryption technique using Edwards curve in Montgomery form
I've been trying to understand the ElGamal encryption/decryption technique. I plan to use it for sending a private message to the server. That is: Alice needs to send $Pm$ (private message encoded via ...
2
votes
3
answers
401
views
Where to apply Montgomery Multiplication in GF(2^n)
I'm optimizing a Reed Solomon decoding library for several polynomials in $\operatorname{GF}(2^k)$, $k\in\{8,10,12\}$.
Reading about the Montgomery Multiplication from Çetin K. Koç & Tolga Acar's ...
- 131
1
vote
0
answers
81
views
Missing Final Step in Montgomery Reduction
I'm following well with using the shifting method to try out the Montgomery reduction (1st round).
However, the computed result is actually equal to:
$$XYR^{-1} \bmod N$$
while the final goal is to ...
- 61
6
votes
1
answer
1k
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 ...
- 968
2
votes
1
answer
303
views
Montgomery Multiplication with CRT
I am attempting to understand how to use Montgomery multiplication in an RSA private key operation: $X \equiv a^{e} \pmod{n}$ where $a$ is the message, $e$ is the exponent, $n$ is the modulus.
Using ...
- 123
1
vote
0
answers
41
views
Size of messages in timing attack on RSA Montgomery
I'm codin' timing attack on RSA Montgomery which compares two sets ( the first one includes those which need a reduction in contrary to the second one ). But I got troubles with the Montgomery ...
0
votes
0
answers
143
views
Can someone explain the timing attack on RSA with Montgomery multiplication?
I have read several articles on the temporal attack against Montgomery multiplication to speedup RSA computations. However, I do not quite get the principle.
I understood that there is a additional ...
1
vote
1
answer
308
views
Montgomery Ladder with affin/projective Coordinates
So I'm trying to understand why the montgomery arithmetic is fast and what the montgomery ladder is.
With this Post i understood the basic affin arithmetic and Ladder.
So this is not really faster ...
- 1,900
3
votes
0
answers
115
views
Attack on Weierstrass Elliptic Curve
I have a naive question(as non specialist in this field).
While reading Weierstrass Curve description,I found that it turns into 2 periodic tori on 2D complex plane.
Is is it possible to create ...
- 31
1
vote
2
answers
203
views
Understanding Montgomery's parameterization of elliptic curves
I'm having a bit of trouble understanding the translation of affine coordinates to projective coordinates in Montgomery curve ECM. Would be very thankful if someone could explain it by expanding the ...
- 411
0
votes
0
answers
89
views
GCD in Montgomery arithmetic
Wikipedia article on Montgomery modular multiplication contains the following statement:
Many operations of interest modulo $N$ can be expressed equally well in Montgomery form. Addition, ...
- 558
4
votes
1
answer
280
views
How to use Montgomery arithmetic for elliptic curves (FIAT cryptography)
Let us consider the source code for curve P-256 from BoringSSL. This source code can be found here. This source code uses the FIAT generated implementation for field arithmetic. This implementation ...
- 327
1
vote
1
answer
241
views
Question about using Montgomery form for elliptic curve operations on bls12-381
Since the prime for bls12-381 is not of a form to allow easy modular reduction , is the best approach to use the Montgomery multiplication + reduction algorithm?
...
- 85
0
votes
1
answer
55
views
montgomery reduction multiplicative identity
How do you figure out the multiplicative and additive identity with respects to R?
I pick some R such that gcd(R, N) = 1 where N is the size of the group.
Given some field element x in the group, I ...
- 1,263
0
votes
0
answers
55
views
Speeding up quotient determination in high-radix montgomery modular multiplication
In this paper Simplifying Quotient Determination in High-Radix Modular Multiplication, the authors have proposed to replace the original modulus $M$ in Montgomery Multiplication $ABR^{-1} \bmod{M}$ to ...
- 1
1
vote
1
answer
132
views
Montgomery Reduction - Conditions on R
In Montgomery Reduction, we need to compute $z = x y \text{ mod } N$ and the Montgomery Reduction of $x$ is $xR^{-1}$.
Why should the choice of $R$ be $2^l$ where $l$ is the length of $N$ to the ...
- 249
2
votes
1
answer
854
views
Questions about the Curve25519-donna implementation
I'm trying to understand the implementation of the following function:
Please note questions in comments.
...
- 234
4
votes
0
answers
1k
views
Fastest known Elliptic Curve Cryptography "solution" (coordinate systems (multiple?), algorithms, precomputed values etc)?
I am writing an Elliptic Curve Cryptography SDK in pure Swift, and currently I am only using Affine Point and simple Double-and-add. I am soon about to work on a faster solution.
I am asking for help ...
- 151
1
vote
1
answer
229
views
What scalars produce the wrong values with X25519's montgomery ladder?
This question is a consequence of an older one about multiplying a twisted Etwards point in Montgomery space. Turns out that this is unsafe in some circumstances.
The following Montgomery ladder as ...
8
votes
2
answers
1k
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. ...
- 363
1
vote
1
answer
523
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 ...
- 161
3
votes
0
answers
234
views
Montgomery modular multiplication – confusion with subtraction of modulus
I'm reading the paper “COMPARISON OF SCALABLE MONTGOMERY MODULAR MULTIPLICATION IMPLEMENTATIONS EMBEDDED IN RECONFIGURABLE HARDWARE” (PDF) on hardware algorithms for montgomery multiplication for ...
- 161
5
votes
2
answers
3k
views
Advantages of Montgomery Ladder-based Scalar Multiplication
I do not quite understand what the greatest advantages are of using the Montgomery ladder algorithm for scalar multiplication?
Can someone help me out?
- 53
4
votes
1
answer
786
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 ...
- 257
1
vote
2
answers
605
views
Montgomery multiplication without final subtraction
I am looking for methods to avoid the final subtraction in Montgomery multiplication. I found this paper "A Cryptographic Library for the Motorola DSP56000 " (http://goo.gl/DHePEx) In this paper they ...
- 1,235
4
votes
2
answers
223
views
Why should $a,b < N$ for Montgomery Reduction?
In Montgomery reduction, when calculating $a \times b \mod N$, it is required that $a \lt N$ and $b \lt N$.
I think $0 \le T \lt N \times R$ is enough for the Montgomery Reduction.
Rationale:
Let $a'...
- 41
2
votes
1
answer
117
views
Meaning of pseudocode "$(C, S):=$"
I've seen pseudocode of this form in the Montgomery multiplication related theses: $(C, S) := a[j]*b[0]+C$.
What's the meaning of "$(C, S):=$", or what is the real code that was converted from this ...
- 21
3
votes
1
answer
305
views
What happens if no final subtraction is done in Montgomery multiplication?
I'm doing Montgomery arithmetic modulo $N = 2^{255}-19$ for the Curve25519, picking $R = 2^{256}$ for Montgomery.
After multiplying two numbers $0 \leq A,B < N$ in the Montgomery representation ...
- 397
3
votes
2
answers
3k
views
Montgomery Reduction
I'm taking a hardware cryptography class and working on a problem that focuses on Montgomery Reduction.
So by definition:
Computing $a * b \text{ mod } N$
Pick $R$, s.t. $R > N$, $gcd(R,N) = 1$
...
- 31
2
votes
0
answers
91
views
Implementing modular reductions (n*n) [closed]
I'm implementing a public key cryptosystem in a proprietary System On Chip that only allows modular reductions by $n$.
However, that cryptosystem requires ($n^2$) modular reductions. Perhaps someone ...
- 21
-1
votes
1
answer
308
views
Montgomery and Galois fields
I'm a little bit confused about the design of a RSA module in VHDL. My question isn't directly related to hardware design. I've read a lot of publications and I bought also a book. In one publications ...
- 227
1
vote
2
answers
646
views
Montgomery Algorithm
I'm trying to understand how it works and how to implement the algorithm described in
this paper. The paper shows a methods to compute a modular multiplication where it is used multiplier with a ...
- 227
0
votes
0
answers
316
views
Montgomery Multiplication in FPGA explanation
I'm trying to implement an RSA module in a FPGA. I choose to use Montgomery multiplication. I've found a document where the Montgomery Multiplication is pretty clear. I don't understand only a step.
...
- 227
1
vote
0
answers
503
views
RSA timing attack
Given an RSA implementation that uses Montgomery multiplications and CIOS exp algo, but NOT CRT.
Given a decryption1 oracle that takes chosen cipher text and responds the plain text and the time it ...
- 11
4
votes
1
answer
811
views
Blockwise Montgomery multiplication
I have to implement a 256*256 bit Montgomery multiplier for pairing computations. The straightforward approach is to use a bit-serial version, but I would like to utilize the built-in 64*64 bits ...
- 307
9
votes
1
answer
6k
views
Which one is fastest? Karatsuba or Montgomery multiplication?
Is there any complexity analysis between Karatsuba and Montgomery multiplication algorithms? It seems that Karatsuba is more general in the sense that is not modulo tuned while Montgomery it is. Does ...
- 6,052
4
votes
1
answer
2k
views
Efficient setup for a Montgomery multiplication
Montgomery described an efficient method to compute a modular multiplication. This works by using a special constant $R$ and assumes the inputs $a$ and $b$ have been made into a special representation ...
- 1,238
2
votes
1
answer
1k
views
Montgomery Exponentiation - selecting input value R for a given BigInteger
I have Montgomery exponentiation working, but it's working quite slow. I suspect there are two reasons for this - I implemented it bit size instead of word size (I didn't realize at the time that ...
- 205