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

36 questions
Filter by
Sorted by
Tagged with
81 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 ...
99 views

### Can we defends against RSA Timing attack when we use java.math.BigInteger.modPow?

I think that Montgomery and sliding window techniques are applied within java.math.BigInteger.modPow (and more specifically ...
123 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 ...
21 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 ...
60 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 ...
79 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 ...
99 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 ...
89 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 ...
40 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, ...
79 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 ...
92 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? ...
38 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 ...
46 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 ...
102 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 ...
493 views

### Questions about the Curve25519-donna implementation

I'm trying to understand the implementation of the following function: Please note questions in comments. ...
686 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 ...
140 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 ...
908 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. ...
409 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 ...
205 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 ...
2k views

I do not quite understand what the greatest advantages are of using the Montgomery ladder algorithm for scalar multiplication? Can someone help me out?
517 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 ...
473 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 ...