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
2 votes
1 answer
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 ...
user avatar
9 votes
1 answer
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), ...
user avatar
  • 191
4 votes
2 answers
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 ...
user avatar
  • 409
0 votes
0 answers
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 ...
user avatar
  • 1
0 votes
0 answers
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,&...
user avatar
1 vote
2 answers
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 ...
user avatar
1 vote
1 answer
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. ...
user avatar
  • 882
5 votes
0 answers
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$ ...
user avatar
  • 13.5k
1 vote
1 answer
82 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 ...
user avatar
  • 882
0 votes
1 answer
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 ...
user avatar
3 votes
0 answers
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 ...
user avatar
1 vote
0 answers
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$...
user avatar
  • 11
-1 votes
1 answer
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 ...
user avatar
2 votes
2 answers
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 ...
user avatar
  • 21
3 votes
1 answer
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 ...
user avatar
  • 133
1 vote
0 answers
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 ...
user avatar
1 vote
0 answers
68 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^...
user avatar
0 votes
2 answers
153 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$...
user avatar
6 votes
1 answer
186 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 ...
user avatar
1 vote
1 answer
241 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 ...
user avatar
  • 11
1 vote
1 answer
80 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 ...
user avatar
  • 1,647
0 votes
1 answer
129 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$...
user avatar
  • 882
2 votes
2 answers
79 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 ...
user avatar
  • 155
2 votes
0 answers
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 ...
user avatar
  • 53
2 votes
1 answer
169 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 ...
user avatar
  • 1,647
3 votes
2 answers
358 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$ ...
user avatar
-1 votes
1 answer
63 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 ...
user avatar
0 votes
2 answers
228 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 ...
user avatar
0 votes
1 answer
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?
user avatar
1 vote
1 answer
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 ...
user avatar
  • 1,647
8 votes
2 answers
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 ...
user avatar
  • 1,647
0 votes
2 answers
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 ...
user avatar
  • 19
6 votes
2 answers
488 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 = ...
user avatar
0 votes
1 answer
236 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 ...
user avatar
8 votes
2 answers
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 ...
user avatar
6 votes
1 answer
149 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 ...
user avatar
  • 125k
-3 votes
1 answer
234 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 ...
user avatar
0 votes
0 answers
84 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 ...
user avatar
4 votes
1 answer
199 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 ...
user avatar
  • 117
1 vote
2 answers
158 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 ...
user avatar
2 votes
1 answer
103 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 $...
user avatar
2 votes
1 answer
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 69
0 votes
1 answer
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, ...
user avatar
2 votes
1 answer
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-...
user avatar
  • 197
8 votes
1 answer
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 ...
user avatar
  • 135
1 vote
2 answers
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$?
user avatar
3 votes
3 answers
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 ...
user avatar
0 votes
1 answer
68 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 ...
user avatar
  • 13
2 votes
1 answer
121 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-...
user avatar
  • 23

1
2 3 4 5
7