Why are primes important in cryptography?
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
Most basic and general explanation: cryptography is all about number theory, and all integer numbers (except 0 and 1) 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 those two 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.