Blockchain and cryptography （区块链与密码学）学习笔记1：对称加密

Dora Dōjo
1

Hacker Dōjo Workshop：
研究种类：密码学，对称加密
资助金额：100 usdt
Bounty链接：Hacker Dōjo|课题研究：对称加密算法 | Bounties | DoraHacks
创作者：Lynndell
本项目由Hacker Dōjo资助，文章转载请联系
Telegram: @DoraDojo0
WeChat: @HackerDojo0
E-mail: hackerdojo0@gmail.com

密码学系列大纲

  • 对称加密 （DES、AES、五种加密模式）

  • 哈希函数 （SHA2、SHA3、MiMC、Rescue、Poseidon）

  • 群与公钥加密 （群，椭圆曲线群，Diffie-Hellman密钥交换，ElGamal加密）

  • 数字签名 （BLS、Schnorr、EdDSA、ECDSA）

  • 零知识证明 （Sigma零知识证明、Groth16、PLONK）

  • 多方ECDSA签名 （Li17两方签名、GG18多方签名、GG20多方签名、CMP20多方签名）

1对称加密

1.1基本概念

混淆： 密钥与密文之间的统计特征尽可能复杂。理解 密钥与明文数据混起来。

扩散： 明文的统计特征消失在密文中。理解 每比特输入，影响50%的输出。
1|436x255#pic_center
2

1.1.1凯撒密码

使用后面第3个字母替换明文

plain: a b c d e f g h i j k l m n o p q r s t u v w x y z

cipher: D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

plain: meet me after the toga party

cipher: PHHW PH DIWHU WKH WRJD SDUWB
3|564x102#pic_center

该密码算法不能公开，一旦公开，则很快会被破解。
密码算法要求：安全性仅依赖于密钥，算法可以公开。

1.1.2对称密码分类

a

流密码

加密： 输入密钥key，运行随机数生成算法，输出任意长的随机数；随机数与明文数据异或运算，输出密文。
5
解密： 输入密钥key，运行随机数生成算法，输出任意长的随机数；随机数与密文异或运算，输出明文数据。
6
b
分组密码

加密： 输入固定长（256bit）的明文数据和固定长的密钥key，输出固定长的密文
7
解密： 输入固定长的密文和固定长的密钥key，输出固定长的明文数据
8
分组密码的应用范围比流密码更广泛，绝大多数基于网络的对称密码使用的都是分组密码。此外，分组密码通过5种加密模式，能够构造流密码。

1.2DES

1.2.1 初始置换

把明文输入块分为64块，然后排列成下面所示输出：
输入：64bit；输出：64bit；IP置换功能：乱序。
12

1.2.2 轮函数Function

假设Bi(64bit)是第i次迭代的结果，Li(left 32bit)和Ri(right 32bit)是Bi的左半部分和右半部分。Ki是第i轮的48位密钥，且f是实现代替、置换、密钥异或等运算的函数，那么每一轮就是：
13
轮函数 funtion 包括4 步：
扩展置换 ­­­ 、密钥异或、S 盒代替、P 盒置换。

1.2.2.1 扩展置换

输入右边Ri 数据right 32bit ，输出数据48bit
14
将数据的右边部分Ri(32bit)按照上图所示扩展为48bit

  • 思路为首位互换，数据段之间交叉填充
  • 尽管输出分组大于输入分组，但每个输入分组产生唯一的输出分组

1.2.2.2 密钥异或

密钥置换分为3步：1.密钥初始化、2.密钥移位、3.密钥压缩置换；

1. PC1 置换 密钥初始化（执行一次）
输入密钥为
15
在DES每一轮中，56位**(64** 位删除8 的倍数的校验位) 密钥进行如下表所示排列:
输入：64bit ；输出56bit ；删除校验位(8,16,24,32,40,48,56,64) 、然后乱序；
16
2. Key_Rotations 密钥移位（每轮执行）
然后将密钥分为两部分： C0是28bit， D0是28bit。

C0=**57,49,**41,33,25,17,9,1,58,50,42,34,26,18,10,2,59,51,43,35,27,19,11,3,60,52,44,36

D0=**63,55,**47,39,31,23,15,7,62,54,46,38,30,22,14,6,61,53,45,37,29,21,13,5,28,20,12,4

每部分28位，然后根据轮数，这两部分分别左移一位或两位。加密左移表：
17
例如：第1轮移位后的结果如下
C1=49,41,33,25,17,9,1,58,50,42,34,26,18,10,2,59,51,43,35,27,19,11,3,60,52,44,36,57

