Questions tagged [modular-arithmetic]
Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" upon reaching a certain value… the modulus.
418
questions
2
votes
1
answer
60
views
Patterson's decoding algorithm for Goppa codes
From this Wiki page: given a Goppa code $\Gamma(g, L)$ and a binary word $v=(v_0,...,v_{n-1})$, its syndrome is defined as $$s(x)=\sum_{i=0}^{n-1}\frac{v_i}{x-L_i} \mod g(x).$$
To do error correction, ...
0
votes
0
answers
34
views
Can a modulo function be linearized or alternatively expressed?
In order to try to simplify or alternatively express cryptographic functions I wonder if the modulo function can be alternatively expressed. Could for example a Fourier series of a sawtooth wave or ...
- 123
2
votes
2
answers
70
views
Is it possible to calculate the modular inverse of a secp256k1 public key?
I know that it wouldn't be possible to use the extended Euclidean algorithm, since it would require the ability to divide a public key and calculate the remainder. I was wondering if there were any ...
- 21
1
vote
1
answer
94
views
If RSA uses $e$ with $\gcd(e,\phi(N))\ne1$ but $e$ is hard to factorize has an adversary still an advantage in finding $d$ for $m^{ed}\equiv m\mod N$?
Usually RSA uses an encryption exponent $e$ with $\gcd(e,\phi(N))=1$.
This question shows why that need to be the case: For $\ne1$ there might exist no decryption exponent $d$ because other $m'\ne m$ ...
- 475
-2
votes
1
answer
44
views
Straightforward modular arithmetic for power-of-two moduli [closed]
Why if $q$ is a power-of-two integer, then doing arithmetic modulo $q$ (addition and multiplication) is very efficient and straightforward?
- 365
1
vote
0
answers
53
views
Examples with Polynomial Multiplication in $\mathbb{Z}_{𝑞}[x]/(x^{n} \pm 1)$
Given the following definitions for $\mathbb{Z}[x] /\left(x^{n}-1\right)$:
$$
a \cdot b \equiv \sum_{i=0}^{n-1} \sum_{j=i+1}^{n-1} a_{i} \cdot b_{j} \cdot x^{i+j}+\sum_{j=1}^{n-1} \sum_{i=n-j}^{n-1} ...
- 31
0
votes
1
answer
33
views
Computing the matrices for the Number Theoretic Transform
I am familiar with Fourier Transform and computing the DFT and FFT matrix for fast multiplication of integers. However, this is the first time I work with NTT applied to polynomial rings of the form $\...
- 31
2
votes
1
answer
114
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 ...
- 31
0
votes
0
answers
33
views
How to Run the Public Key Protocol for a Zero-Knowledge Proof of Identity?
In the paper Zero-Knowledge Proofs of Identity (by Feige, Fiat, and Shamir) a ZK protocol is described that leverages quadratic residues. Section 3 describes an "Efficient Identification Scheme,&...
4
votes
2
answers
367
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 ...
- 365
1
vote
1
answer
268
views
What is the order of the generator point G=9 in curve25519?
In Curve25519 we typically have this generator point or base point:
...
- 1,315
1
vote
1
answer
63
views
Is there a general formula for the number of different sequences produced with $x\mapsto x^\alpha \mod N$?
Depending on $\alpha,N,x$ the sequence $x\mapsto x^\alpha \mod N$ can have a different length. If the first element $x_0$ is initialized with $x_0 = x_r^\alpha$ for a random $x_r$ the sequence will ...
- 475
6
votes
2
answers
536
views
RSA with exponent being a factor of modulus
This weekend I participated in a CTF, but came across a task that I wasn't able to solve. I can't find any write-ups so I hope you can help me.
Given:
$$
n = pq\\
c_1\cong m_1^{\hspace{.3em}p} \mod n\\...
- 67
0
votes
0
answers
100
views
Can random values $\in [1,N-1]$ lead to random members of a certain sequence $x \mapsto x^\alpha \mod N$?
Given (for example) different primes $p,q$ with $2 p+1$, and $4 p+3$ prime as well (same for $q$).
Let
$$N = (4 p+3)\cdot (4 q+3)$$
With this the sequence
$$s_{i+1} = s_i^4 \mod N$$
will have $p\cdot ...
- 475
1
vote
0
answers
46
views
Why can't rsa come out with the same cipher?
When $x < N$, there cannot be the same encrypted message with different outgoing messages.
But why?
- 11
0
votes
1
answer
83
views
RSA rsa residue class ring
I've been working on the RSA method for several weeks and I don't understand what this residual class ring is all about.
I understand that if
$
x^e \bmod n$ there must be $x<n$ because of ...
- 11
1
vote
0
answers
87
views
Question about sequence length/count/security of $x\mapsto x^\alpha \mod (N=Q\cdot R)$, with $Q=2q_1q_2+1$ and $R=2r_1r_2+1$ and $\alpha = 2q_2r_2$
Given a number $N$ with
$$N=Q\cdot R$$
$$Q=2\cdot q_1 \cdot q_2+1$$
$$R=2\cdot r_1\cdot r_2+1$$
with different primes $P,Q,q_1,q_2,r_1,r_2$.
If we now choose an exponent $\alpha$ containing prime ...
- 475
0
votes
1
answer
68
views
Given $N$ with $d$ prime factors. Can the number of unique values $x^d \mod N$ calculated for $d>2$? Does the total amount decrease at some point?
Given a number $N$ with $d$ unique prime factors. Can the number of unique values $v$ with
$$v \equiv x^d \mod N$$
$$x\in[0,N-1]$$
$$N = \prod_{i=1}^{d} p_i$$
be calculated for $d>2$? (Q1)
Does ...
- 475
1
vote
1
answer
44
views
How secure is a projection to a subspace with much lower member size for $x\mapsto x^a$ mod $N = PQ$, $P=2p+1$, $Q=2qr+1$, to target space $r=2abc+1$?
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\cdot r+1$ and $r = 2\cdot u \cdot v \cdot w +1$ with $P,Q,p,q,r,u,v,w$ ...
- 475
3
votes
2
answers
167
views
Common exponent problem related to discrete logarithms assuming Diffie Hellman oracle
Let $g$ be a generator of multiplicative group mod $p$ a prime.
Suppose we know
$$g^{a+km_1}\bmod p$$
$$g^{b-km_2}\bmod p$$
$$g^{a+k'm_3}\bmod p$$
$$g^{b-k'm_4}\bmod p$$
where $m_2m_3-m_4m_1=\phi(p)$ ...
- 882
4
votes
1
answer
143
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 ...
- 475
1
vote
2
answers
73
views
What's the Apostrophe or single quote of a variable means in cryptography?
What's the meaning of Apostrophe over a variable in the context conversations of verification?
Reference number: https://people.eecs.berkeley.edu/~jfc/'mender/IEEESP02.pdf
- 205
1
vote
1
answer
54
views
RSADP/RSAEP with zero base/message value
I have a question about how RSADP/RSAEP are defined (in RFC2437 https://datatracker.ietf.org/doc/html/rfc2437#section-5.1.2):
RSADP (and RSAEP) are described with the same limits for the message (m) ...
- 141
0
votes
1
answer
51
views
Why are there different versions of the Pohlig-Hellman attack?
I think I have an understanding of the Pohlig-Hellman attack on elliptic curves. From page 31 of Pairings for Beginners:
Find the group order $\#E(\mathbb{F}_q)$, call it $n$, and factor it. Example: ...
- 247
0
votes
1
answer
72
views
Breaking RSA with knowledge of the secret key $(n, d)$
I am following the discussion in Koblitz in the second paragraph in the RSA section (page 94 on my edition).The goal is to show that knowledge of an integer $d$ such that $$m^{ed}\equiv m \mod n$$ for ...
1
vote
1
answer
57
views
Trimming uniformly random input for elliptic curve private keys
Imagine there is 256-bit uniform input from CSPRNG. Suppose there is a curve like secp256r1 whose curve order is slightly less than 256 bits.
We cannot just ...
- 229
2
votes
2
answers
352
views
Modulo p in Elliptic Curve Cryptography
To carry out Elliptic Curve Cryptography between parties, are all elliptic curve equations considered to be in the form $\bmod p$?
For example, the $secp256k1$ Bitcoin curve of the equation $y^2=x^3+7$...
- 23
2
votes
2
answers
106
views
Cyclic codes as ideals of a quotient ring
I'm finding the algebra behind cyclic codes somewhat tricky. The starting point is easy enough: $C\subseteq \mathbb F_q^n$ is cyclic if any cyclic shift of a codeword $c\in \mathbb F_q^n$ is still in $...
2
votes
1
answer
270
views
What is the difference between the Fully Homomorphic BFV and BGV schemes?
When I read about BFV or BGV, they all look similar: they use polynomials from $\mathbb{Z}[X]/X^n+1$ as secret keys/pubic keys, etc.
What is the main difference?
- 51
-1
votes
1
answer
48
views
How to define a cryptosystem when the encryption-decyrption scheme is based on Shamir's secret sharing scheme?
I would like to make a parallelism between Shamir's secret sharing scheme and how to define a cryptosystem where the encryption scheme is based on secret sharing. To begin with I do not know if there ...
- 271
2
votes
2
answers
210
views
Why AND gate is * on Fully Homomorphic Encryption, BFV scheme?
According to Representing a function as FHE circuit, the AND gate for FHE encrypted data is just A*B, in the case that the plaintext has only ...
0
votes
0
answers
26
views
Could you provide the proof of a secure multi - secret sharing scheme that fulfils the requirements of correctness and information-theoretic privacy?
Suppose that we have a multi-secret sharing scheme and let $I$ be the a set of agents. Say that $S$ is the space of the (uniform) random variables $s=(s_1,s_2,\cdots,s_I)\in S$ such that the share $...
- 271
1
vote
0
answers
32
views
Finding an element of $\mathbb{Z}_p$ if the order of that element is known [duplicate]
I have two prime numbers $p$ (1024 bits) and $q$ (160 bits) such that $q$ divides $p-1$. Now I want to find an element $b$ in $\mathbb{Z}_p$ with the order of $q$. That means that $b^q \equiv 1 \mod p$...
- 11
0
votes
0
answers
41
views
Could anyone provide any idea of such a protocol?
Could anybody provide the seminal paper and/or every specific manual in mathematics that describes a secure multiparty computation procedure, where the players will exchange encrypted messages (...
- 271
0
votes
0
answers
24
views
Sharing information scheme of cryptography - operations in modular arithmetic
Taking into account my previous question here and the answer about the proposed encryption-decryption scheme. I am trying to understand how to make possible operations in modular arithmetic for a ...
- 271
9
votes
4
answers
2k
views
Is encrypting every number separately using RSA secure?
Suppose RSA is considered a "secure" method for encryption. RSA is meant to encode a sequence of integers base $27$. If we use an $n=pq$ that is hard to factor, Is it still secure if we ...
- 103
1
vote
0
answers
65
views
Which of the following is considered cryptographically hard/easy?
Which of the following are easy, if any? Which are hard? and why.
Case 1) Given $x^3 \bmod N$, where $N$ is a composite number and we don't know any of the factors of $N$, find $x$.
Case 2) Given $x^...
- 21
2
votes
1
answer
51
views
Is there an algorithm to compute the wNAF for an exponent faster than quadratic?
For doing exponentiation in a group for which inversion is trivially easy, such as elliptic curve groups, is there an algorithm for computing the $w$NAF ("$w$-ary non-adjacent form") array ...
- 2,214
0
votes
1
answer
81
views
Get bit i when modulo n
Is there a way to recover the bit sequence of a number ( for example 29 = 0b11101 ) by always dividing it by 2 when in mod 143 for example ?
What I mean by that is recover the number bit by bit by ...
1
vote
1
answer
74
views
conflicting definitions for dP / dQ and exponent1 / exponent2 in PKCS 1?
In Section 2 dP and dQ are defined thusly:
...
- 2,703
0
votes
1
answer
66
views
What Is The Maximum Value For N In Discrete Logarithm Problems?
I have some code, which can crack a discrete logarithm problem in ~ O(0.5n) time. However, this only works if, in the following, N is less than P:
G^N (mod P). To be clear, my program can figure out ...
- 33
0
votes
0
answers
25
views
Securely and Deterministically select a combination of objects from hash (cryptographic seed)
I am working on a project that is using a bit-commitment concept to authenticate information.
I need to select a combination of objects securely from a secure hash, then distribute that hash later. ...
- 1
3
votes
0
answers
101
views
No Final subtraction in Word-level Montgomery Multiplication
I am trying to make an RSA module in VHDL, which in turn will be deployed to an FPGA. I am trying to implement a full Montgomery algorithm which means that I am working with the Montgomery ...
- 31
1
vote
1
answer
176
views
Why does Shamir's Trick for RSA Work
I have read that Shamir's trick can protect RSA with CRT against fault attacks. However, it is not clear to me why the following equations
$$
s_{p}^{*}=m^{d \bmod \varphi(p \cdot t)} \bmod p \cdot t \\...
- 55
0
votes
0
answers
28
views
Group Signature by Camenisch and Stadler
Page 8, Paper: "Efficient Group Signature Schemes for Large Groups" by Camenisch and Stadler
(1)
I was trying to understand membership certificate part. I am have only basic knowledge of ...
- 141
1
vote
1
answer
231
views
Specific case of RSA where cipher text equals plain text
How did they arrive at the conclusion that there are 4 messages where plain text equals cipher text from "It is easy to show that in RSA, when e = 3 there are 4 messages m for which the ...
- 11
1
vote
2
answers
62
views
RC6 Integer operations in modulo 32 between two 32-bit blocks
I am new to cryptography and I am trying to code the RC6 (Rivest cipher 6) algorithm. The algorithm requires addition, subtraction and multiplication in modulo 232. If I am performing these operations ...
- 21
2
votes
1
answer
250
views
Barret reduction to get 64-bit remainder of a 128-bit number
On github there's this code part of Microsoft's SEAL:
...
0
votes
1
answer
120
views
In RSA signing find n from e and many pairs of m and c
When signing using RSA with $e = 65537$ and many pairs of m and c,
where
$$c^e \bmod (n)=m$$
is there a way to find n (n is 2048 bits)?
I planned on computing $ c^e-m $ and then treating those as a ...
- 23
3
votes
1
answer
176
views
What is the reason for Shamir scheme to use modulo prime?
In Shamir's secret sharing scheme, Dealer performs the following steps
Choose a prime number $q$ such that $q > n$
Choose a secret $s$ from finite field $\mathbb{Z}_q$
Choose $t-1$ degree ...
- 421