Cryptography: Crash Course Computer Science #33

Summary

本视频深入探讨了计算机安全中的关键技术——密码学。密码学，源自“秘密写作”，通过算法将明文转换为密文，只有持有密钥者才能解密。历史上，凯撒大帝使用凯撒密码加密通信，而现代密码学则更为复杂，涉及多种加密和解密技术。视频中介绍了替换密码和排列密码，以及德国Enigma密码机的工作原理。随着计算机的出现，密码学从硬件转向软件，如数据加密标准（DES）和高级加密标准（AES）。此外，介绍了密钥交换算法，如Diffie-Hellman，以及非对称加密技术，如RSA，它们允许在不安全的通道上安全地共享密钥。视频强调了密码学在我们日常生活中的应用，如在线购物、电子邮件和网页浏览，确保了信息的安全和隐私。

Takeaways

• 🛡️ 没有完美的计算机系统，系统架构师采用多层安全机制的深度防御策略来挫败攻击者。
• 🔐 加密术（Cryptography）源于“crypto”和“graphy”，意为“秘密写作”，通过算法将明文转换为只有持有密钥才能解密的密文。
• 📜 凯撒密码是一种替换密码，通过固定位数替换字母来加密信息，但存在频率分析的弱点。
• 🧩 排列密码（如列置换密码）通过改变字母的顺序来加密信息，其加密和解密过程依赖于特定的排列顺序和网格大小。
• 🤝 德国的恩尼格玛机（Enigma）使用可配置的转子和反射器，通过复杂的电路实现了高级的替换密码。
• 🔄 恩尼格玛机的加密弱点之一是同一键不能加密成它自己，这最终导致了其被破解。
• 💻 随着计算机的出现，加密技术从硬件转向了软件，如数据加密标准（DES）和高级加密标准（AES）。
• 🔑 AES使用更大尺寸的密钥（128, 192或256位），使得暴力破解变得极其困难。
• ⚖️ AES在性能和安全性之间取得平衡，适用于实际的加密需求，广泛应用于各种加密场景。
• 🔗 互联网时代需要一种方法，使得服务器能够在公共互联网上安全地向用户发送秘密密钥，这通过密钥交换算法实现。
• 🎨 通过单向函数，如Diffie-Hellman密钥交换，可以在不直接发送密钥的情况下，让双方安全地协商出一个共享密钥。
• 🔗 对称加密和非对称加密是现代加密技术的两大支柱，它们共同保护着我们的在线通信安全。

Q & A

什么是防御深度策略？

防御深度策略是一种使用多层不同安全机制来挫败攻击者的策略。它类似于城堡的设计，需要通过多个障碍才能到达核心区域，如躲避弓箭手、越过护城河、攀登城墙等。

什么是密码学？

密码学是一种通过密码算法将明文转换成密文的技术，密文在没有密钥的情况下看起来像乱码。密码学包括加密和解密两个过程，其中加密是将文本变密，解密则是相反的过程。

凯撒密码是如何工作的？

凯撒密码是一种替换密码，通过将消息中的字母向前或向后移动固定数目的位置来加密。例如，凯撒将字母移动三位，所以'A'变成了'D'，'brutus'变成了'euxwxv'。

为什么基本的替换密码容易被破解？

基本的替换密码容易被破解是因为它们保留了字母频率。例如，英语中'E'是最常用的字母，如果'E'被替换成'X'，那么'X'将出现在密文中的频率最高，这为密码分析者提供了破解线索。

列置换密码是如何工作的？

列置换密码通过将消息填入一个表格，然后按照不同的顺序读取列中的字符来加密消息。例如，可以选择5x5的表格，按照从下往上、从左到右的顺序读取字符，形成新的字母顺序，这个顺序就是加密后的消息。

德国的恩尼格玛密码机是如何工作的？

恩尼格玛密码机是一种带有键盘和显示板的机械式密码机，键盘和显示板上都显示了完整的字母表。机器上方有一系列可配置的转子，这些转子通过交叉连接的电线实现字母的替换。恩尼格玛密码机的复杂之处在于它使用了多个转子，每个转子都可以旋转到26个可能的起始位置，并且可以以不同的顺序插入，从而提供多种替换映射。

什么是数据加密标准（DES）？

数据加密标准（DES）是由IBM和NSA在1977年开发的一个加密标准。DES最初使用的是56位长的二进制密钥，这意味着有大约72千万亿种不同的密钥组合。

高级加密标准（AES）为什么比DES更安全？

高级加密标准（AES）使用更大尺寸的密钥——128、192或256位，这使得暴力破解攻击变得极其困难。例如，对于128位的密钥，即使使用地球上所有的计算机，也需要数万亿年才能尝试完所有组合。

