对于分组密码的介绍,主要涵盖一些常见的分组密码构造,如Feistel和SPN结构,以及常用的分组密码算法(DES/AED/SM4)和模式(CBC/CFB/ECB/OFB/CTR)。

基本概念

分组密码定义

分组加密(英语:Block cipher),又称分块加密或块密码,是一种对称密钥算法。它将明文分成多个等长的模块(block),使用确定的算法和对称密钥对每组分别加密解密。分组加密是极其重要的加密协议组成,其中典型的如DES和AES作为美国政府核定的标准加密算法,应用领域从电子邮件加密到银行交易转帐,非常广泛。

分组密码设计原则

扩散(diffusion)和扰乱(confusion)是影响密码安全的主要因素。扩散的目的是让明文中的单个数字影响密文中的多个数字,从而使明文的统计特征在密文中消失,相当于明文的统计结构被扩散。

扰乱是指让密钥与密文的统计信息之间的关系变得复杂,从而增加通过统计方法进行攻击的难度。扰乱可以通过各种代换算法实现。

设计安全的分组加密算法,需要考虑对现有密码分析方法的抵抗,如差分分析、线性分析等,还需要考虑密码安全强度的稳定性。此外,用软件实现的分组加密要保证每个组的长度适合软件编程(如8、16、32……),尽量避免位置换操作,以及使用加法、乘法、移位等处理器提供的标准指令;从硬件实现的角度,加密和解密要在同一个器件上都可以实现,即加密解密硬件实现的相似性。

块加密中,明文块作为一个整体被处理,并用于产生长度相等的密文块。

分组密码构造

基本操作

  1. IP置换,分为初始IP置换与逆置换。初始IP置换为将明文块的位进行换位,其置换表示固定的。初始置换表为8*8的表格,第一位58表示该位置存放明文中的第58位字符。第1位字符已经变换到40位的位置。如果进行初始置换,则必须进行逆初始置换,逆初始置换的实现和初始置换一样,只是置换表不同而已。

  2. XOR异或:如果a、b两个值不相同,则异或结果为1。如果a、b两个值相同,异或结果为0。

a⊕b = (¬a ∧ b)(a ∧¬b)
  1. 移位:
<<,有符号左移位,将运算数的二进制整体左移指定位数,低位用0补齐。
>>,有符号右移位,将运算数的二进制整体右移指定位数,整数高位用0补齐,负数高位用1补齐
  1. P置换:简单的位置置换,只是简单地把一位换成另一位,不进行扩展和压缩。经过P置换,32位的输入得到32位的输出。

  2. S盒:一种非线性代换。在DES中,S盒是唯一的非线性部分,DES的安全强度主要取决于S盒的安全程度。S盒运算其实是一个查表运算。在E盒的扩展之后得到了48位的数据,将其和48位的子密钥进行异或运算,这是密钥参与运算的步骤。将其分成8个组,每组6个,送到8个S盒中去。每一个S盒都是一个6位输入4位输出的结构,也就是说,48位输入到8个S盒会得到4*8=32位的输出。6位输入到8位输出的映射关系如下表所示,其中,第一位和最后一位作为行号,第二位到第五位最为列号。例如,101100,则行号为10=2,列号为0110=6。查得(2,6)=2,化成二进制位0010。注意,8个S盒的映射关系各不相同。

Feistel 结构

对于Feistel网络结构,其加密核心在与F函数的选定,不同的F函数就是遵循Feistel结构的不同的加密算法(如DES),一个好的F函数对于加密效果至关重要,一般情况下,F函数需要满足以下几点:

  1. 不要求可逆:即不求F函数有反函数;
  2. 非线性;
  3. 混乱性;
  4. 扩散性;
  5. 雪崩性:即随着轮数增加其加密效果雪崩式增强;
  6. 比特独立性:一个bit的加密结果不依赖于其他bit。

Feistel结构安全性:

如果轮函数是一个加密安全伪随机函数,以Ki为种子,三轮就足以使分组密码成为伪随机排列,而4轮足以使其成为“强”伪随机排列。

SPN代替置换网络结构

SPN主要依赖的基本技术为代换与置换,是一种迭代密码方案。其迭代过程的设计核心思想如下:

  • 使用密钥扩展算法将输入的一个密钥扩展为多个子密钥(Subkey)
  • 每轮使用一个子密钥进行加密
  • 上一轮的输入作为下一轮的输出,也就是自身迭代

