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
42
votes
4
answers
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 ...
- 531
6
votes
2
answers
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 ...
19
votes
2
answers
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 ...
user27950
33
votes
2
answers
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
3
votes
2
answers
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 ...
- 337
4
votes
1
answer
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
25
votes
4
answers
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. ...
- 251
8
votes
2
answers
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
9
votes
1
answer
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
4
votes
2
answers
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
4
votes
2
answers
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
1
answer
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 ...
- 11
12
votes
2
answers
5k
views
Is it possible to recover an RSA modulus from its signatures?
Let's say that you have some small number of RSA signatures of known data: you know some pairs $(m_k, c_k)$ such that ${c_k}^e \equiv m_k \pmod n$. If you know $e$, because probably it's one of $\{3, ...
- 2,615
7
votes
1
answer
5k
views
Using same modulus for RSA
I know that there exist some attack when using same modulus.
Can two different pairs of RSA key have the same modulus?
RSA cracking: The same message is sent to two different people problem
But ...
- 79
6
votes
2
answers
1k
views
Constant time multiplicative inverse within a word
I was playing with an algorithm which at one step, calculated $f(x) = x^{-1} \mod p$ for $0 < x < p = 2^{64}-59$ (note $p$ is a prime). I used Knuth's Vol 2 Algorithm X algorithm for calculating ...
- 278
5
votes
3
answers
6k
views
Proof for exponentiation in modular arithmetic
If $e$ is a natural number, then this is true:
$$m^e \bmod\ n = (m\bmod\ n)^e\bmod\ n$$
This is often used when encrypting, especially with RSA, since one can avoid directly calculating $m^e$, ...
- 239
5
votes
4
answers
629
views
Where does the $\varphi(n)$ part of RSA come from?
$e d \equiv 1 \pmod{\varphi(n)}$
Where does the $\varphi(n)$ part come from? How did the inventors of RSA arrive at $\varphi(n)$?
- 201
5
votes
2
answers
4k
views
How to use the Extended Euclidean algorithm to invert a finite field element?
I was doing some practice on cryptography (I'm new to this topic) and was wondering what the following question even means or what it is asking me to find. I do know how to do Extended Euclidean ...
- 59
4
votes
2
answers
519
views
Speed up modular exponentation with fixed base and modulus
Can someone explain, how $a^x \mod N$ can be speeded up, when $a$ and $N$ are known constants? How big is the gain and what resources are needed?
https://www.imperialviolet.org/2013/05/10/...
- 1,701
4
votes
2
answers
2k
views
RSA: How to compute the number of possible plaintexts if $e$ is not coprime to $\varphi(n)$?
I'm studying for an exam next week, and there are two questions that me and my friend don't understand:
Question 1:
Let $p,q$ be big prime numbers and $n=pq$.
Let $e$ be a number between $1$ and $\...
- 43
3
votes
1
answer
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 ...
- 33
12
votes
1
answer
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
8
votes
1
answer
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
7
votes
3
answers
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: ...
6
votes
4
answers
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
6
votes
1
answer
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
6
votes
1
answer
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$. ...
- 183
6
votes
1
answer
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
4
votes
2
answers
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 ...
- 43
2
votes
1
answer
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 ...
- 89
2
votes
1
answer
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
2
votes
1
answer
963
views
Factoring RSA weak modulus
Given a public key for RSA, I have extracted the modulus which looks like this :
...
- 75
1
vote
1
answer
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
0
votes
4
answers
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
10
votes
1
answer
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
9
votes
3
answers
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?
user17971
8
votes
2
answers
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
8
votes
2
answers
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
7
votes
2
answers
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
7
votes
2
answers
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
5
votes
2
answers
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
5
votes
2
answers
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:
...
5
votes
4
answers
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
5
votes
3
answers
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
4
votes
1
answer
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
4
votes
1
answer
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 ...
user9070
4
votes
1
answer
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 ...
- 159
4
votes
4
answers
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
4
votes
1
answer
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
4
votes
2
answers
593
views
how to iteratively calculate a^emod n with modulus n sized 4096 bits
In most sites the exponent of the RSA public key is 24 bits. But the modulus can get to 4096 bits size. I have an accelerator that can get max. 2112 bit size modulus. It calculates ...
- 41