东南大学本科生毕业设计(论文)
以上的运算虽然不是标准的按字节的运算,但也是比较简单的计算部件。另外,对于
8,计算u的乘法逆元v可直接采用GF(2)上多项式的欧几里德扩充算法u?GF(2),u不等于0。
得: f(x)g(x)+m(x)h(x)=l (2-4)
其中u=f(x),v=g(x)。即f(x)g(x)=l(modm(x))或者u?v?1。 (2) 系统在GF(28)上的多项式
类似的,4个字节的向量可以表示为系数在GF(2s)上的次数小于4的多项式。 多项式加法就是对应系数相加: 换句话说,多项式的加法就是4字节向量的逐比特异或。
我们规定多项式的乘法运算必须要取模M(x)?x4?1,这样使得次数小于4的多 项式的乘积仍然是一个次数小于4的多项式。即:
(a3x?a2x?a1x?a0)?(b3x?b2x?b1x?b0)?d3x?d2x?d1x?d0 (2-5)
323232其中: d0?a0b0?a3b1? d1?a1b0?a0b1? d2?a2b0?a1b1? d3?a3b0?a2b1?我们将上述计算表示为:
a2b?2a3b?2a2b?2a1b?2a 1 b (2-6) a 2 b (2-7) a 3 b (2-8) ab (2-9) 0
(2-10)
注意到M(x)不是GF(28)上的不可约多项式(甚至也不是GF(2)上的不可约多项式),因此非O多项式的这种乘法不是群运算。不过在RIJNDAEL密码中,这种乘法运算只限于乘一个固定的有
32逆元的多项式b3x?b2x?b1x?b0。有如下定理:
324系数在GF(28)上的多项式a3x?a2x?a1x?a0是模x?1可逆的,当且仅当矩阵
(2-11)
7
东南大学本科生毕业设计(论文)
在GF(28)上可逆
证明如下:a3x3?a2x2?a1x?a0是模x4?1可逆的,当且仅当存在多项式
h3x?h2x?h1x?h0使得
32(a3x3?a2x2?a1x?a0)(h3x3?h2x2?h1x?h0)=1(modx4?1) (2-12)
因此有:
(a3x3?a2x2?a1x?a0)(h2x3?h1x2?h0x?h3)=x(modx4?1) (2-13) (a3x3?a2x2?a1x?a0)(h1x3?h0x2?h3x?h2)=x2(modx4?1) (2-14) (a3x3?a2x2?a1x?a0)(h0x3?h3x2?h2x?h1)=x3(modx4?1) (2-15)
又当且仅当存在多项式h3x3?h2x2?h1x?h0使得
(2-16)
(3) 设计思想
Rijndael密码的设计力求满足以下3条标准: ① 抗所有的已知攻击。
② 在多个平台上速度快,编码紧凑。 ③ 设计简单。
当前的大多数分组密码,其轮函数有Feistel结构或准Feistel结构,即将中间状态的部分比特不加改变的简单转置到其他的位置。RIJNDAEL没有这种结构,其轮函数是由三个不同的可逆一致变换组成的,称它们为三个“层”。所谓“一致变换”是指状态的每个比特都是用类似的方法进行处理的。不同层的特定选择大部分是建立在“宽轨迹策略”的应用基础上的;简单的说,“宽轨迹策略”就是提供抗线性密码分析能力的一种设计。为实现宽轨迹策略,轮函数三个层的每一层都有它自己的功能:
线性混合层: 确保多轮值上的高度扩散。
非线性层: 将具有最优的“最差情形非线性特性”的S盒并行使用。 密钥加层: 单轮子密钥简单的异或到中间状态上,实现一次性掩盖。
在第一轮之前,应用了一个初始密钥加层。这一设计的用意很简单,就是为了使攻击者无法从明文端消去其他计算部件。
8
东南大学本科生毕业设计(论文)
为了使加密和解密算法在结构上更加接近,最后一轮的线性混合层与前面各轮的线性混合层不同。可以证明这种设计不以任何方式提高或降低该密码的安全性。
2.2.2 字节运算(位运算)
有限域中的元素可以才用不同方式描述,在这里我们采用特征多项式描述。一个字节
a7a6a5a4a3a2a1a0可以看作是一个系数属于{0,1}的多项式:
根据取值的不同,共有256个字节和256个多项a7x+a6x+a5x+a4x+a3x+a2x+a1x?a0。
式一一对应。例如某字节为16进制数57H(二进制数表示为01010111),其对应的多项式为
x?x?x?x?1。
64217654321定义两个字节的和为这两个字节逐位异或所得到的值。例如,0x57?0x83?0xd4,即“01010111”+“10000011”=“11010100”。
定义两个字节的乘积为他们所对应的多项式的乘积,再与一个8阶的不可约的二进制多项式m(x)相模。不可约的多项式是在GF(28)上除了1和自身外,不存在其他因子,其中
m(x)= x8?x4?x3?x?1 。例如,0x57?0x83?0xc1,即
(x6?x4?x2?x1?1)(x7?x?1) (2-18)
= x13?x11?x9?x8?x7?x7?x5?x3?x2?x?x6?x4?x2?x?1 = x13?x11?x9?x8?x5?x3?x6?x4?x2?1
= (x?x?x?x?x?x?x?x?x?1)mod(x?x?x?x?1)
=x?x?1 (2-19)
2.2.3 四字节运算
和上述定义类似,一个四字节字{ a3a2a1a0}( ai为一个字节)和一个次数小于4的多项式
a3x?a2x?a1x?a0对应。
321311985364284376定义两个字的加法为对应多项式相应系数之和,即
a(x)= a3x?a2x?a1x?a0, b(x)?b3x?b2x?b1x?b0 (2-20) a(x)?b(x)?(a3?b3)x?(a2?b2)x?(a1?b1)x?(a0?b0) (2-21)
323232定义两个字的乘法为对应的两个多项式相乘再模d(x)= x?1,则
4 9
东南大学本科生毕业设计(论文)
a(x)?b(x)modd(x)?c(x)?c3x?c2x?c1x?c0 (2-22)
32c0?(a0?b0)?(a3?b1)?(a2?b2)?(a1?b3) (2-23) c1?(a1?b0)?(a0?b1)?(a3?b2)?(a2?b3) (2-24) c2?(a2?b0)?(a1?b1)?(a0?b2)?(a3?b3) (2-25) c3?(a3?b0)?(a2?b1)?(a1?b2)?(a0?b3) (2-26)
用矩阵表示为,
(2-27)
2.3 加密算法的四种主要工作模式
一种加密算法模式通常由基本加密算法、某种可选的反馈机制以及一些算术或逻辑运算组合而成,它构成了安全性算法的基础。模式中所包含的运算是简单易行的,因为算法的安全性依赖于基本加密算法,而并不依赖于算法模式。选择何种算法模式不会对算法所提供的安全性造成影响。
在信息安全领域中存在着四种最重要的加密算法模式,它们分别被称为电子编码本模式(Electronic CodeBook,ECB)、密码分组链接模式(Cipher BlockChaining,CBC)、密码反馈模式(Cipher Feedback,CFB)和输出反馈模式(Output Feedback,OFB)。前两种模式工作于分组密码之上,后两种模式是将分组密码视为流密码进行运算的算法模式。下面我将重点介绍本论文采用的ECB模式,并顺带简介其它模式。 (1) ECB模式(电子密码本)
电子编码本模式是最简单的一种算法模式。在这种模式下,待加密的明文被划分为等长的分组(Block),常见的分组长度为64比特或128比特,对每一个这样的分组使用相同的密钥进行独立的加密(见图2-1)。
10
东南大学本科生毕业设计(论文)
明文分组1明文分组2密钥加密密钥加密? ?密钥加密第一步密文分组1第二步密文分组2第n步图2-1 电子编码本模式的加密过程密文分组n明文分组3
信息接收者在接收到密文后,以同样的长度对密文进行分组,再使用与加密过程中相同的密钥进行解密,即可从密文中恢复出明文。在ECB模式中,内容相同的明文分组永远被加密为内容相同的密文分组,反之亦然,所以从理论上可以构造一个由明文分组及其对应密文分组构成的电子编码本(实质上是一个由二元组(明文分组、密文分组)构成的集合),这也是这种模式名字的由来。假设分组长度为128比特,那么电子编码本中最多可包含2128项,这个数字对于计算和存储来说都是一个很大的数目。还需指明的一点就是,每一个不同的密钥都对应着一个不同的电子编码本。
ECB模式的优点是易于实现,每一个明文分组可被独立地乱序加密,不必按照原文顺序进行。但由于对所有的明文分组使用相同的密钥进行加密,相同的明文分组被加密为相同的密文分组,这就为攻击者提供了蛛丝马迹特别在明文较长,分组数目较多,同一分组重复出现概率较高的情况下尤为明显。所以ECB模式只适用于加密分组少、分组重复出现概率低的短明文。 (2) CBC模式(密码分组链接)
CBC模式保证了即使在明文中同一分组多次重复出现,这些相同的明文分组也将被加密为各不相同的密文分组,从而克服ECB模式中固定分组映射和分组重复所带来的隐患。为了达到这一目标,在CBC模式中引入了一种被称为反馈(Feedback)的安全性增强机制:前一个明文分组的加密结果被反馈到(链接)当前分组的加密过程中,换句话说,就是每一个分组的加密结果都被用来调整和修正对下一个分组的加密。每个密文分组不仅仅依赖于产生它的明文分组,还依赖于它前面的所有明文分组。
在CBC模式中,一个明文分组被加密后,其结果被存储在反馈寄存器中,在下一个明文分组被加密之前,将反馈寄存器中的内容与待加密的明文分组进行异或运算,运算的结果作为下一次加密的输入,其结果又被存储在反馈寄存器中,再与下一个明文分组进行异或运算,依此类推,直至整个明文加密结束。解密时,一个密文分组被解密,该密文分组被存储在反馈寄存器中,在下一个密文分组被解密后,将解密结果与反馈寄存器中的内容进行异或运算,接着下一个密文分组又被存储在反馈寄存器中,依此类推,直至整个密文解密结束。
CBC模式可以保证属于同一明文的、内容相同的分组被加密为各不相同的密文分组,但是两个内容部分或全部相同的明文仍有可能被加密为相同的密文。为了避免发生此种情况,我们在对
11