# Questions tagged [prime-numbers]

A prime number is an integer greater than 1 with no divisors other than itself and 1. Primes and prime products play an important role in public key cryptography.

341 questions
Filter by
Sorted by
Tagged with
57 views

### What happens if the Miller-Selfridge-Rabin-Test fails

MRT is a probabilistic test and even the deterministic version relies on the correctness of the Riemann hypothesis. When the test fails and I use a non-prime number in e.g a public key encryption ...
220 views

### Does a 2047-bit factoring oracle affect 2048-bit RSA security?

I started wondering. RSA relies on prime factorisation being hard. So if a 2047-bit oracle machine existed that could instantly factor any 2047-bit number (and you can't look inside at how it works), ...
1k views

### Are there prime numbers that are easy to modulo within 40 bits to 60 bits?

I want to implement LWE-based encryption scheme, the modulo $q$ could be decomposed as $q = q_0\cdot q_1\cdots q_k$ according to CRT. I guess the modular arithmetic by $q_i$ is key operation, so I ...
87 views

### RSA: Obtain private key exploiting badly generated public key

I have to solve the following problem: What I have: $n$, a 2048 bit number What I need to find: $p$ and $q$ such that $n = p\cdot q$. What I know: With $p_1$ the first half of $p$ and $p_2$ the ...
34 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,&...
1 vote
76 views

### Factorization of the product of two specific primes

Help me please. Consider specific primes $p = x^{d} + 1$ and $q = x^{e} + 1$ for some $x, d, e \in \mathbb{N}$. Can their product $n = pq$ be factorized faster than the product of general primes ? In ...
1 vote
47 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. ...
203 views

### Average false-positive rate for a round of Miller–Rabin

I'm aware that the Miller–Rabin primality test will claim primality for a composite number with at most a $\frac{1}{4}$ probability for some arbitrary, odd composite $n$ and a random witness $a$ ...
1 vote
82 views

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 ...
76 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 ...
284 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 ...
1 vote
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$...
81 views

### Why doesnt RSA use composite numbers?

I am currently writing a math paper regarding the importance of prime numbers in RSA encryption. I understand that generating q x p = N (where p and q are prime numbers) is simple for a computer ...
175 views

### How much work to find such $n$?

Let $W$ be a random $200$ bit number. How much work would it take to find a semiprime $n=p_1\cdot p_2$ such that $p_1,p_2 > 2^{50}$ and $|W-n|<2^{12}$? More generally, let $W_b$ be a random ...
176 views

### Given $φ(n)$ how can we find any combinations for $p, q$ prime numbers

Suppose i already have found that $φ(n) = 240$ for $n = 900$. How can i conclude that my $n = pq$ is of type $2^2\cdot3^2\cdot5^2$? What is $q$ and what is $p$ here? To be more precise with my ...
1 vote
69 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 ...
1 vote
68 views

51 views

### When using prime factorization for key gen, is there a limit on the size of the prime factors?

If there is a limit, does that leave a limited number of prime numbers that can be used for key gen? And, if that is the case is the encryption system vulnerable?
1 vote
144 views

### Pollard's p - 1 - how do you set the bound & how do you set the base numbers

In Pollard's p-1 algorithm for factoring N, you try to find a L such that p - 1 divides L. Then you check $gcd(pow(a,L,N)- 1, N)$. If 1 < gcd < N, then you have found one of the factors. I have ...
914 views

### Has there ever been any real world consequences of using probabilistic primality tests for RSA or other similar systems?

Considering the huge amount of RSA certs which have been generated, wouldn't there probably be a small number of certs where one of the primes which may have actually been a composite? Has this ever ...
218 views

### What is the name of this public key encryption cryptosystem?

I have been trying to find the name of a public key encryption cryptosystem that I learnt as an introduction to cryptography some years ago but the only scheme I could find was something similar but ...
488 views

218 views

### Inverse function of RSA and safe prime requirement of DH Key exchange

Ok so the inverse function of RSA encryption (that is decryption) is $m \gets c^{d}\bmod N$ where $d$ is the secret exponent As I understand the hardness of RSA depends on two things: the Integer ...
70 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 ...
2k views

### Finding p and q in RSA with a given n, |p-q|<10000

I've got an RSA encryption I need to crack, but to do it I need to find the p and q values of an N I am given - it's quite large, around 308 symbols. I know that N is the product of primes p & q, ...
82 views

### Does Rabin function lose its one-way property if squaring mod a prime?

I am looking into various one way functions and I stumbled upon a Rabin function, which is squaring modulo an RSA modulus $N=pq$, where $p,q$ are prime: $R_N(x) = x^2 \mod N$. Would it lose the one-...
984 views

### Relation between factors and their sum on RSA

In RSA and other crypto based on prime factors. If I would know the sum of $p+q$, would it reveal any more information than just knowing $p\cdot q$? Edit: I do not know either $p$ or $q$. The question ...
1 vote
265 views

### How to get the order of a group generator in DH?

For a DH parameter prime, if the generator $g$ is 2, how do I get the order $q$?
156 views

### Reason for squaring and not arbitrary exponentiation in Wesolowski and Pietrzak verifiable delay functions (VDFs)

I'm working at understanding the Wesolowski and Pietrzak RSA group based VDFs (verifiable delay functions). These basically work by requiring the prover to do a bunch of repeated squaring within a ...
$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 ...