Private key Cryptography is explored from the Caesar Cipher to the one-time pad. We introduce encryption, decryption, ciphers, cryptanalysis and what it means to design a strong cipher. Finally perfect secrecy is explained with the invention of the one-time pad.
Transcript
Transcript generated by YouTube auto-captions. May contain errors.
[Music] now we can return to our story Alice and Bob have split and must communicate from a distance in order to arrange their next steps however Eve is able to intercept their letters so they need to disguise their meaning the following analogy is helpful first Alice locks her message in a box with a lock that only her and Bob have the combination to this is known as encryption then she sends the box to Bob knowing that it is safe since nobody else knows the combination when Bob receives the box he unlocks it and reads the message this is known as decryption cryptography begins when we perform encryption and decryption with virtual locks instead of physical ones these are known as ciphers this first well-known Cipher a substitution Cipher was used by Julius Caesar around 58 BC it's now referred to as the Caesar Cipher during the war Caesar shifted each letter in his military commands in order to make them appear meaningless should the enemy intercept it imagine Alice and Bob decided in advance to communicate using the Caesar Cipher with a shift of three first Alice writes her message in plain English then she applies a shift of three to each letter so a becomes D B becomes e c becomes F and so on this unreadable or or encrypted message is then sent to Bob openly then Bob simply subtracts the shift of three from each letter in order to read the original message incredibly this basic Cipher was used by military leaders for hundreds of years after Caesar I and one but I haven't conquered over man's Spirit which is inin however a lock is only as strong as its weakest point a lock breaker may look for mechanical flaws or failing that extract information in order to narrow down the correct combination lock breaking and codebreaking are very similar the true weakness of the Caesar Cipher was published 800 Years Later by an Arab mathematician named Ali he broke Caesar Cipher by using a clue based on an important property of the language a message is written in if you scan text from any book and count the frequency of each letter you will find a fairly consistent pattern for example these are letter frequencies of English this can be thought of as the fingerprint of English we leave this fingerprint when we communicate without realizing it this clue is one of the most valuable tools for a codebreaker to break this Cipher they count up the frequencies of each letter in the encrypted text and check check how far the fingerprint has shifted if H is the most popular letter instead of e then the shift was likely three they reversed the shift in order to reveal the message this was a blow to the Caesar Cipher but it didn't stop people from developing stronger ciphers a strong Cipher is one which disguises a fingerprint this fingerprint is a result of unique letter frequencies within a language to make a lighter fingerprint is to flatten this distribution of letter frequencies by the mid 15th century we had Advanced polyalphabetic ciphers to accomplish this imagine Alice and Bob have shared a secret shift word first Alice converts the word into numbers according to the letter position in the alphabet next this sequence of numbers is repeated along the message finally each letter in the message is encrypted by shifting according to the number below it then the encrypted message is sent openly to Bob Bob decrypts the message by subtracting the shifts according to the secret word he also has a copy of now imagine a code breaker Eve she intercepts a series of messages and calculates the letter frequencies she will find a flatter distribution a lighter fingerprint H how could she break this remember code Breakers look for an information link the same as finding a partial fingerprint anytime there is a differential and letter frequency es a leak of information occurs this difference is caused by any repetition in the encrypted message in this case this Cipher suffers from the repetition of the shift word to break the encryption Eve would first need to determine the length of the shift word used not the word itself when she checks the frequency distribution of every fifth letter the fingerprint will reveal itself the problem now is to break five Caesar ciphers in a repeating sequence individually this is a trivial task as we have seen before so for over 400 years the problem remained how could Alice design a cipher that hides her fingerprint thus stopping the wak of information the answer is randomness think of this Alice rolls a 26- sighted dice to generate a list of random shifts and shares this with Bob instead of a shift word now to encrypt her message Alice uses this list of random shifts instead it is important that this list of shifts be as long as the message as to avoid any repetition then she sends it to Bob who decrypts the message by using the same list of random numbers she had given him now Eve will have a problem because the resulting encrypted message will have two powerful properties one the shifts never fall into a repetitive pattern and two the encrypted message will have a uniform frequency distribution because there is no frequency differential and therefore no leak it is now impossible for Eve to break the encryption this is the strongest possible method of encryption and it emerged towards the end of the 19th century it is now known as the onetime pad to understand the true power of this method consider the following experiment to visualize the strength of the onetime pad we must understand the explosion of possibilities for example the Caesar Cipher shifted every letter by the same amount which was some number between 1 and 26 if Alice this was to encrypt her name it would result in one of 26 possible encryptions a small number of possibilities now compare this to the onetime pad where each letter would be shifted by a different number between 1 and 26 the number of possible encryptions is 26 multiplied by itself 5 times almost million this could be hard to visualize so imagine she wrote her name on on a single page and on top of it stacked every possible encryption how high would it be with almost 12 million felet sequences this stack of paper would be enormous over 1 km High when Alice encrypts her name using the One Time Pad it is the same as picking one of these Pages at Rand pH this is perfect secrecy in action