[数据结构与算法]基础加解密知识及算法介绍

1 密码技术概述

1.1 密码算法演进

1.1.1 凯撒密码

凯撒密码是通过将明文中使用的字母表按一定字数平移来加密的，如以下示例中将字母平移3个字母，并将小写字母转换为大写字母，实现了一次简单的加密。解密时只需将密文方向平移即可。

凯撒密码的输入输出如下：

安全性：

使用暴力破解，尝试26次即可破解原文信息

1.1.2 简单替换密码

26个字母之间建立映射关系，如下图为其中某种映射：

安全性：

暴力破解，需要尝试的次数为1 * 2 * 3 * … * 26，约为4 *
10^26。其密码强度较凯撒密码有较大增强，但若按频率分析法可大大加快破译速度。

1.1.3 Enigma密码机

Enigma密码机是二战时德国用于军事通信的密码系统，它通过Enigma密码机和每日密码本来实现加解密操作。

下图是Enigma密码机构造的简单示例，图例用简单的4个字母模拟了实际的26个字母逻辑。其中粗线表示密码机输入输出之间的关系，接线板用于设置密钥。

安全性：

每日通信密码不能泄密

1.2 密码算法的使用原则

1.2.1 不要使用保密的密码算法

历史经验表明，保密的密码算法最终都会被泄密，一旦被泄密后所有采用该算法加密的信息都将被破解

1.2.2 任何密码总是能被破解的

无论采用何种密码算法生成密文，只要将所有可能的密钥都尝试一遍，都能够被破解。因此，在选用加解密算法时，需要做好保密信息价值与破解该信息所需时间之间的权衡。

1.2.3 密码算法的安全性取决于密钥的不可预测性

绝大多数流行的现代密码算法本身都是公开的，其加解密的安全性主要取决于密钥的破译难度。因此，密钥的不可预测性就称为密码算法安全性的关键。一般可通过随机数的方式创建加解密密钥，以防止密钥被破解。

1.3 密码算法分类

信息安全的基本要求为：机密性、完整性、可用性、真实性以及不可抵赖性，所有的加解密算法都是为了实现以上安全要求。按加解密算法的实现方式不同，可分为以下几种：

2 对称加解密算法

2.1 DES算法

des算法是fips（美国联邦信息处理标准）采用的一种对称密码算法（fips46-3），它是一种64bit分块的分组密码算法。其密钥长度为64bit，但由于密钥中每隔7bit会设置1bit的奇偶校验码，因此其实际密钥长度为56bit。

由于分组大小为64bit，因此DES算法需要将明文数据以该size为单位分块，并逐块执行加解密操作。单块加解密操作流程如下图所示：

DES采用下图方式执行明文数据的加密，在该操作中右侧32bit未做任何处理。因此DES需要重复执行16轮相同的操作，且在每次操作时都交换左右数据，每轮的子密钥也都经过密钥置换算法重排。

DES加解密的这种结构叫做feistel网络，其特点如下：

（1）轮函数f可以是任意的

（2）加解密的轮数也是任意的，只要加密轮数等于解密轮数即可

（3）加密和解密可以采用完全相同的结构来实现

由于DES算法的密钥长度只有56bit，随着计算机速度的提升，大型计算机可在很短的时间内暴力破解DES密钥。因此其已是不安全的算法，应避免在新的项目中使用。以下是DES和AES破解时间的对比图：

为了增强DES的强度，NIST采用了3DES作为DES向AES的过渡算法。3DES采用两次加密，一次解密的方式对同一个数据块执行三次加解密操作。在加解密操作中，密钥可通过两个或三个DES密钥组合而成，若密钥长度为112bit，则两次加密的密钥相同。若密钥为168bit，则三次加解密的密钥都不同。以下为3DES算法的加密流程：

3DES算法的缺点为算法速度慢，密钥计算时间长，加密效率不高，实际使用中该算法也应尽量避免使用。

2.2 AES算法

AES是NIST选定用于替代DES的新一代对称加密算法，并将其作为美国的国家标准（fips197），实际上AES已经成了事实上的国际标准。

AES的分组长度固定为128bit，密钥长度可为128/192/256bit。其也采用了轮加密方式，不同密钥长度的加密轮数如下：

其采用了SPN结构，该种结构包含四种变换，字节替代/行移位/列混淆/轮密钥加。下图为AES一轮计算的流程示意图：

