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
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, ...
user avatar
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 ...
user avatar
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 ...
user avatar
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$ ...
user avatar
  • 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?
user avatar
  • 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} ...
user avatar
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 $\...
user avatar
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 ...
user avatar
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,&...
user avatar
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 ...
user avatar
  • 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: ...
user avatar
  • 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 ...
user avatar
  • 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\\...
user avatar
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 ...
user avatar
  • 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?
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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$ ...
user avatar
  • 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)$ ...
user avatar
  • 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 ...
user avatar
  • 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
user avatar
  • 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) ...
user avatar
  • 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: ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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$...
user avatar
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 $...
user avatar
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?
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 $...
user avatar
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$...
user avatar
  • 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 (...
user avatar
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 ...
user avatar
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 ...
user avatar
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^...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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: ...
user avatar
  • 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 ...
user avatar
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. ...
user avatar
  • 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 ...
user avatar
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 \\...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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: ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 421

1
2 3 4 5
9