D1=55,47,39,31,23,15,7,62,54,46,38,30,22,14,6,61,53,45,37,29,21,13,5,28,20,12,4,63
3. PC2 置换 密钥压缩置换（T盒压缩置换）（每轮执行）
然后合并C1,D1 ,再经过置换选PC-2排列:
18
其中删除第9,18,22,25,35,38,43,54位，变为48位密钥K1 .
继续执行步骤2和步骤3：

  • C1 和 D1 再次经过循环左移，生成 C2 和 D2 ，合并后通过 PC-2 生成子密钥 K2 ；
  • C2和D2再次经过循环左移，生成C3和D3，合并后通过PC-2生成子密钥K3；
  • 以此类推得到全部子密钥K1-K16。

异或运算：48bit 数据data 异或 48bit 密钥key 输出 48bit 中间状态数据data’

1.2.2.3 SBox盒代替

中间状态数据data’进入S盒子
48=6*8，拆为8份，每份是6bit
将六bit输入标记为b1,b2,b3,b4,b5,b6.
Y坐标：b1, b6构成一个2位的数00,01,10,11，y=0,1,2,3；
X坐标：b2, b3, b4, b5构成一个4位的数x，x=0,1,2,…,15.
因此，确定一个坐标点(x,y)。
将48位data’ 结果送入S盒进行代替运算。

  • 每一个S 盒有六位输入，四位输出，且这八个S 盒是不同的。
  • 48位的输入块被分为8个6位的分组，每个分组对应一个S盒操作。
    19
    19600×653 95.4 KB
  • 假如第n组数据输入,就有第n组输出为Sn的(x,y)确定输出的数(转化为二进制就有四位)
  • 假设S8的输入(即异或函数的第43~18位)为110011。第1位和最后一位组合形成了11(二进制)，对应S-盒8的第3行。中间的4位组成形成1001(二进制),对应S-盒8的第9列。所以对应S-盒8第3行第9列值是12。则S-盒输出是1100(二进制)。

1.2.2.4 PBox盒置换

S盒运算后得到四位，八盒共得到32位输出.然后依照P盒进行置换。
P盒排布如下表所示:
20
置换后的结果与最初的64位分组的左半部分异或，然后左右不分分别交换,开始下一轮迭代。

1.2.3 末尾逆置换

末置换是初始置换的逆过程.
将初始置换进行16次迭代加密后,得到L16和R16.将此作为输入进行末置换.末置换表如下:
21
最后一轮结束后，左右密钥并未交换，而是将R16与L16并在一起形成一个分组作为末置换的输入。
22
末置换结果的输出就是算法结果的输出。

1.2.4 DES解密

加密与解密唯一不同就是密钥次序是相反的。
加密秘钥是K1、K2、K3, …, K16，
解密秘钥是K16、K15、K14, …, K1。

1.2.5 双重和三重DES

23
双重DES
24
三重DES
25

1.3AES

数据加密标准（Data Encryption Standard: DES）的密钥长度是56比特，因此算法的理论安全强度是256。但是二十世纪中后期正是计算机飞速发展的阶段，元器件制造工艺的进步使得计算机的处理能力越来越强，DES将不能提供足够的安全性。1997年1月2号，美国国家标准技术研究所（National Institute of Standards and Technology: NIST）宣布希望征集高级加密标准（Advanced Encryption Standard: AES）[3]，用以取代DES。AES得到了全世界很多密码工作者的响应，先后有很多人提交算法。最终有5个候选算法进入最后一轮：Rijndael，Serpent，Twofish，RC6和MARS。最终经过安全性分析、软硬件性能评估等严格的步骤，Rijndael算法获胜。

Rijndael由比利时两位非常著名的密码学家Joan Daemen和Vincent Rijmen设计。Rijndael是一个分组密码算法族，其分组长度包括128比特、160比特、192比特、224比特、256比特，密钥长度也包括这五种长度，但是最终AES只选取了分组长度为128比特，密钥长度为128比特、192比特和256比特的三个版本。本文主要结合AES-128进行介绍，AES-196和AES-256的思路基本一样，只是密钥扩展算法的过程会稍有不同，加解密的轮数会适当增加，但加解密的操作都是一样的。另外，本文只对AES算法的各个模块、基本原理进行介绍，旨在加深对算法流程、密码算法实现的了解。在正式软件运用中并不推荐自己编写代码，很多开源项目如Linux，OPENSSL，SRTP等都有非常高效的实现。由于数学知识的缺陷，本文不介绍算法安全性分析相关的知识，有兴趣的读者可以自行阅读相关文献。

1.3.1 加密流程

