Cryptography: Crash Course Computer Science #33

Summary

CrashCourse Computer Science explores the inevitability of computer system vulnerabilities and the strategy of 'defence in depth'. It delves into the history of cryptography, from Caesar ciphers to the complex Enigma machine, and modern encryption standards like DES and AES. The video also explains key exchange mechanisms like Diffie-Hellman and asymmetric encryption with RSA, illustrating how these techniques secure our digital communications.

Takeaways

• 🔒 Cryptography is essential for computer security, providing a means to encrypt and decrypt data.
• 🏰 The concept of defense in depth is used in computer security to protect systems through multiple layers of security.
• 🔑 A cipher is an algorithm that converts plaintext into ciphertext, and a key is required to decrypt it.
• 📜 Historically, ciphers like the Caesar cipher have been used to encrypt messages by substituting letters.
• 🔍 Substitution ciphers have weaknesses, as they preserve letter frequencies, which can be exploited by cryptanalysts.
• 🗝️ Permutation ciphers, like the columnar transposition cipher, reorder letters in a grid to encrypt messages.
• 🇩🇪 The Enigma machine used substitution and permutation to encrypt messages during World War II.
• 💻 Modern cryptography has moved from hardware to software, with standards like DES and AES.
• 🔗 AES uses large keys and multiple rounds of substitution and permutation to secure data.
• 🔄 Key exchange algorithms like Diffie-Hellman allow secure communication over the internet without directly sharing keys.
• 🔑 Asymmetric encryption, such as RSA, uses a public key for encryption and a private key for decryption.

Q & A

What is the concept of 'defence in depth' in computer security?

Defence in depth is a strategy that employs multiple layers of varying security mechanisms to protect computer systems, making it difficult for attackers to compromise security.

What is the meaning of the word 'cryptography'?

Cryptography comes from the roots 'crypto' and 'graphy', roughly translating to 'secret writing'. It involves the use of ciphers to convert plaintext into ciphertext, which is unintelligible without the correct key for decryption.

How did Julius Caesar use cryptography?

Julius Caesar used a simple substitution cipher known as the Caesar cipher, where he shifted the letters in a message forward by three places to encrypt private correspondence.

What is a substitution cipher and what is its main drawback?

A substitution cipher is a method of encryption where each letter in the plaintext is replaced by another letter according to a fixed system. The main drawback is that it preserves letter frequencies, which can be exploited by cryptanalysts to break the cipher.

Can you explain how a columnar transposition cipher works?

A columnar transposition cipher involves writing a message into a grid and then reading the letters out in a different order, such as from the bottom left upwards, to encrypt the message. The order and grid size act as the key.

What was the German Enigma machine and how did it work?

The Enigma machine was an encryption device used by the Nazis during World War II. It used a series of rotors with cross-wired contacts to perform substitution ciphers, a reflector to send the signal back through the rotors, and a plugboard for additional letter swapping.

How did Alan Turing and his colleagues break the Enigma codes?

Alan Turing and his colleagues at Bletchley Park were able to break Enigma codes by developing techniques and machines that could automate the process of testing possible rotor settings and configurations.

What is the Data Encryption Standard (DES) and why was it eventually considered insecure?

DES was an early widespread software cipher developed by IBM and the NSA in 1977, using 56-bit keys. It was considered insecure by 1999 as computing power increased, allowing for the possibility of brute-forcing all possible keys within a short time.

What is the Advanced Encryption Standard (AES) and how does it improve upon DES?

AES is a symmetric encryption standard that uses much larger key sizes (128, 192, or 256 bits) to make brute force attacks impractical. It was developed as a replacement for DES to provide stronger security.

How does the Diffie-Hellman key exchange work?

The Diffie-Hellman key exchange allows two parties to establish a shared secret key over an insecure channel without ever transmitting the key itself. It uses one-way functions, such as modular exponentiation, to ensure that the key can be calculated independently by both parties.

What is asymmetric encryption and how does it differ from symmetric encryption?

Asymmetric encryption uses two different keys, a public key for encryption and a private key for decryption. This is different from symmetric encryption, where the same key is used for both encryption and decryption. Asymmetric encryption allows for secure communication without the need to share a secret key beforehand.

How does public key cryptography ensure secure communication on the internet?

Public key cryptography ensures secure communication by allowing servers to encrypt data with a public key that can only be decrypted with the corresponding private key. This ensures that only the intended recipient can access the encrypted information.

Outlines

00:00

🔐 Introduction to Cryptography