什么是Diffie-Hellman密钥交换？

Diffie-Hellman密钥交换是一种算法，它允许两台计算机在从未发送密钥的情况下达成一致的密钥。它使用单向函数——在某个方向上非常容易执行，但在相反方向上却很难逆转的数学操作。

什么是公钥和私钥？

公钥和私钥是不对称加密中的两个不同的密钥。公钥可以公开，用于加密消息，只有对应的私钥持有者才能解密。私钥是保密的，用于解密公钥加密的消息或使用私钥加密消息，公钥可以解密，这用于数字签名。

RSA加密是如何工作的？

RSA加密是一种基于大整数分解困难性的非对称加密技术。它使用两个不同的密钥：一个公钥用于加密数据，一个私钥用于解密。RSA加密的安全性依赖于大整数分解的难度，目前它是最流行的非对称加密技术之一。

为什么需要密码学来保护在线通信？

密码学用于保护在线通信，确保数据传输的安全性、私密性和完整性。通过使用对称加密、密钥交换和公钥密码学，可以防止未授权访问、篡改和伪造数据，从而保护用户的敏感信息。

Outlines

00:00

🔒 计算机安全与密码学简介

Carrie Anne介绍了计算机安全的概念，并指出没有100%安全的计算机系统。她提到系统架构师采用多层安全机制的防御策略，称为“深度防御”。接着，她引入了密码学，解释了其由来和基本过程，包括加密（将明文转换为密文）和解密（将密文转换回明文）。她还提到了凯撒密码作为替代密码的一个例子，并讨论了其局限性，如字母频率的保留。此外，她还介绍了排列密码，例如列置换密码，并说明了如何使用网格和特定的读取顺序来加密消息。最后，她提到了机械密码机，如德国的恩尼格玛机，以及它是如何工作的，包括转子、反射器和插线板等组件。

05:05

💰 DES与AES加密标准的发展

本段落讨论了数据加密标准（DES）和高级加密标准（AES）的发展。DES最初使用56位的二进制密钥，但到了1999年，计算机已经能够在短时间内暴力破解所有可能的密钥，因此变得不安全。为了提高安全性，2001年发布了AES，它使用更大尺寸的密钥（128、192或256位），使得暴力破解变得极其困难。AES通过将数据分成16字节的块，然后基于密钥值进行一系列的替代和排列操作，以及一些其他操作来混淆消息，这个过程对每个块重复10次或更多。此外，还讨论了为什么选择10轮而不是更多，以及为什么选择128位密钥而不是更大的密钥尺寸，这是因为需要在性能和安全性之间取得平衡。AES广泛应用于各种场景，如iPhone文件加密、Wi-Fi传输和HTTPS网站访问。

10:06

🔑 对称加密与非对称加密

Carrie Anne解释了对称加密和非对称加密的区别。对称加密使用相同的密钥进行加密和解密，如凯撒密码、恩尼格玛机和AES。而非对称加密使用一对不同的密钥，通常一个是公开的，另一个是私有的。公钥可以用于加密只有私钥持有者才能解密的消息。这种方式允许服务器通过公钥加密的方式发送安全消息，而只有私钥持有者才能解密。此外，私钥也可以用来加密消息，然后公钥解密，这在数字签名中非常有用，因为只有密钥的所有者才能使用私钥进行加密。最著名的非对称加密技术是RSA，以它的发明者命名。最后，Carrie Anne强调了现代密码学的关键部分，包括对称加密、密钥交换和公钥密码学，这些都是保护在线通信安全的重要技术。

Keywords

💡防御深度

防御深度是一种安全策略，它通过使用多层不同的安全机制来挫败攻击者。在视频中，它被比喻为城堡的设计，需要通过多重障碍才能到达核心区域。这个概念与视频主题紧密相关，因为它展示了计算机安全不仅仅是单一防护措施，而是需要多层保护来提高安全性。

💡密码学

密码学是关于加密和解密信息的科学，它源自希腊语'crypto'（秘密）和'graphy'（写作）。视频中提到，密码学的基本用途是使信息变得秘密，通过算法（密码）将明文转换成只有拥有密钥才能解读的密文。密码学是计算机安全中最常见的形式之一，是视频讨论的核心主题。

💡加密

加密是将明文转换为密文的过程，使得信息变得难以被未授权者理解。在视频中，加密是密码学的一个重要过程，它确保了信息的安全性。例如，朱利叶斯·凯撒使用凯撒密码通过向前移动字母来加密私人通信。

💡解密

解密是加密的逆过程，它使用密钥将密文转换回原始的明文。视频解释了解密需要相应的密钥，并且是理解密码学如何工作的关键部分。例如，接收者需要知道凯撒密码的密钥（即向前移动的位数）来解密信息。

