Questions tagged [modular-arithmetic]

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

Filter by
Sorted by
Tagged with
40 votes
4 answers
105k 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 ...
DougalMaguire's user avatar
6 votes
2 answers
3k 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 ...
Dennis Cheryshevv's user avatar
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 ...
user avatar
33 votes
2 answers
46k 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 ...
Martin's user avatar
  • 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 ...
Ömer Enes Özmen's user avatar
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. ...
Mohammed Fathi's user avatar
8 votes
2 answers
13k 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?
user7447's user avatar
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?
user1563721's user avatar
9 votes
1 answer
3k 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 ...
Chris's user avatar
  • 989
4 votes
2 answers
635 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 ...
caesar's user avatar
  • 315
4 votes
2 answers
1k 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$ ...
Joe's user avatar
  • 49
1 vote
1 answer
3k 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 ...
user81147's user avatar
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, ...
Myria's user avatar
  • 2,575
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 ...
zywu's user avatar
  • 79
5 votes
2 answers
3k 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 ...
user33032's user avatar
5 votes
4 answers
614 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)$?
Leo Jiang's user avatar
  • 201
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$, ...
Gretty's user avatar
  • 239
4 votes
2 answers
511 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/...
Smit Johnth's user avatar
  • 1,681
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 $\...
CSE371's user avatar
  • 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 ...
user1377493's user avatar
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 ...
user3834282's user avatar
8 votes
1 answer
2k 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 ...
user12230's user avatar
  • 111
7 votes
3 answers
533 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: ...
Pranav Sharma's user avatar
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 ...
Gretty's user avatar
  • 239
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?
James's user avatar
  • 171
6 votes
1 answer
442 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 ...
NumberFour's user avatar
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$. ...
Philipp Murry's user avatar
5 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 ...
yberman's user avatar
  • 268
4 votes
2 answers
333 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 ...
user24828's user avatar
2 votes
1 answer
922 views

Factoring RSA weak modulus

Given a public key for RSA, I have extracted the modulus which looks like this : ...
Mzem's user avatar
  • 75
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: ...
YoavKlein's user avatar
  • 159
1 vote
1 answer
595 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 ...
asmvolatile's user avatar
0 votes
4 answers
248 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$
dhk's user avatar
  • 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 ...
archie's user avatar
  • 1,988
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?
user avatar
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 ...
Skary's user avatar
  • 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, ...
kelalaka's user avatar
  • 48.5k
7 votes
2 answers
491 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 ...
Raoul722's user avatar
  • 2,836
7 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 ...
C.S.'s user avatar
  • 445
5 votes
3 answers
754 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....
SDL's user avatar
  • 1,867
5 votes
2 answers
769 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 ...
Tomirio's user avatar
  • 53
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 ...
Alex Gaynor's user avatar
5 votes
2 answers
562 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: ...
Wouter Doeland's user avatar
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 ...
Mehran Torki's user avatar
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 ...
J. Doe's user avatar
  • 453
4 votes
2 answers
587 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 ...
Israel's user avatar
  • 41
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 ...
abejoe's user avatar
  • 605
4 votes
1 answer
294 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 ...
user avatar
3 votes
3 answers
4k views

Point decompression on an elliptic curve

I'm programming an elliptic curve cryptosystem and I'm having difficulty with decompressing points. The following information is from my project specification as to my understanding: Given a point $x$...
josh's user avatar
  • 31
3 votes
2 answers
189 views

Formal security of recycled random blinding in a Paillier scheme

This question is a follow-up/variant on a previous question. Supposing that we are trying to generate a large number of (indistinguishable) ciphertexts of a given plaintext and want to avoid the ...
Dave's user avatar
  • 385