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
0
votes
0answers
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?
1
vote
1answer
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 ...
1
vote
1answer
118 views
PIN-based authentication with Diffie-Hellman modular arithmetic
Given $\text{server}_\text{pub}= ((2^\text{largerandom}\bmod P) \cdot (2^{\operatorname{intvalueof}(“XXXX”)} \bmod P)^\text{pin})\bmod P$
We know the $\text{server}_\text{pub}$ and we know that $\text{...
1
vote
1answer
37 views
What if the bitlength of the value evaluated in Barrett reduction is greater than 2k the modulus?
For $c\equiv a \pmod n$, in Barrett Reduction, $\mu = \lfloor{\frac{2^{2k}}{n} \rfloor}$ is precomputed, where $k = \lceil{\log_2{n}} \rceil$ and the bitlength of $a$ is assumed to be less than $2k$. ...
0
votes
1answer
74 views
Why computation of $u*v^3*(u*v^7)^{(p-5)/8}$ is suggested instead of $(u/v)^{(p+3)/8}$
Working with Curve25519 I've faced with suggested form of computation square root candidate as: $uv^3(uv^7)^{\frac{p-5}{8}}$ instead of $\left(\frac{u}{v}\right)^{\frac{p+3}{8}}$. Why it is so? Or why ...
0
votes
0answers
48 views
Lattice based cryptography: How do negative coefficients in $Z_q[x]/(X^n+1)$ work? [duplicate]
I saw that in lattice-based cryptography schemes, for example Dilithium, coefficients in $Z_q$ are allowed to be negative. For example, in Dilithium the secret key is $s_1 \in R_q^{k \times l}$, where ...
0
votes
1answer
34 views
Affine Cipher: what to do if the number isnt invertible over mod n? [duplicate]
I am currently solving a simple cryptanalysis problem where I need to decrypt a text file using frequency analysis. The text has been encrypted using an affine cipher over a 68 character alphabet ...
2
votes
1answer
59 views
How does table size impact table lookup speed?
Are there good discussions of how cache pressure impacts large 64k-ish lookup tables used in erasure coding and sometimes signature verification?
I'll focus on erasure coding in small characteristic ...
1
vote
1answer
39 views
ecdsa nonce reuse to compute the private key, modular inverse question
I am following along some cryptography challenges:, in particular ECDSA Nonce Reuse here (second problem):
https://blog.coinbase.com/capture-the-coin-cryptography-category-solutions-fe94d82165c5
I ...
3
votes
0answers
134 views
Computing $a$ and $b$ from $a+b$ and $ab \bmod N$, where factorization of $N$ is unknown
I have
$$\{a+b, a^2+b^2 \bmod N, a^3+b^3 \bmod N,\ldots\}$$
and
$$\{ab \bmod N, a^p b^q \bmod N, a^{p^2}b^{q^2} \bmod N, a^{p^3} b^{q^3} \bmod N,\ldots\}$$
The factorization of $N=(2p+1)(2q+1)$ is ...
2
votes
2answers
134 views
How to handle modular arithmetic with regard to two's-complement negative numbers?
The reason for asking, is that this occurs in real life with CRT calculation of RSA decryption/signing. In CRT RSA, there's the need to calculate subtraction, and it's known negative numbers could ...
1
vote
1answer
46 views
Modular Addition in RC5 is linear or not?
So, far my understanding was Modular addition is non linear function which is mainly used in ARX based ciphers.
While I was glancing through RC5 paper (https://link.springer.com/content/pdf/10.1007/3-...
0
votes
0answers
60 views
Is this a One Way Function?
$f_{p,g,h}(x_1,x_2)=g^{x_1}h^{x_2}\bmod p$ where $g$ is a generator of $\mathbb Z_p^*$; $h\in\mathbb Z_p^*$; $x_1,x_2\in\mathbb Z_{p-1}$
Is this a One Way Function? (Assuming DL is hard)
Anyone has an ...
1
vote
1answer
76 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:
...
1
vote
1answer
121 views
Modular equation system
I have $N=p\cdot q$ and the following system where I know $A,B,C,D, k$:
$$A = B \cdot q^k \pmod N$$
and
$$C = D \cdot p^k \pmod N$$
Is there an easy way to recover $p$ and $q$?
0
votes
0answers
26 views
In RSA, what happens if the plaintext $m$ is not coprime to $n$? [duplicate]
Coming from the Wikipedia page on RSA, I think I understand the following:
RSA is based on generating an integer $n$ as the product of two large primes, $p$ and $q$, and encryption/decryption ...
0
votes
1answer
50 views
Is this zero knowledge protocol for honest verifiers?
Assume the zero knowledge protocol where the prover knows a $x$ such that: $g^x = h \pmod{p}$.
The prover chooses a random $t \in \mathbb{Z}^*_m$ and sends $y = g^t \pmod{p}$
The verifier sends ...
0
votes
1answer
86 views
Discrete logarithm with 2 solutions? A clarification request
I need some clarification on the discrete logarithm problem...
When a friend and I were solving for the discrete logarithm problem of 9 = 2 ^ x mod 11, we got two ...
1
vote
1answer
40 views
Build Encryption Method from Decryption (Reverse Modulo)
So I've been analysing some Javascript Obfuscator. I understand how the strings are decrypted, my interest is now into building the actual encryption method for those strings. I'm not going to post ...
0
votes
1answer
99 views
Is there a problem with this specific RSA protocol?
So a protocol uses two random primes $P$ and $Q$ with the equivalent bit length of around 2048 bits, multiplies to form $N$. The encryption function in detail is:
$m^e \bmod\ N$
$(\text{512-bit-random-...
1
vote
0answers
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 ...
4
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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?
1
vote
3answers
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 ...
0
votes
1answer
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}$$ ...
2
votes
2answers
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 ...
0
votes
0answers
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 ...
1
vote
3answers
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 ...
3
votes
1answer
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, ...
2
votes
1answer
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 ...
1
vote
2answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
2
votes
0answers
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.
1
vote
1answer
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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.
...
0
votes
0answers
33 views
Finding the relationship given by the generating elements of a non-abelian group (for a maximum case) where they correspond to finding cycles
Let $G=(\mathbb{Z}_p \times \mathbb{Z}_p) \rtimes_{\phi} \mathbb{Z}_q$, where $p$ and $q$ are odd distinct primes. Let $G$ be generated by the elements $s=(g_1,e_q)$ and $t=(e_p,g_3)$,
$g_1,e_p \in \...
2
votes
1answer
133 views
Can Eve break this public key cryptosystem if she can solve DLP or DHP?
The PKC is in this way:
Alice and Bob fix a publicly known prime $p$, and all of the other numbers used are private (unless sent). Alice takes her message $m$, chooses a random exponent $a$, and ...
1
vote
0answers
30 views
What is the quickest calculation to check if a number, a, is a primitive root modulo P, a prime? [duplicate]
Trying to find a quick calculation to check if my value is primitive rather than working out every a^n (modP) for n= 1 to p-1?
3
votes
1answer
53 views
Mapping a value $g^x \bmod p$ to a small interval $[1…H]$
My question is in $\mathbb{Z}_p^{*}$ context, where $p=q\cdot k+1$ for two primes $p,q$ and $k \in \mathbb{Z}$; $g$ is the generator of the subgroup $G_q$ of $\mathbb{Z}_p^{*}$, of order $q$.
Let's ...
4
votes
0answers
91 views
Inverse Public Key Proof
Alice has a private key, $x$, and a public key $P = [x] \cdot G$ in a group of order $n$.
Alice would like to also publish her inverse public key (inverted modulo the group order) $P_{inv} = [x^{-1} \...
0
votes
0answers
49 views
How to calculate the exponential inverse in elliptic curve Diffie-Hellman? [duplicate]
In Diffie-Hellman over $Z_p$, I know that if I choose a random $a$ in $Z_p$ and compute the modular inverse mod p-1, not mod p, then, with generator $g$ of my group, I can compute, for example, $(g^{...
6
votes
3answers
297 views
Decrypting small integers under RSA
Let $(n,e)$ be an RSA public key. Suppose $c = m^e \pmod n$, where $c>1$ is a very small integer. For concreteness, say $c=2$ or $c=4$.
Is it hard to find $m$ under the RSA assumption (or any of ...
4
votes
0answers
117 views
The security of blind RSA signatures with modular exponentiation as padding
It is known that (blind) RSA signature implementations should apply some sort of padding to messages before signing or blinding them. Does blind RSA signature with modular exponentiation as a padding ...
3
votes
0answers
164 views
RSA calculate $d$ using Chinese Remainder Theorem with $d_p$, $d_q$ and $e$
Suppose for a RSA system I have the following variables given:
modulus $n$, expononent $e$, $d_p$ and $d_q$Where, $d_p = d\bmod(p-1)$ and $d_q = d\bmod(q-1)$,
Is it possible to find the private ...
2
votes
1answer
47 views
How to solve polynomial modular equation to create a correct decryption algorithm
I recently had a variant of the following problem in my cryptography course and I had trouble solving it and was looking to get some help.
Given the symmetric key cryptosystem: $\text{KG, Enc, Dec}$ ...
3
votes
1answer
107 views
Constructing an integer with specific totient without factorization
Given $N(=pq)$, but not its factorization. Somehow you manage to know, that $k$ divides $\phi(N)$. Is it possible to come up with an integer $N^{*}$, for which $\phi(N^{*})=\phi(N)/k$, without ...
2
votes
1answer
473 views
How to find the inverse of a polynomial in NTRU-PKCS
I am coding a java based implementation of the NTRU public-key cryptosystem. I can comprehend the majority of the algorithms involved in the encryption and decryption process well enough, but the key ...