SPN的安全需求主要有以下两点:

  • 混乱性:密钥和明文密文间有复杂的依赖
  • 扩散:单个密钥或明文的变化影响到更多的密文

SPN网络结构的加密过程由n轮组成,对于每一轮需要进行分操作如下:

  • 白化:子密钥和明文异或
  • S盒代换:将明文分为m组,每组长度为l,按一定规则πs(z)进行代换,代换规则称为S盒
  • P盒置换:代换后进行置换操作,存放置换规则的称为P盒
  • 在多轮中,上一轮输出为下一轮输入,需要和新的子密钥进行异或操作。

分组密码算法

DES

DES全称为Data Encryption Standard,即数据加密标准,是一种使用密钥加密的块算法。DES解密算法与加密算法共用相同的算法过程。两者的不同之处在于解密时的子密钥Ki的使用顺序与加密时的顺序相反。也就说,加密的子密钥使用顺序为K1K2……K16,那么解密时的使用顺序就是K16K15……K1。DES的密钥长度为56,块长度为64,一共16轮。下面为DES的结构。

其中,关键在于F函数,其F函数的流程如下:

  1. 将64bit的明文右半部分即32bit扩展为48bit:采用的是4个bit一组,分为8组,每一组前后各加1bit(增加的bit数=218=16bit)。其增加按照下表进行(虚线以外的为增加的bit所在位置,如:第一组前是32,即在第一组前加一个bit为整个右半部分的32bit的第32位的bit值{0,1}):

  1. 得到的48bit扩充信息,和子密钥Ki进行异或操作,得到48bit的结果;
  2. 将扩充信息和子密钥异或后的结果进行压缩(48bit压缩到32bit),压缩的方式是经过S盒(4*16的矩阵)进行替换,S盒函数是经过严格计算获得的,其S盒的替换表与流程如下所示:

  1. 置换运算P(经过一个P盒进行置换,IP置换和P盒置换中,表中的数字代表新数据中此位置的数据在原数据中的位置,在P盒置换中,没有校验码的位置,即去除了校验码):指的是将32bit压缩后的信息进行bit置换操作,改换位操作目的是打乱其原有排序规律(F函数的混乱性原则)。P盒与S盒的硬件设计规律如下图所示(P盒是打乱原有01序列,S盒是译码器+P盒+编码器构成的(以8-3线为例)):

在DES的整个过程中,子密钥的生成也同样重要。DES算法共需要16轮的迭代运算,每轮迭代运算使用一个子密钥,共需要16个子密钥。子密钥是从用户输入的64位初始密钥生成的。用户输入的密钥有64位,其中有8位用于奇偶校验,分别位于第8,16,24,32,40,48,56,64位。奇偶校验用于检查密钥K的产生和分配以及存储的过程中是否发生了置换的错误,所以DES实际的密钥长度只有56位。

子密钥的生成过程如下:

  1. 输入的种子密钥K(64bits)首先经过一个PC-1置换j进行重排。PC-1置换得到一个56位的输出,经过置换后将不会再有奇偶校验位并且顺序也被打乱,再将这个56位的结果的前28位作为C0,后28位作为D0。下面为置换盒。

  1. 在计算第i轮迭代所使用的子密钥时,首先对Ci-1和Di-1进行循环左移,左移的位数与迭代的轮数对应与下表,分别得到Ci和Di

  1. 再将得到的CiDi作为PC-2置换的输入,从56位中选取48位作为子密钥

另外,在DES的发展中,不断向AED进行过渡,从而催生了3DES,它使用3条56位的密钥对数据进行三次加密。是DES的一个更安全的变形。它以DES为基本模块,通过组合分组方法设计出分组加密算法。比起最初的DES,3DES更为安全。

该方法使用两个密钥,执行三次DES算法,加密的过程是加密-解密-加密,解密的过程是解密-加密-解密。

  • 3DES加密过程为:C=Ek3(Dk2(Ek1§))
  • 3DES解密过程为:P=Dk1(EK2(Dk3©))