16字节的分组先被分成4 *
4字节的方阵，并被复制到state数组中，该数组在下列的每种加解密变换中都会被修改，其示意图如下：

（1）字节替代

以16字节明文中每个字节的值为索引，从一个拥有256个值的替换表（S-box）中查找对用的值，并用查找到的值替换初始值，其中明文对应字节的高四位作为行索引值，低四位作为列索引值。aes算法中S-box表定义如下：

（2）行移位

将state数组的第一行保持不变，第二行左移一个字节，第三行左移两个字节，第四行左移三个字节。示意图如下：

（3）列混淆

使用下图示意的矩阵乘法计算列混淆结果：

其中矩阵的系数基于码字间最大举例的线性编码，以使得每列的所有字节具有良好的混淆性。

（4）轮密钥加

将以上结果与次轮密钥进行异或计算。

SPN网络所有输入比特都会在一轮中被加密，与每轮只加密一半数据的Feistel网络相比，相同加密轮数的安全性更高。而且，这种方式还可以分别按字节、行和列为单位进行并行计算。

2.3 分组密码的模式

当加密的明文长度超过分组长度，需要对分组密码算法进行迭代时，这种迭代方式被称为分组密码模式。常用的分组密码模式为：ECB、CBC、CFB、OFB和CTR。

2.3.1 ECB模式

ecb模式每个明文分组都独立地执行加解密操作，相同的明文分组，密文分组也相同。其流程示意图如下：

由于ecb模式相同的明文分组，都会被转换为相同的密文分组。因此，若知道明文中存在何种重复组合，就可以以此为线索来破译密码。中间人攻击中也可以只通过改变密文的顺序，而使明文的语义发生变化，从而达到攻击目的。因此该种模式存在一定的风险，实际应用中应尽量避免使用。

2.3.2 CBC模式

CBC全称为cipher block
chaining，即密文分组是像链条一样相互连接在一起的。该模式下，首先将明文分组与前一个密文分组进行异或运算，然后再进行加密。其加密流程如下：

与ECB模式不同，CBC模式需要一个初始向量IV，用于与第一个明文分组做异或运算。此后，前一个分组的密文将作为下一个分组的IV。因此，即使有两个分组的明文相同，其密文也不同。

2.3.4 CFB模式

CFB全称为cipher
feedback，即前一个密文的分组会被送到密码算法的输入端。该模式下，首先对前一个分组的密文加密，然后与下一个分组的明文异或。其加密流程如下：

由上图可知，明文分组到密文分组之间只有一个异或操作，而并没有直接对明文分组执行加密操作。CFB模式可被攻击者用于重放攻击，如以下示例中若攻击者用老的分组替换了后三个分组，则最终解密后的第三和第四个分组数据将会被替换。

2.3.5 OFB模式

OFB全称为output-feedback，它不通过密码算法对明文直接加密，而是通过将明文分组与密码算法的输出进行异或来产生密文分组。其加密流程如下：

OFB模式的优点为密钥流生成和异或计算可以并行执行。若提前准备好了密钥流，则对明文分组的异或运算会非常快。因此，OFB模式的加密速度较快。OFB使用时必须确保每次使用不同的IV值，否则也可能被重放攻击。

2.3.6 CTR模式

CTR模式全称为counter模式，它是一种通过逐次累加计数器进行加密来生成密钥流的流密码。其加密流程如下：

CTR每次加密时都会生成一个不同的nonce作为计数器的初值，当分组长度为16字节时，计数器的初始值可能为如下形式：

其中前8个字节为nonce，它在每次加密时必须是不同的，后8个字节为分组序号，它会在加密过程中逐次累加。

CTR模式加密和解密使用完全相同的结构，在程序和硬件上便于实现。且CTR模式可以以任意顺序对分组执行加解密，因此其可以充分利用并行计算，速度也会更快。

2.3.7 分组密码算法模式比较

3 非对称密码算法

3.1 非对称算法原理

非对称算法的密钥对包含公钥和私钥，其中私钥由密钥属主保管，且不能泄露，公钥可以通过明文的方式分发给其它人。通过私钥加密的数据只能由公钥解密，通过公钥加密的数据只能由私钥解密，由于加密和解密使用不同的密钥，因此称为非对称加密。以下是一个非对称加密算法应用示例：

非对称算法的保密性好，密钥交换方便，但其加解密速度远远慢于对称加密，因此不适合用于大数据的加解密操作。算法的典型应用包括：

