数据加密标准
分组密码¶
分组密码分为对称分组密码与非对称分组密码，习惯上多指的是对称分组密码
分组密码主要任务是提供数据保密性，也可以用于构造伪随机数生成器、哈希函数、序列密码等
特点：分组密码加解密速度较快，安全性好，得到了许多密码芯片的支持
分组密码要求¶
- 分组长度足够大
- 分组长度小，攻击者可以通过穷举法进行暴力破解
- 密钥量足够大
- 密码变换足够复杂
- 加密和解密运算简单
- 无数据扩展或压缩
分组密码的设计思想中有扩散与混淆两个重要概念，即雪崩效应和关系复杂化
分组密码要求——关于置换¶
对于一个分组长度为n的分组密码，不同密钥对应不同的加密解密变换，对于给定的密钥k，加密变换\(E_k\)是\(GF(2)^n\)上的一个变换
为了方便密钥管理，通常密钥长度t不能太大
乘积密码¶
原理：依次使用两个或两个以上的基本密码，所得密码强度强于单个密码的强度
实现方法：通常使用混淆、扩散两种基本密码操作组合变换实现
效果：利用少量软硬件资源实现混淆、扩散
乘积密码——SPN¶
SPN是乘积密码的一种由多重S变换和P变换组合成的变换网络，其基本操作是S变换（代换）与P变换（置换），前者称为“S盒”，后者称为“P盒”。
S盒起到混淆作用，P盒起到扩散作用
分组密码结构——子密钥生成¶
- 子密钥生成算法定位
- 从初始密钥产生各轮迭代使用的子密钥，轮函数F的功能是在子密钥的参与和控制下实现
轮函数基本准则：非线性、体现安全性；保证基本的加解密实现；高性能；
分组密码一般采用简单、安全性弱的密码函数进行多轮迭代
DES¶
DES由来¶
1973年，美国国家标准局在美国征集国家加密标准，经过海选、初选、决赛，最后IBM公司的Lucifer加密系统获得了胜利，1977年1月15日NBS决定利用这个算法，并更名为Data Encryption Standard，简称DES
基本参数¶
- 分组加密算法：明文和密文为64位分组长度
- 密码算法：加密和解密除了子密钥编排不同之外，使用同一算法
- 密钥长度：56位，但存在弱密钥
- 采用混淆和扩散的组合：每个组合先代换后置换，共16轮
- 只使用了简单的逻辑运算
加密流程¶
轮函数F实现流程¶
对于\(R_{i-1}\rightarrow R_i\)：选择扩展运算E，将32bit扩展为48bit与子密钥\(K_i\)进行异或运算，再使用压缩运算S将48bit压缩至32bit，使用置换运算P后，再与\(L_{i-1}\)异或得到\(R_i\)
对于\(L_{i}\)，直接使用\(R_{i-1}\)作为\(L_{i}\)
选择扩展置换E¶
8个4位分组，将每个分组扩展为6位，32个输入位正好有16个输入位在输出中出现了两次。但是任意一个输入位都不会在同一个6位的输出分组出现两次。
扩展盒（E-盒）增加了DES的扩散行为，因为某些输入位会影响两个不同的输出位置。
压缩运算¶
S-盒的构造方法¶
示例：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 12 | 1 | 10 | 15 | 9 | 2 | 6 | 7 | 0 | 13 | 3 | 4 | 14 | 7 | 5 | 11 |
| 1 | 10 | 15 | 4 | 2 | 7 | 12 | 3 | 7 | 0 | 4 | 10 | 1 | 13 | 11 | 6 | |
| 2 | 9 | 14 | 15 | 5 | 2 | 8 | 12 | 3 | 7 | 0 | 4 | 0 | 10 | 1 | 13 | 11 |
| 3 | 4 | 3 | 2 | 12 | 9 | 5 | 15 | 10 | 11 | 14 | 1 | 7 | 6 | 0 | 8 | 13 |
现在有6bit数据\(b_1b_2b_3b_4b_5b_6\)，将其拆分为\(b_1b_6\)与\(b_2b_3b_4b_5\)d带入S盒进行计算，有：
DES解密-解析表达¶
密文\(C\leftarrow IP^{-1}(L_{16}R_{16})\)
\(\begin{cases} L_i\leftarrow R_{i-1}\\ R_i\leftarrow L_{i-1}\oplus F(R_{i-1},k_i) \end{cases}\)
明文\(M\leftarrow IP(L_0R_0)\)
DES分析¶
互补性¶
使得DES在选择明文攻击下所需工作量减半
对明文m逐位取补，记为\(\bar{m}\)，密钥\(k\)逐位取补，记为\(\bar{k}\)，若\(c=E_k(m)\)，则有\(\bar{c}=E_{\bar{k}}(\bar{m})\)
这种特性被称为算法上的互补性，是由算法中的两次异或运算的配置所决定的。两次异或运算一次在S盒之前，一次在P盒置换之后。若对DES输入的明文和密钥同时取补，则选择扩展运算E的输出和子密钥产生器的输出也都取补，因而经异或运算后的输出和明文及密钥未取补时的输出一样，这使得到达S盒的输入数据未变，其输出自然也不会变，但经第二个异或运算时，由于左边的数据已取补，因而输出也就取补了。
弱密钥¶
如果给定初始密钥k，经过子密钥产生器产生的各个子密钥相同，即有\(k_1=k_2\dots k_{16}\)，则称给定的初始密钥k为弱密钥
半弱密钥¶
若给定初始密钥k，产生的16个子密钥只有两种，且每种都出现8次，则称k为半弱密钥。
半弱密钥的特点是成对出现，且具有下述性质： 若k1和k2为一对半弱密钥，m为明文组，则有：\(Ek2(Ek1(m))=Ek1(Ek2(m))=m\)
由此类推，可以得到四分之一弱密钥和八分之一弱密钥
但是这种弱密钥在DES的\(2^{56}\)个密钥中占的比例极小，而且极易避开，所以弱密钥的存在对DES安全性威胁不大
差分分析¶
差分分析是一种攻击迭代密码体制的选择明文攻击方法，与一般统计分析法的不同之处是，它不是直接分析密文或密钥和明文的统计相关性，而是分析一对给定明文的异或（对应位不同的个数称为差分）与对应密文对的异或之间的统计相关性。差分分析的基本思想是在攻击的迭代密码系统中找出某些高概率的明文差分和密文差分对来推算密钥。利用此法攻击DES，需要用\(2^47\)个选择明文和\(2^47\)次加密运算，比穷举搜索的工作量大大减少。然而找到\(2^47\)个选择明文的要求使这种攻击只有理论上的意义。
线性分析¶
该方法是日本密码学家松井充(Mitsuru Matsui)于1993年公开的另一种对分组密码进行分析攻击的方法，这种方法试图通过大量的“明-密文对”找出分组密码算法中与密钥有关的线性方程，然后试着得到大量的这类关系从而确定密钥。其基本思想是以最佳的线性函数逼近DES的非线性变换S盒，这是一种已知明文攻击方法，可以在有\(2^43\)个已知明-密文对的情况下破译DES。虽然获得已知明文比选择明文更容易，但线性分析作为一种攻击手段针对DES在实际上仍然不可行
多重DES¶
为了提高DES的安全性，并充分利用已有DES的软件和硬件资源，可以使用多重DES。多重DES就是使用多个密钥利用DES对明文进行多次加解密，使用多重DES可以增加密钥量，从而大大提高抵抗对密钥的穷举搜索攻击的能力
二重DES指的是取两个独立的密钥\(k_1, k_2\)
加密：\(C=DES_{k_2}(DES_{k_1}(m))\)
解密：\(m=DES^{-1}_{k_1}(DES^{-1}_{k_2}(C))\)
得到\(DES_{k_1}(m) = DES_{k_2}^{-1}(C)\)