# Questions tagged [modular-arithmetic]

Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" upon reaching a certain value… the modulus.

79 questions
Filter by
Sorted by
Tagged with
107k views

### Calculating RSA private exponent when given public exponent and the modulus factors using extended Euclid

When given $p = 5, q = 11, N = 55$ and $e = 17$, I'm trying to compute the RSA private key $d$. I can calculate $\varphi(N) = 40$, but my lecturer then says to use the extended Euclidean algorithm to ...
4k views

### Discrete Logarithm: What does it mean to find the discrete logarithm of $a$ to base $g$ modulo $p$?

My understanding is that $a=g^x\bmod p$ is the discrete logarithm problem. Given the question is worded this way, are we trying to find $x=\log_g a\bmod p$ ? For instance, if we are trying to compute ...
5k views

### lcm versus phi in RSA

In textbook RSA, the Euler $\varphi$ function $$\varphi(pq) = (p-1)(q-1)$$ is used to define the private exponent $d$. On the other hand, real-world cryptographic specifications require the Carmichael ...
47k views

### In RSA, why is it important to choose e so that it is coprime to φ(n)?

When choosing the public exponent e, it is stressed that $e$ must be coprime to $\phi(n)$, i.e. $\gcd(\phi(n), e) = 1$. I know that a common choice is to have $e = 3$ (which requires a good padding ...
• 341
3k views

### Efficient function/algorithm/method to do modular exponentiation

I was working on this project where I needed an RSA key, and I wondered if there was and more efficient way of doing $g^a \bmod n$ other than calculating $g^a$ and then finding the remainder when you ...
3k views

### How to calculate RSA CRT parameters from public key and private exponent

Given the public key (n, e) and private exponent (d), how to calculate CRT parameters (p, q, dP, dQ, and qInv) of this RSA key pair?
• 573
14k views

### Is sharing the modulus for multiple RSA key pairs secure?

In the public-key system RSA scheme, each user holds beyond a public modulus $m$ a public exponent, $e$, and a private exponent, $d$. Suppose that Bob's private exponent is learned by other users. ...
14k views

### How to find generator $g$ in a cyclic group?

As generator $g$ is used in DH how do you find a combination of prime $p$ and $g$? eg: if we choose $p=23$ and its generator is $7$ (given in the book) how do we find the generator?
• 81
4k views

### Base point in Ed25519?

The paper "High-speed high-security signatures" by Bernstein et al. introduces the Edwards curve Ed25519. Concerning the base point $B$, it says that $B$ is the unique point $(x, 4/5)\in E$ for ...
• 1,019
674 views

### What is the difference between the standard representants of $\mathbb Z/q\mathbb Z$?

The symbol $\mathbb Z/q\mathbb Z$ (given that $q$ is prime) represents the prime field $\mathbb Z_q$. Basically, the elements of this field are represented by $\{0, 1, \dots, q-1\}$, let's call this ...
• 315
2k views

### Roots in modulo field

I have a point $(X,Y)$ on an elliptical curve $E(a,b)$ where $a=-3$ and $B$ is a large number that is in hexadecimal from -51BD. To compress this point oficially in a program, we know that every $X$ ...
• 49
1 vote
4k views

### How to compute $m$ value from RSA if $phi(n)$ is not relative prime with the $e$?

Here is some information we got : We know the value of $n$, with size $1043$. We know the value of $p$ (size $20$) and $q$ (size $1023$) as the factors. $e = 65537.$ $\varphi(n)$ = $(q-1)(p-1)$ When I ...
5k views

• 43
1k views

### How to perform the modular reduce of Rijndael's finite field

I am trying to understand how to calculate the modular reduction of Rijndael's finite field. The example on this page says that {53} • {CA} = {01}, because ...
4k views

### How to determine the multiplicative inverse modulo 64 (or other power of two)?

I am trying to determine the multiplicative inverse of $47$ modulo $64$. So I have looked for an algorithm or scheme in order to perform this. I found this wiki explaining how to find a ...
• 139
3k views

### Fast modular reduction

I am looking at ways to speed up modular reduction for the polynomial $$2^{256}-2^{32}-2^9-2^8-2^7-2^6-2^4-1$$ I have read the paper "Generalized Mersenne numbers" by J.A. Solinas, but it does not ...
• 111
542 views

### Is there an upper bound to the private exponent in RSA?

In the RSA algorithm, we choose $p$ and $q$ as prime numbers and we select a value $e$ which is coprime to $\varphi(pq)=(p-1)(q-1)$. Then we calculate $d:=e^{-1}\bmod\varphi(pq)$. My question is: ...
4k views

### How do institutions like banks do RSA with big primes?

When encrypting with RSA it is often infeasible to decrypt by just doing c^d mod n, because for example when using the primes $(p,q)=(12553,1233)$, which are small ...
• 239
458 views

### What are the computational benefits of primes close to the power of 2?

Recently I was reading some article about the Bernstein's Curve25519. This is a particular Montgomery curve over $\mathbb{F}_q$ where $q = {2^{255}-19}$. What I missed or was unable to understand is ...
• 417
5k views

### ECDSA: How to retrieve a non-random k

I have a question regarding the random $k$ number of ECDSA encryption. As far as I know, it is possible to retrieve $k$ (and thus the private key) from two signed messages if both used the same $k$. ...
2k views

### Modular exponentiation on calculator for textbook RSA

How do you encrypt $51$ with public key $(n,e) = (91,23)$ I understand that $c = 51^{23} \bmod 91$. How can I calculate the result on a calculator?
• 171
335 views

### How is information disclosed by modular multiplication?

Consider the case that $c = a \cdot b \mod p$ where $p$ is a known prime and $0 < a < p$ and $0 < b < p$ are unknown integers numbers. Furthermore, some bits on the value of $c$ are ...
761 views

### Modular Reduction in the Ring $\mathbb{Z}_{q}[x]/(x^n + 1)$

May someone please explain how the reduction is done? I am familiar with other algebraic structures but wondering if I am doing reduction correctly for this. It is understood that a Polynomial Ring of ...
86 views

### Uniqueness in modular artihmetic

I'm pretty new in crypto, and studying RSA now. I saw few videos and read about it and how it works. So basically, after we have the modulus N and exponent, we encrypt a message with: ...
• 159
963 views

### Factoring RSA weak modulus

Given a public key for RSA, I have extracted the modulus which looks like this : ...
• 75
1 vote
620 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
252 views

### Diffie-Hellman key exchange: Why is $(g^{k_1} \bmod n )^{k_2} \bmod n \equiv (g^{k_2} \mod n)^{k_1} \bmod n$

In a Diffie-Hellman key exchange, with a generator $g$ and a modulo $n$, and two keys $k_1$ and $k_2$, why is $(g^{k_1} \bmod n )^{k_2} \bmod n \equiv (g^{k_2} \mod n)^{k_1} \bmod n$
• 39
1k views

### How does NaCl Poly1305 implementation do modular multiplication?

The NaCl ref implementation of Poly1305 performs modular multiplication to calculate a polynomial $\mod 2^{130} - 5$ using the following modular multiplication ...
• 1,998
7k views

### Why does the modulus of Diffie–Hellman need to be a prime?

I read a lot about Diffie-Hellman, but there is one thing I dont understand: why does the modulus p need to be a prime? What if it would not be a prime?
2k views

### Difference between FFT and NTT

What are the main differences between the Fast Fourier Transform (FFT) and the Number Theoretical Transform (NTT)? Why do we use the NTT and not the FFT in cryptographic applications? Which one is a ...
• 485
2k views

### Security concern about reducing hash value using modulo operation

As stated in the title, what I am looking for is information about a "technique" that I would like to use in some of my algorithms. Sometimes I need to map a hash function's result into a range of ...
• 371
3k views

### How to avoid side channel attacks when handling large numbers?

For cryptography, the platforms have limited size as 32 or 64-bit operations. We definitely need big numbers to implement the encryption/decryption and digital signatures for cryptosystems like RSA, ...
• 49.3k
499 views

### Regular and Efficient doubling in $GF(2^n)$

A naive approach to compute a multiplication $a \cdot b$ in a Galois field of the form $GF(2^n)$ is the russian peasant algorithm. However, it does not run in constant time and therefore is not safe ...
• 2,873
799 views

### Incorrect solution for Discrete Log Problem when using the Index Calculus algorithm

The index calculus algorithm can be used for computing discrete logarithms. The basic idea is that you search for a set of linear independent vectors. When you solve the corresponding matrix, you find ...
• 53
565 views

### Affine plaintext attack with GCD != 1

I'm trying to crack an affine cipher, but when cracking I cannot find the inverse of a number because the GCD is not 1. This is my plaintext and this is my ciphertext: ...
5k views

### Pseudocode for constant time modular exponentiation

I'm looking to implement modular exponentiation (for RSA) in constant time, but most of the examples I've found are more mathematical descriptions of the operations. Are there any references with ...
• 356
778 views

### Attack against modular inversion operation using side-channels?

I'm building a device that performs a modular inversions using a secret modulus. I would like to know if it is possible to recover all or part of this modulus by side-channels (timing, power, EMR, etc....
• 1,907
2k views

### Discrete logarithm weak group

I'm looking for weak groups in discrete logarithm, that $x$ can be extracted from $Y$ in polynomial time where $Y \equiv g^x \pmod{p}$ . I thought one way is to produce a prime $p$ that $p-1$ is an ...
• 302
296 views

### Do equivalent RSA keys exist?

If $m^{ed} \bmod n = m$ for message $m$, public key $e$ and private key $d$, then adding any integer multiple of $n$ to $m^{ed}$ still equals $m$ modulo $n$. Supposing it exists, how do I find an ...
2k 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 ...
1k views

### Is there any alternative for extended euclidean algorithm to perform modulo division?

I'm implementing point addition and point doubling operations for elliptic curve cryptography. I have implemented extended euclidean algorithm to perform modulo division. It appears the that ...
• 605
166 views

### Given a cycle $x \mapsto x^a$ with his starting point $x_1$. Can another starting point $x_2$ be transformed to generate the same cycle?

A cyclic sequence can be produced with $$s_{i+1} = s_i^a \mod N$$ with $N = P \cdot Q$ and $P = 2\cdot p+1$ and $Q = 2\cdot q+1$ with $P,Q,p,q$ primes. and $a$ a primitive root of $p$ and $q$. The ...
• 453