AES是一个分组密码，属于对称密码范畴，AES算法的模块在对称密码领域特别是分组密码领域常有使用。

26
26554×767 107 KB

27

1.3.2 轮函数Function

轮函数包含 4 种操作：字节替代（ SubBytes ）、行移位（ ShiftRows ）、列混淆（ MixColumns ）和轮密钥加（ AddRoundKey ）
下图给出了AES加解密的流程，从图中可以看出：1）解密算法的每一步分别对应加密算法的逆操作，2）加解密所有操作的顺序正好是相反的。正是由于这几点（再加上加密算法与解密算法每步的操作互逆）保证了算法的正确性。加解密中每轮的密钥分别由种子密钥经过密钥扩展算法得到。算法中16字节的明文、密文和轮子密钥都以一个4x4的矩阵表示。

28
28554×760 133 KB

29

1.3.2.1 字节替代

字节代替的主要功能是通过S盒完成一个字节到另外一个字节的映射。S盒的详细构造方法可以参考文献[4]。这里直接给出构造好的结果，下图(a)为S盒，图(b)为S-1（S盒的逆）。S盒用于提供密码算法的混淆性。
S和S-1分别为16x16的矩阵，完成一个8比特输入到8比特输出的映射，
输入的高 4-bit 对应的值作为行标，低 4-bit 对应的值作为列标。
假设输入字节的值为a=a7a6a5a4a3a2a1a0，则输出值为S[a7a6a5a4][a3a2a1a0]，S-1的变换也同理。
例如：字节00000000B替换后的值为（S[0][0]=）63H，再通过S-1即可得到替换前的值，（S-1 [6][3]=）00H。
30
31
32
用进行等价描述

  1. 按字节值的升序逐行初始化S盒子。第1行是{00},{01},…,{0F}；第2行是{10},{11},…,{1F}。因此，在y行x列的字节值是{yx}
  2. S盒子中每个字节映射为有限域 GF(28)中的逆，其中{00}映射为{00}。
  3. S盒子中的每个字节的8位记为(b7,b6,…,b0) ，对每个字节进行如下变换
    33
    其中ci是值{63}字节c的第i位 (c7,c6,c5,c4,c3,c2,c1,) = (01100011)
    对应的逆变换为
    34
    其中字节d={05}或00000101。
    也可以用矩阵等价描述
    35
    对应的逆变换为
    36
    37
    37509×552 86.2 KB

1.3.2.2 行移位

行移位是一个4x4的矩阵内部字节之间的置换，用于提供算法的扩散性。
1) 正向行移位
正向行移位用于加密，其原理图如下。其中：

  • 第一行保持不变，第二行循环左移 8 比特，
  • 第三行循环左移 16 比特，第四行循环左移 24 比特。
    假设矩阵的名字为state，用公式表示如下：
    38
    39

2) 逆向行移位
逆向行移位即是相反的操作，即：

  • 第一行保持不变，第二行循环右移 8 比特，
  • 第三行循环右移 16 比特，第四行循环右移 24 比特。
    用公式表示如下：
    40

1.3.2.3 列混淆

不可约多项式（本原多项式）定义：不能写成两个次数较低的多项式之乘积的多项式。没有多项式因子。

LIDL94 Lidl, R. and Niederreiter, H. Introduction to Finite Fields and Their Applications. Cambridge: Cambridge University Press, 1994.

字节运算规定：字节相加，就是位异或运算；字节相乘，就是有限域内的乘法运算，模不可以多项式。
1) 列混淆
列混淆计算方法1： 使用域F2n上的不可约多项式
41
列混淆计算方法2：
正向列混淆的原理图如下：
42
根据矩阵的乘法可知，在列混淆的过程中，每个字节对应的值只与该列的4个值有关系。此处的乘法和加法都是定义在GF(28)上的，需要注意如下几点：

  • 将某个字节所对应的值乘以 2 ，其结果就是将该值的二进制位左移一位。如果原始值的最高位为 1 ，则还需要将移位后的结果异或 00011011 ；
  • 乘法对加法满足分配率，
    43
  • 此处的矩阵乘法与一般意义上矩阵的乘法有所不同，各个值在相加时使用的是模28加法（异或运算）。
    下面举一个例子，假设某一列的值如下图，运算过程如下：
    44
    在计算 02 与 C9 的乘积时，由于 C9 对应最左边的比特为 1 ，因此需要将 C9 左移一位后的值与 (0001 1011) 求异或。同理可以求出另外几个值。

2) 逆向列混淆
逆向列混淆的原理图如下：
45
由于：
46
说明两个矩阵互逆，经过一次逆向列混淆后即可恢复原文。

