图解密码学

1 历史上的密码

1.1 什么是凯撒密码

凯撒密码是一种相传尤利乌斯-凯撒曾使用过的密码。

凯撒密码是通过将明文中使用的字母按照平移一定的字数得到的。

加密解密可以通对应的平移来加密或者解密传输数据。

使用暴力破解来破译密码

在凯撒密码中只有26中平移，可以一一尝试，来获得有意义的一些单词，从而获得加密方式。

1.2 简单的密码替换

如果我们将字母表中的26个字母，分别与这26个字母建立一对一的对应关系，那么无论哪一种对应关系就都可以作为密码来使用。

简单替换密码的秘钥空间

简单替换密码很难通过暴力来破译，这是因为简单替换密码中可以使用的秘钥数量远比凯撒密码多很多。

一种密码能够使用的“所有秘钥的集合”称为秘钥空间，所有可用秘钥的总数就是秘钥的大小。秘钥空间越大，暴力破解就越难。

简单替换密码中，26个字母，我们可以计算出简单替换密码的没有总数是26的阶乘。

用频率分析破译密码

假设获得一段密文，按每个字母的统计频率，根据通常字母出现的频率来猜测，比如密文中出现频率最高的是m，我们频率使用最多的是e，这可找出对应关系m->e,然后根据通常the使用最多，这可找密文m之前的连个字母的对应关系。之后在猜测翻译密文，不断找到对应关系。

通过上面的破解过程，可以总结一下结论：

除了高频字母以外，低频字母也可能成为线索。
搞清楚开头与结尾能够成为线索，搞清单词之间的分隔也能够成为线索
密文越长越容易破解
同一个字母连续出现能够成为线索
破译速度会越来越快

1.3 Enigma

什么是Enigma

这是一种专门用于加密与解密的机器。

Enigama由键盘，齿轮，电池和灯泡组成的机器。发送者和接收者各种拥有一台Enigma。

当Enigma设置好后，发送者假设按a键，D灯泡亮，记录d，则认为a–>d,接收者拿到加密后的d，按d，a灯泡亮，则解密为a。

2 对称密码

2.1 从文字密码到比特序列密码

编码

计算机操作对象并不是文字，而是0，1排列而成的比特序列。

XOR

比特位不相同的异或结果为1，否则为0.

A xor B xor B = A,因为B xor B得到得到的结果是0，A xor 0 = A

2.2 DES

DES是1977年美国联邦信息处理标准中所采用的一种对称密码。然而，随着计算机的进步，现在DES已经能够被暴力破解，强度大不如前了。

DES是一种将64比特的明文长度加密成64比特密文的对称密码算法，它的秘钥长度是56比特。从严格的来说DES的秘钥长度是64比特，但由于每隔7个比特会设置一个错误检查的比特，因此实质上其秘钥长度是56比特。

DES的结构（Feistel结构）

DES的基本结构是有Horst Feistel设计的，因此也称为Feistel网络结构或者Feistel密码。下图展示了Feistel网络中一轮的计算流程。DES是一种16轮循环的Feistel网络。

一轮的计算步骤：

将输入的数据等分为左右两个部分
将输入的右侧直接发送到输出的右侧
将输入的右侧发送到轮函数
轮函数根据右侧数据和子秘钥，计算出一串看上去是随机的比特序列
将上一步得到的比特序列与左侧序列进行XOR运算，并将结果作为加密后的左侧。

因为右侧没有变换，但是需要对不同的子秘钥进行若干次，这就需要在每两轮处理之间将左侧与右侧数据对调。

Feistel网络的解密操作只要按照相反的顺序来使用子秘钥就可以完成了，而Feistel网络本身的结构，在加密和解密时都是完全相同的。

2.3 三重DES

什么是三重DES

三重DES是为了增加DES的强度，将DES重复3次所得的结果，缩写为3DES

加密过程

解密过程

2.4 AES

什么是AES

AES（advance Encryption Standard)是取代前任标准DES而成为新标准的一种对称密码算法。经过一系列的对比的筛选，选择Rijindael为这个标准。

2.5 Rijindael

这个是由比利时的密码学家设计的分组密码算法，于2000年备选为新一代的标准密码算法。