（1）信息加密：使用接收方的公钥加密信息，则只有对应私钥的持有者才能解密消息

（2）密钥交换：对称算法密钥本身数据量小，但通信双方密钥交换不方便，此时可通过非对称算法交

换双方密钥。

（3）数字签名：通过私钥对数据的hash值做数字签名，从而可以验证数据的完整性和不可抵赖性

（4）数字证书：数字证书用于验证公钥的合法性

3.2 RSA算法

3.2.1 RSA算法原理

1 欧拉函数

欧拉函数是指给定任意正整数n，在小于等于n的正整数之中，有多少个数与n构成互质关系。根据中国剩余定理可证明如下关系：

φ(n) = φ(p1p2) = φ(p1)φ(p2)

即当p1和p2是互质的整数，且p1 *
p2等于n时，n的欧拉函数计算可分解为分别对p1和p2求欧拉函数。由于任何正整数都可分解为一系列互质的整数乘积，因此欧拉函数的计算可分解如下：

2 欧拉定理

欧拉定理指的是若存在两个互质的正整数a和n，则n的欧拉函数φ(n)可表示如下：

即a的φ(n)被n除的余数为1。由于质数p的欧拉函数φ§
为p-1，则进一步推导可得在正整数a与质数p之间有如下关系：

3 模反元素

若存在两个正整数a和n互质，则一定可以找到正整数b，使其满足以下关系：

3.2.2 RSA密钥创建

1 选择两个不相等的质数p和q

2 计算p和q的乘积n

3 计算n的欧拉函数为：

φ(n) = φ(pq) = φ§φ(q) = （p-1）*（q-1）

4 选择一个随机的正整数e，使其满足条件1 < e < φ(n)，且e与 φ(n)互质

实际应用中该值常选择为65537

5 计算e对φ(n)的模反元素d，即

ed ≡ 1 (mod φ(n))

6 以上算法中n和e被封装为公钥，n和d被封装为私钥

7 RSA私钥的安全性分析：

由以上可知，ed≡1 (mod φ(n))。

要计算私钥e，必须要知道φ(n)，而φ(n) =
（p-1）（q-1），因此只有知道p和q才能计算出φ(n)。

而n=pq，因此只有将n因数分解后才能计算出p和q。

由于大数的因数分解是非常困难的，因此rsa算法安全性的核心取决于大数因数分解的难度

8 RSA密钥创建流程示意图（其中L=(p-1)(q-1))

3.2.3 RSA加解密操作

1 RSA加密公式如下

m^e = c（mod n）

其中m为明文信息，e为公钥，n为模数，c为密文。其中明文的值m必须要小于n，因此在rsa-nopad

模式下，明文的长度不能等于模数n的长度，否则会导致概率性地加解密错误。

2 RSA解密公式如下

c^d = m (mod n)

其中c为密文，d为私钥，n为模式，m为明文

3.2.4 RSA的填充

由上面论述可知，RSA也是一种块加密算法，其加解密的块长度等于模数N的长度，因此理论上RSA单次能加密的最大数据长度等于N的长度。但实际上由于RSA加密特定的明文会生成确定的密文（下面的ECC算法则会生成不同的密文），因此若不执行填充操作或填充技术比较弱，则较小的明文和小型公开指数e将易于受到攻击。因此，RSA加解密一般都需要使用特定的填充技术。

1 NO PADDING模式

当明文数据小于块长度时，在明文前面填充若干0数据，以使填充后的数据长度等于块长度。解密后，则将解密数据前的0去掉。

实际应用中会带来如下问题，若明文数据以0开头，则在解密后开头的0数据也被作为填充内容而去掉，从而导致解密后的数据与明文不一致。

2 PKCS1.5填充

填充数据至少为11字节，因此加密的明文数据最多为N的长度减去11。其填充方式为：

EM= 0x00 || BT || PS || 0x00 || T

其中：

（1）首字节填充0x0，其长度为一个字节

（2）BT为一个字节，它有三个取值：0x0和0x1表示私钥加密，0x2表示公钥加密

（3）PS表示填充字段。对于BT为0x2时，其为随机生成且不含0的数。对于BT为0x0时，其直接

填充0。对于BT为0x1，其会填充0xff。其长度为len（N）- 3 -
len（T），且其最小长度为8

字节。其中len（N）为块长度，len（T）为消息长度

3 OAEP填充

OAEP模式填充长度至少为41字节，因此加密的明文数据最多为N的长度减去41。oaep填充模式的流程如下：

