保研夏令营复习计划-密码学
密码学是网络空间安全的主要的一门专业课之一，主要包括对称加密算法、非对称加密算法以及密码学算法的安全性以及应用。
对称加密和消息机密性
对称加密原理
一个对称加密方案由五部分组成：
- 明文
- 加密算法
- 秘密密钥
- 密文
- 解密算法
密码体制
密码体制一般从三个不同的方面进行分类：
- 明文转换成密文的操作类型
- 使用的密钥数：发送者接受者使用同一密钥，该体制就是对称加密算法，反之为非对称加密算法。
- 明文处理方式：分组密码一次处理一个输入元素分组，输出与输入对应的分组。流密码连续的处理输入元素，每次产生一个输出元素。
密码分析
计算安全：
- 破解密文的代价超出被加密信息的价值
- 破解密文需要的时间超出信息的有用寿命
Feistel密码结构
分组密码的操作取决于下列参数：
- 分组大小：分组越大安全性越高效率越低，128bit合理且折中
- 密钥大小：越长的密钥越安全，但是也会降低效率，普遍使用密钥长度128bit
- 迭代轮数：典型迭代轮数16轮
- 子密钥产生算法：复杂度越高，密码破译难度越高
- 轮函数：同样，复杂度越高越难以破解
对称分组加密算法
数据加密标准DES
算法描述：
明文长度为64it，密钥长度为56bit，更长的明文被分为64bit的分组来处理。采用16轮迭代，从原始的56bit密钥产生16组子密钥，每一轮迭代使用一个子密钥。
DES解密过程在本质上和加密过程相同。规则如下：使用密文作为DES算法的输入，但是子密钥Ki的使用顺序与加密时相反。即第一次使用K16，第二次使用K15，以此类推知道最后一次使用K1.
穷举密钥消耗的时间：
三重DES
3DES使用三个密钥执行三次DES算法，其组合过程依照加密-解密-加密的顺序：
C = E（K3，D（K2，E（K1，P）））
P = D（K1，E（K2，D（K3，C）））
高级加密标准AES
AES使用的分组大小为128bit，密钥长度可以为128、192、256bit。常用128bit密钥长度
算法描述：
AES没有使用Feistel结构，而是在每轮替换和移位时都并行处理整个数据分组。
输入密钥被扩展成为44个32比特字的数组w[i]。4个不同的字（128bit）用作每轮的轮密钥。
进行了4个不同的步骤，一个是移位，3个是替换：
- 字节替换：使用S盒来对分组进行逐一的字节替换
- 行移位：对行做简单的移位
- 列混合：对列的每个字节做替换，是一个与本列全部字节有关的函数
- 轮密钥加：将当前分组与一部分扩展密钥简单的按位异或
加密和解密的最后一轮都只包含3个步骤，这么做是为了使密码可逆
随机数和伪随机数
满足随机性和不可预测性
真随机数发生器、伪随机数生成器和为随机函数
密码应用程序通常利用了随机数生成的算法技术。这些算法具有确定性的特点，因此产生的数列不具有统计上的随机性。虽然如此，如果这个算法很好，那么产生出的数列将会通过很多合理的随机性测试，这种数字被称为伪随机数字
真随机数发生器将一个有效的随机源作为输入源，这个源被称为熵源。
伪随机函数(PRF): PRF被用来产生一些固定长度的伪随机比特串。例如对称的加密密钥和随机数。典型的PRF采用种子加上上下文中特定的值作为输入，例如用户名ID和应用程序ID。
流密码和RC4
流密码结构
如果伪随机数生成器设计合理，对同样的密钥长度，流密码和分组密码一样安全。流密码的主要优点是流密码与分组密码相比几乎总是更快，使用更少的代码。本节中的示例RC4能用仅仅几行代码实现。最近几年，随着AES的引进，这个优势已经消失了，因为AES可以用软件方式高效实现。比如，Intel AES指令集含有一轮加解密和密钥产生过程使用的机器指令。使用硬件指令实现AES跟仅使用软件方式相比，速度提高了-一个数量级。
RC4算法
由于RC4算法加密是采用的xor，所以，一旦子密钥序列出现了重复，密文就有可能被破解。那么，RC4算法生成的子密钥序列是否会出现重复呢？由于存在部分弱密钥，使得子密钥序列在不到100万字节内就发生了完全的重复，如果是部分重复，则可能在不到10万字节内就能发生重复，因此，推荐在使用RC4算法时，必须对加密密钥进行测试，判断其是否为弱密钥。其不足主要体现于，在无线网络中IV（初始化向量）不变性漏洞。
分组密码工作模式
电子密码本模式ECB
最简单的一种使用方式是所谓的电子密码本(ECB) 模式，在此模式下明文一-次被处理b比特，而且明文的每-一个分组都使用同-密钥加密。之所以使用术语密码本，是因为对于给定的密钥，每个b比特的明文分组对应唯一的密文。 因此，可以想象一个庞大的密码本，它包含任何可能的b比特明文对应的密文。
如果同一个64比特的明文分组在消息中出现了不止一次，它总是产生相同的密文。因此，对于过长的消息，ECB模式可能不安全。
密码分组链接模式CBC
加密算法输入是当前明文分组与前一密文分组的异或；每个分组使用同一密钥。这就相当于将所有的明文组连接起来了。加密函数每次输入和明文分组之间的关系不固定。
解密时，用解密算法依次处理每个密文分组。将其结果与前一密文分组进行异或，产生明文分组：
为了产生第一个密文分组，将一个初始向量IV和第一个明文分组进行异或。解密时将IV和解密算法的输出进行异或来恢复第一个明文分组。
发送者和接收着都必须知道IV。为了提高安全性，IV需要像密钥一样进行保护。这可以通过使用ECB加密传送IV来完成。要保护IV的一个理由如下：如果攻击者成功欺骗接收者使其使用一个不同的IV值，接着攻击者就能把明文的第一个分组的某些位取反。
密码反馈模式CFB
这种模式可以将任意分组密码转换成流密码。流密码不需要将消息填充为分组的整数倍，它还能实时操作，因此，如果传送字符流，使用面向字符的流密码，每个字符都能被及时的加密并传送。
加密：加密模块的输入是一个64bit的移位寄存器，初始值设定为某一初始向量IV。加密模块输出的最左边s比特和明文P1的第一单元进行异或，产生密文C1的第一个单元，然后传输，接下来移位寄存器的内容都左移s比特，同时将C1方在移位寄存器的最右边s比特。这个过程一致持续知道所有明文单元都已被加密。
解密时使用同样的方案，不同的时将接收到的密文单元和加密模块的输出进行异或得到明文单元。注意这里使用的是加密函数，而不是解密函数。
计数器模式CTR
计数器初始化为某一值，然后随着消息块的增加计数器值增加1 (以2的b次方为模，b为分组长度)。在加密时，计数器被加密然后与明文分组异或来产生密文分组，这里没有链接。当解密时，相同序列的计数器值与密文异或来恢复相对应的明文分组。
公钥密码和消息认证
消息认证的方法
利用常规加密的消息认证
假设只有发送者和接受者共享一个密钥，那么假定接收者能够识别有效的消息时，只有真正的发送者才能够成功的为对方加密消息。此外，如果消息里带有错误检测码和序列号，则接收者能够确认消息是否被篡改过和序列号是否正常。
事实上，对数据认证而言只使用对称加密的方法不是一个合适的工具。比如使用ECB加密的分组加密算法，攻击者重排密文分组次序仍然可以解密。
非加密的消息认证
这里分析几种不依赖于加密消息认证方法。所有的这些方法都会生成认证标签，并且附在每一条消息上用于传输。消息本身并不会被加密，所以它在目的地可读而与目的地认证功能无关。
消息认证码
一种认证技术利用私钥产生一小块数据，称之为消息认证码，将其附到消息上。假设只有消息发送者和接收者知道密钥，若收到的认证码与计算的一致，即可证明：
- 消息没有被篡改
- 接收者确保消息来自合法的发送者
- 如果消息中包含序列号，而攻击者不能成功修改序列号，那么接收者就可以确认消息的正确序列
单向散列函数
MAC的一种替代方法是使用单向散列函数。如同MAC，散列函数接收变长消息M作为输入，生成定长的消息摘要H(M)作为输出。与MAC不同的是散列不需要密钥，为了消息认证，消息摘要要随消息一起以可信的形式传送。
安全散列函数
散列函数的要求
散列函数的目的是为文件、消息或其他数据块产生指纹，H函数必须具有以下性质：
- H可适用于任意长度的数据块
- H能生成固定长度的输出
- 对于任意x，计算H(x)相对容易，并且可以用软硬件方式实现
- 需要具有单向性，或具有抵抗原像攻击性
- 对于人一给定数据块x，找到满足H(y)=H(x)的y!=x在计算上是不可行的，即具有抗弱碰撞攻击性
- 找到满足H(y)=H(x)的任意一对xy在计算上是不可行的。满足这一特性的散列函数称为抗碰撞性，有时也被称为抗强碰撞性
散列函数的安全性
有两种方法可以攻击一个安全的散列函数：密码分析法和蛮力攻击法
散列函数抵抗蛮力攻击的强度完全依赖于算法生成的散列码的长度。攻击一个长度为n的散列码所需要付出的代价如下：
| 攻击 | 复杂度 |
|---|---|
| 抗原像 | 2^n |
| 抗第二原像 | 2^n |
| 抗碰撞 | 2^(n/2) |
简单散列函数
所有散列函数都按照下面基本原理操作。把输入看成n比特块的序列。对输入用迭代的方式每次处理一块，生成n比特的散列函数。
SHA安全散列函数
sha512流程：
消息认证码
HMAC
目标：
- 不必修改而直接使用现有的散列函数。特别是很容易免费得到软件上执行速度较快的散列函数及其代码。
- 嵌入式散列函数要有很好的可移植性，以便开发更快或更安全的散列函数。
- 保持散列函数的原有性能，不发生显著退化。
- 使用和处理密钥简单。
- 如果已知嵌入的散列函数的强度，则完全可以知道认证机制抗密码分析的强度。
公钥密码原理
公钥密码思想
基本步骤如下：
- 每个用户都生成一对密钥用来对消息进行加密和解密。
- 每个用户把两个密钥中的一个放在公共寄存器或其他可访问的文件夹里，这个密钥便是公钥，另一个密钥自己保存。
- 如果Bob希望给Alice发私人消息，则他用Alice的公钥加密消息。
- 当Alice收到这条消息，用私钥解密。因为只有Alice知道她自己的私钥，其他人收到消息无法进行解密
公钥密码系统的应用
- 加密解密
- 数字签名：私钥签名，公钥验证
- 密钥交换
公钥密码算法
RSA公钥密码算法
对一明文块M和密文块C，加密和解密有如下形式：
C = M^e mod n
M = C ^ d mod n = M^ed mod n
设A为明文，B为密文，则：
A=B^d mod n；
B=A^e mod n；
e和n是公钥，d是私钥。
n=p*q, d=e^-1 mod (p-1)(q-1)发送方和接收方都必须知道n和e的值，并且只有接收者知道d的值。RSA公钥密码算法的公钥KU = {e,n}，私钥KR = {d,n}。为使该算法能够用于公钥加密，它必须满足下列要求：
- 可以找到e、d、n的值，是的对所有的M<n,M^ed mod n = M成立
- 对所有满足M<n的值，计算M^e C^d 相对容易
- 给定e和n，不可能推出d
Diffie-Hellman密钥交换
Diffie-Hellman算法的目的就是使两个用户能够安全的交换密钥，供以后加密消息时使用。该算法本身局限于密钥交换。
算法：
可能遭受中间人攻击：
其他公钥密码算法
- 数字签名标准DSS：专为数字签名功能而设计的算法。与RSA不同，它不能用来加密或者密钥交换
- 椭圆曲线密码ECC：ECC相比于RSA主要吸引力在于它只需要少数比特就可以提供相同强度的安全性，从而减轻了处理开销
数字签名
假设Bob想给Alice发送消息。虽然这条消息的保密性并不重要，但是他想Alice能够确定这条消息确实是来自于他。当Alice收到密文时，她发现能够用Bob的公钥进行解密，从而证明这条消息确实是Bob加密的。因为没有其他人拥有Bob的私钥，所以其他任何人都不能创建由Bob的公钥能够解密的密文。因此，整个加密的消息就成为一个数字签名(digital signature)。此外，由于没有Bob的私钥就不可能篡改消息，所以数字签名不仅认证了消息源，它还保证了数据的完整性。