Carrie Anne introduces the topic of computer security and the concept of 'defence in depth', emphasizing that no system is 100% secure. She explains cryptography as a common form of computer security, which involves converting plain text into ciphertext using a cipher. The process of making text secret is called encryption, and the reverse is decryption. Historical examples of ciphers are given, such as the Caesar cipher used by Julius Caesar, which shifted letters by three places. The limitations of basic substitution ciphers, like preserving letter frequencies, are discussed, along with the columnar transposition cipher as an example of a permutation cipher. The script also touches on the mechanical encryption devices like the German Enigma machine used during World War II, explaining its rotors, reflector, and plugboard as part of the encryption process.

05:05

💻 Evolution of Cryptography

This section discusses the evolution of cryptography from mechanical devices to software algorithms. The Data Encryption Standard (DES) developed in 1977 is mentioned, which used 56-bit keys, but by 1999, it was considered insecure due to advancements in computing power. The Advanced Encryption Standard (AES) was introduced in 2001 to address these security concerns, using much larger keys (128, 192, or 256 bits) to make brute force attacks impractical. AES operates on 16-byte blocks of data, applying multiple rounds of substitutions and permutations based on the key. The script also explains the concept of key exchange, necessary for secure communication over the internet, using the analogy of mixing paint colors to demonstrate how two parties can agree on a secret key without directly sharing it. The Diffie-Hellman Key Exchange, which uses one-way functions like modular exponentiation, is introduced as a method for establishing a shared secret key.

10:06

🔑 Symmetric vs Asymmetric Encryption

The final paragraph distinguishes between symmetric and asymmetric encryption. Symmetric encryption uses the same key for both encryption and decryption, exemplified by the Caesar Cipher, Enigma, and AES. Asymmetric encryption, on the other hand, involves two different keys: a public key for encryption and a private key for decryption. The concept of digital signatures is also explained, where data encrypted with a private key can be decrypted with the corresponding public key, serving as a form of authentication. RSA is highlighted as a popular asymmetric encryption technique. The script concludes by emphasizing the importance of cryptography in securing online transactions, communications, and browsing activities, ensuring privacy and security.

Keywords

💡Cryptography

Cryptography is the practice and study of techniques for secure communication in the presence of third parties. It involves the use of codes and ciphers to protect information from unauthorized access. In the context of the video, cryptography is the central theme, with a focus on how it secures digital communication. The script discusses various historical and modern cryptographic techniques, such as the Caesar cipher and the Enigma machine, illustrating the evolution of cryptography over time.

💡Defence in depth

Defence in depth is a security strategy that employs multiple layers of defense mechanisms to protect systems. It is likened to the layers of security in a castle, such as walls, moats, and guards, each providing an additional barrier to entry. In the video, this concept is used to introduce the idea that no single security measure can be completely foolproof, hence the need for multiple layers of protection in computer security.

💡Cipher

A cipher is an algorithm or method for performing encryption or decryption. It is used to convert plaintext into ciphertext, making the message unreadable without the key. The script explains that Julius Caesar used a simple cipher by shifting letters to encrypt his messages, which is an early example of substitution ciphers.

💡Encryption

Encryption is the process of encoding information in such a way that only authorized parties can access it. It is a fundamental concept in cryptography and is used to protect data from unauthorized access. The video describes encryption as the act of making text secret using a cipher, which is crucial for secure communication.

💡Decryption

Decryption is the reverse process of encryption, where ciphertext is converted back into plaintext using a key. It is essential for making encrypted information readable again. The video mentions decryption in the context of how recipients can reverse the encryption process to read the original message.

💡Substitution cipher

A substitution cipher is a method of encryption where each letter in the plaintext is replaced with another letter or symbol according to a fixed system. The Caesar cipher is an example of a substitution cipher, where each letter is shifted by a fixed number of positions in the alphabet. The video points out the weakness of basic substitution ciphers due to the preservation of letter frequencies.

💡Permutation cipher

A permutation cipher rearranges the order of the characters in a message to encrypt it. The columnar transposition cipher mentioned in the script is an example, where letters are filled into a grid and read out in a specific order to create the ciphertext. The key in permutation ciphers is the order of the permutation.

💡Enigma machine

The Enigma machine was an encryption device used by the Germans during World War II. It combined substitution and permutation to create a complex cipher. The video describes the Enigma machine's rotors, reflector, and plugboard, which made it extremely difficult to break. The script also mentions how Alan Turing and his team at Bletchley Park eventually cracked the Enigma codes.

💡Data Encryption Standard (DES)

DES is an early cryptographic algorithm that was widely used for securing electronic data. The video explains that DES originally used 56-bit keys, which were considered secure at the time of its development in 1977. However, with advancements in computing power, DES became insecure, leading to the development of the Advanced Encryption Standard (AES).