Rijindael的分组长度为128比特，秘钥长度可以为32比特为单位在128~256比特范围内选择，不过在AES的规格中，秘钥长度只有128，192，256比特三种。

Rijindael的加密和解密

Rijindael没有使用Feistel网路，而是使用SPN结构。

SubBytes：可以理解为之前的简单的替换密码算法

ShiftRows：将SubBytes结构混合成MixColumns列。

AddRoundKy: MixColumns结果与轮秘钥进行XOR

上图只是一轮的结构，这样的运算还要进行10~14轮。

2.6 RC4 流加密算法

RC4 -- Rivest Cipher4

基本原理

RC4属于对称密码算法中的流密码加密算法

密钥长度可变，面向字节操作

加密过程

初始化S表

1. 对S表进行线性填充，一般为256个字节
1. 用种子密钥填充另一个256字节的k表
1. 用K表对S表进行置换

密钥流的生成（为每个待加密的字节生成一个伪随机数，用来异或）

1、先初始化状态向量S（256个字节，用来作为密钥流生成的种子1）
	按照升序，给每个字节赋值0,1,2,3,4,5,6.....,254,255
2、初始密钥（由用户输入），长度任意如果输入长度小于256个字节，则进行轮转，直到填满
	例如输入密钥的是1,2,3,4,5   ,  那么填入的是1,2,3,4,5,1,2,3,4,5,1,2,3,4,5........
	由上述轮转过程得到256个字节的向量K（用来作为密钥流生成的种子2）
3、开始对状态向量S进行置换操作（用来打乱初始种子1）
	按照下列规则进行
	从第零个字节开始，执行256次，保证每个字节都得到处理
     j = 0;
      for (i = 0 ; i < 256 ; i++){
        j = (j + S[i] + K[i]) mod 256;
        swap(S[i] , S[j]);
      }

	这样处理后的状态向量S几乎是带有一定的随机性了
	
4、最后是秘钥流的生成与加密，很多人在这里不是特别理解，别的博客也没有写的很简洁明了
    假设我的明文字节数是datalength=1024个字节（当然可以是任意个字节）
    i=0;
    j=0;
    while(datalength--){//相当于执行1024次，这样生成的秘钥流也是1024个字节
        i = (i + 1) mod 256;
        j = (j + S[i]) mod 256;
        swap(S[i] , S[j]);
        t = (S[i] + S[j]) mod 256;
        k = S[t];这里的K就是当前生成的一个秘钥流中的一位
        //可以直接在这里进行加密，当然也可以将密钥流保存在数组中，最后进行异或就ok
        data[]=data[]^k； //进行加密，"^"是异或运算符
    }
    解密按照前面写的，异或两次就是原文，所以只要把密钥流重新拿过来异或一次就能得到原文了

3 分组密码的模式

3.1 分组密码的模式

分组密码与流密码

分组密码：每次只能处理特定长度的一块数据的一类密码算法，例如DES的64比特，AES的128比特，192，256比特等。

流密码：是对数据流进行连续处理的一类密码算法。流密码中一般以1，8，32比特进行加密与解密。

什么是模式

分组密码只能加密固定长度的分组，但是我们需要加密的明文长度可能会超过分组密码的分组长度，这时就需要对分组密码算法进行迭代，以便将一段很长的明文全部加密而迭代的方法称为分组密码的模式。

模式有很多种类，分组密码的主要模式5种：ECB（Electronic CodeBook mode),CBC(Cipher Block Chaining mode),CFB(Cipher FeedBack mode),OFB(Ouput FeedBack mode),CTR(CounTeR mode)

3.2 ECB模式

在ECB模式中，将明文分组加密之后的结果将直接称为密文分组

使用ECB模式加密时，相同的明文分组会被转换成相同的密文分组，也就是说，我们可以将其理解为一个巨大的“明文分组->密文分组”的对应表

当最后一个明文分组的内容小于分组长度时，需要用一些特定的数据进行填充

ECB模式的特点

ECB模式是所有模式中最简单的一种。如果明文中存在多个相同的明文分组，则这些明文分组最终都将转换为相同的密文分组。这样一来，只要观察一下密文，就可以知道明文中存在怎样的重复组合，并可以以此线索来破译密码。

