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.

Filter by
Sorted by
Tagged with
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
votes
1answer
65 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 ...
2
votes
2answers
161 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 ...
2
votes
1answer
142 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
0answers
42 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
0answers
62 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^...
0
votes
2answers
93 views

The number of odd integers we have to test until to find one that is a prime for any arbitrary RSA modulus size

Popular RSA modulus sizes are $1024$, $2048$, $3072$ and $4092$ bit. How many random odd integers do we have to test on average until we expect to find one that is a prime? I know roughly every $\ln p$...
6
votes
1answer
166 views

Finding large devious primes

Call a prime $p$ devious if $(p-1)/2$ is a Carmichael number. They are called devious since they superficially look like safe primes but are not. In particular, Diffie-Hellman using such a prime could ...
1
vote
1answer
132 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
1answer
73 views

The significance of the field of the factor in Lenstra’s ECM

I am going through Lenstra's Elliptic Curve Factorisation from Silverman's Mathematical Cryptography book. I have understood the algorithm itself, but unable to understand a specific point the book ...
0
votes
1answer
98 views

Setting up the discrete logarithm framework

The discrete logarithm problem over prime cyclic groups consist of finding $x$ satisfying $g^x\equiv h\bmod p$ where $g$ is generator of multiplicative group $\mathbb Z/p\mathbb Z$ at a large prime $p$...
2
votes
2answers
54 views

Constraints on q for q-ary lattices?

In lattice cryptography, people often work with q-ary lattices so that we can use the hardness of short integer solution (SIS) and learning with errors (LWE). I saw in some notes that sometimes we ...
2
votes
0answers
76 views

What would be the safety requirements for the primes in $n=p \cdot q$ regarding the factorization?

Let it be $p, q \in \mathbb{P}$ with $p,q \in [2^{b-1}, 2^b]$ for some $b \in \mathbb{N}$ and $p \cdot q = n \in \mathbb{N}$. What would be the distance between $p$ and $q$ (as a function of b) so ...
2
votes
1answer
122 views

Quadratic Sieve: Is there a thumb rule for deciding how many numbers to sieve?

In the Quadratic Sieve algorithm, we first decide on a B & then look for B-smooth prime factors by sieving using a quadratic polynomial. I can find a few formulas which help figure out how to ...
3
votes
2answers
354 views

Recognize whether two random values are raised to the same power

Alice selects two random numbers from a finite field $Z_p$ : $a$ and $b$. Bob does one of the two following steps randomly (sometimes he does step 1; sometimes step 2): He chooses a random number $r$ ...
-1
votes
1answer
61 views

Is there some function of $n$ that is a multiple of $\phi(n^2)$?

Not sure which forum to post this question so here is a link to it from MSE. This is to adapt the approach of Fermat's Little Theorem to the Paillier encryption system. I understand that this will ...
0
votes
2answers
149 views

Factoring RSA when reusing N

Suppose in two RSA instances the same $p,q,N$ are used, but different public keys $a,b$ (and corresponding private keys) Suppose now we have the two equations $c_{1}=m^{a} \bmod N$ $c_{2}=m^{b} \bmod ...
0
votes
1answer
49 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
1answer
99 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 ...
7
votes
2answers
831 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 ...
0
votes
2answers
207 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 ...
5
votes
2answers
332 views

Breaking RSA with Factor in Range of $\sqrt{N}$

Suppose on of the RSA prime factors $p$ is the range of $\sqrt{N}$, in particular it holds that $|p-\sqrt{N}|<\sqrt[4]{N}$ I want to show that RSA can be broken in time poly(log N) Given hint: $N = ...
0
votes
1answer
152 views

How many points in RSA, such that $m^e = m \bmod n$

For every RSA-cryptosystem, there exist some messages $m$, for which it holds that $m^e \equiv m \pmod n$ As to the question, how many such messages exist, this question has already been asked and ...
8
votes
2answers
2k views

Prime factorization (102 digits)

I have a number that consists of 102 digits and I need to factor it. I ran it in alpertrom.com.ar, but it'll take up to 40 hours if I counted all right. Is there any way to make it by hand (stupid ...
6
votes
1answer
139 views

Schnorr groups allowing fast modular reduction, vs GNFS

I'm looking for Schnorr groups allowing fast modular reduction. Say, using the notation in DSA, with 256-bit prime $q$ and 3072-bit prime $p$, and $p\equiv1\pmod q$. Are there standards, RFC, or other ...
-3
votes
1answer
213 views

Can Big Data together with deep neural networks attack RSA by affording the vast calculation of prime multiplications in advance?

This is a spin-off from Can Big Data attack RSA by just calculating many prime multiplications in advance? [duplicate]. Intro I am somewhat new to cryptography. Repeating the basics of RSA from How ...
0
votes
0answers
83 views