💡替代密码

替代密码是一种密码学技术，它根据某种转换规则将消息中的每个字母替换为另一个字母。视频中提到，尽管替代密码可以隐藏信息的内容，但它们存在一个主要缺点，即字母频率被保留下来，这可能被密码分析家利用来破解密码。

💡排列密码

排列密码是另一种密码学技术，它通过改变字母的顺序来加密信息。视频中以列行置换密码为例，通过将字母填入一个矩阵，然后按照特定的顺序读取字母来进行加密。排列密码的关键在于字母的新顺序，即排列，这与视频的主题紧密相关，因为它展示了密码学的多样性和复杂性。

💡恩尼格玛机

恩尼格玛机是20世纪初德国使用的一种密码机，它通过一系列可配置的转子和反射器来实现复杂的加密。视频中提到，恩尼格玛机的加密能力来自于转子上的字母交换，以及转子的旋转和顺序变化，这增加了密码的复杂性。恩尼格玛机是密码学历史上的一个重要案例，它展示了机械式密码机的工作原理。

💡数据加密标准

数据加密标准（DES）是1977年由IBM和NSA开发的一个广泛使用的软件密码。它最初使用的是56位长的二进制密钥，这意味着有大约72千万亿种不同的密钥组合。视频中解释了DES的密钥长度在20世纪70年代意味着几乎不可能通过暴力破解所有可能的密钥，但随着计算能力的提升，DES变得不安全，因此被更先进的加密标准所取代。

💡高级加密标准

高级加密标准（AES）是2001年最终确定并发布的加密标准，旨在使用更大尺寸的密钥——128、192或256位，使得暴力破解攻击变得极其困难。视频中提到，AES通过将数据分成16字节的块，并应用基于密钥值的一系列替代和排列操作，以及一些其他操作来混淆消息。AES是现代广泛使用的加密技术，它平衡了性能和安全性，提供了实用的密码学。

💡密钥交换

密钥交换是一种算法，允许两台计算机在不实际传输密钥的情况下达成一个共享密钥。视频中通过油漆颜色的比喻解释了密钥交换的工作原理。密钥交换是互联网时代安全通信的关键技术，它允许服务器和用户在公共互联网上安全地共享密钥，而无需担心密钥在传输过程中被拦截。

💡非对称加密

非对称加密是一种加密方法，使用一对不同的密钥，通常一个是公开的，另一个是私有的。只有使用私有密钥才能解密使用公钥加密的消息。视频中通过盒子和挂锁的比喻来说明非对称加密的概念。非对称加密不仅用于加密消息，还用于数字签名，其中服务器使用其私有密钥加密数据，任何人都可以使用服务器的公钥解密它，这就像一个不可伪造的签名。RSA是目前使用最广泛的非对称加密技术。

Highlights

不存在完全100%安全的计算机系统，系统架构师采用多层防御策略来挫败攻击者。

密码学是计算机安全中最常见的形式之一，它使用密码算法将明文转换成密文。

凯撒密码是替换密码的一个例子，通过字母表向前移动固定数量的位置来加密信息。

基本替换密码的一个缺点是字母频率被保留，这可能被密码分析家利用。

排列密码，如列置换密码，通过改变字母顺序来加密信息。

20世纪初，密码学通过加密机（如德国的恩尼格玛机）实现机械化。

恩尼格玛机使用可配置的转子和反射器，以及插线板，增加了加密的复杂性。

艾伦·图灵和布莱切利公园的同事们成功破解了恩尼格玛密码，并自动化了这一过程。

随着计算机的出现，密码学从硬件转向软件，如1977年开发的DES。

DES使用56位长的二进制密钥，但到了1999年，计算机已经可以在两天内尝试所有可能的密钥。

为了提高安全性，2001年发布了使用更大密钥的AES。

AES将数据分成16字节的块，并应用一系列基于密钥值的替换和排列操作。

AES平衡了性能和安全性，提供了实用的密码学应用。

在互联网时代，需要一种方法让服务器通过公共互联网安全地发送密钥给用户。

密钥交换算法允许两台计算机在不发送密钥的情况下达成一致。

迪菲-赫尔曼密钥交换使用单向函数，如模指数运算，来计算共享密钥。

对称密钥加密，如凯撒密码、恩尼格玛和AES，使用发送者和接收者都知道的密钥。

非对称加密使用一对不同的密钥，通常一个是公开的，另一个是私有的。

RSA是目前使用最广泛的非对称加密技术，用于安全网站连接和数据传输。

现代密码学的关键部分包括对称加密、密钥交换和公钥密码学，它们共同保护我们的在线通信安全。

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!