3DES采用两个密钥进行三重加密,其主要目的和好处在于:

  • 两个密钥合起来有效密钥长度有112bit,可以满足商业应用的需要,若采用总长为168bit的三个密钥,会产生不必要的开销。
  • 加密时采用加密-解密-加密,而不是加密-加密-加密的形式,这样有效的实现了与现有DES系统的向后兼容问题。因为当K1=K2时,三重DES的效果就和原来的DES一样,有助于逐渐推广三重DES。
  • 三重DES具有足够的安全性,还没有关于攻破3DES的报道。

AES

自DES 算法公诸于世以来,学术界围绕它的安全性等方面进行了研究并展开了激烈的争论。在技术上,对DES的批评主要集中在以下几个方面:

  1. 作为分组密码,DES 的加密单位仅有64 位二进制,这对于数据传输来说太小,因为每个分组仅含8 个字符,而且其中某些位还要用于奇偶校验或其他通讯开销。
  2. DES 的密钥的位数太短,只有56 比特,而且各次迭代中使用的密钥是递推产生的,这种相关必然降低密码体制的安全性,在现有技术下用穷举法寻找密钥已趋于可行。
  3. DES 不能对抗差分和线性密码分析。
  4. DES 用户实际使用的密钥长度为56bit,理论上最大加密强度为256。DES 算法要提高加密强度(例如增加密钥长度),则系统开销呈指数增长。除采用提高硬件功能和增加并行处理功能外,从算法本身和软件技术方面都无法提高DES 算法的加密强度。

因此,在分组加密算法的研究中,又推出了AES(高级加密标准)。

AES在1997年提出,安全性相当于3DES,并且比3DES快。明文分组的长度为128位即16字节,密钥长度可以为16,24或者32字节(128,192,256位)。根据密钥的长度,算法被称为AES-128,AES-192或者AE-256。AES的整个加密过程大致为:对明文,先进行轮密钥加,然后进行轮运算,每轮中分别进行字节代换、行移位、列混合、轮密钥加,最后一轮为字节代换、行移位、轮密钥加。下图为其加解密流程:

其中,涉及到几个运算:

  1. 字节代换:把该字节的高4位作为行值,低4位作为列值,取出S盒或者逆S盒中对应的行的元素作为输出

  1. 行移位:左右循环移位操作,正行移位为左循环移位操作。当密钥长度为128比特时,状态矩阵的第0行左移0字节,第1行左移1字节,第2行左移2字节,第3行左移3字节,如下图所示,逆变换则相反:

  1. 列混合:通过矩阵相乘来实现,经行移位后的状态矩阵与固定的矩阵相乘,得到混淆后的状态矩阵,如下图的公式所示,逆变换中,乘的矩阵和正变换中矩阵的乘积正好为单位矩阵:

SM4/SMS4

借用本科一位老师的话,一个国家密码学的发展与否,在某种程序上与核武器的发展是相当的,不管是在军事、商业还是其他用途中,如何保证信息的安全是十分重要的,而这便促使国家需要能够自己发展属于自己的密码算法,内部的一些发展咱也不懂,至少从商用密码来看,国密还是在不断发展的。而SM4和SMS4,则是其中的一部分。

2012年3月,国家密码管理局正式公布了包含SM4分组密码算法在内的《祖冲之序列密码算法》等6项密码行业标准。与DES和AES算法类似,SM4算法是一种分组密码算法。SM4采用非对称 Feistel结构,其分组长度为128bit,密钥长度也为128bit。加密算法与密钥扩展算法均采用32轮非线性迭代结构,以字(32位)为单位进行加密运算,每一次迭代运算均为一轮变换函数F。SM4算法加解密算法的结构相同,只是使用轮密钥相反,其中解密轮密钥是加密轮密钥的逆序。

SM4基本运算:

  1. 模2加:⊕,32 比特异或运算
  2. 循环移位:<<< i ,把32位字循环左移i 位

基本密码部件:

  1. 非线性字节变换S盒:起混淆作用,8位输入,8位输出。本质上是8位的非线性置换。以输入的高半字节为行号,低半字节为列号,行列交叉点 以输入的高半字节为行号,低半字节为列号,行列交叉点处的数据即为输出。 处的数据即为输出。设输入为"ef",则行号为e,列号为f,于是S盒的输出值为表中第 e 行和第 f 列交叉点的值,即 列交叉点的值。设输入为a,输出为b,S盒运算可表示为:
