Cryptography: Crash Course Computer Science #33

Key Takeaways

hi i'm carrie anne and welcome to crash course computer science over the past two episodes we've talked a lot about computer security but the fact is there's no such thing as a perfectly 100 secure computer system there will always be bugs and security experts know that so system architects employ a strategy called defense in depth which uses many layers of varying security mechanisms to frustrate attackers it's a bit like how castles are designed first you've got to dodge the arches then cross the moat scale the walls avoid the hot oil get over the ramparts and defeat the guards before you get to the throne room but in this case we're talking about one of the most common forms of computer security cryptography [Music] the word cryptography comes from the roots crypto and griffy roughly translating to secret writing in order to make information secret you use a cipher an algorithm that converts plain text into ciphertext which is gibberish unless you have a key that lets you undo the cipher the process of making text secret is called encryption and the reverse process is called decryption ciphers have been used long before computers showed up julius caesar used what's now called a caesar cipher to encrypt private correspondence he would shift the letters in a message forward by three places so a became d and the word brutus became this to decipher the message recipients had to know both the algorithm and the number to shift by which acted as the key the caesar cipher is one example of a larger class of techniques called substitution ciphers these replace every letter in a message with something else according to a translation a big drawback of basic substitution ciphers is that letter frequencies are preserved for example e is the most common letter in english so if your cipher translates e to an x then x will show up the most frequently in the ciphertext a skilled cryptanalyst can work backwards from these kinds of statistics to figure out the message it was the breaking of a substitution cipher that led to the execution of mary queen of scots in 1587 for plotting to kill queen elizabeth another fundamental class of techniques are permutation ciphers let's look at a simple example called a commoner transposition cipher here we take a message and fill the letters into a grid in this case we've chosen five by five to encrypt our message we read out the characters in a different order let's say from the bottom left working upwards one column at a time the new letter ordering what's called a permutation is the encrypted message the ordering direction as well as the 5x5 grid size serves as the key like before if the cipher and key are known a recipient can reverse the process to reveal the original message by the 1900s cryptography was mechanized in the form of encryption machines the most famous was the german enigma used by the nazis to encrypt their wartime communications as we discussed back in episode 15 the enigma was a typewriter-like machine with a keyboard and lampboard both showing the full alphabet above that there was a series of configurable rotors that were the key to the enigma's encryption capability first let's look at just one rotor one side had electrical contacts for all 26 letters these connected to the other side of the rotor using cross-crossing wires that swapped one letter for another if h went in k might come out the other side if k went in f might come out and so on the letter swapping behavior should sound familiar it's a substitution cipher but the enigma was more sophisticated because it used three or more rotors in a row each feeding into the next rotors could also be rotated to one of 26 possible starting positions and they could be inserted in different orders providing a lot of different substitution mappings following the rotors was a special circuit called a reflector instead of passing the signal onto another rotor it connected every pin to another and sent the electrical signal back through the rotors finally there was a plug board at the front of the machine that allowed letters coming from the keyboard to be optionally swapped adding another level of complexity with our simplified circuit let's encrypt a letter on this example enigma configuration if we press the h key electricity flows through the plug board then the rotors hits the reflector comes back through the rotors and plug board and illuminates the letter l on the lamp board so h is encrypted to l know that the circuit can flow both ways so if we type the letter l h would light up in other words it's the same process for encrypting and decrypting you just have to make sure the sending and receiving machines have the same initial configuration if you look carefully at this circuit you'll notice it's impossible for a letter to be encrypted as itself which turned out to be a fatal cryptographic weakness finally to prevent the enigma from being a simple substitution cipher every single time a letter was entered the road is advanced by one spot sort of like an odometer in a car so if you entered the text aaa it might come out as bdk where the substitution mapping changed with every key press the enigma was a tough cookie to crack for sure but as we discussed in episode 15 alan turing and his colleagues at bletchley park were able to break enigma codes and largely automate the process but with the advent of computers cryptography moved from hardware into software one of the earliest software ciphers to become widespread was the data encryption standard developed by ibm and the nsa in 1977. des as it was known originally used binary keys that were 56 bits long which means that there are two to the 56 or about 72 quadrillion different keys back in 1977 that meant that nobody except perhaps the nsa had enough computing power to brute force all possible keys but by 1999 a quarter million dollar computer could try every possible des key in just two days rendering the cipher insecure so in 2001 the advanced encryption standard aes was finalized and published aes is designed to use much bigger keys 128 192 or 256 bits in size making brute force attacks much much harder for 128-bit key you'd need trillions of years to try every combination even if you used every single computer on the planet today so you'd better get started aes chops data up into 16 byte blocks and then applies a series of substitutions and permutations based on the key value plus some other operations to obscure the message and this process is repeated 10 or more times for each block you might be wondering why only 10 rounds or why only 128 bit keys and not 10 000 bit keys well it's a performance trade-off if it took hours to encrypt and send an email or minutes to connect to a secure website people wouldn't use it aes balances performance and security to provide practical cryptography today aes is used everywhere from encrypting files on iphones and transmitting data over wi-fi with wpa2 to accessing websites using https so far the cryptographic techniques we've discussed rely on keys that are known by both sender and recipient the sender encrypts a message using a key and the recipient decrypts it using the same key in the old days keys would be shared by voice or physically for example the germans distributed code books with daily settings for their enigma machines but this strategy could never work in the internet era imagine having to crack open a code book to connect to youtube what's needed is a way for a server to send a secret key over the public internet to a user wishing to connect securely it seems like that wouldn't be secure because if the key is sent in the open and intercepted by a hacker couldn't they use that to decrypt all communication between the two the solution is key exchange an algorithm that lets two computers agree on a key without ever sending one we can do this with one way functions mathematical operations that are very easy to do in one direction but hard to reverse to show you how one-way functions work let's use paint colors as an analogy it's easy to mix paint colors together but it's not so easy to figure out the constituent colors that we use to make a mixed paint color you'd have to test a lot of possibilities to figure it out in this metaphor our secret key is a unique shade of paint first there's a public paint color that everyone can see then john and i each pick a secret paint color to exchange keys i mix my secret paint color with the public paint color then i send that mix color to john by any means mail carrier pigeon whatever john does the same mixing his secret paint color with the public color then sending that to me when i receive john's color i simply add my private color to create a blend of all three paints john does the same with my mixed color and voila we both end up with the same paint color we can use this as a shared secret even though we never sent each other our individual secret colors a snooping outside observer with no partial information but they'd find it very difficult to figure out our shared secret color of course sending and mixing paint colors isn't going to work well for transmitting computer data but luckily mathematical one-way functions are perfect and this is what diffie-hellman key exchange uses in diffie-hellman the one-way function is modular exponentiation this means taking one number the base to the power of another number the exponent and taking the remainder when divided by a third number the modulus so for example if we wanted to calculate 3 to the fifth power modulo 31 we would calculate 3 to the fifth which is 243 and then take the remainder when divided by 31 which is 26. the hard part is figuring out the exponent given only the result in the base if i tell you i raised 3 to some secret number modulo 31 and got 7 as the remainder you'd have to test a lot of exponents to know which one i picked if we make these numbers big say hundreds of digits long then finding the secret exponent is nearly impossible now let's talk about how diffie-hellman uses modular exponentiation to calculate a shared key first there's a set of public values the base and the modulus that like our public paint color everyone gets to know even the bad guys to send a message to curly to john i would pick a secret exponent x then i'd calculate b to the power of x modulo m i send this big number over to john john does the same picking a secret exponent y and sending me b to the y modulo m to create a shared secret key i take what john sent me and take it to the power of x my secret exponent this is mathematically equivalent to b to the x y modulus m john does the same taking what i sent to him to the power of y and we both end up with the exact same number it's a secret shared key even though we never sent each other our secret number we can use this big number as a shared key for encrypted communication using something like aes for encryption diffie-hellman key exchange is one method for establishing a shared key these keys that can be used by both sender and receiver to encrypt and decrypt messages are called symmetric keys because the key is the same on both sides the caesar cipher enigma and aes are all symmetric encryption there's also asymmetric encryption where there are two different keys most often one that's public and another that's private so people can encrypt a message using a public key that only the recipient with their private key can decrypt in other words knowing the public key only lets you encrypt but not decrypt it's asymmetric so think about boxes with padlocks that you can open with a key to receive a secure message i can give a sender a box and a padlock they put their message in it and lock it shut now they can send that box back to me and only i can open it with my private key after locking the box neither the sender nor anyone else who finds the box can open it without brute force in the same way a digital public key can encrypt something that can only be decrypted with a private key the reverse is possible too encrypting something with a private key that can be decrypted with a public key this is used for signing where a server encrypts data using their private key anyone can decrypt it using the server's public key this acts like an unforgeable signature as only the owner using their private key can encrypt it it proves that you're getting data from the right server or person and not an imposter the most popular asymmetric encryption technique used today is rsa named after its inventors rivest shamir and adelman so now you know all the key parts of modern cryptography symmetric encryption key exchange and public key cryptography when you connect to a secure website like your bank that little padlock icon means that your computer has used public key cryptography to verify the server key exchange to establish a secret temporary key and symmetric encryption to protect all the back and forth communication from prying eyes whether you're buying something online sending emails to bffs or just browsing cat videos cryptography keeps all that safe private and secure thanks cryptography crash course computer science is produced in association with pbs digital studios at their channel you can check out our playlist of shows like eon's physics girl and it's okay to be smart this episode was filmed at the chad and stacy emma got studio in indianapolis and it was made with the help of all these nice people and our wonderful graphics team thought cafe thanks for the random access memories i'll see you next time [Music] you