💡Advanced Encryption Standard (AES)

AES is a symmetric encryption standard that replaced DES. It uses larger keys (128, 192, or 256 bits) to make brute force attacks infeasible. The video highlights AES's use in various applications, such as securing data on iPhones, transmitting data over WiFi, and accessing websites using HTTPS. AES is an essential part of modern cryptography, balancing security and performance.

💡Key exchange

Key exchange is a method that allows two parties to securely establish a shared secret key over an insecure channel. The video uses the analogy of mixing paint colors to explain how key exchange works, without the need to transmit the actual secret keys. The Diffie-Hellman key exchange, which uses one-way functions like modular exponentiation, is mentioned as a method for securely exchanging keys.

💡Symmetric encryption

Symmetric encryption is a type of encryption where the same key is used for both encryption and decryption. The video mentions that symmetric keys are used in techniques like the Caesar Cipher, Enigma, and AES. It contrasts with asymmetric encryption, where different keys are used for encryption and decryption.

💡Asymmetric encryption

Asymmetric encryption uses two different keys: a public key for encryption and a private key for decryption. The video explains that this allows anyone to encrypt a message that only the intended recipient can decrypt with their private key. Asymmetric encryption is used for secure communication and digital signatures, where the private key is used to sign data, and the public key is used to verify the signature.

💡RSA

RSA is an asymmetric encryption algorithm widely used for secure data transmission. Named after its inventors Rivest, Shamir, and Adleman, RSA is based on the mathematical properties of large prime numbers. The video mentions RSA as the most popular asymmetric encryption technique used today, which plays a crucial role in secure online transactions and communications.

Highlights

Defence in depth is a strategy using multiple layers of security to protect computer systems.

Cryptography is the practice of secure communication, involving encryption and decryption.

A cipher is an algorithm that converts plaintext into ciphertext.

The Caesar cipher is an example of a substitution cipher used historically.

Substitution ciphers have drawbacks due to preserved letter frequencies.

Permutation ciphers, like the columnar transposition cipher, reorder letters in a grid to encrypt messages.

The German Enigma machine was an encryption device used during World War II.

The Enigma machine used rotors for substitution and a reflector for signal redirection.

The Enigma's encryption process was advanced by its ability to change substitution mappings with each key press.

Alan Turing and Bletchley Park played a crucial role in breaking Enigma codes.

The Data Encryption Standard (DES) was developed in 1977 with 56-bit keys.

Advanced Encryption Standard (AES) was introduced in 2001 with larger key sizes for enhanced security.

AES uses a series of substitutions and permutations for encryption.

Key exchange allows two parties to agree on a key without ever sending it over the network.

Diffie-Hellman Key Exchange uses one-way functions for secure key exchange.

Asymmetric encryption involves a public key for encryption and a private key for decryption.

RSA is a popular asymmetric encryption technique used widely today.

Cryptography ensures secure communication for online activities like banking and browsing.

Transcripts

Hi, I’m Carrie Anne, and welcome to CrashCourse 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 defence 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 archers,

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.

INTRO

The word cryptography comes from the roots ‘crypto’ and ‘graphy’, 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: "euxwxv".

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.

Indeed, 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 columnar transposition cipher.

Here, we take a message, and fill the letters into a grid.

In this case, we’ve chosen 5 by 5.

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 5 by 5 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.

This 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 on to another rotor, it connected every pin to another,

and sent the electrical signal back through the rotors.

Finally, there was a plugboard 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 plugboard, then the rotors, hits

the reflector, comes back through the rotors and plugboard, and illuminates the letter

‘L’ on the lampboard.

So H is encrypted to L.

Note that the circuit can flow both ways – so if we typed 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 rotors advanced by one spot, sort of like an odometer in a

car.

So if you entered the text A-A-A, it might come out as B-D-K, 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 2 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 a 128-bit keys, you'd need trillions of years to try every combination, even if you

used every single computer on the planet today.

So you 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 ten or more times for each block.

You might be wondering: why only ten rounds?

Or why only 128 bit keys, and not ten thousand bit keys?

Well, it’s a performance tradeoff.

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

WiFi 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

codebooks with daily settings for their Enigma machines.

But this strategy could never work in the internet era.

Imagine having to crack open a codebook 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 were used 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 mixed 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 would know 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 dividing by a third number, the modulus.

So, for example, if we wanted to calculate 3 to the 5th power, modulo 31, we would calculate

3 to the 5th, which is 243, then take the remainder when divided by 31, which is 26.

The hard part is figuring out the exponent given only the result and 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 securely 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 XY 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 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 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 Adleman.

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!