对ECB模式的攻击

加入攻击者M，他能够修改密文的分组的顺序。当接收者对密文进行解密时，由于密文分组的顺序改变了，因此响应的明文分组的顺序也会改变，也就是说，攻击者M无需破译密码就能够操纵明文。

3.3 CBC模式

全称是cipher block chaing模式，之所以叫这个名字是因为密文分组是像链条一样连接在一起的。

文件: cbc.drawio

初始化向量

当加密第一个明文分组时，由于不存在前一个密文分组，因此需要事先准备一个长度为一个分组的比特序列来代替，这个比特序列称为初始化向量。一般来说，每次加密时都会随机产生一个不同的比特序列作为初始化向量

CBC特点

因为明文分组需要与前一个密文分组进行XOR运算，即使明文分组1，2是相等的，密文分组1，2也是不相同的，这样一来，ECB模式的缺陷在CBC模式中就不存在了。

CBC模式的攻击

假设主动攻击者M的目的是通过修改密文来操纵解密后的明文。如果能够对初始化向量中的任一比特进行反转，则明文分组中相应的比特也会被反转。

CBC的应用实例

确保互联网安全的通信协议之一IPsec，就是使用CBC模式来确保通信的机密性，如使用CBC模式三重DES的3DES-CBC，以及CBC模式AES的AES-CBC等

此外，CBC模式还被用于一种叫作kerberos version 5的认证系统中。

3.4 CFB模式

全称是Cipher FeedBack模式，密文反馈。在CFB中，前一个密文分组被送回到密码算法的输入端，所谓的反馈，这里指的就是返回输入端的意思。

在ECB模式和CBC模式中，明文分组都是通过密码算法进行加密的，然而在CFB模式中，明文分组并没有通过密码算法来直接进行加密。

我们可以将CBC模式和CFB模式对比一下。

CFB解密

CFB模式解密时，需要注意的是分组密码算法依然是通过执行加密操作，因为秘钥流式通过加密操作得到的。

CFB模式的攻击

对CFB模式可以实施重放攻击。

对2，3，4进行替换，只有第2个会出错，但是是传输错误还是被修改就不得而知了。

3.5 OFB模式

全称是output feedback模式，输出反馈模式。密码算法的输出会反馈到密码算法的输入中。

CFB模式和OFB模式的对比

在OFB模式中，XOR所需的比特序列可以事先通过密码算法生成，和明文无关。只要提前准备好所需的秘钥流，则在实际从明文生成密文的过程中，就完全不需要动用密码算法了，只要将明文与秘钥流进行XOR就可以了。

3.6 CTR模式

CTR模式是一种通过逐次累加的计数器进行加密生成秘钥流的流密码。

计数器的生成方法

每次加密都会生成不同的值来作为计数器的初始值，当分组长度为128比特时，计数器的初始值可能像下面这样的形式：

其中前8个位nonce，这个值在每次加密时必须是不同的，后8个字节为分组序号，这个部分时累加的。

按照上述生成方法，可以保证计数器的值每次是不同的。由于计数器的值每次是不同，因此每个分组将计数器进行加密所得到的的秘钥流也是不同的。

OFB模式与CTR模式的对比

CTR模式与OFB模式一样，都属于流密码。如果我们将单分组加密拿出来，那么OFB模式和CTR模式之间的差异很容易理解的。

在OFB模式中，如果对秘钥流的一个分组进行加密后其结果碰巧和加密前是相同的，那么这一分组之后的秘钥流将会变成同一值的不断重复，在CTR模式中不存在这一问题。

3.7 应该使用哪种模式

4 公钥密码

4.1 秘钥的配送问题

解决秘钥配送问题的方法有一下几种：

通过事先共享秘钥来解决
通过秘钥分配中心来解决
通过Diffie-Hellman秘钥交换来解决
通过公钥密码来解决

通过事先共享秘钥来解决

如果有成千上万需要的话，这样秘钥分配就会很繁琐且不易管理。

通过秘钥分配中心来解决

通过秘钥分配中心钥配送问题，避免由于参与通信人员多导致需要秘钥数量变得巨大。

