Blockchain and cryptography (区块链与密码学)学习笔记1:对称加密

Hacker Dōjo Workshop:
研究种类:密码学,对称加密
资助金额:100 usdt
Bounty链接:https://dorahacks.io/zh/daobounty/137
创作者:Lynndell
本项目由Hacker Dōjo资助,文章转载请联系
Telegram: @HackerDojo0
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盒操作。
  • 假如第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个候选算法进入最后一轮:RijndaelSerpentTwofishRC6和MARS。最终经过安全性分析、软硬件性能评估等严格的步骤,Rijndael算法获胜。

Rijndael由比利时两位非常著名的密码学家Joan DaemenVincent 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算法的模块在对称密码领域特别是分组密码领域常有使用。


27

1.3.2 轮函数Function

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


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

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 密钥扩展算法

密钥扩展的原理图如下:


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


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

1.4.3 CBC密码快链接模式

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

最后一个分组需要填充

需要初始化向量

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

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

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

1.4.4 CFB密文反馈模式

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


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

1.4.5 OFB输出反馈模式

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


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

1.4.6 CTR计数器模式

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


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

1.4.7 优缺点对比

58


关于我们
:small_orange_diamond:Hacker Dōjo是由Hacker共建的加密、Web3前沿技术开源知识社区。Dōjo会以直播/音频/文字等形式定期组织分享session,内容包括Web3领域前沿技术论文解读、技术研讨、工作坊等。欢迎在Hacker Dōjo社区讨论、学习和交流。加入Dōjo的Hacker可以提出自己的学习期望,主动提案自己擅长的技术话题,由Dōjo组织分享。同时,Hacker Dōjo推出Web3前沿课题研究计划,定期选题,由hacker进行研究和讲解,并以bounty形式奖励研究贡献者。
合作事项
:small_orange_diamond:认领Bounty:DoraHacks
:small_orange_diamond:转载文章:请保留Hacker Dōjo Workshop介绍并联系我们hackerdojo0@gmail.com。