密码

密码学是一种通过使用密码来保护信息和通信的方法，这样只有信息的使用者才能阅读和处理信息。

前缀“crypt”的意思是“隐藏的”，后缀“graphy”代表“写作”。

历史密码

Scytale（700BC 公元前700年）
斯巴达军队在战斗期间使用Scytale发送敏感信息。

换位（Transposition）与置换（Substitution）

Scytale是转位密码（transposition cipher）的一个例子
我们改变的不是字母，而是顺序。

另一类是替换密码（substitution cipher）
字母改变了，但顺序保持不变。

替换密码（Substiution Cipher）

系统地用字母或字母组替换其他字母或字母组

例如，“fly at once”变成了“gmz bu podf”，将每个字母替换为拉丁字母中后面的字母。

凯撒密码 （100BC 公元前100年）

明文中的每个字母都被字母表中更靠后一些固定位置的字母所取代。

移位密码

考虑加密英文文本
密钥空间：k属于{0, 1, …, 25}
加密：将每个字母x替换成x+k
解密：将每个字母x替换成x-k

1. ROT13是一个键为13的移位密码。
2. 凯撒密码是一种密钥为3的移位密码。
   

破坏替换密码

课文中最常见的字母
x，i，e，h

已知密文攻击

1. 使用英语字母的概率（E：12.7%，T：9.1%，A：8.1%）
2. 字母对的使用概率（HE, AN, IN, TH）

密码中的d可能是明文中的e

维吉尼亚密码

替换密码可以是单字母的（monoalphabetic）

1. 每个字母总是被编码成相同的字母。

Vigenère Cipher是一个多字母密码的例子

基本上，它对不同的文本位置应用不同键的移位密码。

例如，key = crypto

现代密码学核心原理

从历史观点上说

密码学是一门艺术（启发式、特别设计和分析)
在70年代末和80年代初，密码学开始发展成为一门严谨的科学

密码学的三个步骤：

1. 精确指定威胁模型（安全含义的形式化模型和定义）
2. 提出一个结构
3. 证明在威胁模型下打破结构将解决一个潜在的困难问题

模型和定义的重要性

如果你不知道自己想要实现什么，你怎么可能知道自己何时(或是否)实现了呢?

开发精确的威胁模型和安全定义迫使设计师思考他们真正想要的是什么。

1. 什么是必要的(有时更重要)，什么不是

威胁模型和安全定义可以对方案进行有意义的评估和比较

一个清晰的威胁模型和安全定义可以让其他人理解某些方案提供的安全保证

1. 允许将方案用作更大系统的组件

明确假设的重要性

一般来说，密码学目前需要计算假设。

1. 允许研究人员尝试验证这一假设。
2. 允许基于不同假设的方案之间进行有意义的比较。
3. 在假设被证明是错误的情况下的实际影响。
4. 启用安全性证明

对称和非对称

对称加密使用相同的密钥进行加密和解密。
非对称加密使用不同的密钥进行加密和解密。
优缺点：

1. 对称通常要快得多，但密钥需要通过非加密通道传输。
2. 另一方面，不对称更安全，但速度较慢。

对称密码：定义

定义：定义在（k, m, c）的是：

E是加密函数，需要两个输入:密钥k和消息m。这个函数生成密文c。
D是需要两个输入的解密函数:一个密钥k和一个密文c。它产生消息m。

一次性密码本（One-Time Pad）

非对称密码术（公钥密码术）

使用了两个不同但在数学上相关的密钥—公钥和私钥。

从一个密钥(“私钥”)计算另一个密钥(“公钥”)在计算上是不可行的，即使它们必然相关。

相反，这两个密钥都是作为相互关联的对秘密生成的。

密钥生成

使用一个不可预测的(通常是大而随机的)数字开始生成适合于非对称密钥算法使用的可接受的密钥对。

加密和解密技术

任何人都可以使用公钥加密消息，但只有配对私钥的持有者才能解密。安全性取决于私钥的保密性。

反向使用:数字签名

附在电子传输文件上的一种数字代码(由公钥加密生成并验证)，用于验证文件的内容和发送人的身份。

生成数字签名：

1. 消息通过商定的算法进行散列，形成消息摘要。
2. 消息摘要使用发送方的私钥加密。
3. 加密的消息摘要是添加到消息并发送的签名。
4. 接收方计算消息摘要，并使用发送方的公钥解密签名。
5. 接收方将MD与解密签名进行比较。如果匹配，则表示消息未被篡改。

签名验证!用私钥加密的版本附加到原始消息中。在收到消息和签名之后，Bob使用公钥来验证消息的真实性。验证是通过使用公钥解密消息并确定哈希/摘要是否与原始消息匹配来完成的。

总结

1. 传统的 （换位vs置换）
2. 现代的（对称vs非对称）

Acknowledgements: Jiangtao Wang