1.3.2.4 轮密钥加

这个操作相对简单，其依据的原理是“任何数和自身的异或结果为0”。加密过程中，每轮的输入与轮子密钥异或一次；因此，解密时再异或上该轮的轮子密钥即可恢复。
47

1.3.3 密钥扩展算法

密钥扩展的原理图如下：

48
48456×548 66.9 KB

49
密钥扩展过程说明： 16 个字节扩展为 43 个字节

  • 将种子密钥按图(a)的格式排列，其中k0、k1、……、k15依次表示种子密钥的一个字节；排列后用4个32比特的字表示，分别记为w[0]、w[1]、w[2]、w[3]；4组，每组4个字节
  • 按照如下方式，依次求解w[j]，其中****j 是整数并且属于 [4,43] ；
    若j%4=0,则w[j]=w[j-4] ⊕ g(w[j-1]) ，j=4,8,12,16,20,24,28,32,36,40
    否则w[j]=w[j-4] ⊕ w[j-1] ；j=5,6,7; 9,10,11; 13,14,15; 17,18,19; 21,22,23; 25,26,27; 29,30,31; 33,34,35; 37,38,39; 41,42,43;

函数g的流程说明：
将w循环左移8比特；
分别对每个字节做S盒置换；
与32比特的常量（RC[j/4],0,0,0）进行异或，RC是一个一维数组，其值如下。（RC的值只需要有10个，而此处用了11个，实际上RC[0]在运算中没有用到，增加RC[0]是为了便于程序中用数组表示。由于j的最小取值是4，j/4的最小取值则是1，因此不会产生错误。）

50
详细原理：
51

1.3.4 小结

对称加密（哈希函数）的核心思想：

  • 线性变换：线性运算关系，作用：让每bit输入影响50%输出；

  • 非线性变换：S****盒子，非线性变换，抵抗解方程组攻击；

  • 轮密钥加：添加一些随机数或常量，提高信息商。

AES, SHA3

密码算法要求是可逆的，这样解密算法才能正确的恢复明文。在密钥固定的情况下，明文和密文在整个输入空间是一一对应的。因此，算法的各个部件也都是可逆的，再将各个部件的操作顺序设计成可逆的，密文就能正确的解密了。
参考文献

  1. William Stallings著；王张宜等译. 密码编码学与网络安全——原理与实践（第五版）[M]. 北京：电子工业出版社，2012.1.
  2. Advanced Encryption Standard, Advanced Encryption Standard - Wikipedia, 2017年3月获取.

64bit DES N次

128bit AES N/2次

分组密码循环调用多次，实现对任意长数据的加密。

1.4对称加密五种工作模式

对称加密与哈希函数的核心思想：

  • 线性变换：线性运算关系，作用：让每bit 输入影响每bit 输出

  • 非线性变换：S 盒子，非线性变换，抵抗解方程组攻击

  • 密钥加：添加一些随机数；提高信息商；轮常量
    52

1.4.2 ECB电子密码本模式

ECB模式是分组密码的基本工作方式。在该模式下,每个加密区块按顺序进行独立加密，得到独立的密文区块,每个加密区块的结果都不会被其他区块影响,用此方式,可用平行处理实施加速加、解密运算,且在网络传输时任何一个区块出现错误,也不存在影响到其他区块传输的结果,这是该模式的好处。

ECB模式的不足是易使明文的数据模式暴露。很多数据均存在固有模式,这主要是由数据结构与数据冗余导致的。若无任何措施,针对在需加密的文件里出现多回的明文,这部分明文如果刚好是加密区块的大小,则可能会得到一样的密文,且密文内容如果受到剪贴、代替,也很难被发现。

53
53554×557 43.8 KB

Msg: 256, 50%，差分能力，判断你到底，AES/DES
如果攻击者获得了大量的明文和密文；分析能力。提高了攻破概率。

1.4.3 CBC密码快链接模式

密文没有规律，引入雪崩效应：是优点，也是缺点。

最后一个分组需要填充

需要初始化向量

第一个加密区块先与初始向量做异或运算,再进行加密。其他每个加密区块在加密之前,必须与前一个加密区块的密文做一次异或运算,再进行加密。每个区块的加密结果都会被前面全部区块内容的影响,因此尽管在明文里出现多次一样的明文,也会得到不一样的密文。

还有,密文内容如果遇到剪贴、替换,或于网络传输时出现错误,则它后面的密文会被破坏,不能顺利解密还原,这是这一模式的优点也是缺点。

