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.

Filter by
Sorted by
Tagged with
0
votes
1answer
45 views

How to caculate the summation of successive modular inverses?

$p$ is a big prime. $p>2^{2048}$. So how to caculate the summation of successive modular inverses over $p$? $$ \sum_{i=1}^{\frac{p+1}{2}-1}{i^{-1}}\pmod p $$ As to $p$ is a big prime, it's ...
0
votes
1answer
56 views

Lifting a congruence $f(X) \equiv gh (\textrm{mod} \ p)$ to a higher power moduli

I have the polynomial ring $R = \mathbb{Z}[X]/(X^N - 1)$ with $N = 11$ and $h \in R$ with \begin{equation*} h = 7 -11X - 7X^2 -12X^3 + 8X^4 - 11X^5 + -8X^6 + 11X^7 - 4X^8 + 2X^9 + 3X^{10} \end{...
4
votes
2answers
310 views

How is information disclosed by modular multiplication?

Consider the case that $c = a \cdot b \mod p$ where $p$ is a known prime and $0 < a < p$ and $0 < b < p$ are unknown integers numbers. Furthermore, some bits on the value of $c$ are ...
35
votes
3answers
78k views

Calculating RSA private exponent when given public exponent and the modulus factors using extended euclid

When given $p = 5, q = 11, N = 55$ and $e = 17$, I'm trying to compute the RSA private key $d$. I can calculate $\varphi(N) = 40$, but my lecturer then says to use the extended Euclidean algorithm to ...
0
votes
1answer
85 views

Retrieve message from rsa ciphertext based on some conditions

Assume: $x = m^{e-1}\bmod n$ $y = m^{d-1}\bmod n$ Here $m$ is a message, $e$ is the public exponent, $d$ is the private key and $n$ is the modulus of an RSA key pair. Now if I know $e=65537$, $x$, $...
1
vote
1answer
117 views

Two formulas work for this three-pass exchange problem, but I can't figure out why one of them works

Problem statement: "Suppose that users Alice and Bob carry out the 3-pass Diffie-Hellman protocol with p = 101. Suppose that Alice chooses a 1 = 19 and Bob chooses b 1 = 13. If Alice wants to ...
0
votes
1answer
30 views

Finding product of two unknown numbers each raised to a known power

Let $G$ be a group, and let $a, b\in G$, and let $[3] = \{0,1,2\}$. Let $(x_i,y_i)$ for $i\in[3]$ be known constants. Assume that I know the elements: $$c_i = a^{x_i}b^{y_i},\quad i\in[3]$$ Then, ...
8
votes
2answers
1k views

Why is Approximate GCD a hard problem?

There are many Fully Homomorphic Encryption over the Integers schemes whose security is based on the intractability of the Approximate GCD (AGCD) problem. The paper Algorithms for the Approximate ...
3
votes
1answer
52 views

Proving that RSA encryption function with non-square free modulus is not a permutation

Here is a backgroung for the question on hand. While studying RSA I came up to the question about what happens if $p$ and $q$ involved in modulus computation are not actually primes? There is already ...
0
votes
1answer
287 views

Count elements with a given order in the multiplicative group $n=pq$ (RSA) [closed]

We know that the order of an element $a$ in the group $\mathbb Z_n^*$ is $k$ where $k|lcm(p-1,q-1)$ where p,q are distinct primes. Something else i think we know is that the elements that have order $...
0
votes
1answer
139 views

Why discrete logarithm modulo composite moduli not popular and not defined in standards?

The classical discrete logarithm problem is to find $x$ such that $g^x\equiv h\bmod p$ where $p$ is a prime and $g$ is generator of multiplicative group modulo $p$. The demerit of this approach seems ...
0
votes
2answers
95 views

Resources for mathematics of cryptology

I am an undergraduate student looking for resources (books or lectures) explaining mathematics involved in cryptography, such as number theory, elliptic curves etc. I found the book 'A Course in ...
7
votes
1answer
260 views

Why is a number of shares that is greater than a threshold required to construct secret?

In this][1] paper of Asmuth–Bloom threshold SSS, the algorithm is as follows: Shares Distribution To distribute n shares of a secret $K$ among the set of participants $P = \{ p_i : 1 ≤ i ≤ n\}$, the ...
5
votes
2answers
411 views

Non-commutitive and nonassociative algebraic structures in cryptography

Are there any cryptographic algorithms or primitives that have been developed and studied that make use of non-commutative or non-associative algebraic structures such as quaternion integers or ...
1
vote
1answer
80 views

Why $f(x)=x^e$ is a bijection i.f.f $e\in{\mathbf{Z^*_{\phi(N)}}}$?

I understand that if $e\in{\mathbf{Z^*_{\phi(N)}}}$ then $\gcd(e,\phi(N))=1$ and if $e\not\in{\mathbf{Z^*_{\phi(N)}}}$ than $\gcd(e,\phi(N))\neq{}1$. But I couldn't figure out why this implies ...
4
votes
0answers
102 views

How are the constants found in the AVX2 implementation of CRYSTALS-KYBER round 2 generated?

