[Courses] [security] Crypto Scientists Crack Prime Problem

[Raven Alder]

Heya. all --

	Sorry for the unintentional but long hiatus.  My job ate me.  So
I quit it, and became a consultant.  Heh.  I should be around more now.

	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.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 (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 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 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.

	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.

	Comments and discussion welcome -- please let me know if this
made any sense or not.  I thought y'all would appreciate some insight
into crypto news.

Cheers,
Raven   

"Do you know where the RSA t-shirt is?"
"No." 
"Well, I need the algorithm, so I'm doing laundry."
  -- me and RavenBlack