（1）M为明文信息，lHash为标签L的hash值，若L未指定则计算空字符串的hash。

PS长度为outlen -1 -hLen - len（M），其填充值为0x0。因此，DB填充后的数据为：

hash||PS||0x01||M

（2）seed为随机数

（3）以seed为参数调用掩码生成函数MGF生成DB掩码，并用该掩码与DB做异或得到maskedDB

（4）以maskedDB为参数调用MGF函数生成新的掩码，并与seed做异或得到maskedseed

（5）将其第一字节设置为0x0，从而得到填充后的消息：0x00 || maskedseed ||
maskedDB

（6）对填充好的明文执行RSA加密操作，生成密文

4 PSS填充

PSS填充的流程可表示为下图，具体流程不再分析

3.3 ECC算法

3.3.1 ECC算法原理

1 椭圆曲线的定义

椭圆曲线是满足y^2 = x^3 + ax + b，且4a^3 +
27^2不等于0的曲线，其中后一个条件主要用于满足曲线不包含奇点。椭圆曲线用于加解密操作，必须要定义一套曲线上的点运算操作，它应用了阿贝尔群的方式实现。

（1）点加P+Q=R计算

（2）点乘3P可分解为P + P + P方式计算

（3）椭圆曲线中某一点的阶

如果椭圆曲线上一点P，存在最小的正整数n使得nP为无穷大，则称n为P的阶。以下是一个典型的例子，由于27P与P的横坐标都为3，因此按上述的加法计算其结果为无穷大

3.3.2 ECC密钥创建流程

1 选择一条椭圆曲线E，并在曲线上选择一点G作为生成元，n为G的阶，且n必须为素数

2 选择一个私钥k（k < n），并生成公钥Q=kG

3 其中k为私钥，E、Q、G为公钥组

3.3.3 ECC加解密

1 加密流程

（1）选择一个随机数r（r<n），并使用以下公式计算密文：

C = {rG，M+rQ}

其中明文为M，r为随机数，G为生成元，Q为公钥，C为密文（点对）。由于在加密时引入了随机

数r，因此相同密钥，相同明文的数据经ECC加密后的密文也不同。

2 解密流程

(M + rQ) - krG = (M + rkG) -krG = M

3.3.4 ECC的优点及应用

1
相对于RSA，ECC算法的密钥长度更短，相同密码强度的加解密性能也更高。以下是相同加解密长

度下不同算法的密钥长度对比：

以下为某次测试RSA和ECC算法的性能对比

2
由于突出的安全性以及性能优势，ECC已经在越来越多的场合被应用。如数字签名、数字证书、TLS、区块链（比特币、以太坊）等

4 消息摘要与消息认证码

消息摘要可通过单向散列函数生成，其hash值可用于检查消息的完整性。被选用于消息摘要的hash函数需要具有以下特征：

（1）任意长度的输入消息都会输出固定长度的hash值

（2）hash函数必须具备单向性，无法通过hash值反向算出消息原文

（3）不同的输入消息，其输出消息也不同，即其应具有强抗碰撞性

（4）hash值的计算速度要快

常用的hash算法有MD5，SHA1、SHA256、SHA384、SHA512、SHA3等。由于MD5和SHA1的强抗碰撞性已经被攻破，因此其已经不再是安全的算法，我们在应用中应避免使用。SHA2和SHA3尚未被攻破，当前可放心使用。

4.1 MD5算法原理

4.1.1 MD5介绍

MD5算法对输入信息处理后可以产生一个128位的hash值。它也是一种分组算法，其分组大小为512位，在运算过程中又将分组分为16个32位子分组，并在处理完成后生成128位的结果。

4.1.2 数据填充

由于需要使用64位空间存储填充前的数据长度，因此需要将明文信息填充为N * 512 +
448位长度，以使总的分组长度为512位对齐，即N * 512 + 448 + 64 = （N+1）*
512。填充的内容为1个1和k个0。

4.1.3 循环计算

MD5每个子分组都需要经过四轮计算，每轮计算的流程如下：

其中初始输入的链接变量ABCD为标准定义的32位魔数，其值分别为0x67452301、0xefcdab89、0x98badcfe及0x10325476。Mi为32位的子分组数据，s为该次计算的移位位数，变换函数F在每轮计算中不同，可分别定义为F、G、H、I。

1 四个变换函数定义

F(X,Y,Z)=(X&Y)|((~X)&Z)

