3.2 分组密码概述 — lmn

1年前发布

900

3.2 分组密码概述 – lmn

分组密码(block cipher)是密码系统的基本组成部分之一。分组密码的数学模型是将明文消息编码表示后的数字（简称明文数字）序列，划分成长度为n的组（可看成长度为n的矢量），每组分别在密钥的控制下变换成等长的输出数字（简称密文数字）序列。

与流密码不同的是，是对数据流进行连续处理的算法，每次加密数字流的一位或一字节。
分组密码对128位明文进行加密生成128位密文，是128位数据分组加密的可逆加密函数。128位也称为分组密码的分组长度。密钥是长度通常为128或256的位串。可以将分组密码看作一个非常大的映射表，用于明文到密文的映射。

加密：E(K,p)或者Ek(p)
解密：D(K,p)或者Dk(p)

分组密码的主要任务是提供数据保密性，也可以用到在许多方面，如构造伪随机数生成器、序列密码、认证码和哈希函数等。

0x01 分组密码背景

20世纪70年代中期后，基本上是围绕DES进行的，推出了一些类似的算法，例如：LOKI，FEAL，GOST等。
20世纪90年代，人们对DES算法研究更加深入，特别是差分密码分析（differential cryptanalysis）和线性密码分析（linear cryptanalysis）的提出，迫使人们不得不研究新的密码结构。

IDEA密码打破了DES类密码的垄断局面，随后出现了SQUARE、SHARK、SAFER-64等采用了结构非常清晰的代替—置换（SP）网络，每一轮由混淆层和扩散层组成，从理论上给出了最大差分特征概率和最佳线性逼近优势的界，证明了密码对差分密码分析和线性密码分析的安全性。

目前分组密码所采用的整体结构可分为Feistel结构（例如CAST—256、DEAL、DFC、E2等）、SP网络（例如Safer+、Serpent等）及其他密码结构（例如Frog和HPC）。

0x02 理想分组密码

理想分组密码的核心是随机置换，对于每个密钥值，分组密码都有一个随机置换，而且不同密钥对应的置换应该是完全独立的。

一个大小为128的分组密码含2128个元素，对应大小为2128的查找表。
实际中常将n分成较小的段，例如可选n=r*n0，其中r和nq都是正整数，将设计n个变量的代换变为设计r个较小的子代换，而每个子代换只有n0个输入变量。一般nq都不太大,

0x03 分组密码攻击

大部分分组密码攻击都为明文攻击，对于分组密码安全的定义覆盖了所有可能的攻击形式，唯密文攻击，已知明文攻击，选择明文攻击，相关密钥攻击等所有攻击。

相关密钥攻击，由Eli Biham于1993年首次提出，假设攻击者已知到加密函数位、未知密钥的情况下，通过这些函数密钥之间的相关性进行攻击。在实际系统中的不同密钥之间存在相关性。
选取一部分进行攻击，对剩余部分采用相关密钥攻击。

128位的密钥是足够长的，但是可能会遇到碰撞攻击，例如1.2 密码学研究重点中提到的生日攻击或中间人攻击。可以针对n位的安全等级，分组密码的长度采用2n位长，但很难遵循。

0x04 分组密码的一般模型

分组密码是将明文消息编码为二进制序列后，划分成固定大小的块(Block)，每块分别在密钥的控制下变换成二进制序列。明文编码后的二进制序列为x0,x1…xi，将其划分为若干固定长度的分组（Block,块）。考虑某个分组，分组在密钥的控制下变换为长度为q的密文分组。

其本质是一个从明文空间（长度为p的比特串集合）M到密文空间（长度为q的比特串的集合）C的映射，该映射由密钥确定。

分组密码的要求

分组长度要足够大
密钥量要足够大
密码变换足够复杂
加密和解密运算简单
无数据扩展或压缩

扩散和混淆

扩散

