分组密码

目录索引

将一个明文分组作为整体加密并且通常得到的是与明文等长的密文分组（一般为 64 位或 128 位）
与流密码一样，分组密码也需要共享一个对称加密密钥。

  • 功能：提供数据保密性，构造伪随机数生成器、序列密码、认证码、哈希函数
  • 分类：分为对称分组密码、非对称分组密码，通常指对称分组密码
  • 优点：分组密码加解密速度快、安全性好，有很多密码芯片支持
    将明文编码后划分成若干固定长度，每一组使用密钥进行加密
%3 cluster_1 加密过程 cluster_2 解密过程 密钥1 密钥 加密算法 加密算法 密钥1:e->加密算法:w 明文1 明文 明文1:s->加密算法:n 密文2 密文 密文1 密文 加密算法:s->密文1:n 密钥2 密钥2 明文2 明文 密文1->明文2 解密算法 解密算法 密钥2:e->解密算法:w 明文2:s->解密算法:n 解密算法:s->密文2:n

要求

  • 分组长度要足够大：太小难以抵御选择明文攻击
  • 密钥量要足够大：太小可以通过穷举破解
  • 密码变换足够复杂：除去穷举法不应该有其他有效方法
  • 加密解密运算简单：便于软硬件实现、性能好
  • 无数据扩展或压缩

设计思想

代换

每个明文元素或元素组被唯一地替换为相应的密文元素或元素组
替换内容，不替换顺序，类似于代换密码

置换

明文元素的序列被替换位该序列的一个置换，但没有元素的添加、删除、替换，只改变顺序，类似于置换密码
置换不能改变单个字符或置换块上的统计特性

扩散

明文的每一比特的变化应该尽可能多地影响到输出密文序列的变化，以便隐蔽明文的统计特性（雪崩效应）
尽可能使明文和密文之间的统计关系变得复杂，使得铭文的统计特征消散在密文里
常用的方法是让每一位密文尽可能多地被明文影响

混乱

在加解密变换过程中，明文、密钥以及密文之间的关系尽可能地复杂化，以防密码破译者采用解析法进行破译攻击，从而减少推测密钥的可能性
混乱应该是可逆的，分组密码算法应有复杂的非线性因素
使用简单的代替算法几乎无法增加混淆

乘积密码

依次使用两个或两个以上的基本密码，所得结果的密码强度将强于所有单个密码的强度。
通过混合使用扩散和混乱两种基本密码操作的组合变换，产生比各自单独使用更强大的密码系统。

SPN

使用多重 S 变换和 P 变换组合成的变换网络，是乘积密码的一种。基本操作是 S 变换（代换，S 盒）和 P 变换（置换，P 盒）
S 盒负责实现混乱、P 盒负责实现扩散
SPN 具有雪崩效应，输入的微小变化会导致输出的巨大变化

分组密码基本特点

  • 分组长度: 负责抵御选择明文攻击
  • 密钥长度: 抵御穷举攻击
  • 子密钥生成算法
    迭代分组算法的重要组成部分，从初始（种子）密钥产生格伦迭代要使用的子密钥算法
    • 需要简单、快速生成子密钥
    • 种子密钥的所有比特对每个子密钥比特的影响大致相同
    • 没有弱密钥，或弱密钥容易确定
  • 轮函数 F
    分组密码的核心，是分组密码中单轮加解密函数
    • 非线性
    • 可逆性
    • 雪崩效应
  • 迭代轮数
    一般而言，迭代轮数越高，越难以破解。过高的迭代轮数会使加解密性能下降，实际安全性增强却不明显。
    决定迭代轮数的准则：密码分析的难度大于简单穷举搜索攻击的难度

Feistel 密码（费斯妥密码）

长度为 nn 位的分组密码，共有 2n2^n 种不同的明文分组，不同变换的个数为 2n!2^n! 个，且由于加密是可逆的，因此明文分组和密文分组一一对应，称为可逆变换或非奇异变换
对于可以生成最大数量的加密映射映射明文分组的密码，称为理想分组密码
当 nn 很小的时候，可以很容易通过统计的方法进行批结，但这个脆弱性与替代密码无关，是因为分组密码规模太小

密码结构