G(X,Y,Z)=(X&Z)|(Y&(~Z))

H(X,Y,Z)=X^Y * Z

I(X,Y,Z)=Y^(X|(~Z))

2 每个子分组的计算流程

FF(a,b,c,d,Mj,s,Ki) 表示a=b+((a+F(b,c,d)+Mj+Ki)<<<s)

GG(a,b,c,d,Mj,s,Ki) 表示a=b+((a+G(b,c,d)+Mj+Ki)<<<s)

HH(a,b,c,d,Mj,s,Ki) 表示a=b+((a+H(b,c,d)+Mj+Ki)<<<s)

II(a,b,c,d,Mj,s,Ki) 表示a=b+((a+I(b,c,d)+Mj+Ki)<<<s)

其中Ki的值是标准规定的，每个子分组的操作中其值都不同，具体可参考下述四轮计算流程

3 四轮计算

（1）第一轮计算

a=FF(a,b,c,d,M0,7,0xd76aa478)

b=FF(d,a,b,c,M1,12,0xe8c7b756)

c=FF(c,d,a,b,M2,17,0x242070db)

d=FF(b,c,d,a,M3,22,0xc1bdceee)

a=FF(a,b,c,d,M4,7,0xf57c0faf)

b=FF(d,a,b,c,M5,12,0x4787c62a)

c=FF(c,d,a,b,M6,17,0xa8304613)

d=FF(b,c,d,a,M7,22,0xfd469501)

a=FF(a,b,c,d,M8,7,0x698098d8)

b=FF(d,a,b,c,M9,12,0x8b44f7af)

c=FF(c,d,a,b,M10,17,0xffff5bb1)

d=FF(b,c,d,a,M11,22,0x895cd7be)

a=FF(a,b,c,d,M12,7,0x6b901122)

b=FF(d,a,b,c,M13,12,0xfd987193)

c=FF(c,d,a,b,M14,17,0xa679438e)

d=FF(b,c,d,a,M15,22,0x49b40821)

（2）第二轮计算

a=GG(a,b,c,d,M1,5,0xf61e2562)

b=GG(d,a,b,c,M6,9,0xc040b340)

c=GG(c,d,a,b,M11,14,0x265e5a51)

d=GG(b,c,d,a,M0,20,0xe9b6c7aa)

a=GG(a,b,c,d,M5,5,0xd62f105d)

b=GG(d,a,b,c,M10,9,0x02441453)

c=GG(c,d,a,b,M15,14,0xd8a1e681)

d=GG(b,c,d,a,M4,20,0xe7d3fbc8)

a=GG(a,b,c,d,M9,5,0x21e1cde6)

b=GG(d,a,b,c,M14,9,0xc33707d6)

c=GG(c,d,a,b,M3,14,0xf4d50d87)

d=GG(b,c,d,a,M8,20,0x455a14ed)

a=GG(a,b,c,d,M13,5,0xa9e3e905)

b=GG(d,a,b,c,M2,9,0xfcefa3f8)

c=GG(c,d,a,b,M7,14,0x676f02d9)

d=GG(b,c,d,a,M12,20,0x8d2a4c8a)

（3）第三轮计算

a=HH(a,b,c,d,M5,4,0xfffa3942)

b=HH(d,a,b,c,M8,11,0x8771f681)

c=HH(c,d,a,b,M11,16,0x6d9d6122)

d=HH(b,c,d,a,M14,23,0xfde5380c)

a=HH(a,b,c,d,M1,4,0xa4beea44)

b=HH(d,a,b,c,M4,11,0x4bdecfa9)

c=HH(c,d,a,b,M7,16,0xf6bb4b60)

d=HH(b,c,d,a,M10,23,0xbebfbc70)

a=HH(a,b,c,d,M13,4,0x289b7ec6)

b=HH(d,a,b,c,M0,11,0xeaa127fa)

c=HH(c,d,a,b,M3,16,0xd4ef3085)

d=HH(b,c,d,a,M6,23,0x04881d05)

a=HH(a,b,c,d,M9,4,0xd9d4d039)

b=HH(d,a,b,c,M12,11,0xe6db99e5)

c=HH(c,d,a,b,M15,16,0x1fa27cf8)

d=HH(b,c,d,a,M2,23,0xc4ac5665)

（4）第四轮计算

a=II(a,b,c,d,M0,6,0xf4292244)

b=II(d,a,b,c,M7,10,0x432aff97)

