# Tag Info

31

Primes are important because the security of many encryption algorithms are based on the fact that it is very fast to multiply two large prime numbers and get the result, while it is extremely computer-intensive to do the reverse. When you have a number which you know is the product of two primes, finding these two prime numbers is very hard. This problem is ...

31

The premise "we don't have a way of generating and verifying a 2048-bit prime number with 100% accuracy" is wrong (if we trust the computers performing the operations): it has long been known practicable ways to generate randomly-seeded provable primes, and it is a (somewhat marginal) practice in RSA key generation (see FIPS 186-4 appendix B.3.2). ...

27

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 small factors. A fairly naive algorithm for factoring N is the following: while N > 1: for p in increasing_primes: while p divides N: N = N / p ...

26

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 that same document is actually more popular. Why was this particular number picked? Well, it's a safe prime; in addition, the leading 64 bits and the ...

17

What we really need is a number $\lambda$ satisfying $x^{\lambda+1} \equiv x \pmod n$ for all integers $x$ (which, by induction, then implies that $x^{k\lambda+1} \equiv x \pmod n$ for any $k$). Given such a $\lambda$, and an arbitrary encryption exponent $e$ which is coprime to it, we can then find the multiplicative inverse of $e$ modulo $\lambda$, i.e. a ...

16

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 factors by trial division, it remains much easier to find very small prime factors than large ones. If we chose $p$ and/or $q$ at random without consideration for ...

15

A Mersenne prime is a prime number that can be written in the form $M_p = 2^n-1$, and they’re extremely rare finds. Of all the numbers between 0 and $2^{25,964,951}-1$ there are 1,622,441 that are prime, but only 42 are Mersenne primes. The second sentence is wrong. What they meant to say is that there are 1,622,441 numbers of the form they mentioned in ...

15

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 $e = 13$ and $d = e^{-1} \bmod 30 \times 560 = 3877$. Then, if we pick a random message $m=2$, then $2^e \bmod n = 8192$, and $8192^{3877} \bmod n = 2$; ...

14

If $p=2q+1$ is a safe prime (that is, $q$ is a prime as well), then $p-1=2q$ has exactly two prime factors: $2$ and $q=(p-1)/2$.