b=S_Box(a)
  1. 非线性字变换τ :起混淆作用,其实是4个S盒进行并行置换,为32位字的非线性变换,

  1. 字线性部件L变换:其扩散作用,32位输入,32位输出,输入为B,输出为C,其运算规则如下:
C=L(B)=B⊕(B<<<2)(B<<<10)(B<<<18)(B<<<24)
  1. 字合成变换T:由非线性变换τ 和线性变换L 复合而成,先S盒变换,后L变换:
T(X)=L(τ(X))

SM4轮函数F

  • 输入数据:(X0,X1,X2,X3),128位,四个32位字。
  • 输入轮密钥:rk ,32位字。
  • 输出数据:32位字。
  • 轮函数F :F(X0,X1,X2,X3,rk)= X0 ⊕T( X1⊕ X2⊕ X3⊕rk)

SM4加密与解密

SM4的加密过程图下图所示:

其中,包含加密变换与反序变换两种:

  • 输入明文:(M0 , M1 , M2 , M3)=(X0 , X1 , X2 , X3), 128位,四个字。
  • 输入轮密钥:rki ,i=0,1,…,31,共32个轮密钥。
  • 输出密文:(Y0,Y1,Y2,Y3),128位,四个字。
  • 算法结构: 轮函数 算法结构:轮函数32轮迭代,每轮使用一个轮密钥。 轮迭代,每轮使用一个轮密钥。
  • 加密变换:Xi+4=F(Xi,Xi+1,Xi+2,Xi+3,rki)= Xi ⊕T( Xi+1⊕ Xi+2⊕ Xi+3⊕rki), i = 0,1…31
  • 反序变换:(Y0,Y1,Y2,Y3)=(X35,X34,X33,X32)

SM4密码算法是对合的,因此解密与加密算法相同,只是轮密码算法是对合的,因此解密与加密算法相同,只是轮
密钥的使用顺序相反:

  • 输入密文:Y0,Y1,Y2,Y3)=(X35,X34,X33,X32)
  • 输入轮密钥:rki ,i=31,30,29…,1,0 共32个轮密钥。
  • 输出明文:(X0 , X1 , X2 , X3)
  • 算法结构:轮函数进行32轮迭代,每轮使用一个轮密钥。
  • 解密变换:Xi = F(Xi+4,Xi+3,Xi+2,Xi+1,rki)= Xi+4 ⊕ T( Xi+3 ⊕ Xi+2 ⊕ Xi+1 ⊕rki ), i=31,…1,0
  • 反序变换:(X1,X2,X3,X4) =(M0 , M1 , M2 , M3)

分组加密模式

ECB电子密码本模式

将数据按8个字节一段进行DES加密或解密后连接在一起组成密文或明文,最后不足8字节的补足。其有以下特点:

  • 简单,有利于并行计算,误差不会被传送;
  • 不能隐藏明文的模式;
  • 可能对明文进行主动攻击。

CBC密文分组链接模式

CBC模式在ECB模式基础上进行了改进,将前一个密文分组与当前明文分组的内容混合起来进行加密,这样就可以避免ECB模式的弱点。

加密步骤如下:

  1. 首先将数据按照8个字节一组进行分组得到D1D2…Dn(若数据不是8的整数倍,用指定的PADDING数据补位)
  2. 第一组数据D1与初始化向量VI异或后的结果进行DES加密得到第一组密文C1(初始化向量I为全零)
  3. 第二组数据D2与第一组的加密结果C1异或以后的结果进行DES加密,得到第二组密文C2
  4. 之后的数据以此类推,得到Cn
  5. 按顺序连为C1C2C3…Cn即为加密结果。

解密是加密的逆过程,步骤如下:

  1. 首先将数据按照8个字节一组进行分组得到C1C2C3…Cn
  2. 将第一组数据进行解密后与初始化向量VI进行异或得到第一组明文D1(注意:一定是先解密再异或)
  3. 将第二组数据C2进行解密后与第一组密文数据进行异或得到第二组数据D2
  4. 之后依此类推,得到Dn
  5. 按顺序连为D1D2D3…Dn即为解密结果。

这里注意一点,解密的结果并不一定是我们原来的加密数据,可能还含有你补得位,一定要把补位去掉才是你的原来的数据。