扩散是指明文的每–位(比特)尽可能多地影响密文的比特位，以隐蔽明文的统计特征。密钥的每一位(比特)也尽可能迅速地扩散到较多的密文比特中去。

混淆

混淆指在加密变换过程中明文、密钥以及密文之间的关系尽可能地复杂，以使密码分析者（敌手）无法分析出密钥。

Feistel密码结构

乘积密码指顺序地执行两个或多个基本密码系统，使得最后结果的密码强度高于每个基本密码系统产生的结果。
Feistel还提出了实现代换和置换的方法。其思想实际上是Shannon提出的利用乘积密码实现混淆和扩散思想的具体应用。

Feistel特性

分组大小：分组越大则安全性越高，但加密速度就越慢。分组密码设计中最为普遍使用的分组大小是64比特。
密钥大小：密钥越长则安全性越高，但加密速度就越慢。现在普遍认为64比特或更短的密钥长度是不安全的，通常使用128比特的密钥长度。
轮数：单轮结构远不足以保证安全性，但多轮结构可提供足够的安全性。典型地，轮数取为16。
子密钥产生算法：该算法的复杂性越大，则密码分析的困难性就越大。
轮函数：轮函数的复杂性越大，密码分析的困难性也越大。

0x05 置换的奇偶性

建立置换表步骤

通过索引i到值i的意义映射进行初始化表
重复交换条表的两个元素来创建置换

置换类型

奇置换：进行奇次数置换，对于一个给定的密钥，对所有可能的明文进行加密以提取置换，如果是奇置换可认为是理想分组密码，因为真正的分组密码不能进行奇置换
偶置换：进行偶次数置换

0x06 实际分组密码

设计一种新的分组密码很容易，但是设计出好的分组密码就十分困难。几乎所有的分组密码都由一个弱分组密码重复多次，每一次运算称为1轮，通过多次重复形成强分组密码。

分组密码方案

数字加密标准 (DES) – 1990 年代流行的分组密码。它现在被认为是一个“破碎的”分组密码，主要是因为它的小密钥大小。
Triple DES – 它是基于重复 DES 应用程序的变体方案。它仍然是一种受人尊敬的分组密码，但与可用的新的更快的分组密码相比效率低下。
高级加密标准 (AES) – 它是一种基于加密算法Rijndael的相对较新的分组密码，赢得了 AES 设计竞赛。
IDEA – 它是一个足够强大的块密码，块大小为 64，密钥大小为 128 位。许多应用程序使用 IDEA 加密，包括早期版本的 Pretty Good Privacy (PGP) 协议。由于专利问题，IDEA 方案的使用受到限制。
Twofish – 这种分组密码方案使用 128 位的块大小和可变长度的密钥。它是 AES 决赛选手之一。它基于较早的块密码 Blowfish，块大小为 64 位。
Serpent – 块大小为 128 位，密钥长度为 128、192 或 256 位的块密码，也是 AES 竞赛决赛选手。它比其他分组密码更慢但具有更安全的设计。

DES

数据加密标准（DES）是应用最广泛的一种分组密码算法，有56位密钥长度和64位分组长度。在进行大量数据运算时可采用3DES的分组加密算法，使用某种特殊顺序使用2个密钥执行3次DES加密流程。

数据加密标准（DES）是美国的一种由来已久的加密标准，它使用对称密钥加密法，并于1981年被ANSI组织规范为ANSI X.3.92。3DES（即Triple DES）是DES向AES过渡的加密算法，它使用3条56位的密钥对数据进行三次加密。是DES的一个更安全的变形。

3DES加密过程为：C=Ek3(Dk2(Ek1(P)))
3DES解密过程为：P=Dk1(EK2(Dk3(C)))

这是一轮DES加密，首先将明文进行IP置换，分为左右两个部分，为32位的L0与32位的R0。DES算法有16轮加密，为0，1，2 … 15，每一轮使用一个48位的轮密钥ki，这16个轮密钥从分组密码的56位种选择48位生成，通过轮函数f改变R0与L0的值。

