Bruce Willis is an FBI agent trying to protect an autistic child whose mathematical abilities allow him to break the government's top secret codes.
Now, it is true that some of the most frequently used "unbreakable" codes today are based on number theory, and are only unbreakable due to our limited abilities at arithmetic (in particular, factoring) really large whole numbers. (See box below.) And, it is also true that some autistic people have been known to have exceptional interest in and ability with the arithmetic of whole numbers. However, I'm told that this movie takes these ideas a bit beyond believability. (I haven't seen it yet, but the idea that the government would TEST its new code by publishing it as a puzzle in a children's magazine does seem a bit ridiculous!)
Contributed by
Alex Kasman
Let's look at number theory and codes. The thing that makes this new breed of code, technically called public key encryption algorithms, different is that you can give everyone the information necessary to send you coded messages without giving them the information to read them. (Think about it. With an old fashioned code, if I told you enough about the code you would not only be able to send me messages but would also be able to read any messages other people send me.) This is important in internet applications, for instance, because a company like Amazon.com wants to have lots of people send them encrypted messages (with credit card info, for example) but do not want all of those people also to be able to read those messages! That's where the difficulty of factoring huge numbers into their prime factors comes into play! In the RSA algorithm anyone who knows some really large number (an integer with thousands of digits) can encrypt a message just by turning it into a number, raising it to a power, and finding the remainder when you divide by the large number. However, in order to decode the message one needs to know the prime factors of that number. If the number is large enough, it could take years, decades or centuries to find those prime factors. Here's how the RSA encryption algorithm works:
- If I want to
receive a coded message (whether I'm a person or a computer, it
doesn't matter), I pick three numbers. Two prime numbers p and
q and a third number r which has no factors in common with
(p-1)(q-1). So, for example, if I want to get a message
from you, I can pick p=11 and q=3. Then, I could pick r=3
because 3 and 20=(11-1)(3-1) have no common factors. In
reality, these numbers are much too small, but for this example
let's ignore that problem.
- Then I must also find the number d less than (p-1)(q-1)
with the property that the remainder when you divide rd by
(p-1)(q-1) is 1. In the example, d must be 7. Note
that 3 X 7=21 which leaves a remainder of 1 when divided by
20.
- Now comes the interesting part. I publicly announce to you and
everyone else both the product p X q and the number r.
However, I don't tell anyone what p or q or d are!
So, I would announce to you that the product of p and q
is 33 and that the value of r is 3.
- Now comes your part. You want to send me a message and encode
it using the knowledge of those two numbers. In fact, your message
has to be a number too. However, that's not too hard. Everything
in a computer is numbers in the end. However, as it has to be a
number less than p X q, we are sort of restricted here.
But, as a simple example,
let's suppose the message you want to send me is the number ``18''.
But first, you encode the
message by raising it to the power of r dividing by the product
p X q. In fact, the coded message is just the remainder in
that division! Even though you want to tell me
`18'', what you'll send me is the remainder when
you divide 183 by 33. That is, you'll send the message
24.
- Don't forget that anyone who was listening to our previous
conversation knows the two numbers I sent you, and they know the
number you sent me as the coded message. But, they cannot
decode it unless they know the numbers that I've kept secret! (The
factors of 33 and especially the number d...that's the secret,
right?)
- Now, to turn the encoded message back to its original form, I
need to raise the message you sent me to the power d and get the
remainder when that is divided by p X q. In the
example, this means I will compute 247 and divide it by
33...or rather just find the remainder. And, guess what, this
gives me back the message 18!
- Of course, there is something silly in the above example. The
math is all correct, whatever message you start with I will be able to
decode it back to your original just because of the way the number
theory works. However, if I tell everyone my number 33 then there
is no real secret what its factors are! 33=11 X 3 is the only
way to factor it! The thing is, when this gets used for real, the
numbers involved are super huge. They use numbers that are
thousands of digits long, and the fact is that at the moment we have
no way to factor those numbers in a short time. In twenty to one
hundred years someone could factor it and break the code...but by then
the information in the message will probably be obsolete.
|
|