Prerequisite: algebra
The toughest of ciphers in Code Decipherment are not impregnable, because algorithms can be thought of as a function. No matter how complex the procedure, the systematic nature gives it away and like algebra, functions can be worked backwards.
Another problem is with key distribution. For the recipient to be able to decrypt a message, the recipient must have the key as well. This is particularly significant to digital communications where the key cannot simply be handed over in person (which defeats the purpose of digital communication!). To send the key digitally requires another key to secure the first key, and another for the second.. like an infinite Matryoshka doll. No way.
The thing to do then, is to 1) find an irreversible function and 2) find a way to decrypt a message without exchanging keys.
The breakthrough idea was formed separately first by James Ellis, Clifford Cocks, and Malcolm Williamson, then Whitfield Diffie, Martin Hellman, Ralph Merkle, Ronald Rivest, Adi Shamir, and Leonard Adleman. The concept can be described with the following analogy:
Alice is trying to send a message to Bob while Eve is eavesdropping.
Alice puts her message in a box.
Alice puts lock A on the box using key A, which she keeps secret.
Alice sends the box to Bob.
Eve cannot open the lock A on the box.
Bob puts another lock B on the box using another key B, which he keeps secret.
Bob sends the box back to Alice.
Eve cannot open lock A and B on the box.
Alice unlocks lock A using key A
Alice sends the box back to Bob.
Eve cannot open lock B on the box.
Bob unlocks lock B using key B.
Bob opens the box and reads Alice's message!
This solves the key distribution problem since no keys are exchanged, but it requires the function to be commutative as well as irreversible. So what kind of function fits the description?
The modular function~
There are two ways to understand it. One is to think of it as a clock. 12 (mod 7) = 5 would be 12 jumps around a 7 hour clock, landing at 5. Another way is to take 12 divided by 7, then state the remainder 5.
The following example applies modular functions not as an algorithm of the message itself, but as the algorithm to exchanging keys.. without exchanging keys:
Alice and Bob agree on a the function 3^x (mod 7) = y.
Eve overhears this function.
Alice chooses 6 as her key A, solves 3^(6) (mod 7) = 1, and reports the answer "1" to Bob.
Bob chooses 10 as his key B, solves 3^(10) (mod 7) = 4, and reports the answer "4" to Alice.
Eve overhears the exchange "1" and "4" but cannot reverse them with the function or do anything.
Alice solves B^A (mod 7), which (4)^(6) (mod 7) = 1.
Bob solves A^B (mod 7), which (1)^(10) (mod 7) = 1.
And so "1" is the agreed key for their message!
(I should have chosen better numbers where in reality the numbers are veeeeeeery large and do not coincide)
One may reverse the function through rigorous trial and error, but it is simply too exhausting when the key can reach astronomical lengths. The way to encrypt messages directly is as follows:
Alice choose two veeeeery laaaaarge prime numbers p and q, which she keeps secret.
Alice multiplies the two numbers to get N, and picks another number n. These two numbers she announces as a public key.
Bob wants to send Alice the letter "B", which he has to digitize first with ASCII binary digits or something.
Bob uses Alice's public keys to encrypt his letter "B" with the formula B^n (mod N) = C, solves for C, and sends it to Alice.
Eve overhears the message C but cannot do anything with it, not even with Alice's public keys since modular functions are not reversible.
Alice solves for a private decryption key d with the formula nd = 1 (mod (p-1)(q-1)) using Euclid's Algorithm (whatever that is).
Alice then deciphers Bob's message with the formula C^d (mod N) = B to get B.
It only gets crazier when you cross cryptography with physics. Just you wait. Be prepared to encounter some photons in a followup post..
No comments:
Post a Comment