link管理
链接快照平台
- 输入网页链接，自动生成快照
- 标签化管理网页链接
相关文章推荐
|
谦虚好学的路灯 · loaddatawithbaseurl - ...· 4 月前 · |
|
|
独立的草稿本 · 暗影谍云 - 第四百八十二章 有点猜疑 - ...· 7 月前 · |
|
|
坚强的葫芦 · /var/lib/mysql/ibdata1 ...· 1 年前 · |
|
|
个性的跑步机 · 数据库mysql转为postgresql变动 ...· 1 年前 · |
|
|
讲道义的水桶 · 决战东南亚新十年：中日争夺7亿人汽车梦-虎嗅网· 1 年前 · |
link管理
›
Cryptography/Block Ciphers.ipynb at master · reata/Cryptography · GitHub
| 高级加密标准 aes加密 分组密码 伪随机 |
| https://github.com/reata/Cryptography/blob/master/Block%20Ciphers.ipynb?short_path=3a0ab7d |
|
老实的打火机
2 月前 |
You signed in with another tab or window.
Reload
to refresh your session.
You signed out in another tab or window.
Reload
to refresh your session.
You switched accounts on another tab or window.
Reload
to refresh your session.
Latest commit
147 lines (147 loc) · 12 KB
/
Block Ciphers.ipynb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
{
"cells"
: [
{
"cell_type"
:
"
markdown
"
,
"metadata"
: {},
"source"
: [
"
# 三、分组密码
\n
"
,
"
## 分组密码的定义
\n
"
,
"
将明文切割成若干等长的模块（block），然后对每个模块分别加密。加密的过程是一个迭代过程，每一轮加密使用原始密钥生成的对于子密钥，利用前一轮加密的密文作
\n
"
,
"
为原文。典型的分组密码包括3DES（模块64位，密钥168位，迭代48次），AES（模块128位，密钥128位或192位或256位，迭代10次）。
\n
"
,
"
\n
"
,
"
从加密速度来看，分组密码的速度显著慢于流密码。
\n
"
,
"
\n
"
,
"
伪随机函数（PRF）根据密钥和明文生成与明文同长的随机密文，也即是普通映射，允许存在多对一关系；伪随机变换（PRP）根据密钥和明文对明文加密，**但密文与明>文存在唯一对应关系**，也即是一一映射，因而存在反函数，可以有效求逆。故PRP是一种特殊的PRF。分组密钥最终是要构造一个PRP。
\n
"
,
"
\n
"
,
"
一个安全的伪随机函数加密的密文，攻击者无法辨别是来自真随机函数还是伪随机函数。一个安全的伪随机变换加密的密文，攻击者也无法辨别是来自伪随机变换还是伪>随机函数。
\n
"
,
"
\n
"
,
"
多次使用同一个安全的伪随机函数，可以作为伪随机数生成器使用。并且多次使用这个过程相互独立，因此可以实现并行计算，从而大幅提升效率的。
\n
"
,
"
\n
"
,
"
## 数据加密标准（Data Encryption Standard，DES）
\n
"
,
"
DES是基于IBM的Lucifer密码，参考美国国家标准改造的加密方式。模块长度64位，密钥长度56位，1997年已经被穷举搜索破解，从而被AES加密算法替代。
\n
"
,
"
\n
"
,
"
DES算法的核心，是Feistel网络结构。给定D个伪随机函数，两组长度为n的模块。每次迭代过程，左模块变为上次迭代时的右模块，而右模块变为上次迭代时左模块与伪>随机函数加密的右模块的异或，共计迭代D次。
\n
"
,
"
\n
"
,
"
该网络模拟，可以在任意伪随机函数不可逆的情况下，整体可逆。并且逆算法（解密算法）依然沿用原有的伪随机函数，仅调换次序。对于硬件来说，效率很高。
\n
"
,
"
\n
"
,
"
Feistel网络是分组密码构建可逆函数的主流办法，但AES并未采取该办法。
\n
"
,
"
\n
"
,
"
可以证明，只要每个伪随机函数是安全的，则只要三轮迭代的Feistel网络就是一个安全的伪随机变换。
\n
"
,
"
\n
"
,
"
DES算法的过程，给定64位的模块，经过序列转换之后，成为两个32位的子模块，进入Feistel网络，16轮迭代之后，对两个子模块做之前序列转换的逆运算，得到密文。
\n
"
,
"
\n
"
,
"
Feistel网络中的伪随机函数这样确定：32位子模块，通过重复抽样成为48位子模块，与密钥生成的对应48位密钥做异或运算。得到的结果分位8份，每份6位，将6位利用>查阅表格成为4位，8份重组为32位。32位经过序列变换，输出32位。
\n
"
,
"
\n
"
,
"
查阅表格成为S-boxes。六位数字的最左和最右位组合作为纵轴，有4种。六位数字的中间四位作为横轴，有16种。从而组合出对应4位的32种组合。
\n
"
,
"
\n
"
,
"
4位序列如果恰好可以由6位序列线性异或而成，则会造成整体DES加密不安全。
\n
"
,
"
\n
"
,
"
## 穷举搜索
\n
"
,
"
对于DES加密，任意给定一组明文和密文，对应的密钥最多只有一份的概率大于99.5%（1-1/256）。
\n
"
,
"
\n
"
,
"
给定两组明文和密文，DES密钥唯一的概率1-1/271，AES密钥唯一的概率是1-1/2<sup>128</sup>。因此对于穷举搜索而言，只要获得两组明文和密文即可。
\n
"
,
"
\n
"
,
"
DES的密钥长度是56位，因为存在256种可能。在发明的时候，这个数字不可能穷举。直到1997年，有机构花三个月时间穷举破解了DES加密。而经过特殊设计造价达到25万
\n
"
,
"
美元的硬件EFF machine在1998年只需要三天就可以破解。06年，一台价值仅一万美元的机器，花7天时间就可以破解DES。
\n
"
,
"
\n
"
,
"
解决方案一：3DES。三组相互独立的密钥，3E((k<sub>1</sub>,k<sub>2</sub>,k<sub>3</sub> ),m)=E(k<sub>1</sub>,D(k<sub>2</sub>,E(k<sub>3</sub>,m)))。3DES的
\n
"
,
"
密钥长度因此达到了3 * 56=168位，加密速度只有DES的三分之一。之所中间加上一道解密算法，是为了适配很多集成DES的硬件。把三组密钥设为相同，可以回到DES算法
\n
"
,
"
。
\n
"
,
"
\n
"
,
"
为什么不用2DES？2E((k<sub>1</sub>,k<sub>2</sub> ),m)=E(k<sub>1</sub>,E(k<sub>2</sub>,m))。尽管2DES的密钥长度达到了112位，但穷举算法并不需要花费2<sup>112</sup>的时间。将k<sub>2</sub>的256种可能穷举，加密算法对明文列出所有可能的中间密文。然后反向，解密算法对密文计算所有的中间明文。寻找匹配。这样需要
\n
"
,
"
花费的时间为2<sup>56</sup> * log2<sup>56</sup> + 2<sup>56</sup> * log2<sup>56</sup> < 2<sup>63</sup> << 2<sup>112</sup>。同理，穷举破译3DES也只需要2<sup>118</sup>，而非2<sup>168</sup>。
\n
"
,
"
就目前的计算能力来说，2<sup>63</sup>是一种可以达到的数字，而2<sup>118</sup>暂时还不能。2<sup>90</sup>以上的量级都可以认为是安全的。
\n
"
,
"
\n
"
,
"
解决方案二：DESX。三组相互独立的密钥，EX((k<sub>1</sub>,k<sub>2</sub>,k<sub>3</sub> ),m)=k<sub>1</sub>⊕E(k<sub>2</sub>,m⊕k<sub>3</sub> )。密钥长度184，穷举可以在2120时间内完成。注意，去除k1或者k3将使加密失效。另外，DESX虽然可以应对穷举搜索，但无法应对其他攻击。保密性不如3DES。
\n
"
,
"
\n
"
,
"
## 分组密码的其它攻击方式
\n
"
,
"
旁路攻击：对系统的物理学分析和实现方式分析，而非通过密码学的分析，来破解密码系统。如监测加密时间，电流等。
\n
"
,
"
\n
"
,
"
故障攻击：最后一轮加密过程的计算错误可能会暴露密钥。
\n
"
,
"
\n
"
,
"
线性差分攻击：某几位的加密过程存在固定模式，对明文与密文做异或运算，能够预测结果的概率为1/2+ε。那么给定1⁄ε<sup>2</sup> 对明文和密文，就可以在1⁄ε<sup>2</sup> 的时间内破解出对应位数的密钥。剩下的穷举破解，可大幅缩减整体穷举的时间。对于DES算法，其中14位密钥可以通过线性差分攻击破译，而ε为1/2<sup>21</sup>。也就是说，给定2<sup>42</sup>对密文和明文，总破解时间只需要2<sup>42</sup>+2<sup>42</sup>的时间，非常不安全。
\n
"
,
"
\n
"
,
"
量子攻击：基于量子计算机，每一位可表示的数字超过两位。传统基于图灵架构的计算机，穷举的时间为O(|X|)，而量子计算机穷举的时间是O(|X|<sup>1/2</sup>)。目>前，量子计算机离成形依然非常遥远。
\n
"
,
"
\n
"
,
"
## 高级加密标准（Advanced Encryption Standard，AES）
\n
"
,
"
核心是Subs-Perm网络（替换-变换网络），共10轮迭代。每轮迭代过程，首先与子密钥异或，然后按照查询表格替换，最后变更次序（最后一轮除外）。
\n
"
,
"
\n
"
,
"
模块共16字节，写成4 * 4的矩阵。子密钥也同样写成矩阵形式，异或。
\n
"
,
"
\n
"
,
"
替换-变换过程包括三个函数。1）字节替换函数：构造替换框（s-box）替换明文矩阵。2）行位移，第二行向左移动一个单位，第三行两个，第四行三个。3）取其中一列
\n
"
,
"
，替换以其他列线性表示。
\n
"
,
"
\n
"
,
"
提前生成替换-变化函数，可以大幅提高加密速度，但也会使代码变得臃肿。浏览器通常包含了由JavaScript编写的AES模块，提前生成函数提前计算。Intel包括AMD的处>理器通常也都内置了AES计算的相应指令集。
\n
"
,
"
\n
"
,
"
128位密钥的AES，最佳密钥恢复攻击需要花费2<sup>126</sup>单位时间，比穷举快四倍。而AES-256可能面临相似密钥攻击，收集2<sup>99</sup>对明文密文，可以在2<sup>99</sup>单位时间内恢复密钥。
\n
"
,
"
\n
"
,
"
## 利用伪随机数生成器（PRG）构造分组密码
\n
"
,
"
对一个密钥使用一次伪随机生成器，生成的序列一分为二，得到两份密文，就构造出了一个对应1位密钥的伪随机函数。对两个子序列继续使用伪随机生成器，生成的序列
\n
"
,
"
继续一分为二，得到四份密文，就构造出了一个对应2位密钥的伪随机函数。
\n
"
,
"
\n
"
,
"
依次类推，可以得到对于任意长度密钥的伪随机函数。
\n
"
,
"
\n
"
,
"
尽管通过伪随机生成器生成的伪随机函数不可逆，但是利用Feistel网络，构造三层，就可以得到伪随机序列，从而成功构造分组密码。
\n
"
,
"
\n
"
,
"
在实践当中，由于这种办法速度太慢，实际上没有采用这种办法来构造分组密码。
\n
"
,
"
\n
"
]
},
{
"cell_type"
:
"
markdown
"
,
"metadata"
: {},
"source"
: [
"
# 四、使用分组密码
\n
"
,
"
## 回顾：伪随机序列和伪随机函数
\n
"
,
"
PRP和PRF的安全性也是用语义安全（统计量优势）来定义的。
\n
"
,
"
\n
"
,
"
当明文长度足够长的时候，一个安全的PRP，同时也是安全的PRF。二者统计量优势之差的绝对值小于q<sup>2</sup>⁄(2|x|)，其中q是可获得的明文密文对，而x是明文长>度。
\n
"
,
"
\n
"
,
"
从这一章开始，可以不再过多考虑AES和3DES的内部工作原理，只要知道它们在现阶段都是安全的PRP，主要考虑如何使用就可以。
\n
"
,
"
\n
"
,
"
## 运行模式：一次性密钥
\n
"
,
"
邮件的加密就是这种模式，每段新明文，都使用新密钥。
\n
"
,
"
\n
"
,
"
如果密钥永不更换，这种形式叫做电子密码本（Electronic Code Book，ECB）。那么内容相同的模块（block）会得到相同的密文，加密是不安全的。以图片为例，加密>后的图片就会依然呈现出某种模式。
\n
"
,
"
\n
"
,
"
ECB不具备语义安全，可以非常简单地被攻破，攻击者只要发送的两条明文中，一条存在重复的情况，则就可以通过返回密文是否存在重复来辨别。
\n
"
,
"
\n
"
,
"
安全的分组密码使用方法，是对每个模块添加计数器，传入密钥和计数器用伪随机函数加密。
\n
"
,
"
\n
"
,
"
## 多次密钥的安全性
\n
"
,
"
文件系统和IPsec都是多次使用相同的AES密钥。
\n
"
,
"
\n
"
,
"
对于多次密钥，攻击者可以使用选择明文攻击（Chosen Plaintext Attack，CPA）。先传入两条相同的明文，得到对应密文。在传入之前的明文和新明文，可以清楚地分>辨所得密文是否来自先前的明文。
\n
"
,
"
\n
"
,
"
解决方案一：在加密过程中加入随机性，使得一条明文可以映射为多条密文。这样对同一条明文加密两次很大可能得到两条不同的密文，而明文由于需要包含随机数，会>长于密文。在伪随机函数安全的前提下，只要随机数取值空间足够大很大可能不会出现重复，该加密方案对于选择明文攻击就是语义安全的。
\n
"
,
"
\n
"
,
"
解决方案二：引入不重复数nonce，每次加密，传入明文、密钥和nonce。密钥重复使用，但需要保证（key，nonce）对不重复。Nonce可以随机，也可以是计数器。
\n
"
,
"
\n
"
,
"
## 运行模式：多次密钥
\n
"
,
"
CBC和CRT，课件里结合图讲得更清楚，这里不仔细记录了。
"
]
}
],
"metadata"
: {
"anaconda-cloud"
: {},
"kernelspec"
: {
"display_name"
:
"
Python [conda root]
"
,
"language"
:
"
python
"
,
"name"
:
"
conda-root-py
"
},
"language_info"
: {
"codemirror_mode"
: {
"name"
:
"
ipython
"
,
"version"
:
3
},
"file_extension"
:
"
.py
"
,
"mimetype"
:
"
text/x-python
"
,
"name"
:
"
python
"
,
"nbconvert_exporter"
:
"
python
"
,
"pygments_lexer"
:
"
ipython3
"
,
"version"
:
"
3.5.2
"
}
},
"nbformat"
:
4
,
"nbformat_minor"
:
1
}