c=II(c,d,a,b,M14,15,0xab9423a7)

d=II(b,c,d,a,M5,21,0xfc93a039)

a=II(a,b,c,d,M12,6,0x655b59c3)

b=II(d,a,b,c,M3,10,0x8f0ccc92)

c=II(c,d,a,b,M10,15,0xffeff47d)

d=II(b,c,d,a,M1,21,0x85845dd1)

a=II(a,b,c,d,M8,6,0x6fa87e4f)

b=II(d,a,b,c,M15,10,0xfe2ce6e0)

c=II(c,d,a,b,M6,15,0xa3014314)

d=II(b,c,d,a,M13,21,0x4e0811a1)

a=II(a,b,c,d,M4,6,0xf7537e82)

b=II(d,a,b,c,M11,10,0xbd3af235)

c=II(c,d,a,b,M2,15,0x2ad7d2bb)

d=II(b,c,d,a,M9,21,0xeb86d391)

4
分组计算完成后，把输出的ABCD与上一轮的初始ABCD相加后，作为下一轮计算的初始ABCD。当

所有分组都计算完成后，最终的128位输出数据即为该消息的MD5值

4.2 SHA1算法原理

4.2.1 sha1算法介绍

sha1算法对输入信息处理后可以产生一个160位的hash值。它也是一种分组算法，其分组大小为512位，因此也需要对输入信息执行填充操作，其填充方式与MD5相同。

4.2.2 算法流程

1 将输入数据分为16个32位子分组，分别记为W0 - W15

2 将16个子分组扩展为80个子分组，扩展公式如下

即以W0 - W15为初始数据，按上述公式依次计算W16 - W79的值

3
接下来对输入分组执行以下80个步骤操作。与MD5算法相同，其初始的ABCDE也是标准定义的。

4
其单步处理流程与MD5类似，也是定义了四个变换函数F、G、H、I，以上的80步也被分为4轮计算，其中每轮20步。每一轮的计算都遵循如下流程，只是变换函数、输入数据以及Wt和Kt不同。

5
计算结果与链接变量的初始值求和作为下一个分组的链接变量。当所有分组都计算完成后，最终输出的160bit结果即为sha1值

4.2.3 其它hash算法

其它hash算法的原理都类似，如sha256算法的输出长度，变换函数形式和数量，以及扩展子分组等与sha1有些区别，但总体思路都是类似的

4.2.4 hash算法的问题

hash算法能够校验数据的完整性，但若原始数据本身和hash值都被攻击者替换了（如中间人攻击中，攻击者截获了信息，对信息篡改后再用篡改后的信息生成新的hash值），则依然无法确保原始消息的真实性。而数字签名和消息认证码则可以解决该问题。

4.3 消息认证码

4.3.1 消息认证码介绍

消息认证码是一种确认数据完整性并认证的技术，它包含任意长度的输入消息和一个发送者与接收者之间共享的密钥。它与单向散列函数的区别如下：

4.3.2 HMAC算法原理

hmac算法流程如下所示：

1 密钥填充

若密钥长度小于hash分组长度，则在末尾用0填充到长度等于分组hash长度。若密钥长度比分组长度长，则计算密钥的hash值，并用该hash值作为HMAC的密钥

2 ipadkey计算

填充后的密钥与ipad做异或，其中ipad为0b00110110的循环，其长度等于分组长度。其结果被称为ipadkey

3 ipadkey与消息组合

ipadkey与消息组合即将ipadkey附加在消息的开头

4 计算hash值

使用对应的hash函数对上述组合的数据计算hash值，其中hash计算方式与上一节消息摘要计算方式相同

5 opadkey计算

填充后的密钥与opad做异或，其中opad为0b01011100的循环，其长度等于分组长度。其结果被称为opadkey

6 将步骤4计算得到的散列值拼接到opadkey后面

7 用hash函数对步骤6输出的消息计算hash值，该值即为最终的HAMC值

4.3.3 CMAC算法原理

cmac是利用cbc模式加密方式计算mac值的方法，加密算法可以使用DES、3DES或AES，当前通常使用的都是aes
cbc模式。按数据是否块对齐，其处理方式有以下两种：

1 生成子密钥K1、K2

（1）使用aes算法对128位全0消息加密，得到加密后的128位消息L

（2）若L的最高位为0，则K1 = L<< 1。否则，K1 = (L << 1)再与Rb异或