明文共 2w2w 位，被平均分为 LL 和 RR 两部分
从密钥 KK 可以计算出子密钥 K×iK \times i ，子密钥与密钥之间互不相同
每轮操作都使用子密钥进行替代和置换操作，并重复多次得到最终密码

加密 解密
{Li+1=RiRi+1=Li⊕F(Ri,Ki)\left\{ \begin{aligned} &L_{i+1}=R_i \\ &R_{i+1}=L_i \oplus F(R_i,K_i) \end{aligned} \right. {Ri=Li+1Li=Ri+1⊕F(Li+1,Ki)\left\{ \begin{aligned} &R_i=L_{i+1} \\ &L_i=R_{i+1} \oplus F(L_{i+1},K_i) \end{aligned} \right.

费斯妥密码的结构可见下图，这里有一个很重要的的特点可以发现：无论F函数如何，费斯妥密码都是可逆的！

由 {Li+1=RiRi+1=Li⊕F(Ri,Ki)\left\{ \begin{aligned} &L_{i+1}=R_i \\ &R_{i+1}=L_i \oplus F(R_i,K_i) \end{aligned} \right. 联立可得 Ri+1=Li⊕F(Li+1,Ki)R_{i+1}=L_i \oplus F(L_{i+1},K_i) ，移项可得 Li=Ri+1⊕F(Li+1,Ki)L_i = R_{i+1} \oplus F(L_{i+1},K_i)，也即无论 FF 函数如何，费斯妥密码都可逆（可以稍微改动加密程序实现解密程序）

%3 f0 F or0 ⊕ f0->or0 k0 k0 f0->k0 f1 F or1 ⊕ f1->or1 k1 k1 f1->k1 f2 F or2 ⊕ f2->or2 k2 k2 f2->k2 f14 F or14 ⊕ f14->or14 k14 k14 f14->k14 f15 F or15 ⊕ f15->or15 k15 k15 f15->k15 s1 LE1 RE1 or0->s1:r s2 LE2 RE2 or1->s2:r s3 LE3 RE3 or2->s3:r s15 LE15 RE15 or14->s15:r s16 LE16 RE16 or15->s16:r s14 LE14 RE14 s17 LE17 RE17 s3->s14 ..... s14:r->f14 s14:l->or14 s14:r->s15:l s0 LE0 RE0 s0:r->f0 s0:l->or0 s0:r->s1:l s1:r->f1 s1:l->or1 s1:r->s2:l s2:r->f2 s2:l->or2 s2:r->s3:l s15:r->f15 s15:l->or15 s15:r->s16:l s16:r->s17:l s16:l->s17:r

特征

  • 分组长度：分组长度越高，安全性越高，但是会降低加解密速度。通常使用 64 位
  • 密钥长度：密钥越长，安全性越高，但会降低加解密的速度。通常使用 128 位
  • 迭代轮数：单论不能取得很好的安全性，而多轮可以。通常迭代 16 轮
  • 子密钥产生算法：子密钥产生越复杂，分析越难
  • 轮函数 F：论函数越复杂，抗攻击能力越强。轮函数不要求可逆
  • 快速加解密：为了避免硬件实现麻烦，加密算法很多使用软件实现，因此运算速度很重要
  • 简化分析难度：算法本身简洁更容易分析脆弱性

DES (Data Encryption Standard)

采用 6464 位分组长度和 5656 位密钥长度
将 6464 位输入经过一系列变换称为 6464 位的输出，解密和加密使用相同的密钥（属于对称加密）

DES 本身使用的是Feistel密码结构

加密算法

  • 输入：
    • 6464 位明文
    • 6464 位密钥（ 5656 位密钥内容 + 88 位校验）
  • 输出：
    • 6464 位密文
  • 加密步骤
    • 初始置换：进行初始化置换操作，重新排列明文
    • 分组: 将 6464 位的数据平均分成 3232 位的两部分
    • 生成子密钥
      • 对原 6464 位密钥进行置换 1，得到 5656 位结果
      • 将结果分为相同的两部分，分别 2828 位
      • 循环 1616 次得到 1616 个子密钥
    • 对两部分分别进行循环左移（移动位数由轮数决定）
    • 拼接两部分并进行置换 2，得到一个 4848 位子密钥
  • 16 轮函数操作：
    • 左部分为原本的右部分
    • 右部分为右部分与子密钥传入函数运算，并与左部分异或
      • 函数：
        • 将输入进行拓展置换
        • 置换结果与子密钥异或
        • 异或结果进行普通置换
  • 将最后的两部分互换后拼接
  • IP 逆置换：IP 置换的逆置换

解密算法

改变子密钥使用顺序，以及 IP 置换与逆置换

DES代码实现

更详细的 DES 实现细节可见DES 算法实现

DES 差分攻击

TODO: 待补全

DES 的互补性

选择明文攻击下，有 c1=Ek(m),c2=Ek(m)c_1=E_k (m),c_2=E_k (m) 由互补性有 cˉ2=Ekˉ(m)\bar{c}_2=E_{\bar{k}}(m)
在穷举搜索密钥时，如果输出密文是 c1c_1 ，则加密密钥就是所用的密钥；若输出密钥是 cˉ2\bar{c}_2， 则可知加密密钥是当前密钥的补。这样一次加密尝试，可以得知两个密钥是否是真正的密钥

互补性会使DES在选择明文攻击下所需工作量减半

多重 DES

由于 DES 本身不构成一个群，因此可以使用多重 DES 的方式来增加密码强度

双重 DES

使用密钥 k1k_1 加密明文得到密文 c1c_1，再次使用密钥 k2k_2 对 c1c_1 进行加密可得到密文 c2c_2，这种将明文通过两次加密得到密文 c2c_2 的过程称为双重 DES

一般而言，k1k_1 和 k2k_2 的密钥空间都为 2562^{56}，那么总的双重 DES 密钥空间应该为 21122^{112} ，但是实际上并非如此！

对于 c=DESk2(DESk1(p)),p=DESk1−1(DESk2−1(c))c=DES_{k_2}(DES_{k_1}(p)),p=DES_{k_1}^{−1}(DES_{k_2}^{−1} (c))，有DESk1(p)=DESk2−1(c)DES_{k_1}(p)=DES_{k_2}^{−1}(c)
只需要枚举所有的 k1k_1 加密 pp 并存储结果，并枚举所有的 k2k_2 解密 cc 并存储结果，对比两者结果的相同值，那么对应的 k1k_1 和 k2k_2 就是实际的密钥。

二重DES并未将密钥长度提高到 256×256=21122^{56}×2^{56}=2^{112} 比特，而只有256+256=2572^{56}+2^{56}=2^{57} 比特

三重 DES

由于双重 DES 对安全性的提高并不显著，因此有了三重 DES
三重 DES 并非直接进行三次 DES 加密，而是使用两个或三个密钥进行加密、解密、加密过程（这里主要是为了实际使用时可以充分理由设备）

%3 P P E1 E1 P->E1 C C K11 K1 K11->E1 K2 K2 D D K2->D K12 K1 E2 E2 K12->E2 E1->D D->E2 E2->C
  • 优点：
    • 密钥长度增加到112或168位，克服了DES面对的穷举攻击
    • 增强了算法复杂度，提高了安全性
    • 由于DES已大规模应用，升级到3DES比更新算法成本小很多
    • DES比其他任何加密算法受到分析的时间都长的多，抗分析能力也更强
  • 缺点：
    • 3DES加解密速度较慢
    • 虽然密钥长度增加了，但明文长度没变，与密钥长度的增长不匹配

雪崩效应

明文和密钥的微笑改变会对密文产生巨大的影响
设计时应该遵循严格雪崩效应准则(SAC)：对于所有的 ii 和 jj，它要求若 SS 盒的输入的任意一位 ii 发生变化，输出的任意一位 jj 发生变化的可能性为 12\frac{1}{2}

性质

攻击方式 效果
针对算法攻击 S 盒目前没有致命弱点
计时攻击 DES 目前能很好抵抗计时攻击

流密码

流密码中每个加密数据流的一位或一个字节
Vigenere 密码和 Vernam 属于古典流密码的经典例子
位流发生器是一个由密钥控制的算法，必需产生在密码学意义上是强壮的位流，两个用户只需共享生成密钥就可以各自产生密钥流

参考资料