
Crypto Scientists Crack Prime Problem
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/21001104949170.html
If 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 = N
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
Looks 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.
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 one
could 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 (p1)(q1).
 What this boils down to is that E and N have to be relatively prime.
 They can't share any common components.
8 and 9 are relatively prime. When broken down as much as possible,
8 = 2 x 2 x 2
9 = 3 x 3
Nothing in common.
8 and 20 are not relatively prime.
8 = 2 x 2 x 2
20 = 2 x 2 x 5
They have 2 in common, so they're not relatively prime.
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 N
M = C to the D power mod N
So, 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 bruteforcing 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.
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/).
