Questions tagged [montgomery-multiplication]

A modular multiplication algorithm invented by Peter Montgomery that allows modular arithmetic to be performed efficiently when the modulus is large (typically several hundred bits).

Filter by
Sorted by
Tagged with
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 ...
curious's user avatar
  • 6,160
8 votes
2 answers
2k 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. ...
kkl's user avatar
  • 383
7 votes
1 answer
2k 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 ...
Aravind A's user avatar
  • 1,020
5 votes
1 answer
620 views

Reverse engineering hardware crypto processor for modular multiplication

I'm currently working with an undocumented crypto offload processor that is capable of accelerating modular multiplication in some fashion. I need to figure out what operation it is implementing ...
Hendi's user avatar
  • 53
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 ...
bob's user avatar
  • 1,238
4 votes
1 answer
818 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 ...
Khalid's user avatar
  • 307
4 votes
1 answer
397 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 ...
mip's user avatar
  • 327
4 votes
2 answers
227 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'...
Alpha's user avatar
  • 41
3 votes
1 answer
335 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 ...
NumberFour's user avatar
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$ ...
linos's user avatar
  • 31
3 votes
0 answers
310 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 ...
Lukie Boy's user avatar
3 votes
0 answers
170 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 ...
TheJonaMr's user avatar
3 votes
0 answers
120 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 ...
user3116271's user avatar
3 votes
0 answers
244 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 ...
asmvolatile's user avatar
2 votes
1 answer
908 views

Concrete example of Montgomery Multiplication

I have read about Montgomery Multiplication on several sites, but I haven't found any examples on specific numbers that explain the algorithm to someone who doesn't have a PhD in number theory. I know ...
Kevin Stefanov's user avatar
2 votes
3 answers
609 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 ...
Aki Suihkonen's user avatar
2 votes
1 answer
1k views

Questions about the Curve25519-donna implementation

I'm trying to understand the implementation of the following function: Please note questions in comments. ...
Vega4's user avatar
  • 234
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 ...
Saf's user avatar
  • 205
2 votes
1 answer
119 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 ...
user3042720's user avatar
2 votes
1 answer
411 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 ...
Henry Bergin's user avatar
2 votes
2 answers
271 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 ...
einstein's user avatar
  • 421
2 votes
0 answers
134 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 ...
Bosco Rohan Jacinto's user avatar
2 votes
0 answers
95 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 ...
maral's user avatar
  • 21
1 vote
2 answers
677 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 ...
Rick's user avatar
  • 1,265
1 vote
2 answers
659 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 ...
haster8558's user avatar
1 vote
1 answer
87 views

Montgomery Curve Point Multiplication in Projective Coordinates

Is the result of 4G the same when calculated as 3G + 1G or 2G + 2G in projective coordinates? Considering a curve like (y^2 = x^3 + 10x^2 + x (mod 83)) with a Generator point G = (3, 28) in affine ...
Nawras Hussein's user avatar
1 vote
1 answer
313 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? ...
bsdevlin's user avatar
1 vote
1 answer
136 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 ...
Zoey's user avatar
  • 259
1 vote
1 answer
595 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 ...
asmvolatile's user avatar
1 vote
0 answers
36 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. ...
meran_kud's user avatar
1 vote
0 answers
58 views

Montgomery algorithms for Lattice based schemes [closed]

Why most of Lattice based scheme use Montgomery Multiplication algorithm?
Don Freecs's user avatar
1 vote
0 answers
108 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 ...
Pi-Turn's user avatar
  • 83
1 vote
0 answers
45 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 ...
Black cryptographer's user avatar
1 vote
0 answers
510 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 ...
user1547360's user avatar
0 votes
1 answer
57 views

Base point in Montgomery curve

in the Montgomery Curve using Affine coordinates, we have points that lie on either the (0,0) coordinate or have a y-coordinate of 0. The question here is: Can we use these points as the Generator ...
Nawras Hussein's user avatar
0 votes
1 answer
60 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 ...
WeCanBeFriends's user avatar
0 votes
0 answers
40 views

Why doesn’t acc0 need to be cleared in p256OrdMul?

p256OrdMul method in crypto/internal/nistec/p256_asm_amd64.s, ...
Emman Sun's user avatar
  • 101
0 votes
1 answer
67 views

Finite Field Arithmetic _ Montgomery reduction

In an attempt to understand the mathematical operations related to encryption with elliptic curves, in particular finite field arithmetic (Modular reduction) I found in the Montgomery reduction that ...
Nawras Hussein's user avatar
0 votes
0 answers
47 views

ECC, Montgomery Curve cofactor bigger than 1

I read that in elliptical curve cryptography, the order of the Montgomery Curve is a multiple of 8, this mean that we can't have cofactor one curves which can be problematic in some corner cases ...
Nawras Hussein's user avatar
0 votes
0 answers
36 views

Montgomery Reduction with Even Modulus

Montgomery Reduction requires that $gcd(R,N) = 1$, where N is the original modulus and R is the selected modulus which is like $2^k,k\in\mathbb{N}$, because the computer adopts binary coding. When N ...
槿铃兔's user avatar
0 votes
0 answers
47 views

Golang NIST P256 ARM64 ASM p256OrdMul/p256OrdSqr Montgomery Multiplication

In go/src/crypto/internal/nistec/p256_asm_arm64.s Line 448 / 473 / 498 / 524, We can see the code mul Ord with hlp1 but NOT hlp0. According Montgomery Multiplication, shouldn't we mul Ord with hlp0? <...
Emman Sun's user avatar
  • 101
0 votes
0 answers
163 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 ...
pointat8's user avatar
0 votes
0 answers
178 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 ...
Black cryptographer's user avatar
0 votes
0 answers
108 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, ...
Alexey Ustinov's user avatar
0 votes
0 answers
56 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 ...
mksit's user avatar
  • 1
0 votes
0 answers
319 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. ...
haster8558's user avatar
-1 votes
1 answer
329 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 ...
haster8558's user avatar