Skip to main content
32 votes
Accepted

Why does RSA need p and q to be prime numbers?

However, factoring a large integer is extremely difficult, even for a computer using known factoring algorithms. Not categorically. Factoring a large integer is trivial if it is only composed of ...
marcelm's user avatar
  • 596
27 votes
Accepted

NIST Diffie-Hellman prime: how was it picked? Where did it come from?

Is this number specified anywhere? It was formally specified in this RFC as the 1536 bit MODP group (although its use predates that RFC). However, from what I've seen, the 2048 bit MODP group from ...
poncho's user avatar
  • 149k
18 votes
Accepted

Why does GMP only run Miller-Rabin test twice when generating a prime?

The Baillie-PSW test is being used in place of 24 Miller-Rabin tests. This is not unreasonable for large numbers when the cost of Miller-Rabin testing can become burdensome and also helps to prevent ...
Daniel S's user avatar
  • 24.1k
17 votes
Accepted

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

The probability of accidentally mistaking a composite for a prime, for a number that you chose yourself, is extremely low and quantifiable, as others have mentioned. This is the situation that is ...
Mikero's user avatar
  • 13.9k
16 votes

Why does RSA need p and q to be prime numbers?

The main reasons we usually choose $p$ an $q$ prime numbers are: For a given size of $N=p\,q$, that makes $N$ harder to factor, hence RSA safer. Although efficient factoring algorithms do not find ...
fgrieu's user avatar
  • 143k
15 votes
Accepted

How to efficiently generate a random safe prime of given length?

There is no more efficient way of generating a safe prime. Even in OpenSSL's optimized code, it can take a long time to generate a safe prime (30 seconds, a minute, 2 minutes). Run "openssl gendh 1024"...
Yehuda Lindell's user avatar
15 votes
Accepted

Prime factorization (102 digits)

Your 102-digit nuber is two digits more than the first RSA challenge RSA-100 that has 330-bit. This can be easily achieved with existing libraries like; CADO-NFS ; http://cado-nfs.gforge.inria.fr/ ...
kelalaka's user avatar
  • 49.1k
14 votes

How to encrypt the number one using RSA?