The post-quantum lattice-based cryptosystem CRYSTALS-KYBER which has made it to the second round of NIST PQC includes two implementations: 1) a baseline reference implementation in C and 2) an ...
4
votes
1answer
248 views

Proving the knowlege of e-th root in an non-interactive way

Just like in this question: Protocol for proof of knowledge of $l$-th root I want to prove that for $u^e = w$ I know $u$ without revealing it. Three other requirements are: e is small (65537) The ...
3
votes
3answers
79 views

Is there any Information on the “Modular Approximate Greatest Divisor” problem?

The Approximate Greatest Common Divisor (AGCD) problem is the difficulty of obtaining the value $\ p\ $ when given samples of $\ pq_i + e_i$ for secret values $p, q_i, e_i$. I would like to know how ...
1
vote
1answer
68 views

The way to break Diffie-Hellman(small nonprime number)

i am wondering how to break DH(small nonprime number). Let's say we don't know: $a$: Alice's private key $b$: Bob's private key And we know: $N$: nonprime number $p$,$q$: $N = p * q$ ($p$ and $q$...
3
votes
2answers
1k views

Is computing roots moduli a composite $N$ a hard problem without knowing the factorization of $N$?

Suppose that we are given $\mathbb{Z}_{N}$ and an element $x^u \in \mathbb{Z}_{N}$ with $u \in (0,l]$ where $l$ is the bit-size of $N$. Is it difficult to recover $x$ by knowing $u$ without knowing ...
3
votes
0answers
105 views

RSA calculate $d$ using Chinese Remainder Theorem with $d_p$, $d_q$ and $e$

Suppose for a RSA system I have the following variables given: modulus $n$, expononent $e$, $d_p$ and $d_q$Where, $d_p = d\bmod(p-1)$ and $d_q = d\bmod(q-1)$, Is it possible to find the private ...
4
votes
2answers
83 views

Protocol for proof of knowledge of $l$-th root

Assume we have Group G in which the adaptive root assumption holds. This assumption states that if we choose an element $w$ and after that, if we receive a prime value $l$ it is hard to find the $u$ ...
0
votes
0answers
36 views

Point-halving/solving quartic equations over the elliptic curve E(Z_N)/ring Z_N where N = pq

I am wondering whether there are any results/whether there is any knowledge about the following problem: Given a univariate polynomial (say, a quartic) equation defined over $\mathbb{Z}_N$, is it ...
0
votes
0answers
53 views

Trivariate Coppersmith Implementation

Bivariate Coppersmith is standard package in math software with number theory support. Bauer and Antoine Joux introduced trivariate Coppersmith in https://www.iacr.org/archive/eurocrypt2007/45150361/...
3
votes
1answer
92 views

Constructing an integer with specific totient without factorization

Given $N(=pq)$, but not its factorization. Somehow you manage to know, that $k$ divides $\phi(N)$. Is it possible to come up with an integer $N^{*}$, for which $\phi(N^{*})=\phi(N)/k$, without ...
0
votes
2answers
121 views

Why is Multiplicative group used in RSA or Euler's theorem but not additive?

I am on the verge to understanding RSA, but suddenly a question popped into mind. When we are calculating $U(N)$ i.e $U(PQ)$, we are taking invertible elements that are co-prime to $N$. For example, $...
0
votes
0answers
45 views

FLT is partly applying to RSA equation, and also relation between ED mod phi and Phi + 1 mod N

After numerous attempts from myself and all of you guys, I finally came to understand RSA. I can now prove it and understand how I got there. But I still have some very few polishing questions. 1) We ...
2
votes
1answer
99 views

Relation between $N = P \times Q$, and $\Phi(N)$

When studying RSA, and proving simple concepts to myself, I went and understood groups and rings, but I failed to understand Lagrange's theorem. I did understand how from invertible finite groups I ...
0
votes
0answers
34 views

Proof of two pairs with same exponent

Lets assume we have a group $G$ with unknown order. And we have a pair $(A_1,K_1), (A_2,K_2)$ in which all $A_1,K_1,A_2,K_2$ are group elements. The claim is $A_1= K_1 ^ x$ and $A_2 = K_2 ^ x$. or ...
1
vote
1answer
58 views

number theory question in a group with unknown order

I was reading a paper and I am struggling understanding one part of it. Lets say we have a group $G$ of an unknown order $n$. we know that $B<n<B+C$. both B and C are large values). we choose a ...
10
votes
3answers
5k views

What place do prime numbers have in cryptography?

My understanding of hashing and encryption is rather limited. I certainly do not understand the mathematical formulas at play in these algorithms. With that said, what part do prime numbers play in ...
1
vote
2answers
84 views

A number theory problem in RSA

Let say we have $N=pq$ (Both $p$ and $q$ are safe primes, meaning $\gcd(p-1,q-1)=2$) let's assume $e$ is an odd number which can be efficiently factored and assume that we know the $e$'th root of 1 ...
3
votes
1answer
94 views

Schnorr proof of group with unknown order (but the prover know the order)