32位R0首先通过扩展函数得到48位，与轮密钥进行异或，之后输入到S盒中通过非线性映射成为32位，之后与L0异或得到新的R1，进入下一轮加密。

DES算法的基本结构称为Feistel结构，每一轮通过L与F(Ki,R)的异或生成新的L，然后R与L进行交换。其中S盒、扩展函数、位变换函数通过结合实现了扩散功能。
扩散指输入函数的任意一位都会影响输出密文的许多位。

DES的互补性质

如果使用取反的密钥加密取反的明文数据，所得到的密文是原密文取反。

AES

高级加密标准（AES）采用了与DES不同的架构，没有采用Feistel结构。

最初由 NIST 于 2001 年创建，使用更有趣的名称 Rijndael 密码/算法（这个名字来自其发明者，比利时研究人员 Daemen 和 Rijmen），它已成为一种广泛使用和流行的公共加密标准，因为它对破坏尝试具有极强的弹性. AES 用于加密世界各地的机构、政府、银行和其他组织的绝密数据，被认为是现有最强大的加密方法之一。

首先输入16字节（128位）的明文数据，将明文与16字节的轮密钥进行异或操作，之后对特定的数据进行重新排列，使用先行混合函数进行异或运算得到输出结果。

整个AES算法约10-14轮，根据密钥的长度选择轮数。
AES的密钥长度有128位、192位、256位。

128位：加密10轮
192位：加密12轮
256位：加密14轮

AES优点

实现高速运算
对内存的需求低，适合于受限环境
分组长度和密钥长度设计灵活
AES标准支持可改变分组长度，分组长度可设定为32比特的任意倍数
加密和解密算法完全不同

Serpent

Serpent算法在很多方面与AES相反，更加注重安全，但速度只有AES的1/3。
Serpent是一种对称密钥分组密码，它是高级加密标准 (AES) 的选手，仅次于Rijndael。Serpent 由Ross Anderson、Eli Biham和Lars Knudsen设计。

与其他AES提交一样，Serpent的块大小为128位，并支持128、192或256位的密钥大小。该密码是一个32轮替换置换网络，在四个32位字块上运行。每一轮并行应用8个4位到4位S-box中的一个32次。Serpent的设计使得所有操作都可以使用32个1位切片并行执行。这最大限度地提高了并行性，但也允许使用在DES上执行的大量密码分析工作。Serpent被广泛认为对安全性采取了更保守的方法，选择了更大的安全余量。

Serpent 主页：https://www.cl.cam.ac.uk/~rja14/serpent.html

Twofish

Twofish和AES加密算法一样快，但安全性更高，Twofish和DES使用相同的结构：Feistel结构。
Twofish是一种对称密钥分组密码，分组大小为128位，密钥大小高达256 位。它是高级加密标准竞赛的五个之一，但没有被选为标准化。Twofish与较早的分组密码Blowfish相关。

Twofish 的显着特点是使用预先计算的依赖于密钥的S-box，以及相对复杂的密钥调度。n位密钥的一半用作实际加密密钥，而n位密钥的另一半用于修改加密算法（密钥相关的S盒）。Twofish 借鉴了其他设计的一些元素；例如，来自SAFER密码系列的伪 Hadamard 变换(PHT) 。Twofish 使用与 DES 相同的Feistel结构。

在大多数软件平台上，对于 128 位密钥，Twofish 比Rijndael（为高级加密标准选择的算法）稍慢，但对于 256 位密钥来说要快一些。

参考文章：
https://www.researchgate.net/figure/Advanced-Encryption-Standard-AES-Algorithm_fig5_321587376
https://wenku.baidu.com/view/f3bc927fb90d6c85ec3ac6f9.html
https://community.fandom.com/wiki/Community_Central

评分

欢迎为Ta评分

赏点小钱