Why are primes important in cryptography?

Question

One thing that always strikes me as a non-cryptographer: Why is it so important to use Prime numbers? What makes them so special in cryptography?

Does anyone have a simple short explanation? (I am aware that there are many primers and that Applied Cryptography is the Bible, but as said: I am not looking to implement my own cryptographic algorithm, and the stuff that I found just made my brain explode - no 10 pages of math formulas please :))

Thanks for all the answers. I've accepted the one that made the actual concept most clear to me.

Answer 1

Here is a very simple and common example.

The RSA encryption algorithm which is commonly used in secure commerce web sites, is based on the fact that it is easy to take two (very large) prime numbers and multiply them, while it is extremely hard to do the opposite - meaning: take a very large number, given which it has only two prime factors, and find them.

Answer 2

Simple? Yup.

If you multiply two large prime numbers, you get a huge non-prime number with only two (large) prime factors.

Factoring that number is a non-trivial operation, and that fact is the source of a lot of Cryptographic algorithms. See one-way functions for more information.

Addendum: Just a bit more explanation. The product of the two prime numbers can be used as a public key, while the primes themselves as a private key. Any operation done to data that can only be undone by knowing one of the two factors will be non-trivial to unencrypt.

Answer 3

This is a good article explaining the concept.

Answer 4

There are some good resources for ramping up on crypto. Here's one:

• http://research.microsoft.com/en-us/groups/crypto/firstcrypto.aspx

From that page:

In the most commonly used public-key cryptography system, invented by Ron Rivest, Adi Shamir, and Len Adleman in 1977, both the public and the private keys are derived from a pair of large prime numbers according to a relatively simple mathematical formula. In theory, it might be possible to derive the private key from the public key by working the formula backwards. But only the product of the large prime numbers is public, and factoring numbers of that size into primes is so hard that even the most powerful supercomputers in the world cant break an ordinary public key.

Bruce Schneier's book Applied Cryptography is another. I highly recommend that book; it's fun reading.

Answer 5

Cryptographic algorithms generally rely for their security on having a "difficult problem". Most modern algorithms seem to use the factoring of very large numbers as their difficult problem - if you multiply two large numbers together, computing their factors is "difficult" (i.e. time-consuming). If those two numbers are prime numbers, then there is only one answer, which makes it even more difficult, and also guarantees that when you find the answer, it's the right one, not some other answer that just happens to give the same result.

Answer 6

Most basic and general explanation: cryptography is all about number theory, and all integer numbers are made up of primes, so you deal with primes a lot in number theory.

More specifically, some important cryptographic algorithms such as RSA critically depend on the fact that prime factorization of large numbers takes a long time. Basically you have a "public key" consisting of a product of two large primes used to encrypt a message, and a "secret key" consisting of the primes used to decrypt the message. You can make the public key public, and everyone can use it to encrypt messages to you, but only you know the prime factors and can decrypt the messages. Everyone else would have to factor the number, which takes too long to be practical, given the current state of the art of number theory.

Answer 7

Because nobody knows a fast algorithm to factorize an integer into its prime factors. Yet, it is very easy to check if a set of prime factors multiply to a certain integer.

Answer 8

I think what are important in cryptography are not primes itself, but it is the difficulty of prime factorization problem

Suppose you have very very large integer which is known to be product of two primes m and n, it is not easy to find what are m and n. Algorithm such as RSA depends on this fact.

By the way, there is a published paper on algorithm which can "solve" this prime factorization problem in acceptable time using quantum computer. So newer algorithms in cryptography may not rely on this "difficulty" of prime factorization anymore when quantum computer comes to town :)

Answer 9

It's not so much the prime numbers themselves that are important, but the algorithms that work with primes. In particular, finding the factors of a number (any number).

As you know, any number has at least two factors. Prime numbers have the unique property in that they have exactly two factors: 1 and themselves.

The reason factoring is so important is mathematicians and computer scientists don't know how to factor a number without simply trying every possible combination. That is, first try dividing by 2, then by 3, then by 4, and so forth. If you try to factor a prime number--especially a very large one--you'll have to try (essentially) every possible number between 2 and that large prime number. Even on the fastest computers, it will take years (even centuries) to factor the kinds of prime numbers used in cryptography.

It is the fact that we don't know how to efficiently factor a large number that gives cryptographic algorithms their strength. If, one day, someone figures out how to do it, all the cryptographic algorithms we currently use will become obsolete. This remains an open area of research.

Answer 10

One more resource for you. Security Now! episode 30(~30 minute podcast, link is to the transcript) talks about cryptography issues, and explains why primes are important.

Answer 11

To be a little more concrete about how RSA uses properties of prime numbers, the RSA algorithm depends critically upon Euler's Theorem, which states that for relatively prime numbers "a" and "N", a^e is congruent to 1 modulo N, where e is the Euler's totient function of N.

Where do primes come into that? To compute the Euler's totient function of N efficiently requires knowing the prime factorization of N. In the case of the RSA algorithm, where N = pq for some primes "p" and "q", then e = (p - 1)(q - 1) = N - p - q + 1. But without knowing p and q, computation of e is very difficult.

More abstractly, many crypotgraphic protocols use various trapdoor functions, functions which are easy to compute but difficult to invert. Number theory is a rich source of such trapdoor functions (such as multiplication of large prime numbers), and prime numbers are absolutely central to number theory.

Answer 12

I would suggest the book A Mathematical Journey In Code. The book has a nice down to earth feel, which is surprising, since it is about cryptography. The book summarizes Sarah Flannery’s journey from learning puzzles as a child to creating the Cayley-Purser (CP) algorithm at the age of 16. It gives an amazingly detailed explanation of one way functions, number theory, and prime numbers and how they relate to cryptography.

What makes this book even more specific to your question is Sarah tried to implement a new public key algorithm using matrix's. It was much faster then using prime numbers but a loop hole was found that could exploit it. It turns out her algorithm was better used as a private encryption mechanism. The book is a great testament to using prime numbers for encryption as it has stood the test of time and the challenges of very smart individuals.