Recently, a group of Indian scientists made news by announcing an algorithm that appears to be able to tell quickly whether a number is prime or not.
http://zdnet.com.com/2100-1104-949170.htmlIf you're mathematically minded, the actual downloadable primality.pdf is worth reading.
So what does this actually mean for cryptography? First, a little background.
Many of the popular common crypto algorithms work because of "something to do with prime numbers". Most security books are about that vague. So math research about primes could have interesting effects on our field. But is being able to determine whether a number is prime quickly going to be able to help or hinder us? Let's look at the RSA algorithm as an illustrative example. (It lost its patent a few years back, so it's okay to discuss now.)
When P and Q are large prime numbers:
P x Q = NLooks like Greek, doesn't it? Let's explain it. A lot of the math that goes into crypto is really nothing more complicated than multiplication and division.
E x D = 1 mod (P - 1)(Q - 1)
C = M to the E power mod N
M = C to the D power mod N
First of all, "mod" is short for modulus. A modulus is nothing more than the remainder that's left over after division. So:
Nine divided by four is two with a remainder of onecould also be expressed as
9 divided by four is two mod one.That's all. No magic.
Public key crypto algorithms such as RSA depend on there being two keys used to encrypt and decrypt a message. (Hence, the "generate a key pair" step you see when setting up many applications that use cryptography.) Every user has a complimentary set made up of a private key and a public key. Anything encrypted with the private key can be decrypted with the public key, and anything encrypted with the public key can be decrypted with the private key. Only you should have a copy of your private key, but anyone can have your public key because it's, well, public. If someone encrypts traffic with your public key, it doesn't matter to you because only you can decrypt it.
So, you're probably thinking, if I have a message to send to Jane, I want to encrypt it. I can't encrypt it with my public key, because she doesn't have my private key to decrypt it. So I'll encrypt it with my private key, and she can decrypt it with my public key. Right? Not quite, but this is a really common mistake. Sure, Jane can decrypt the message with your public key. But so can anyone else. What you need to do is encrypt the message with Jane's public key, so that only Jane's private key (which only Jane should have) can decrypt it.
So, the RSA algorithm says this:
- Take two large prime numbers.
- When multiplied together, they have a product N.
- Find two numbers E and D, such that:
- When E is multiplied by D, that should be equal to one mod (p-1)(q-1).
- What this boils down to is that E and N have to be relatively prime.
- They can't share any common components.
8 = 2 x 2 x 2Nothing in common.
9 = 3 x 3
8 and 20 are not relatively prime.
8 = 2 x 2 x 2They have 2 in common, so they're not relatively prime.
20 = 2 x 2 x 5
If E and D are chosen correctly, then let's make C the ciphertext and P the plaintext.
C = M to the E power mod NSo, something encrypted with N and E (the public key) can be solved for M -- decrypted into the plaintext. Something encrypted with N and D (the private key) can be solved for the ciphertext C. And since E and D fit together in a defined mathematical relationship as above, you cannot automatically deduce one from the other, but can encrypt and decrypt. The beauty of the modulus is that it's a one way operation. You know what the remainder is, but you'll have to try brute-forcing it to figure out whether it's C multiplied by one with a remainder of three, by two with a remainder of three... by forty thousand with a remainder of three... [grin] That takes a lot of time.
M = C to the D power mod N
If you want to see an example of this worked out with numbers, there's a clear one at http://math.kennesaw.edu/maa/talks/RSAEncryptionAlgorithm.htm
So, back to our original point. Being able to quickly determine whether a number is prime -- what effect does that have on all this? Well, one of the weakest points about RSA and other public key algorithms is that their large prime numbers are only probably prime. It's really hard to tell whether a number with eight zillion digits is actually prime or not -- you have to try dividing it by every prime number up to half of its value or so. That's very time consuming. Since those of us that use PGP, etc., don't want to wait too long for our keys to be generated, the RSA algorithm picks values for P and Q that are very likely to be prime, but that's not known for certain.
If those numbers aren't actually prime, then there may be different solutions for the equations other than the ones that are supposed to work. So, someone might be able to decrypt a message without having the matching key -- they'd just need a matching key, if there were more than one. (That's what could happen if P and Q aren't prime.) If the new algorithm can determine whether P and Q are really prime and they're not for a given key pair, that could lead to a weakness in RSA. But if that's the case, RSA and other algorithm authors could modify their software to use the new algorithm to ensure that P and Q really are prime, and that would defeat that sort of attack.
There's a lot of sound and fury at the moment about this article, and many people are freaking out about it, but I don't think it's anything to worry about. Mathematicians haven't fully satisfied themselves yet that it's a good tester for primes -- I don't think we'll be seeing exploit code in the near future.
Update
Jacinta wrote a paper discussing what prime numbers are, why they are so important, and how to generate them for use in RSA keys.
Copyright (c) 2002 by Raven Alder. This material may be distributed only subject to the terms and conditions set forth in the Open Publication License, v1.0 or later (the latest version is presently available at http://www.opencontent.org/openpub/).
