Questions tagged [modular-arithmetic]
Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" upon reaching a certain value… the modulus.
391
questions
2
votes
0answers
39 views
+50
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?
1
vote
1answer
38 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 ...
2
votes
2answers
126 views
+100
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
0answers
21 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 $...
1
vote
0answers
30 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$...
1
vote
0answers
39 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 (...
1
vote
0answers
22 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 ...
9
votes
4answers
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 ...
1
vote
0answers
60 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^...
2
votes
1answer
47 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 ...
0
votes
1answer
77 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
1answer
58 views
conflicting definitions for dP / dQ and exponent1 / exponent2 in PKCS 1?
In Section 2 dP and dQ are defined thusly:
...
0
votes
1answer
56 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 ...
0
votes
0answers
23 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. ...
3
votes
0answers
89 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 ...
1
vote
1answer
138 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 \\...
0
votes
0answers
20 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 ...
1
vote
1answer
130 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 ...
1
vote
2answers
49 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 ...
2
votes
1answer
200 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
1answer
42 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 ...
2
votes
1answer
125 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 ...
1
vote
2answers
169 views
Can there be an injective function that maps a large set of integers to a smaller set while being "collision-aware"
Consider two sets:
The "big set" contains all integers between $0$ and $2^{160}$ exactly once.
The "small set" contains all integers between $0$ and $2^{32}$ exactly once.
Given ...
4
votes
1answer
189 views
Can modular exponentiation with a public index be considered a secure permutation?
Secure permutation can be used in Sponge and Duplex constructions to build hash functions and encryption. To potentially use them in public-key cryptography, some arithmetic properties is desired.
Can ...
1
vote
1answer
64 views
Exponentiation modulo trick
Let's say I have
$p, g$ - known constant, $p$ is prime number, $g$ is composite.
$x$ - unknown random number, $2 < x < p - 1$
$k$ - my input
$S = k^x \bmod p$
$1 < S < p-1$
So, what $k$ ...
0
votes
0answers
80 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
2answers
199 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
144 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
72 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
77 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
53 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
51 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
74 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
125 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
138 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
153 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
61 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
66 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 ...
2
votes
1answer
81 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
131 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
77 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
56 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
145 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
53 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
115 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
46 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
88 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
102 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
57 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
394 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 ...
