Keys

• The simplest cipher consists merely of encrypting and decrypting algorithms. The problem is that it’s way too easy to break the cipher.
• So keys were developed, a secret string of characters that could be changed every so often. The encryption algorithm required a key. The decryption algorithm required the same key. The German Enigma Machine, for example, used a key — the settings of the machine — that changed daily. This meant that the Germans had to manually distribute codebooks to every Enigma user with the upcoming daily settings, a risky practice that turned out badly for the Germans when the Allies captured U-559.
• This gave rise to the key distribution problem: is there a way to use keys without having to manually distribute them?
• A simple, ingenious solution was set forth in 1976: use two keys mathematically related so that one key (the public key) is used for encryption and the second key (the private key) is used for decryption.

Problem: Key Distribution

Enigma, Example of the Problem

• Suppose the German naval command wanted to send an encrypted message to U-boat captains.  The plaintext message was handed to an Enigma Machine operator who typed the message one letter at a time. After each keystroke, a letter on the lampboard would light up and the operator’s helper would write down the encrypted letter. Once encrypted, the helper handed the ciphertext to a telegrapher, who transmitted the coded message by Morse Code over the radio. The process was reversed at the receiving end, with the ship’s Enigma Machine operator typing the ciphertext one letter at a time and his helper writing down the plaintext letters as they appeared on the lampboard. If the EM operator at naval command had typed a T displaying a G on the lampboard, the EM operator on the U-boat would have typed a G, making the T light up.

wikipedia.org/wiki/Enigma_machine

• The Allies were listening to the Enigma radio transmission and eventually figured out how the machines worked. The Germans didn’t care because the settings on the machines were changed daily, settings for the rotors, plugboard, and mirror.  A total of 10 quadrillion different combinations.
• But there was a major drawback to the system (beyond the flaws that enabled Enigma to be broken).  German naval command every so often had to distribute the upcoming daily settings for the Enigma to all the U-boats. How did they do this? 
• One way not to distribute the settings is by using the Enigma machine itself.  For if the Allies were to discover the settings for just one day, they would be able to decipher messages from then on.
• The Germans solved the problem by manually distributing codebooks with the daily settings for the upcoming month.

wikipedia.org/wiki/Enigma_machine

Solution: Public Key Encryption

• In 1976 Whitfield Diffie and Martin Hellman, and Ralph Merkle working independently, invented public key cryptography, solving the key distribution problem  According to the Britannica, this is “one of the most inspired insights in the history of cryptology.”  The idea was to use different keys, one for encrypting and the other for decrypting, rather than one shared key for both.  The system would have obviated the need for the German codebooks.
• In 1977 Ronald Rivest, Adi Shamir, and Leonard Adleman of MIT developed RSA encryption, the most widely used implementation of public key cryptography.
• Here’s how it works.
• I want to send you an encrypted message. So I first ask you for your public key.
• To make a new public key:
  • You randomly select two prime integers about 150 digits long. (An integer is prime if it’s divisible only by itself and 1, e.g. 5, 13, 61, 83, and 7243.)
  • You multiply the integers getting what’s called the Modulus.
  • From the Modulus you create two other large integers, the Public Key and the Private Key.
  • Your integers might look like this:
    • Modulus
      • 8718772945016244851104832429513579869316279158689503999264781659881219158909166877117053949457407391066577487761801867412583768369072749634408233752101936290999568562994573496059303059518939628461361070798293055768627021619060817240364157054647019857926156434955984598076613928963416081122155648430749
    • Public Key
      • 3618726460875190544565072902714240280840796093754927635349045273789587677829933311293616377463811672931582230890656193397692194016942435478986189146482814393724559416440113288228816438552212154071942284651182821935926189083301533876437371940108798770100807754430923432366190000205295753402422209434593
    • Private Key
      • 458833836068390807053787684334566618714167469655224783098974930175593040074508055741834161428190257956457974434708182596118639731272348297197287876561660408512700241034195965682532287538823224171645041027019795719839947880238118781003356269714867762797016952978734289454205891649762243682197116572617
• You send me the Modulus and the Public Key and keep the Private Key to yourself.

• To encrypt my message,  “ABORT THE MISSION,” I first convert the letters into a single number, using standard Ascii Codes (A=65, B=66, C=67, D=68, etc.)
  • Numeric Plaintext = ToCharacterCode[“ABORT THE MISSION”]
    • = 6566798284328472693277738383737978
• Then using a standard function in modular arithmetic, PowerMod, along with the Public Key and the Modulus you sent me, I encrypt the Numeric Plaintext.
  • Ciphertext = PowerMod[Numeric Plaintext, Public Key, Modulus]
    • 3784637852570272124308215659344935465013326902441845308514517788649942137876145048608044236534859236029460857371124361327094221107508710393354577893433527662738579028210156790976201499564335169403451804720026500350299067313617281396750130959908395031351131853084224629522613861738720376875535334197650
• I send you the ciphertext.
• You use Power Mod to decrypt the Ciphertext. Instead of the Public Key, however, you use your secret Private Key:
  • Numeric Plaintext = PowerMod[Ciphertext, Private Key, Modulus]
    • 6566798284328472693277738383737978
• Finally, you convert the Numeric Plaintext into English using Ascii codes:
  • ToCharacterCode[6566798284328472693277738383737978]
    • = “ABORT THE MISSION”

Notes

• Use larger modulus for example
• Show how to break PKE if you can factor the modulus
• Computationally Fast
  • plaintext + modulus + public key -> ciphertext
  • ciphertext + modulus + private key -> plaintext
• Computationally Infeasible
  • ciphertext + modulus + publice key -> plaintext
• Factoring products of 2 large primes
• wikipedia.org/wiki/RSA_(cryptosystem)
  • signing a message
• wikipedia.org/wiki/RSA_numbers