（3）若K1的最高位为0，则K2 = K1<< 1。否则，K2 = (K1 << 1)再与Rb异或

其中，Rb为给定的常量字符串，对于aes算法，其值为128位的数据，前面120位都为0，最后8位为0b10000111

2 将数据按分组长度分块，若分块数为n，则对前n-1个分块执行aes-cbc算法

3 若最后一个块是完整块，则将其与K1异或后作为输入数据，并执行aes-cbc算法

4
若最后一个块为非完整块，则用10…0模式填充该块，再与K2异或后作为最后一个块的输入数据，并执行aes-cbc算法

5 将最后一个分组的计算结果作为cmac输出值

5 AEAD算法

5.1 AEAD算法方案

aead算法是一种同时具备保密性、完整性和可认证性的加密方式。为了实现该目的，可选用以下几种不同的方案。

1 EtM（encryption then MAC）

该方案先对数据加密，然后对密文执行MAC运算，并把密文与MAC值拼接后作为aead输出数据。解密时则先验证MAC值，然后再解密密文数据。其流程如下图所示：

2 MtE（MAC then encryption）

该方案先对原始数据执行MAC运算，将MAC值与原始数据拼接后再执行加密算法。解密时先解密数据，再对解密后的数据执行MAC计算。其流程如下图所示：

3 E&M（encryption and MAC）

该方案同时对原始数据执行加密和MAC运算，并把加密数据与MAC拼接后作为输出数据。解密时先解密原文，再对解密后的数据计算MAC值。其流程如下图所示：

4
在一个算法内同时实现加密和认证，相对于上面的组合算法这种方式的安全性更好。当前常用的算法有AES-GCM、AES-CCM和ChaCha20-Poly1305等。在我们的算法选择中，应尽量选用这种类型算法

5.2 AES-GCM算法原理

与ECB，CBC和CTR类似，GCM和CCM其实也是一种加密模式。它全称为Galois/Counter
mode，即是一种集合了GMAC和CTR两种算法的模式。其流程示意图如下：

1 其包含的输入参数为明文数据PT，密钥Ek，初始向量IV以及附加消息AAD

2 加密流程除了加入了iv值以外与CTR模式类似。

3
每个分组计算流程中都加入了MAC计算，其中初始MAC计算的输入数据为AAD。AAD数据在整个算法中只参与MAC计算，而不参与加解密流程。

4 加解密完成后，也同步计算得到来消息验证码

5.3 AES-CCM算法原理

ccm算法的流程如下图所示：

1 该模式由两部分组成，ctr模式用于加密数据，cbc模式用于计算MAC值

2 B0 - Bk为IV（nonce）、AAD以及PT以标准规定的格式组合而成

3 B0的第一个字节计算规则如下

4 B00 - B0[ivlen
-1]保存iv值，其中ccm的iv值为12字节。B0中剩余的字节填写输入数据长度

5
B1及之后的分组将填入AAD数据和PT数据，其中block1的头两个字节用于填充aad的长度，其填充规则如下：

block1[0] = ( add_len >> 8 ) & 0xFF

block1[1] = ( add_len ) & 0xFF

6 数字签名与数字证书

6.1 数字签名

数字签名是使用hash算法与公钥加密技术实现，用于鉴别数字信息真实性和不可抵赖性的方法。它有以下几个特征：

（1）报文鉴别：接收者能校验发送者对报文的签名

（2）报文完整性：接收者不能伪造报文签名或更改报文内容

（3）不可抵赖：发送者事后不能抵赖对报文的签名

数字签名流程如下：

接下来分析该流程是否符合以上三个特征

（1）报文鉴别：数字签名中的私钥具有唯一性，除签名者之外都不能伪造签名，并防止被假冒

（2）报文完整性：由于数字签名中包含hash算法，对签名文档的任何未经授权的修改将立即被显见

（3）不可抵赖性：由于报文经过了发送者的私钥签名，他人无法获取其私钥，故无法伪造其签名，因此发送者也无法抵赖

6.2 数字证书

数字签名流程中接收者需要用公钥验签发送者的签名，若中间人用自己的公钥替换了发送者的公钥，则他就可以用自己的私钥签名信息，而接受者使用被攻击者替换的公钥验签数据就可以被通过。为了解决公钥派送问题，可以通过数字证书来对发送者的公钥做认证。

6.2.1 数字证书的构成

数字证书格式遵循ITUTX.509标准，X509证书包含以下内容：

（1）证书版本

（2）证书序列号