The algorithm you quote is usually called textbook RSA and is not used in practice for numerous security reasons (the problem you pointed out, is just one of them). In practice, you have to pad (or ...
mat's user avatar
  • 2,528
14 votes
Accepted

Algorithm to find primes $q$ and $p$ with $q\, |\, p - 1$?

The critical facts enabling to find such $p$ in practice are: We can easily tell with practical certainty if an integer with many thousand bits is prime or not, using a primality test such as Miller-...
fgrieu's user avatar
  • 143k
14 votes
Accepted

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

We expect that the encryption will fail since the incorrect $\varphi(n)$. Not always; for example, consider the case $p=31$ (a Mersenne prime) and $\bar{p} = 561 = 3 \times 11 \times 17$. We'll set $...
poncho's user avatar
  • 149k
13 votes
Accepted

Efficient function/algorithm/method to do modular exponentiation

Efficient is not sufficient in cryptography. You also need secure computation. Consider a standard repeated squaring implementation in Python; ...
kelalaka's user avatar
  • 49.1k
12 votes

Why does RSA need p and q to be prime numbers?

RSA moduli are generally of the form $N = pq$ for two primes $p$ and $q$. It is also important that $p$ and $q$ have (roughly) the same size. The main reason is that the security of RSA is related to ...
user94293's user avatar
  • 1,779
12 votes
Accepted

Intentionally craft a 180 to 255 bits Integer that bypass this miller‑rabin test with having a known factor

If your Miller-Rabin tests are being computed for random bases, then there is very little chance as at least seventy-five per cent of possible bases will fail for any given modulus. If the bases of ...
Daniel S's user avatar
  • 24.1k
10 votes
Accepted

Why are elliptic curves constructed using prime fields and not composite fields?

For a prime $p$ and an integer $n\geq1$, the ring $\mathbb{Z}/p^n\mathbb{Z}$ is a field if and only if $n=1$. There are fields with $p^n$ elements, usually denoted $\mathbb{F}_{p^n}$ or $\operatorname{...
CurveEnthusiast's user avatar
10 votes
Accepted

Relation between factors and their sum on RSA

Let $n = p \cdot q $ be product of distinct primes $p$ and $q$, of arbitrary size as in the RSA setup. The RSA public key $(n,e)$ contains both the modulus and the public exponent, so we assume both ...
kelalaka's user avatar
  • 49.1k
10 votes

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

First, this is obviously true with no restrictions on $b$. For example, for $b = 2^n-2$ we get that $2^n - b = 2^n - (2^n-2) = 2$ is prime. This is boring, and likely not what you mean (and instead, I ...
Mark Schultz-Wu's user avatar
  • 13.5k
9 votes

Is it feasible to build an index of prime factors?

The Prime Number Theorem proves that there are approximately $\frac{x}{\ln x}$ primes less than any positive integer $x$. There are thus about $\frac{2^{2048}-1}{\ln (2^{2048}-1)}-\frac{2^{2047}}{\ln (...
SAI Peregrinus's user avatar
9 votes
Accepted

How does Python's pycrypto library generate primes?

The documentation is not directly telling the implemented algorithm. One can check from the source code. getPrime uses isPrime ...
kelalaka's user avatar
  • 49.1k
9 votes

How to verify if $g$ is a generator for $p$?

Steps: Factor $p-1$, that is, find the primes which, multiplied together, produce $p-1$. In your case, $2685735182215186 = 2 \times 1342867591107593$ For each prime factor $q$ of $p-1$, verify that $...
poncho's user avatar
  • 149k
9 votes

How to verify if $g$ is a generator for $p$?

In general, proving that $g$ is a primitive root (often called a generator) of a cyclic group is fairly simple. Note this holds true for non prime modulo as well Step 1: Verify that $0\leqslant g \...
justanotheruser's user avatar
9 votes

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

I am not sure if this question should be considered on topic here, but I will answer anyway. Theorem: All prime numbers larger than $3$ can be written as $6k+1$ or $6k-1$ for some natural number $k$. ...
Meir Maor's user avatar
  • 11.8k
9 votes
Accepted

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

Although this might not be the solution you're looking for, the Coppersmith theorem offers a simple answer to this. The (general) Coppersmith theorem states: let $f(x)$ be a monic univariate ...
Samuel Neves's user avatar
  • 12.7k
8 votes

primitive root of a very big prime number (Elgamal DS)

When considering a big prime $p$, the group of invertible integers modulo $p$ are all integers from $1$ to $p-1$. There are $p-1$ of them. The order of an integer $g$ modulo $p$ is the smallest ...
Thomas Pornin's user avatar
8 votes
Accepted

Magic Number to calculate number of rounds for M-R in FIPS 186-4

This constant is used to approximate $(\pi(2^k) - \pi(2^{k-1}))^{-1}$, as shown in (4.1) of the Damgard et al. paper: $$ p_{k,t} \le (\pi(2^k) - \pi(2^{k-1}))^{-1} \sum\nolimits'_{n \in M_k} \bar{\...
Samuel Neves's user avatar
  • 12.7k
8 votes
Accepted

Does a Finite Field of 36 elements exist?

Finite fields only exist for an order $q$ if $q$ is prime or a power of a prime (http://mathworld.wolfram.com/FiniteField.html). Since 36 is neither a prime itself, nor it is a power of a prime ($36 = ...
Ceriath's user avatar
  • 406
8 votes

Factoring 2048 bit number is easy?

my PC found a factor for (2^2048)-1 in under a second...so does that make RSA-2048 less secure right? No. Factoring numbers with special forms like that is easy. You have a Mersenne number, $n = 2^...
Squeamish Ossifrage's user avatar
8 votes

Why does GMP only run Miller-Rabin test twice when generating a prime?

The article, "Strengthening the Baillie-PSW primality test" referred to above, suggests adding a third test to the standard BPSW (MR test base 2 combined with Lucas). But there's a third ...
Robert Baillie's user avatar
7 votes

How to test implementation of primality tests like Miller–Rabin?

Well, the obvious thing to do is give it a long list of integers of known primality, and see whether the algorithm reports it correctly (with it occasionally reporting a composite as "relatively-prime"...
poncho's user avatar
  • 149k
7 votes

Is it feasible to build an index of prime factors?

You are underestimating something, either the number of primes that an attacker would have to generate and store, or the size of the primes that must be multiplied in standard factorisation-based ...
Geoffroy Couteau's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible