Mary Queen of Scot's Guide to Asymmetric Ciphers

Before proceeding, you may want to read the backgrounder.

Before asymmetric ciphers, the sender of a message that was secured with a symmetric cipher would need to communicate the key value used to encrypt the message to the receiver via a separate secure communications channel. They are referred to as symmetric because both the sender and the receiver must share the same key to encrypt and then decrypt the data. The encoding cipher used by Mary Queen of Scots in the Babington Plot is an example of a symmetric cipher.

Like symmetric ciphers, asymmetric ciphers also provide encryption and decryption; however, the key value used in encryption is different than the key value used in decryption. At a vastly simplified level, the encryption functions used with asymmetric ciphers are examples of forward-only functions, where the inputs of the function cannot be deduced by knowing the output. Consider the function x + y = z. If we know that x = 4 and z = 2, then we can deduce that y was 2 (4 + 2 = 6). This is an example of a symmetric cipher... x is our private key and z if our enciphered output. If we know the key and the output, then we can calculate the contents of the message (y). Now imagine that the numbers of x + y = z function are times: 4 PM + y = 6 PM. Naively we can say y must equal 2 hours. However, it could just as easily equal 26 hours to get the same result. Or 50 hours. And so on. There are an infinite number of possible values for y. We can no longer deduce the value of y with forward only function the way we can with a two way function, such as a symmetric cipher.

An asymmetric cipher can be thought of like this one way function. It doesn't matter how many people know the key to your scheme, they won't be able to deduce the plaintext of the message without some other piece of information... and you keep this piece of information (your private key) secret from everyone.

Now Mary Queen of Scots could never possess the computing machines that we do, but they really were one great mathematician away from having something like our Public Key Infrastructure (PKI) and Digital Signatures. What would Mary and Babington's communications have looked like if they had?

Step 1. Exchanging Keys - Babington and Mary need to exchange public keys. The royal eavesdroppers could not change the integrity of these keys and still allow the parties to communicate. Effectively, they are free to exchange keys. Of course, the Spy Master keeps them both.

Step 2. Writing to Babington - Mary writes the message "Please tell me more about your plan".

Step 3. Encrypting the Message - She then encrypts it using a two-way, symmetric algorithm with the key "tennetsale". The result is "eirogneyfmyjdyeeork".

Step 4. Encrypting the Key - Now Mary needs to communicate the key and the message to Babington. To do this she encrypts the key "tennetsale" using Babington's public key and a one-way function, the result is "$&#*$&@%!@". This takes a very long time because asymmetric functions are so much slower than the alternative. Luckily, she didn't have to encrypt her entire message this way, only the key to the simpler encrypted message. She also counts the characters in her original message as a form of rudimentary checksum, and adds the encrypted result to the key.

Step 5. Encrypting the Signature - Mary now signs the entire message by encrypting her name using her private key, which results in "&*@#".

Step 6. Sending the Message - Mary's agents would take the encrypted message and key and store it in the hollow stopper of a beer barrel. The brewer would then deliver the barrels to Babington's agents.

Step 7. Intercepting the Message - Elizabeth's Royal Spy Master would intercept the barrels and make a copy of the message and key, passing the original back on to the brewer. However, no amount of effort would allow him to decrypt the original key of "tennetsale". It is not possible to deduce the plaintext of the message from knowing Mary's public key, Babington's public key, and the encrypted text. He can, however, prove that it was indeed Mary who sent the message because the signature line of "&*@#" can be decrypted in "Mary" using Mary's public key.

Step 8 - Verifying the Signature - Babington receives the message "eirogneyfmyjdyeeork", the key "$&#*$&@%!@", and the signature "&*@#". The first thing he does is use Mary's public key to decrypt her signature line from "&*@#" to "Mary", thus proving that the message really does come from her.

Step 9 - Decrypting the Key - Using his own private key, Babington now decrypts "$&#*$&@%!@" into "tennetsale". After great effort, he now has the encryption key that the Spy Master was unable to obtain. He also notes that there should be 35 characters in the message, information which Mary included with the key phrase.

Step 10 - Decrypting the Message - Babington now uses the key "tennetsale" to decrypt the message, receiving the text "Please tell me more about your plan". Since the message contains exactly 35 characters he can be reasonably sure that it was not altered in transit.

All four relevant facets of security were maintained throughout. Confidentiality was ensured by the Spy Master's inability to decrypt anything more but the conspirator's signature lines. Integrity was ensured by the basic checksum of 35 characters in the message. Authentication was proven by Mary's signature line, which when decrypted with her public key proved it was produced with her private key. And Non-repudiation was presumably ensured by Babington’s response.

Viola, history is irrevocably changed forever. Without being able to stop the plot, the Queen is dethroned and Mary replaces her. More importantly, no royal is ever executed for a crime, the population continues to believe royals are only accountable to God, and we're all probably serfs. Enjoy your farming.