Cryptographers-U-Like
 |
| |
 |
| |
 |
| |
 |
| |
 |
| |
 |
| |
 |
| |
 |
| |
 |
| |
 |
| |
 |
| |
 |
| |
 |
| |
 |
| |
 |
| |
 |
| |
 |
Features:
- Large Prime Numbers
- Fermat's Little Theorem
- Not a Lot About Monkeys
- $1million Prize
| Cryptography for the New Millennium |
Introduction
Pretty much all cryptographic security for financial transactions these days is provided by
some version of the factoring problem. That is to say, it is 'easy' to multiply two large
Prime Numbers together, but 'hard' to factorise the resulting number. A technique to
quickly factor such numbers would have huge ramifications, possibly for the solution of
the P=NP problem, maybe the class of NP-complete problems as a whole, certainly the
collapse of secure internet transactions as we know them. If all of this is as
comprehensible as Swahili* to you, you may be on the wrong page; go back to a bit about
monkeys (we did say some users may experience disappointment).
some version of the factoring problem. That is to say, it is 'easy' to multiply two large
Prime Numbers together, but 'hard' to factorise the resulting number. A technique to
quickly factor such numbers would have huge ramifications, possibly for the solution of
the P=NP problem, maybe the class of NP-complete problems as a whole, certainly the
collapse of secure internet transactions as we know them. If all of this is as
comprehensible as Swahili* to you, you may be on the wrong page; go back to a bit about
monkeys (we did say some users may experience disappointment).
*isipokuwa wewesema Kiswahili, katika yapi bueta ukaimu "Kiswidi".
How It Works
| A Simple Example of a Grid |
|
In order to figure out how to decrypt things,
we must first learn how they are encrypted.
In general, any data you may want to
encrypt must first be turned into a numeric
value. There are all sorts of ways of doing
this, and the exact details are generally
unimportant. One method is to use a grid
like the one here
----------------------------------->
we must first learn how they are encrypted.
In general, any data you may want to
encrypt must first be turned into a numeric
value. There are all sorts of ways of doing
this, and the exact details are generally
unimportant. One method is to use a grid
like the one here
----------------------------------->
Hence, 'A' would become 72, '$' would be coded
as 46, and 'Monkey' would become
935141115052.
as 46, and 'Monkey' would become
935141115052.
Now all we need to do is find a way of disguising this number, so that others
cannot read it. However, this is not as easy as it may first appear - we want
it to be easy for people to disguise messages they want to send to us, but
difficult for anyone else to de-code them. For this, we need what is
sometimes referred to as a 'scrambled-egg' function; a function that is
easy to do (scrambling the eggs) but difficult to undo (unscrambling them).
In fact, it is not even quite that simple, as we still want to be able to decode
the messages people send us easily. Fortunately, the Factorisation
Problem provides a method.
This method relies on the fact that multiplying together 2 large prime
numbers is 'easy', whilst factorising the resulting product is 'hard'. I might
get round to discussing the P=NP issue, NP-completeness etc. etc. soon,
but you don't really need that information to understand what follows.
First we need a couple of large prime numbers, which we can call 'monkey'
and 'nuts'. How large is 'large' I hear you cry? The bigger the better, but
about 90 digits is probably sufficient for now.
We need the number 'monkeynuts', which is just monkey, multiplied by nuts.
This will be quite big, and has only two factors, monkey and nuts (this
seems intuitive, but intuition is often wrong. This fact is proven as a
consequence of the Fundamental Theorem of Arithmetic).
We must then find a positive integer 'apple', so that apple has no factor in
common with (monkey-1)(nuts-1). This is often easier than it sounds.
Next we need to find a positive integer 'banana', so that applebanana - 1 is
divisible by
(monkey-1)(nuts-1) with an integer answer. Again, not too tricky.
Now for the technical bit.
To encrypt a number, we raise the number to the power of apple, divide the
result by monkeynuts, and take the remainder.
Symbolically:
f(x) = x^apple mod monkeynuts (equation 1)
To decrypt, we take our encrypted number, raise it to the power of banana,
divide the result by monkeynuts, and take the remainder.
Symbolically:
g(x) = x^banana mod monkeynuts (equation 2)
Use f(x) for encryption, g(x) for decryption*.
cannot read it. However, this is not as easy as it may first appear - we want
it to be easy for people to disguise messages they want to send to us, but
difficult for anyone else to de-code them. For this, we need what is
sometimes referred to as a 'scrambled-egg' function; a function that is
easy to do (scrambling the eggs) but difficult to undo (unscrambling them).
In fact, it is not even quite that simple, as we still want to be able to decode
the messages people send us easily. Fortunately, the Factorisation
Problem provides a method.
This method relies on the fact that multiplying together 2 large prime
numbers is 'easy', whilst factorising the resulting product is 'hard'. I might
get round to discussing the P=NP issue, NP-completeness etc. etc. soon,
but you don't really need that information to understand what follows.
First we need a couple of large prime numbers, which we can call 'monkey'
and 'nuts'. How large is 'large' I hear you cry? The bigger the better, but
about 90 digits is probably sufficient for now.
We need the number 'monkeynuts', which is just monkey, multiplied by nuts.
This will be quite big, and has only two factors, monkey and nuts (this
seems intuitive, but intuition is often wrong. This fact is proven as a
consequence of the Fundamental Theorem of Arithmetic).
We must then find a positive integer 'apple', so that apple has no factor in
common with (monkey-1)(nuts-1). This is often easier than it sounds.
Next we need to find a positive integer 'banana', so that applebanana - 1 is
divisible by
(monkey-1)(nuts-1) with an integer answer. Again, not too tricky.
Now for the technical bit.
To encrypt a number, we raise the number to the power of apple, divide the
result by monkeynuts, and take the remainder.
Symbolically:
f(x) = x^apple mod monkeynuts (equation 1)
To decrypt, we take our encrypted number, raise it to the power of banana,
divide the result by monkeynuts, and take the remainder.
Symbolically:
g(x) = x^banana mod monkeynuts (equation 2)
Use f(x) for encryption, g(x) for decryption*.
*The fact that g(x) undoes what f(x) does is a
consequence of Fermat's Little Theorem,
which states that if a is not divisible by p,
where p is prime, then a^(p-1) - 1 is divisible
by p (where a and the answer to the division
are all positive integers. p, of course, must
be an integer).
consequence of Fermat's Little Theorem,
which states that if a is not divisible by p,
where p is prime, then a^(p-1) - 1 is divisible
by p (where a and the answer to the division
are all positive integers. p, of course, must
be an integer).
Why Does it Work?
What makes this method so hard to break?
To set up the code, you generate the large primes monkey and nuts,
then choose apple. Then you find a value that works for banana, where all the values are
integers.
You let the whole world know what apple and monkeynuts are, because this is all they
need to send you messages. This is all the info they need to do equation (1).
If you want to decrypt a message though, you need to find banana, and the only way of
doing this is to solve an equation involving the separate terms monkey and nuts. If you
recall, these were 2 large primes, so in order to find banana the would be eavesdropper
must factorise monkeynuts. Which is really, really hard. In fact, the well known
cryptography company RSA regularly issues challenges for people to try and factorise
these sorts of numbers - a 155 digit monkeynut number took 35.7 years' of computer time
to factorise; a 200 digit monkeynut took over half a century of run time to crack.
We, of course, already know what banana is, so we can decrypt our messages easily
using equation (2) in about 2 minutes.
To set up the code, you generate the large primes monkey and nuts,
then choose apple. Then you find a value that works for banana, where all the values are
integers.
You let the whole world know what apple and monkeynuts are, because this is all they
need to send you messages. This is all the info they need to do equation (1).
If you want to decrypt a message though, you need to find banana, and the only way of
doing this is to solve an equation involving the separate terms monkey and nuts. If you
recall, these were 2 large primes, so in order to find banana the would be eavesdropper
must factorise monkeynuts. Which is really, really hard. In fact, the well known
cryptography company RSA regularly issues challenges for people to try and factorise
these sorts of numbers - a 155 digit monkeynut number took 35.7 years' of computer time
to factorise; a 200 digit monkeynut took over half a century of run time to crack.
We, of course, already know what banana is, so we can decrypt our messages easily
using equation (2) in about 2 minutes.
Didn't You Say Something About a $1 Million Prize?
It is not currently know which complexity class the problem of factorising large monkeynut
numbers belongs to (specifically, whether it is NP-complete or not; it probably isn't, in this
Small Monkey's humble opinion). However, a general Polynomial Time Solution to the
monkeynut problem, or even a proof that such a solution exists, might have important
implications for the related problem of whether P=NP or not (ie whether 'hard' problems
are intrinsically 'hard', or we're just not being clever enough yet). You would also have
undermined every secure transaction that takes place on the internet instantly, which is a
pretty cool thing to be able to say you did.
If you can solve the P=NP problem (is there a procedure that can solve a
Non-deterministic Polynomial Time Problem in Polynomial time? Or can you show that no
such procedure can exist?), the Clay Institute has a $1million prize waiting for you. This is
pretty small change though, because if you can just solve the specific case of the
monkeynut problem with a Polynomial Time Procedure, RSA will probably offer you all the
cash in the world to keep it quiet.
numbers belongs to (specifically, whether it is NP-complete or not; it probably isn't, in this
Small Monkey's humble opinion). However, a general Polynomial Time Solution to the
monkeynut problem, or even a proof that such a solution exists, might have important
implications for the related problem of whether P=NP or not (ie whether 'hard' problems
are intrinsically 'hard', or we're just not being clever enough yet). You would also have
undermined every secure transaction that takes place on the internet instantly, which is a
pretty cool thing to be able to say you did.
If you can solve the P=NP problem (is there a procedure that can solve a
Non-deterministic Polynomial Time Problem in Polynomial time? Or can you show that no
such procedure can exist?), the Clay Institute has a $1million prize waiting for you. This is
pretty small change though, because if you can just solve the specific case of the
monkeynut problem with a Polynomial Time Procedure, RSA will probably offer you all the
cash in the world to keep it quiet.
** In 1994 Peter Shor discovered an algorithm for factorising large numbers in
Polynomial time, provided you could run it on a Quantum Computer. Now all
you have to do is build a large quantum computer, but that achievement will
also make you a bit more than $1million. If you have been in some way
inspired by this site, and go on to claim one of these prizes, do let us know. If
only so we can guilt you into a donation. We might know someone on the
Fields Medal Committee; if you're over 40 you're on your own though.
Polynomial time, provided you could run it on a Quantum Computer. Now all
you have to do is build a large quantum computer, but that achievement will
also make you a bit more than $1million. If you have been in some way
inspired by this site, and go on to claim one of these prizes, do let us know. If
only so we can guilt you into a donation. We might know someone on the
Fields Medal Committee; if you're over 40 you're on your own though.
| Monkey Wisdom Corner Our brain hurts now, we're going to the pub. |