当需要进行加密通信时，秘钥分配中心会生成一个通信秘钥，每个人只要和秘钥中心事先共享秘钥就可以了。

模拟A和B通信的过程：

A向秘钥中心发送希望和B进行通信的请求。
秘钥分配中心通过随机生成器生成y一个会话秘钥秘钥是供A与B在本次通信中使用的临时秘钥
秘钥中心去除A和B的秘钥
秘钥分配中心用A的秘钥会会话秘钥进行加密，发送给A
秘钥分配中心用B秘钥会会话秘钥进行加密，发送给B
A和B用各自的秘钥进行解密，得到会话秘钥。
之后通信使用会话秘钥进行加密

但是秘钥分配中心会成为攻击重点。

通过Diffie-Hellman秘钥交换来解决秘钥配送问题

在这个算法中，只要通信双方交换一些信息，而这些信息被第三方听到页没有关系。

下面是来自wiki的图

这个p应该是取很大的质数。

通过公钥密码来解决秘钥配送问题

在对称密码中，加密秘钥和解密秘钥是相同的，但公钥密码中，加密密码和解密密码确实不同的。只要拥有加密秘钥，任何人都可以进行加密，但没有解密秘钥是无法解密的。

什么是公钥密码：可以公开的，用于发送者加密使用。

公钥通信的流程

A使用公钥加密明文得到密文，发送给B
B使用私钥解密密文得到明文

公钥密码无法解决的无问题

需要判断所得到的公钥是否正确合法，这个问题被称为公钥的认证问题。公钥密码还有一个问题就是，它的处理速度只有对称密码的几百分之几。

4.2 RSA

RSA是一种公钥密码算法，他的名字是由它的三位开发者，Ron Rivest,Adi Shamir,Lernard Adleman.

RSA加密

可以使用一个公式来概括

密文 = 明文 ^ E mod N （RSA加密） 
说明：明文的E次方求mod N的结果

可以E和N的组合，就是公钥。

RSA解密

明文 = 密文 ^ D mod N （RSA加密） 
说明：密文的D次方求mod N的结果

可以说D和N的组合是私钥。

生成密钥对

步骤：

求N
求L（L仅在生成秘钥对的过程中使用的数）
求E,和N组成公钥
求D,和N组成私钥

求N

首先准备很大的质数两个，p和q

p和q很小的话很容易破解，但太大的话计算时间又会变得很长。例如，假设p和q的大小都是512比特，相当于155位的十进制数字。

N = q x p

求L

L是p-1和q-1的最小公倍数，用lcm(q-1,p-1)表示

求E

E是一个比1大的数，比L小。此外，E和L的最大公约数（gcd）必须为1，随机找出一个数，看看这个数是否符合条件。

1<E<L
gcd(E,L) == 1

求D

1 < D < L 
E x D mod L = 1

只要数D满足上述条件，则通过E和N进行加密的密文，就可以通过D和N进行解密。

5 混合密码系统

5.1 混合密码系统

对称密码与公钥密码

公钥密码还有两个很大的问题

公钥密码的处理速度远远低于对称密码
公钥密码难以抵御中间人攻击

混合密码系统

混合密码系统是将对称密码和公钥密码的优势结合的方法。

混合密码系统中会先用快速的对称密码来对消息进行加密，然后我们只要保证对称密码的密钥的机密性就可以了。这里就轮到公钥密码了，可以用公钥密码对加密消息使用对称密码的密钥进行加密。由于对称密码的密钥一般比消息短，因此公钥密码速度慢的问题就可以忽略了。

加密

下面是密码系统的加密过程

解密

理解了加密之后，解密也就不难理解了。混合密码系统的解密过程如下。

混合密码系统的具体例子

著名的密码软件PGP，以及网络上的密码通信所使用的SSL/TLS都运用了混合密码系统。

5.2 怎样才是高强度的混合密码系统

伪随机数生成器

混合密码系统中，伪随机数生成器被用于生产会话秘钥。如果伪随机数生成器很差的话，容易被攻击者推测出来。

对称密码

混合密码系统中，对称密码被用于加密信息。需要选择一定长度的秘钥，还需要使用合适的分组密码模式。

