What place do prime numbers have in cryptography?

Question

My understanding of hashing and encryption is rather limited. I certainly do not understand the mathematical formulas at play in these algorithms. With that said, what part do prime numbers play in cryptography?

When I was in college, one of my professors told me that the fact that there is no formula to predict a prime number (other than just trying them) is what makes many encryption schemes (like PGP) so secure, since it's not possible to guess the number used for the public/private key in any reasonable amount of time. Is that correct?

Answer 1

No, the fact that there's no known practical formula that produces only prime numbers doesn't really come into play; if someone found one tomorrow, that wouldn't have any cryptographical implications.

You may want to go through the How does asymmetric encryption work? thread; the short answer is that for public key operations, the public and the private keys must be related, but not in an obvious way. What means that whatever scheme is used has some mathematical structure. Number theory is a place where we find 'related-but-not-in-an-obvious-way' mathematical structures, and primes are rather, err, primary in number theory.

Exactly how the primes are used depends on which asymmetric algorithm is used; in RSA, we exploit the fact that, given $M^e \mod N$ (and $e$ and $N$), there's no known way to recover $M$ without knowing the prime factors of $N$ (but with that information, it's easy). In DH/DSS, we exploit the fact that, given $G^x \mod p$ (and $G$ and $p$), there's no known way to recover $x$ (and we have $p$ be a prime because the problem with composite moduli becomes a lot easier if someone finds the factorization). In Elliptic Curve Cryptography, we exploit the difficulty of recovery $k$ given $kG$ (where $G$ is a known point); a prime is involved because Elliptic Curves are defined only a field, and the only finite fields (that is, fields with a bounded set of elements) have size $p^N$, for prime $p$ (and positive integer $N$).

Now, you occasionally see primes used in symmetric crypto; it's not nearly as common (and those primes aren't secret).

Answer 2

Prime numbers are so important because for every number $a$ there is exactly only one multiplicatively inverse number $a^{-1}$, so that $a·a^{-1} \mod N = 1$ only if $gcd(a, N) = 1$, i.e. if they are relatively prime.

If you take a prime number as the modulus, you have not to care about relative primeness anymore, any numbers between $0$ than $N$ are relatively prime to $N$.

Another reason is the Fermat's little theorem used in RSA.

Answer 3

Yes, that's correct.

Take a look at this question / answer: How does asymmetric encryption work? about the related math, in a simple way.

When you deal with large numbers, there is no easy way to find all the factors of such a number (if they are not mostly small factors).

And think the following: If you multiply one prime number by another one, you'll end up with a third number. Like $ab = c$. Now it is easy to come from $a$ and $b$ to $c$, but it is hard to come from $c$ to $a$ and $b$ (although there are exactly those two factors of $c$).

There are some factoring algorithms more efficient than simply trying all numbers, but still there is no algorithm sufficiently fast to factor sufficiently large (and still practically usable) composite numbers in our life-time. (On the other hand, there are efficient algorithms to show that a number is or is not a prime number, without finding any factors. This is actually used to generate a key.)

For RSA we use $a$ and $b$ (in fact, $\phi(c) = (a-1)(b-1) = c+1 - (a+b)$) to create the private key, while $c$ is part of the public key.