My understanding of hashing and encryption is rather limited. I certainly do not

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?

Explanation / Answer

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 Me 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 Gx 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 pN, 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).

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.