The 2024 Developer Survey results are live! See the results

# 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.

272 questions
Filter by
Sorted by
Tagged with
1 vote
159 views

### Example of elliptic curves endomorphism construction

I've started learning about complex multiplication (CM) on elliptic curves. For clarity (and intuition), I want to make some basic example of elliptic curves endomorphism construction for a concrete ...
73 views

• 930
1 vote
49 views

• 361
217 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,194
97 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 ...
1 vote
106 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
622 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
167 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$ ...
48 views

• 655
241 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
299 views

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, ...
323 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 ...
• 453
51 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
1k views

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\\... • 253 1 vote 1 answer 58 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. ... • 930 2 votes 1 answer 196 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^xmod n are uniformly distributed because of the modulo operation. Suppose however that from the original output space Y, we only consider ... • 324 3 votes 2 answers 228 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 pg^{b-km_2}\bmod pg^{a+k'm_3}\bmod pg^{b-k'm_4}\bmod p$$where m_2m_3-m_4m_1=\phi(p) ... • 930 1 vote 0 answers 139 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 ... • 159 1 vote 1 answer 177 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 ... • 930 1 vote 1 answer 39 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 ... • 145 0 votes 1 answer 153 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 ...
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 ...