CBC模式具有以下特点:

  • 不容易主动攻击,安全性好于ECB,适合传输长度长的报文,是SSL、IPSec的标准。
  • 每个密文块依赖于所有的信息块,明文消息中一个改变会影响所有密文块
  • 发送方和接收方都需要知道初始化向量
  • 加密过程是串行的,无法被并行化(在解密时,从两个邻接的密文块中即可得到一个平文块。因此,解密过程可以被并行化)。

CFB密文反馈模式

类似于CBC,可以将块密码变为自同步的流密码;工作过程亦非常相似,CFB的解密过程几乎就是颠倒的CBC的加密过程。

在CFB模式中,需要使用一个与块的大小相同的移位寄存器,并用IV将寄存器初始化。然后,将寄存器内容使用块密码加密,然后将结果的最高x位与平文的x进行异或,以产生密文的x位。下一步将生成的x位密文移入寄存器中,并对下面的x位平文重复这一过程。解密过程与加密过程相似,以IV开始,对寄存器加密,将结果的高x与密文异或,产生x位平文,再将密文的下面x位移入寄存器。

另外,这种模式与CBC相似,平文的改变会影响接下来所有的密文,因此加密过程不能并行化;而同样的,与CBC类似,解密过程是可以并行化的。

OFB输出反馈模式

输出反馈模式(Output feedback, OFB)可以将块密码变成同步的流密码。它产生密钥流的块,然后将其与明文块进行异或,得到密文。与其它流密码一样,密文中一个位的翻转会使平文中同样位置的位也产生翻转。这种特性使得许多错误校正码,例如奇偶校验位,即使在加密前计算而在加密后进行校验也可以得出正确结果。

每个使用OFB的输出块与其前面所有的输出块相关,因此不能并行化处理。然而,由于明文和密文只在最终的异或过程中使用,因此可以事先对IV进行加密,最后并行的将明文或密文进行并行的异或处理。

可以利用输入全0的CBC模式产生OFB模式的密钥流。这种方法十分实用,因为可以利用快速的CBC硬件实现来加速OFB模式的加密过程。

OFB模式加密过程具体如下:

  1. 将移位寄存器初始化为IV,假设移位寄存器长度为len比特;
  2. 移位寄存器经加密器和秘钥加密得到Ki(i=1,2,3…);
  3. 明文长度为m(m≤len)比特,与K1的高m比特异或,得到m比特密文;
  4. 将移位寄存器左移m位,将刚刚得到的Ki的高m位填充到移位寄存器的低m位;
  5. 重复步骤2-4,直到所有明文被加密完成。

CTR计数器模式

Counter mode,计数器模式。CTR模式与OFB模式类似,它通过加密“计数器”的连续值来生成下一个密钥流块。计数器可以是任何保证长时间不会产生重复序列的函数。使用简单的确定性输入函数曾经是有争议的;批评者认为,“故意将密码系统暴露在已知的系统输入中是一种不必要的风险。”然而,目前CTR模式被广泛接受,任何问题都被认为是底层分组密码的一个弱点,无论其输入是否存在系统偏差,这种分组密码都是安全的。

CTR模式具有类似于OFB的特性,但在解密期间也允许随机访问属性。CTR模式非常适合在可以并行加密块的多处理器机器上运行。此外,它不存在影响OFB的短周期问题。

CTR模式加密过程如下图所示。其中Nonce和前文所述的初始向量IV一样,由于密文需要Nonce和计数器Counter共同计算所得,故如果计数器出错,则不能得到正确的密文。

CTR 模式被广泛用于 ATM 网络安全和 IPSec应用中,相对于其它模式而言,CTR模式具有如下特点:

  • 硬件效率:允许同时处理多块明文 / 密文。
  • 软件效率:允许并行计算,可以很好地利用 CPU 流水等并行技术。
  • 预处理:算法和加密盒的输出不依靠明文和密文的输入,因此如果有足够的保证安全的存储器,加密算法将仅仅是一系列异或运算,这将极大地提高吞吐量。
  • 随机访问:第 i 块密文的解密不依赖于第 i-1 块密文,提供很高的随机访问能力。
  • 可证明的安全性:能够证明 CTR 至少和其他模式一样安全(CBC, CFB, OFB, …)
  • 简单性:与其它模式不同,CTR模式仅要求实现加密算法,但不要求实现解密算法。对于 AES 等加/解密本质上不同的算法来说,这种简化是巨大的。
  • 无填充,可以高效地作为流式加密使用。

参考

《武汉大学-密码学》