其次,一定得选取1个初始向量来加密第1个区块,且加密作业时不能用平行处理加速加密运算,不过解密运算,做异或的加密区块结果已经有了,则还可用平行处理加速。
54
245bits
C1,…Cn,…,Cm
1bit传输错误，那就后续全错。

1.4.4 CFB密文反馈模式

简单讲就是前一模块的密文输出，参与下一模块的加解密
密文没有规律，明文分组和一个数据流进行异或操作，生成密文
需要初始化向量
不需要填充

55
55554×625 88.4 KB

有严格的顺序关系：导致无法并行运算。效率较低。

1.4.5 OFB输出反馈模式

初始化向量一次加密并参与各分组的加密过程
特点，密文没有规律，明文分组和一个数据流按位异或生成密文
需要初始化向量
不需要填充

56
56554×551 56.3 KB

初始向量 一旦传输错误，则一切都完蛋。
256bit 的随机数，
地球– 太空
芯片初始化，巨大的容错能力。

1.4.6 CTR计数器模式

用计数器代替OFB模式中的向量
不需要初始化向量
不需要填充

57
57554×550 62.4 KB

起始状态：
并行计算、密文之间互不影响、
key256bit, 加密1G数据

1.4.7 优缺点对比

58

关于Dorahacks
DoraHacks 是一个全球范围内的极客运动、全球黑客马拉松组织者，也是全球最活跃的多链 Web3 开发者平台之一。DoraHacks.io平台使得世界各地的Hacker和开源开发者可以参与黑客马拉松、Bounty、Grant、Grant DAO，以及公共物品质押等加密原生协议和基础设施进行协作并获得资助。到目前为止，DoraHacks 社区的 4000 多个项目已经获得了来自全球行业支持者超过 3000 万美元的资助。大量开源社区、DAO 和 超过50个主要区块链生态系统正在积极使用 Dora 的基础设施（DoraHacks.io）进行开源融资和社区治理。

关于Dorahacks DAO Bounty
Dorahacks DAO Bounty，为各类DAO和组织赋能！
Bounty计划为DAO和组织提供了一个强大的平台，通过社区激励的形式，发布问题，协调任务，鼓励用户积极参与。
作为Bounty发布者，您可以根据我们的指南，发布社区相关的悬赏任务，解决问题的同时，提升社区活跃度：How to publish a bounty and easily fund bounty hunters
作为赏金猎人，您可以在DAO Bounty计划中发挥自己的专长和能力，认领悬赏，解决问题，获得酬金：DAO Bounties | DoraHacks

关于Hacker Dōjō
Hacker Dōjō是由Hacker共建的加密、Web3前沿技术开源知识社区。Dōjō会以直播/音频/文字等形式定期组织分享session，内容包括Web3领域前沿技术论文解读、技术研讨、工作坊、技术领袖研讨会等。欢迎在Hacker Dōjo社区讨论、学习和交流：Dora Dōjo - Dora Community Forum

目前Hacker Dōjō已分享的主题有：

  • 密码学：基础专题（对称加密算法、哈希函数、群和公钥加密、数字签名和KZG承诺、零知识证明、非对称密码算法、分布式密码学）
  • 密码学：算法代码专题（Halo、Halo2、Plonk、Groth16、分布式密钥生成）
  • 密码学：抗量子计算破解算法专题
  • Layer1架构：Move系列、模块化公链、共识协议Bullshark、内存池协议Narwhal和共识协议Tusk、Aptos共识与交易并行执行
  • Layer2架构：zkSync研究、Layer2的支付通道扩容方法、Polygon Hermez、Optimism、StarkWare技术与生态梳理
  • IRS系列：Interest Rate Swap and DeFi Platforms、Interest Rate Swap and Perpetual Swap、The Future Dencentralized Interest Rate Swap
  • 量子计算系列：量子计算基础、Qiskit专题（Qiskit入门、Deutsch-Jozsa算法、Bernstein-Vazirani算法、Simon算法、量子卷积神经网络、量子傅里叶变换、量子相位）、Pennylane专题（利用变分量子电路拟合傅里叶级数）、实验法观测宏观量子叠加态
  • AIGC系列：ChatGPT比较语料评测、GPT-4论文解读

加入Dōjō的Hacker可以提出自己的学习期望，主动提案自己擅长的技术话题，由Dōjō组织分享。同时，Hacker Dōjō推出Web3前沿课题研究计划，定期选题，由Hacker进行研究和讲解，并以bounty形式奖励研究贡献者。欢迎各位Hacker认领Bounty：DAO Bounties | DoraHacks

联系我们：

Telegram: @DoraDojo0

WeChat: @HackerDojo0

E-mail: hackerdojo0@gmail.com