公钥密码

使用高强度的公钥密码算法并确保秘钥具有足够的长度。

6 单向散列函数

什么是单向散列函数

单向散列函数有一个输入和一个输出，其中输入称为消息，输出称为散列值。单向散列函数可以根据消息的内容计算出散列值，而散列值就可以被用于检查消息的完整性。

这里的消息比一定是文字，可以是图像或声音文件。散列值的长度和消息的长度无关。

6单向散列函数的性质

根据任意长度的消息计算出固定长度的散列值
能够快速计算出散列值
消息不同散列值也不同
具备单向性

6.1 单向散列函数的实际应用

检测软件是否被篡改
基于口令的加密：将口令和salt混合后计算其散列值，然后将这个散列值作为加密的秘钥。
消息认证码
数字签名
伪随机生成器
一次性口令

6.2 单向散列函数的具体例子

MD4，MD5

MD4是Rivest与1990年设计的单向散列函数，能够产生128比特的散列值。

MD5是用Rivest于1991年设计的单向散列函数，能够产生128比特的散列值。

SHA-1,SHA-256,SHA-384,SHA-512

RIPEMD-160

能够产生160位比特的散列的单向函数。

AHS与SHA-3

7 单向散列函数SHA-1

整体流程

填充：对消息进行填充，使其长度为512比特的整数倍。
计算w0,~w79:根据输入分组的512比特计算出80个32比特的值
分组处理：对输入分组一次进行80个步骤的处理，计算5个32比特的值作为SHA-1的内部状态。对所有的分组都要进行这一操作。
单步处理：分组处理由80个步骤的处理组成，其中每个步骤都是基于w0-w79使内部状态进行复杂变化处理。

7.1 单向散列函数无法解决的问题

使用单向散列函数可以实现完整性的检查，但有些情况下即使能够检查完整性也是没有意义的。

加入A伪装为B向C发送消息和散列值，但是C能够验证消息的完整性无法验证就是B发送的。这时就需要数字签名。

8 消息认证码-消息被正确传送了吗

什么是消息认证

一种确认完整性并进行认证的技术，取三个单词的首字母MAC(message authentication code)

消息认证码的输入包括任意长度的消息和一个发送者和接收者之间共享秘钥，他可以输出固定长度的数据，这个数据成为MAC值。

这个单向散列函数很类似，但是单向散列函数中计算散列值不需要秘钥，而消息认证码指哪个则需要使用发送者和接收者之间共享秘钥。

消息认证码的使用步骤

8.1 消息认证码的应用实例

SWIFT

全称是society for worldwide interbakc financial telecommunication,环球银行金融电信协会。

IPsec

IPsec是对互联网基本通信协议ip协议增加安全性的一种方式。在IPsec中，对通信内容的认证和完整性校验都是采用消息认证码来完成的。

SSL/TLS

普遍应用在web中，经常可以看到网站使用https协议，其中就是用到了该算法。

8.2 消息认证码的实现方法

使用单向散列函数实现

使用SHA-1，MD5之类的单向散列函数可以实现消息认证码，其中一种实现方法称为HMAC

使用分组密码实现

使用DES，AES之类的分组密码可以实现消息认证码。

将分组组密码的秘钥作为消息认证的共享秘钥来使用，并使用CBC模式将消息全部加密。由于消息认证码不需要解密，因此将除最后一个分组以外的密文部分全部丢弃，而将最后一个分组作为MAC值。由于CBC模式的最优一个分组会受到整个消息以及密钥的双重影响，因此可以将它作为消息认证码。

8.3 HMAC的详细介绍

HMAC是一种使用单向散列函数来构造消息认证码的方法。

HMAC步骤

8.4 对消息认证码的攻击

重放攻击

狡猾的主动攻击者M想到可以通过将事先保存的正确的MAC值不断重放来发送攻击，如果这种攻击成功的话，就可以让100w滚雪球变成1亿元。

有几种方法可以防御重放攻击

