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).

18 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
3 votes
0 answers
312 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
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
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
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
68 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
164 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