（3）证书所使用的签名算法

（4）证书的发行机构名称，一般采用X500格式

（5）证书的有效期，通常采用UTC时间

（6）证书所有人名称，一般采用X500格式

（7）证书所有人的公钥

（8）证书发行者对证书的签名

6.2.2 数字证书的颁发

数字证书是由数字证书认证中心（CA）颁发，用于认证证书持有者身份的，其核心是使用认证中心的私钥对证书申请人身份（主要是公钥）进行签名认证。认证中心可以形成以下的层级结构，即根证书认证机构可为二级认证机构颁发证书，二级认证机构可为三级认证机构颁发证书，同时他们都可以为用户颁发证书。

本质上，数字证书是数字证书认证中心对证书申请者的信息和公钥做签名，以自身的权威性为其身份做背书。

以上数字证书的层级结构叫做数字证书链，其中顶层的证书被称为根证书，它是由根证书中心自签名的。在验证数字证书时可按照该证书链逐级验证证书的合法性。根证书的合法性是由其自身保证的，因此一般会被预先安装到操作系统或浏览器等软件中。

6.2.3 数字证书CRL和OCSP

数字证书在颁发时即设置了有效时间，但若需要在有效时间内撤销证书，则可向证书颁发机构申请撤销证书，证书被撤销后将被保存到证书撤销列表（CAL）中。

证书验证时需要验证其是否位于证书撤销列表中，OCSP（在线证书状态协议）就是用于在线查询证书状态的。

根据X509标准，CRL的内容如下：

（1）版本

（2）签名算法

（3）签发者

（4）更新时间

（5）下一次更新时间

（6）废止的证书列表

（7）用户证书序列号

（8）废止时间

（9）CRL入口扩展

6.2.4 数字证书相关文件格式

在数字证书申请和使用流程中，有几种常见的文件格式：

（1）der格式证书：.cer，.crt

（2）pem格式证书：.pem

（3）pkcs12格式：.pfx，.p12

（4）pkcs10证书申请格式：.p10

（5）pkcs7证书申请应答格式：.p7r

（6）pkcs7二进制格式：.p7b

6.2.5 创建自己的CA

所有公司都可以颁发数字证书，公司颁发的证书不一定能在国际上得到广泛认可。但若在自己生产的终端中安装自己建立的CA根证书，则可以建立自身的CA信任链。

7 密钥交换

非对称加解密公钥可以公开交换，但其加解密速度比对称加解密慢得多（大概为几百分之一）。而对称加解密双方的密钥若通过明文传输，则很容易受到中间人攻击，因此需要采用特定的方法实现双方密钥的交换。

7.1 PSK密钥交换

PSK方案通信双方使用预先共享的密钥进行通信，以下为evita中一个采用PSK方案的例子。

每个ecu都将其密钥预置到keymaster中，在需要通信时，keymaster产生一个session
key，并分别用ecu1的密钥k1加密后发给ecu1，用ecu2的密钥k2加密后发给ecu2。ecu1和ecu2接收到信息后用各自的密钥解密后得到session
key，此后双方可使用该session key实现加密通信。

7.2 非对称方式密钥交换

该方法通信双方需要先交换公钥，在通信前用非对称算法进行session密钥协商。即通信一方使用随机数创建一个密钥，然后用自己的私钥加密后发送给对方，接收方用发送方的公钥解密出密钥后。双方可使用该session
key执行加密通信。

tls通信方式的基础即是上述方式，只是其中增加了通过数字证书进行身份认证，以及使用更复杂的密钥协商策略等。

7.3 DH算法密钥交换

DH算法是一种密钥交换算法，它可以在双方不直接传递密钥的情况下完成密钥交换。其流程如下图所示：

1 Alice选择一个素数p，底数g和随机数a，并执行如下计算

A = g^a mod p

2 Alice把p，g和A发送给Bob

3 Bob接收到数据后，选择一个随机数b，并执行以下计算

B = g ^b mod p

s = A^b mod p

4 Bob将B发送给Alice

5 Alice执行如下计算

B^a mod p

= (g^b mod p)^a mod p

= g^ab mod p

= (g^a mod p)^b mod p

= A^b mod p

= s

6 因此Alice和Bob都计算得到了共享密钥s，此后可以用该密钥进行加密通信

注：本文的图片和公式大部分都从网上或相关资料截取，在此对原作者表示感谢。若原作者不同意相关内容的载，请私信联系我删除，谢谢。