序号：约定在每次对发送的消息赋予一个递增的编号，并且在计算MAC值时将序号也包含在消息中。这种方法虽然有效，但是对每个通信对象都需要记录最后一个消息序号。
时间撮：约定在发送消息时包含当前的时间。这种方法虽然有效，但是发送者和接受者的时间必须一致，而且考虑到通信的延迟，必须在时间的判断上留下缓冲，于是多多少少还是会存在可以进行重放攻击的空间。
nonce：在通信之前，接收者向发送者发送一个一次性的随机数，这个随机数一般称为nonce。发送者在消息中包含这个nonce并计算MAC值。会增加通信的数据量。

8.5 消息认证码无法解决的问题

消息认证码也不能解决所有问题，例如“对第三方证明”和“防止否认”。

对第三方证明

假设A和B通信，C要验证这条消息时A发送的，C不知道共享秘钥。且知道了也无法任务这是A发送的，因为C认为MAC是正确的，发送这条消息的人也不一定是A，可能是B。

防止否认

B收到A发送的包含MAC值的信息，这个MAC是正确的，因此B可以判断这是A发送，但是无法向第三发C说这是A发送的，A可以说这不是我发送的。

8.6 数字签名-消息到底是谁写的

数字签名就是通过公钥密码反过来用实现的。

8.7数字签名的方法

直接对消息签名的方法
对消息的散列值签名的方法

算法过程

DSA算法中应用了下述参数：

p：L bits长的素数。L是64的倍数，范围是512到1024；

q：p – 1的160bits的素因子；

g：g = h^((p-1)/q) mod p，h满足h < p – 1, h^((p-1)/q) mod p > 1；

x：x < q，x为私钥；

y：y = g^x mod p ，( p, q, g, y )为公钥；

H( x )：One-Way Hash函数。DSS中选用SHA( Secure Hash Algorithm )。

p, q, g可由一组用户共享，但在实际应用中，使用公共模数可能会带来一定的威胁。

签名及验证协议：

1.P产生随机数k，k < q；
2.P计算 r = ( g^k mod p ) mod q s = ( k^(-1) (H(m) xr)) mod q 签名结果是( m, r, s )。
3.验证时计算 w = s^(-1)mod q u1 = ( H( m ) w ) mod q u2 = ( r w ) mod q v = (( g^u1 * y^u2 ) mod p ) mod q 若v = r，则认为签名有效。

直接对消息签名的方法

步骤

Aliceo用自己的私钥对消息进行加密
Alice将消息发送给Bob
Bob用Alice的公钥对收到的签名进行解密
Bob将签名解密后得到的消息与Alice直接发送的消息进行对比

对消息的散列值签名的方法

Aliceo用自己的私钥对消息散列进行加密
Alice将消息发送给Bob
Bob用Alice的公钥对收到的签名进行解密
Bob将签名解密后得到的散列值与Alice直接发送的消息的散列值进行对比

8.8 数字签名的应用实例

安全信息公告
软件下载
公钥证书
SSL/TLS

8.9 各种密码技术的对比

添加图片注释，不超过 140 字（可选）

证书-为公钥加上数字签名

证书的应用场景

添加图片注释，不超过 140 字（可选）

Bob生成密钥对
Bob在认证机构Trent注册自己的公钥
认证机构用自己的私钥对Bob的公钥施加数字签名并生成证书
Alice得到带有认证机构的数字签名的Bob的公钥
Alice使用认证机构的公钥验证数字签名，确认Bob的公钥的合法性
Alice用Bob的公钥加密消息并发送给Bob
Bob用自己的私钥解密密文叨叨Alice的消息

8.10 公钥基础设施

公钥基础设施是为了能够更有效的运用公钥而制定的一系列规范的总称。

8.11 对证书的攻击

在秘钥注册之前进行攻击

在提交公钥之前，攻击者把公钥换成攻击者自己的。要防止这种攻击，可以下面的做法。例如B可以在将公钥发送给认证机构进行注册时，使用认证机构的公钥对B的公钥进行加密。此外，认证机构在确认B的身份时，也可以将公钥的指纹一并发送给B进行确认。

注册相似人名进行攻击

证书是认证机构对公钥及其持有者的信息加上数字签名的产物，对于一些相似的身份信息，计算机可以进行区别，但是人类往往很容易认错。

Wednesday, April 16, 2025