# Questions tagged [modular-arithmetic]

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

365 questions
Filter by
Sorted by
Tagged with
64 views

### Why is ((m^e mod n)^d mod n) = (m^ed mod n) in RSA? [duplicate]

$$RsaPrivate(RsaPublic(m)) = (m^e \bmod n)^d \bmod n = (m^e)^d \bmod n$$ $$RsaPublic(RsaPrivate(m)) = (m^d \bmod n)^e \bmod n = (m^e)^d \bmod n$$ why is this always true?
44 views

### DHKE Square and Multiply

Given is a DHKE algorithm. The modulus 𝑝 has 1024 bit and 𝛼 is a generator of a subgroup where 𝑜𝑟𝑑(𝛼)≈2160. Assuming the public keys have already been computed, how many number of modular ...
118 views

36 views

### Missing Final Step in Montgomery Reduction

I'm following well with using the shifting method to try out the Montgomery reduction (1st round). However, the computed result is actually equal to: $$XYR^{-1} \bmod N$$ while the final goal is to ...
72 views

### Can RSA re-encrypt a message without decrypting it?

The goal of this question is to allow a server/proxy to forward an encrypted message without being able to read it with this procedure being transparent to the original sender and receiver. Assume we ...
76 views

### Why in RSA do we use mod n rather than mod phi(p⋅q)?

When we pick $e$: $$e \in \{1,2,3,4,...,\phi(p\cdot q)-1\}$$ where $\gcd(e,\phi(p\cdot q))=1$. Similarly when computing $d$ which is the modular inverse of $e$ (the private key) we use the extended ...
50 views

### Why is it necessary that the mod in an elliptic curve is a prime? [duplicate]

For the elliptic curve y^2 = x^3+2x+2 mod(23), why is it necessary that 23 is a prime. Why is the elliptic curve y^2 = x^3+2x+2 mod(24) not suitable for elliptic curve cryptography?
157 views

### secp256k1 prime modulus vs order

For curve secp256k1 prime modulus is $2^{256}-2^{32}-977$ and order is smaller number but has near half of starting bits set. If I draw number to be private key, it must be less than order. All field ...
62 views

### RSA polynomial cubic root

Let's suppose we are given a linear polyonmial \begin{align}f(x) = ax + b\end{align} where a and b is known which satisfies this equation \begin{align}y^3 - f(x) \equiv 0\mod(n) \end{align} ...
213 views

### How to find the co-efficients of a function within Zp[x]?

I am a newbie in Finite Field arithmetic and while trying to implement an Elliptic Curve Cryptography based ABE scheme in a programming language, I am unable to understand how to implement function ...
50 views

### Cryptographic properties of field multiplication (Continued)

This question follows-up from this question/comment. Suppose, you are given $X \odot Y$, where $X~(\neq 0) \in \operatorname{GF}(2^{128})$ is random, $Y~(\neq 0) \in \operatorname{GF}(2^{128})$ is ...
98 views

### Can “(input * X) mod Y” with N iterations be computed in less than N operations?

I think a simple question but here it goes (and sorry for my lack of math notation skills): Given input I, a fixed factor X and fixed modulo Y and N iterations, does the process need to be performed ...
70 views

### Repeated modular square roots to recover original base

I'm given a large prime $p$ and $c \equiv m^e \pmod p$, and $e = 2^{64}$. Typical RSA rules don't apply here, since $\phi(p) = p - 1$ is even, and $e$ is a power of two, so they share a common factor, ...
1k views

### Multiplicative inverse in ${GF}(2^4)$

I want to create a $4\times4$ multiplicative inverse table in $GF(2^4)$. The primitive polynomial given is $P(x)= x^4+x+1$ (NOTE: the values in the table need to be in hexadecimal format, hence I'll ...
141 views

### Problems with calculating inverse of finite field $GF(2^8)$ of AES

I know this question is being asked to death here but please hear me out. I was learning how to encrypt using AES and in one of the methods, we have to calculate multiplicative inverse in the finite ...
150 views

### How the message is decrypted in an RSA chosen ciphertext attack when it's a modulo?

During the last stage of decryption of a chosen ciphertext attack we are left off with this equation $$c = m \cdot t \pmod n$$ Removing all exponents like $d$ and $e$ where $c$ is the decrypted ...
125 views

### Two formulas work for this three-pass exchange problem, but I can't figure out why one of them works

Problem statement: "Suppose that users Alice and Bob carry out the 3-pass Diffie-Hellman protocol with p = 101. Suppose that Alice chooses a 1 = 19 and Bob chooses b 1 = 13. If Alice wants to ...
26 views

### Homomorphic encryption scheme for modulo reduction

I want to know if there is any Homomorphic encryption scheme that supports modulo reduction, i.e., using $Enc_{pk}(m)$ and a public $w$ to compute $Enc_{pk}(m \mod w)$. Thank you.
893 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 ...
55 views

### Does knowing modular eth roots help in factoring n?

Consider $x^e \equiv a\pmod n$, given $n$, $a$, and $e>2$, with $n$ being a composite integer and unknown $x$. Can a hypothetical function $f(a)=x$, an $eth$ root extractor, be used / adapted to ...
76 views

### Could someone please elaborate on how $(c^d \bmod n) \bmod p = c^d \bmod p$, given that $n = pq$, where $p$ and $q$ are prime numbers?

I'm following this (Chinese Remainder Theorem and RSA) post, but I don't understand how $(c^d \bmod n) \bmod p = c^d \bmod p$. Being told that it's because $n=pq$ is not enough for me to understand. ...
33 views