We assume that we have $n = pq$, where $p = 2p'+1$, $q = 2q'+1$, and all $p, q, p', q'$ are large primes. Pick $g' \gets_R Z_n^*$, and compute $g = (g')^2 \bmod n$. Then we have a generator $g$ for $...
7
votes
1answer
141 views

Distance between consecutive primes distribution

In several prime generation schemes I saw we pick a random number uniformly at random from a wide range and find the next prime after it. Obviously with such a scheme some primes are more likely than ...
1
vote
0answers
24 views

Help with next step in the Quadratic Sieve

So I am at the same step as someone from math.stackexchange but he never recieved an answer so I will copy-paste his question here: Say, for N = 90283, I compute bound 𝐵=𝑒(12+𝑜(1))(ln(𝑛)ln(ln𝑛√))...
7
votes
1answer
231 views

Sigma protocol when order is unknown

In the following paper (page 5) they have a proof that a triple $\left(g,b_{i-1},b_{i}\right)$ is of the form: $\left(g,g^{x},g^{x^{2}}\right)$ for some x. The relevant text from the paper is as ...
2
votes
0answers
69 views

Reciprocity Laws in Cryptography

Does anybody know applications of higher reciprocity laws (i.e. the reciprocity laws "higher" than the quadratic one, like the cubic or quartic reciprocity law) in cryptography? So far I have found ...
4
votes
0answers
50 views

Generalized Benaloh cryptosystem with $r=2$

Benaloh cryptosystem requires $\gcd(r, (q-1))=1$ which is impossible if $q>2$ (since it needs to be a large prime) and $r=2$. This confuses me, since Benaloh is referred to as an "extension" or "...
3
votes
2answers
82 views

Size of $E$ over $\mathbb{F}_p$ contains $p+1$ points

I am struggling to prove this claim: I proved that the map $x\mapsto x^3+1$ is a bijection from $\mathbb{F}_p$ to itself if we have that $p\equiv 2\bmod{3}$. We have to use this fact to prove that ...
0
votes
1answer
71 views

Why does a primitive root mod n gives a uniform distribution over n?

The result from a primitive root mod n seemly has a uniform distribution over n, is it true? For instance, 3 is a primitive root ...
1
vote
2answers
2k views

Is there an algorithm for factoring N, which is just as simple as this one, but faster?

I found a simple algorithm for factoring semiprime numbers, you can read about it in Factoring Semiprimes and Possible Implications for RSA (paywall-free). It basically works like this: You reverse ...
1
vote
1answer
62 views

Paillier Complex Residuosity problem?

Paillier Cryptosystem depends on both the factorization where $n = p.q$ and the complex residuosity problem which is defined in the original paper as: The problem of deciding n-th residuosity, i.e. ...
16
votes
4answers
18k views

What is the relation between RSA & Fermat's little theorem?

I came across this while refreshing my cryptography brain cells. From the RSA algorithm I understand that it somehow depends on the fact that, given a large number (A) it is computationally ...
1
vote
1answer
325 views

What does modular inversion mean?

I'm trying to implement an e-voting algorithm, which is described at the paper "Internet Voting Protocol Based on Improved Implicit Security" by Abhishek Parakh & Subhash Kak. At the Example 1 ...
1
vote
2answers
74 views

Difference between when select x from $\mathbb{Z}_{p-1}$ and $\mathbb{Z}_p$ in discrete logarithm Problem?

Reading "Security Arguments for Digital Signatures and Blind Signatures" paper, I confused by some questions. Q1. when it refers to "El Gamal signature scheme", The key generation algorithm: it ...
0
votes
1answer
111 views

How to compute ElGamal decryption by hand

Lets say that $u=3, x=5, v=2$, how do we work out $u^{-x}*v$, so $3^{-5} * 2$. I know how to work out the answer if it was $3^5 * 2$ but how do we do it with negative exponents?
1
vote
2answers
601 views

How to prove if a Hash Function is collision resistant

Say we have the following Hash Function, H(x) = 4x mod N where N is a number generated by multiplying two prime numbers and x={0,1,2,3,...,N-1}. So lets assume that ...
0
votes
2answers
184 views

Why are some group representations much easier to compute discrete logarithm for? [duplicate]

The multiplicative group mod $p$ is isometric to the additive group mod $p-1$, yet computing discrete logarithms in the additive group is easy and completing discrete logarithms in the multiplicative ...
3
votes
2answers
207 views

Why does square root $\pmod n$ find $p$ and $q$ (as $n = p \cdot q$)?

Let $n = p*q$, with $p \neq q$ and $x^2=1 \pmod n$, $x+1 \neq 0 \pmod n, x-1 \neq 0 \pmod n$ (So x is a non-trivial square root mod n.) I don't see how $\gcd(x+1,n) \in \{p,q\}$ follows. I ...
-2
votes
1answer
166 views

Why can every prime number be written as 6k±1? [closed]

I want to know how to be sure that each prime number can be written in the form $6k±1$. How I can find the prime number that exists after a composite number with this property of prime or other ...