14

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 armor) your message. This should be done using the RSA-OAEP (also called PKCS#1 v2.0) scheme. It transforms your message (1) into a pseudorandom block (not 1) ...

13

I can think of two places where we use a Mersenne Prime within cryptogaphy: As a modulus within a prime elliptic curve. $2^{521}-1$ is a prime, and so we can define an elliptic curve using $GF(2^{521}-1)$, which is in moderately common use. One reason we use such a modulus (rather than another prime of approximately the same size) is that the special form ...

13

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" on your computer to see (on my 2015 MacBook pro it can take a long time, but the variance is really high so try a few times). The comments talk about safe ...

12

"I understand that the typical approach is to use pre-generated lists of large primes." This is what I also thought. But I had not considered how many primes we might choose from. As it turns out you choose from ~2.8x10^147 primes with a 1024 bit RSA key and from about ~7.0x10^613 with a 4096 bit RSA key. Then you have up to 4.9x10^1227 possible ...

12

In order to generate a RSA key pair, you are to find a public exponent $e$ and a private exponent $d$ such that, for all $m \in \mathbb Z_n^*$, i.e. $m$ is relatively prime to $n$, $(m^e)^d \equiv m \pmod n$. It is a consequence of Euler's theorem that if $e, d$ satisfy the equation $ed \equiv 1 \pmod {\phi(n)}$, they are such a valid public/private exponent ...

12

Well, this is semi-easy. You should know that public key consists of modulus $N = pq$ with public exponent $e$ and private key is the same modulus with private exponent $d$, where $de=1\pmod{\varphi(N)}$. Now, calculate $k = de-1$ then brute force $gcd(g^{k/2^x}\pm 1, N)$ for random $g$ and small $x$, and with high probability that quickly provides one of ...

12

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 the factoring problem. The most difficult numbers to factor are numbers that are the product of two primes of similar size. Note. There are basically two ...

12

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-Rabin, even though we are typically unable to tell all its factors when it is not prime. About $1.4/b$ integers of $b$ bits are prime. Thus it is more likely ...

10

We want a non-trivial factorization of a moderate odd integer $n$ into positive integers $p$ and $q$, knowing that such factorization with $|p-q|$ suitably small exists. Perhaps the most elementary method answering the question is trial division by integers starting at $\lfloor\sqrt n\rfloor$, going down. This succeeds after checking divisibility of $n$ by ...

9

You need a large random prime modulus where the discrete log is hard. Read about how to choose a prime so the discrete log is hard. Also, you want $p-1$ to have as few small factors as possible. Therefore, the short version is, I suggest you choose a large random 2048-bit prime $p$ such that $(p-1)/2$ is prime. However, Pohlig-Hellman has some serious ...

9

This is actually a special case of a more general property of the Euler totient function: it is a multiplicative function, meaning that, for any two coprime numbers $p$ and $q$, $\phi(pq) = \phi(p)\phi(q)$. The special case where $p$ and $q$ are (distinct) primes is easy to prove. By definition, $\phi(n)$ gives the number of positive integers coprime to and ...

9

If $N = pq$ and both $p$ and $q$ are close to $\sqrt N$, chances are that there exists an odd integer $x$ close to $\sqrt N$, such that $r = N \bmod x^2$ is significantly smaller than $N$. This happens to be the case for the public modulus in the example. When this happens, note that $p = x - s$ and $q = x + t$ for some positive integers $s, t$ such that $k =... 9 There is consensus that it is safe to use random primes$p$and$q$when generating 2048-bit (or wider) RSA public moduli which two prime factors$p$and$q$are about half the key size. That is sanctioned by FIPS 186-4, appendix B.3; specifically, wording in B.3.1 item A: Using methods 1 and 2 [yielding provable (1) and probable (2) random primes], ... 9 The question asks how to systematically pick the public exponent$e$in RSA. I'll stick to public modulus$N$that is the product of exactly two distinct odd primes$p$and$q$, but the choice of$e$is not fundamentally different in multiprime RSA. What's an acceptable public exponent$e$? The public exponent in RSA should be an integer$e>1$with$\...

9

What's actually important isn't prime numbers as such, it's numbers that have factors (other than 1 and themselves) but are very difficult to factor. You get such numbers by multiplying together two very large primes. Numbers that are equally large but have more smaller factors are very much easier to factor, and hence are unsuitable for cryptography ...

9

The documentation is not directly telling the implemented algorithm. One can check from the source code. getPrime uses isPrime and that calls the Rabin-Miller Primality test. getPrime generates a random odd number $\texttt{N}$ and calls isPrime number=getRandomNBitInteger(N, randfunc) | 1 while (not isPrime(number, randfunc=randfunc)): ...

9

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$. Proof: The remainder of a number modulo $6$ is between $0$ and $5$. If it is $1$ or $5$, the above criterion holds. It remains to show that, if it is $0$, $2$,...

8

Here is the issue about hardware errors that Brent is worried about on the slides (I'm not saying I agree; I just saying what the issue is): Suppose we ran our algorithm, and it gave a result "it's prime"; how can we be certain that the algorithm didn't gave us the wrong answer because of an internal hardware error while running the algorithm? This may ...

8

Let me try a simple explanation of NFS. I will necessarily skip lots of details, but I hope you will get the main ideas. The number field sieve algorithm (NFS) is a member of a large family: index calculus algorithms. All algorithms in the family, which can be used for factoring and discrete logarithms in finite fields, share a common structure: ...

8

Assume $n$ is 21. If you try to find the possible factors you have to try around until you find 3 and 7. This is of course easy because of the small numbers, but there is no effective way to do that for big numbers. (And those used in RSA are really big) Now assume $n$ is 32. You can split that into 2 * 2 * 2 * 2 * 2. Now you only have to multipy those (...

8

For many areas of encryption, you actually DO want as truly random of a value as possible. Primes (or more accurately, relative primes) only enter in to the equation when dealing with certain forms of asymmetric encryption. Asymmetric encryption is where one person has a public key to encrypt a message and then the recipient has a different private key ...

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