Can Big Data attack RSA by just calculating many prime multiplications in advance? [duplicate]

Intro I am somewhat new to cryptography. Repeating the basics of RSA from How are the primes used to generate RSA keys?: Textbooks say the one-way function is merely two primes (with some critical ...
4
votes
1answer
169 views

Why does PGP still use the Fermat primality test? What if it hits one of the Carmichael numbers?

Since the Fermat primality test is not very reliable, most applications use it for pretesting only. Wikipedia says that PGP still uses it: Another well known program that relies only on the Fermat ...
1
vote
2answers
133 views

Who provides prime numbers for cryptographic protocols?

I am currently writing a thesis about different cryptographic protocols like DH-Key exchange, TLS or IKE. Most of them rely on a prime number earlier or later, so for security reasons I wondered if ...
2
votes
1answer
88 views

GetModulus negligible probability

I have this textbook definition, I shall include below. GenModulus denotes a ppt algorithm that, on input $1^n$, outputs $(N, p, q)$ where $N = p\,q$ and (except with negligible probability) $p$ and $...
2
votes
1answer
198 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 ...
0
votes
1answer
58 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
869 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, ...
2
votes
1answer
61 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-...
6
votes
1answer
476 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
2answers
184 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$?
3
votes
3answers
135 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 ...
0
votes
1answer
64 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 ...
2
votes
1answer
106 views

Using Optimal Prime Field in ECC

"Optimal Prime Field is a family of 'low-weight' prime fields that allow for efficient software implementation of all operations requiring a modular reduction, in particular the field-...
0
votes
0answers
60 views

How do I retrieve a number which has been multiplied with a random number?

I have a 1024-bit number $n$ obtained by multiplying two 512-bit randomly generated prime numbers $p$ and $q$. Then there's $\phi = (p-1)(q-1)$, which is another 1024-bit number. I do not have $\phi$ ...
1
vote
0answers
57 views

Will a list of all prime numbers upto certain number of bits compromise crytopgraphic algorithms based on prime factorization? [duplicate]

I understand that many cryptographic algorithms depend on the difficulty of large prime factorization. Will a list of all prime numbers upto certain number of bits make it easy for an attacker to ...
4
votes
0answers
112 views

Source of very large prime numbers

The RSA cryptosystem makes use of $n=pq$ where $p, q$ are large prime numbers. With quantum computing, factorization might become easier, so it will probably be useful to use much much bigger $p$, $q$ ...
0
votes
0answers
32 views

RSA encryption. Does message have to be coprime to n? [duplicate]

If I understand correctly, for RSA to work we need the message(cleartext) M $\in Z_n$ and gcd(M,n)=1. That is M coprime to n. This is to fulfil the requirement for Eulers theorem. How does RSA make ...
3
votes
1answer
80 views

Repeated modular square roots to recover original base

I'm given a large prime $p$ and $c \equiv m^e \pmod p$, and $e = 2^{64}$. Typical RSA rules don't apply here, since $\phi(p) = p - 1$ is even, and $e$ is a power of two, so they share a common factor, ...
0
votes
1answer
668 views

why to use a safe-prime in Diffie-Hellman key exchange?

In order for Diffie-Hellman to be extra secure we must use a safe prime which is (p – 1) / 2 will also be a prime. so my question is what extra benefit of using ...
8
votes
2answers
2k views

Is there a pseudo message that will encrypt and decrypt correctly if one of the primes is a pseudo prime in RSA

For prime number generation, one can use a probabilistic prime number generation algorithm like the Miller–Rabin primality test that will yield a composite as a probable prime with probability $\frac{...
3
votes
1answer
115 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 ...
4
votes
1answer
134 views

Consequence of $p\bmod e=2$ in RSA prime generation

When generating a prime $p$ for use in an RSA modulus with public exponent $e$, it is necessary that $\gcd(p-1,e)=1$. When $e=3$, and since $p$ is a large prime, that implies $p\bmod e=2$. Assume an ...
0
votes
1answer
328 views

If $((p-1)*(q-1) -1)$ divisible by $e$ ($e$ is odd number) , then $\text{gcd}(e,(p-1)*(q-1)) = 1$

If $((p-1)(q-1) -1)$ divisible by $e$ ($e$ is odd number) , then $\text{gcd}(e,(p-1)(q-1)) = 1$. ($p,q$ are prime numbers ) Is this true, if yes why, if not why not ?
1
vote
2answers
164 views

ZKP for product of two primes

I'm struggling to understand the intuition of the zero knowledge-ness of this proof from the following paper. The proof is a 2 round where the verifier asks the prover to extract square roots of ...

1
2 3 4 5
7