Questions tagged [number-theory]
Number theory is the study of the properties and construction of numbers, particularly integers. Prime numbers are of particular interest to number theorists and consequently cryptographers as they are considered the "building blocks" of numbers and produce many interesting results which are useful in cryptography. Questions covering number theory and primes should use this tag; questions involving finite fields and groups might use this tag if relevant.
263
questions
2
votes
1
answer
45
views
Reflecting a point on the Edwards curve
Let's say we have a point $nP = (x,y)$ on a curve $E$ over a prime $p$. The corresponding Edwards curve coordinates are $(u,v)$. I want to construct the point corresponding to $(u,-v)$ on the Edwards ...
- 135
1
vote
2
answers
61
views
RSA: does it matter that we recover something congruent to x rather than equal to it?
In the proof that RSA successfully decrypts the message $x$, we show that $x^{e^{d}}\equiv x \pmod N$. However, I am wondering whether it is a problem that we don't recover $x$ exactly, but merely a ...
- 123
1
vote
1
answer
101
views
finding r-th root in $\mathbb{Z}/n\mathbb{Z}$
I was reading the paper One-way Accumulators: A Decentralized Alternative to Digital Signatures by Benaloh and de Mare [link], and in section 4.2, they say that given $z\in (\mathbb{Z}/n\mathbb{Z})^*$ ...
- 445
2
votes
1
answer
245
views
Concrete example of Montgomery Multiplication
I have read about Montgomery Multiplication on several sites, but I haven't found any examples on specific numbers that explain the algorithm to someone who doesn't have a PhD in number theory.
I know ...
- 129
1
vote
1
answer
93
views
Special algorithms for edge cases of binary arithmetic?
I have several mathematical operations on binary numbers that are special cases of more general arithmetic operations. I am wondering whether there exist more specialized algorithms purpose-made for ...
- 129
3
votes
1
answer
179
views
Purpose of the b1, b2, b3.... terms in Rabin-Miller Primality Test
In Rabin-Miller primality test, let N be the number you're checking for primality. Here N = 78007.
Let m be the number you get after dividing (N - 1) by 2 several times until you can no longer do so. ...
- 129
1
vote
1
answer
476
views
Challenges like RSA factoring challenge
RSA factoring challenge is a famous one and is still not completely solved.
Are there similar challenges for
Discrete log over $\mathbb Z_p^*$?
Discrete log over Elliptic curves?
LWE?
LPN?
- 908
1
vote
1
answer
176
views
Rabin-Miller Primality Test - Elaboration needed
In short, my question is:
What exactly do people mean when they say that "The more you apply the Rabin-Miller test to a number, the more certain you can be that the number you're testing is prime....
- 129
4
votes
1
answer
319
views
Discrete Logarithm Challenges and Records
I am wondering whether there are any current challenge problems for Discrete Logarithms.
Specifically in $\mathbb{Z}_p^\ast$ as well as in elliptic curve groups.
It turns out CERTICOM still has some ...
- 21k
2
votes
1
answer
83
views
Why is $d = e^{-1} \mod \phi(N) \equiv e^{\phi(N)-1} \mod \phi(N)$ and not commonly used in RSA key generation?
On some lecture slides regarding to RSA-Encryption, the formula for calculation of the private key is given as $d = e^{-1} \equiv e^{\phi(N)-1} \mod \phi(N)$. The second equation is justified by the ...
- 21
1
vote
1
answer
89
views
Non probabilistic algorithm : Given secret key $d$ we can factorize $n$ assuming $e$ is small
I read in an introduction to a paper that if $e$ is small enough and we were given secret key $d$ in RSA, then there is an efficient deterministic algorithm to factorize $n$. I've searched about that ...
- 173
2
votes
2
answers
127
views
Verification through prime modulus
Asking this question here since it has a flavor similar to some cryptographic protocols. How likely are two integers which are smaller than some threshold, mod by some prime number to have the same ...
- 123
1
vote
1
answer
142
views
Proving the generator criterion for group $Zp$
I am trying to understand how to find a generator of Zp. How to find generator $g$ in a cyclic group?.
I have heard that we can pick random a Zp and for each primitive d| p-1 check wether:
a^[(p-1)/...
- 173
1
vote
0
answers
23
views
Possible plain text needed on a congruence modulo - based encryption
Suppose m is a positive integer converted from the plain text in bytes.
And there are two positive integers a, ...
- 11
0
votes
1
answer
67
views
Computing the eth root in Z(N)* i.e set of all elements coprime to N
I understand that it is easy to compute eth root in Z(P)* but what about with Z(N)? I know that it requires the factorization of N but what does that actually mean? What is an example of calculating ...
1
vote
1
answer
155
views
Does it weaken a RSA modulus to publish a generator of a small subgroup?
Let $n = P\cdot Q$ be the product of two safe primes $P = 2p+1$ and $Q=2q+1$.
Let $g$ be a generator of $C_{p} \subset \mathbb{Z}_n^*$, the multiplicative subgroup of order $p$. In other words, $g^p = ...
- 339
2
votes
2
answers
168
views
Proving in zero-knowledge the "sign" of a discrete logarithm in groups of unknown order
Suppose we have the description of a group $\mathbb{G}$, a group of unknown order: the size of the group is unknown. For instance, an RSA group ($\mathbb{Z}^{*}_N,$ where $N=pq$ for unknown primes $p$ ...
- 1,164
3
votes
1
answer
92
views
Do ideal non-cyclotomic lattices provide better compression in lattice-based cryptography?
Let $f \in \mathbb{Z}[x]$ be an irreducible polynomial of degree $N$ and $q \in \mathbb{N}$. Consider the rings $R := \mathbb{Z}[x]/f$ and $R_q := R/q$. Obviously, an element of $R_q$ can be ...
- 365
1
vote
1
answer
73
views
Expectation of the size of algebraic norm in power of two cyclotomic field
Let $\mathcal R$ be the ring of integers of a power of two cyclotomic field.
That is, $\mathcal R = \mathbb Z[x] /\langle x^{2^k}+1\rangle $ for some integer $k$.
We denote $\mathcal R / q \mathcal R$ ...
- 13
1
vote
1
answer
455
views
Specific RSA challenge
It was a challenge from CTF (ended), but I didn't solve it.
p, q = keygen(512)
n = p * q
flag = bytes_to_long(flag)
enc = pow(n + 1, flag, n**3)
So we have module ...
- 11
2
votes
1
answer
113
views
Significance of having remainder $3$ when divided by $4$ for both $p$ and $q$ in BBS
In the Blum Blum Shub random number generator, we take two random prime numbers $p$ and $q$ such that both have a remainder of $3$ when divided by $4$. My question is why can't we just take any $2$ ...
- 21
0
votes
1
answer
47
views
Precise heuristic for size of a uniform sample in $(\mathbb{Z} / N \mathbb{Z})^\times$
I'm primarily a mathematicians dipping my toes into cryptography, and I have often seen/heard cryptographers use the heuristic that a uniformly random sample $a$ from $(\mathbb{Z} / N \mathbb{Z})^\...
- 103
0
votes
0
answers
229
views
RSA with huge ciphertext
I am trying to find the flag from an RSA ciphertext, I am able to get the factors from factordb.com but the given e is not ...
- 33
1
vote
1
answer
72
views
Does a list of discrete log equations reveal information?
Given public generator $g$ of some cyclic group, a secrets $x\in Z_q$, and public pairs $(a_1,b_1),...,(a_n,b_n)$ (where $a_1,...,a_n$ are selected at random from a big set), and prime p, that ...
- 79
2
votes
1
answer
100
views
Can functional encryption encrypt and decrypt negative integers?
I want to use DCR-based functional encryption for encryption and decryption purpose. However, I'm unsure whether DCR-based functional encryption can support negative integers.
Is there any ...
- 21
1
vote
1
answer
248
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$ ...
- 571
1
vote
1
answer
56
views
Secure modification of DSA?
In DSA, we compute the signature $(r,s)$ on $m$ by sampling $k\in\{1,...,q-1\}$ and then computing
$r := g^k \bmod p$
$s := k^{-1}*(m+x*r) \bmod q$
During verification, we compute $v:=g^{m*s^{-1}}*y^{...
- 529
0
votes
1
answer
178
views
What does Euler's theorem have to do with RSA?
In RSA we compute e (encryption key) and d (decryption key) $\bmod phi(n)$ and not $\bmod n$, so how come when we get the keys and encrypt and decrypt we use $\bmod n$ not $\bmod phi(n)$ using the ...
- 157
0
votes
1
answer
189
views
Additively homomorphic (modified) RSA?
Is there a way to modify the RSA so that it's homomorphically additive?
I did some research and came across a paper which describes MREA (Modified RSA Encryption Algorithm), an RSA modification that, ...
- 1
5
votes
1
answer
297
views
Which is the smallest, cyclic in 3 directions, consistent structure of random values which can be hidden at the adversaries machine? (some comparison)
Or more general each member can be part of up to three 2D locally euclidean planes of 2 different dimensions each.
(each of those planes is cyclic in two orthogonal directions, like a torus)
Given ...
- 571
2
votes
1
answer
43
views
Duality Results for Some Module Lattices
Let $R$ be the ring of integers of a cyclotomic field $\mathbb{Q}(\zeta_n)$, where $n$ is a power of two, and $\boldsymbol{a} \in R_{q}^{m}$, for $m\in\mathbb{Z}^+$, $q\in\mathbb{Z}_{\geq2}$ prime. ...
- 381
6
votes
2
answers
1k
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\\...
- 231
1
vote
1
answer
51
views
Division by $2$ or principal root with DH oracle
Assume $g$ is generator of multiplicative group modulo prime $p=2q+1$ where $q$ is prime.
Assume we know $g^{2t}\bmod p$ and $g^{2}\bmod p$ and assume we can have access to a Diffie-Hellman oracle.
...
- 908
2
votes
1
answer
195
views
Distribution of group elements with chosen bits and hardness of discrete log problem
For generator $g$ of order $n$ the group elements $y=g^x$mod $n$ are uniformly distributed because of the modulo operation.
Suppose however that from the original output space $Y$, we only consider ...
- 294
3
votes
2
answers
198
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)$ ...
- 908
1
vote
0
answers
101
views
Working the multivariate Coppersmith algorithm
I recently studied the multivariate Coppersmith algorithm.
Let $f(x)$ be $n$-variate polynomial over $\mathbb{Z}_p$ for some prime $p$.
Informally, the multivariate Coppersmith's theorem stated that ...
- 149
1
vote
1
answer
133
views
On access to a Diffie Hellman oracle
Assume $g$ is generator of multiplicative group modulo prime $p$.
Assume we know $g^X\bmod p$ and $g^{XY}\bmod p$ and assume we can have access to a Diffie-Hellman oracle.
Can we find $g^Y\bmod p$ in ...
- 908
1
vote
1
answer
35
views
Internal direct product of group of invertible elements in a Paillier modulus
Let $p$ and $q$ are Sophie-Germain primes such that $p=2p'+1$ and $q=2q'+1$. Also let $n=pq$ and $n'=p'q'$. In Section 8.2.1 of this paper, the internal direct product of $\mathbb{Z}_{n^2}^*$ is shown ...
- 125
0
votes
1
answer
124
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 ...
3
votes
0
answers
289
views
Elliptic Curve how to calculate y value [duplicate]
I have been reading the book Mastering Bitcoin written by Andreas. It was the process of compressing public keys that hurt my mind. Specifically, a public key after being generated from a private key ...
- 85
1
vote
2
answers
174
views
How to find the extractor in the Knowledge-of-Exponent Assumption?
From Mihir Bellare's paper
Let $q$ be a prime such that $2q +1$ is also prime, and let $g$ be a generator of the order $q$ subgroup of ${Z^∗}_{2q+1}$. Suppose we are given input $q$, $g$, $g^a$ and ...
- 2,167
0
votes
1
answer
77
views
An equivalent definition for shamir secret sharing?
Taking into account this paper I will write here a definition that the authors provide.
$\textbf{Definition:}$ (linear secret sharing scheme). A $(t,n)$ secret sharing scheme is a linear secret ...
- 279
-1
votes
1
answer
49
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 ...
- 279
2
votes
0
answers
46
views
Centrality of Gaussian distribution for LWE error
Consider the LWE problem.
Let $A$ be an $m \times n$ matrix, $x$ is an $n \times 1$ vector, $u$ is a $m \times 1$ vector, and $e$ is sampled from a Gaussian distribution.
We are given either $Ax + e ~~...
- 347
1
vote
0
answers
261
views
Building an Adversary for a PRF game
Here is the game:
How can I make an $\mathcal{O}(k^2)$-time adversary making only one query to its Fn oracle and achieving advantage $= 1 - 1/(p-1)$
Here is my idea so far:
query $2^{-1}$, which when ...
- 21
2
votes
1
answer
336
views
Sage code for finding generator matrix of MDS code
Let $L$ be an $[n,k]$ code. A $k\times n$ matrix $G$ whose rows form a basis for $L$ is called a generator matrix for $L$.
A linear $[n,k,d]$ code with largest possible minimum distance is called ...
- 23
2
votes
1
answer
177
views
What are the expected values of a particular rotational-XOR property of a sequence of random bitstrings?
Assuming that $x$ is a sequence of $l$ bits and $0 \le n < l$, let $R(x, n)$ denote the result of the left bitwise rotation of $x$ by $n$ bits. For example, if $x = 0100110001110000$, then $$\begin{...
- 1,248
0
votes
0
answers
114
views
Matrix formulation of Number-theoretic transforms (NTT)
I have two polynomials over a finite field. I am trying to compute the product of these polynomials using Number-theoretic transforms. For my use case, it makes sense to do this in the matrix form.
...
- 23
1
vote
0
answers
116
views
Modifying discrete logarithm problem in Zp by selecting a subset of group elements
Let $g$ generator of cyclic group $Z_p$ of order $p-1$, where $g$ can generate all group elements $\alpha \in Z_p$ as $\alpha = g^x$mod$p$, $x \in (0..p-1)$, where the discrete logarithm problem is ...
- 294
0
votes
1
answer
123
views
RSA: why $( e^{-1} ~\text{mod}~ n \cdot \varphi(n)) ~\text{mod}~ \varphi(n) = e^{-1} ~\text{mod}~ \varphi(n)$ holds for a specific setting of RSA
Let $p,q$ are primes and $n = pq$ as in every RSA setting and now use a random $e$ that holds the following properties
$gcd(e, \phi(n)) \neq 1$
$(e^{-1} ~\text{mod} ~\phi(n))^{4}\cdot3 < n$
$e^{-1}...
