Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [montgomery-multiplication]

0
votes
0answers
27 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
vote
1answer
54 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 ...
2
votes
1answer
134 views

Questions about the Curve25519-donna implementation

I'm trying to understand the implementation of the following function: Please note questions in comments. ...
2
votes
0answers
184 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 ...
1
vote
1answer
56 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 ...
0
votes
1answer
211 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 ...
3
votes
0answers
150 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 ...
4
votes
2answers
1k 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?
4
votes
1answer
298 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 ...
1
vote
1answer
354 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 ...
4
votes
2answers
198 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'...
2
votes
1answer
88 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 converted from this ...
3
votes
0answers
180 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 ...
3
votes
2answers
2k 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$ ...
2
votes
0answers
87 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 ...
-1
votes
1answer
210 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 ...
1
vote
2answers
467 views

Montgomery Algorithm

I'm trying to undestand how it works and how to implement the algo described in this paper. The paper shows a methods to compute a modular multiplication where it is used multiplier with a resolution ...
0
votes
0answers
263 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. ...
1
vote
0answers
391 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 ...
4
votes
1answer
736 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 ...
8
votes
1answer
4k 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 ...
3
votes
1answer
1k 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
vote
1answer
917 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 ...