Public Key Cryptography
based on Chapter 4 of
9 Algorithms that Changed the Future
The Ingenious Ideas that drive today's Computers
John MacCormick, 2012
To share a secret by mail you can use a sealed envelope
But when you are using the internet you are using something akin to a postcard that many others on the way from sender to receiver can read.
Similarly, sharing a secret on the internet is like trying to share a secret by speaking out loud in a classroom where everyone can hear you
How can I securily share my credit card number by saying it out loud?
"My credit card number is 7531"
I can say an encrypted number.
Only someone that has a shared secret with me is able to decrypt 7531 and get my "real" credit card number
add 1234 7531 + 1234 = 8765
reverse digits 8765 -> 5678
shared secret used here . . .
On the internet if we want to disguise our messages, we need to encrypt them using a shared secret.
For example, using Caesar cipher with a specific shift count.
The easy part is encrypting & decryptig a message using a shared secret.
The hard part is establishing a shared secret between sender and receiver in the first place.
Somehow we must be able to establish a shared secret over the internet.
How do you establish a shared secret with someone (like an online merchant) ....
when everything you communicate could potentially be seen by someone . . .
To establish a shared secret between computers over the Internet we use very large prime numbers and "mix" them by using math.
Once you have a "mixed" number it is pretty much impossible (even for very fast computers) to determine what the original numbers might have been.
Here, rather than mathematically "mixing" prime numbers as our shared secret, assume our shared secret is a
mixed color
Once mixed together it is impossible to unmix - i.e. impossible to tell if a mixed color used
333 drops of blue 287 red 886 green
or
332 drops of blue 288 red 887 green
If we knew only how to multiply but did NOT know how to divide you could think of
a color = prime number
mixed color = product of prime numbers
Since we don't know how to divide we can't get back the original prime numbers.
The REAL math used ...
Objective
Produce a mixed color that only you & the person you want to communicate with can use as a shared secret ...
without anyone else who may be "listening" knowing that color
Need 3 Volunteers
Step 1
The two parties communicating each choose a PRIVATE color.
1
1
With billions of colors to choose from, it is almost a certainty that both will choose different colors
Step 2
The sender chooses and publicly shares a
PUBLIC color
The two communicating each now know their PRIVATE and PUBLIC colors
thief has
2
2
2
2
1
2
1
2
Step 3 the two communicating each mix their PRIVATE
& the PUBLIC color
and publicly share their mix
thief now has
1
2
1
2
2
1
2
1
2
1
2
1
2
1
2
1
2
Step 4
Take the mix you received and mix it with your PRIVATE color.
1
1
2
1
1
2
thief now has
1
2
1
2
2
thief cannot
get this mix
and thus have established
ends up with a mix of
1
1
2
ends up with a mix of
1
1
2
thief now has
1
2
1
2
2
thief cannot
get this mix
DONE
You and the person you want o communicate with have created a color only the two of you know.
You have established a
shared secret
Private
Private
Public
Public
Public
Private
Public
Private
Public
Private
Public
Private
Public
Private
Public
Private
Public
Private
Public
Private
Private
Public
Private
sender receiver
Public
Private
Public
Private
Public
hacker
Details on the math involved in public key cryptography