当前位置: 王朝网络 >> vc >> IBM的MARS加密算法实现(上)

IBM的MARS加密算法实现(上)

王朝vc·作者佚名 2006-01-17

IBM的MARS加密算法实现(上)

一、背景知识

1977年颁布的数据加密标准DES算法。其56位长的密码空间在芯片技术和计算技术高速发展的今天，越来越不适应安全需求。1997年9月美国国家标准技术研究所(NIST)提出了征求新的加密标准---AES

（Advanced Encryption Standard）的建议，作为一种取代DES的二十世纪加密标准技术。其目标是：（1）执行速度快；（2）易于设计；（3）从大型计算机到智能IC卡（CPU卡）都可实现。1998年8月第一次AES会议（AES1）上，宣布了来自12个国家的15种候选AES算法。于1999年8月第二次AES会议（ARD2）上，从中筛选出5个候选算法:

Algorithm Author(s)

(1) MARS IBM (US)

(2) RC6 RSA Laboratories(US)

(3) Rijndael John Danemen,Vincent Rijmen(Belgium)

(4) Serpent Ross Anderson(UK),Eli Bihan(Israel),Lars Knudsen(Nornay)

(5) Twofish Bruce Schneier,John Kelsey,Doug Whiting,David Wagner,Chris

Hall,Nids Ferguson

经过大量的分析及评估后，NIST队伍最终选择了Rijndael。这是在考虑安全，性能，效率，易用和灵活等诸多方面做的一种权衡选择,正如NIST在其报告中称："所有这五种算法对AES都很安全".本文将介绍一下由IBM公司提出的MARS算法的原理和部分笔者编写的算法实现代码.

二、算法原理

密钥增加作为预白化处理，经8轮无密钥的向前混合，8轮有密钥的向前变换，8轮有密钥的向后变换，8轮无密钥的向后混合，以及作为后白化处理的密钥减法。16轮有密钥的转换称为密码核（cryptographic

core），无密钥的迭代使用两个8x32 bit S-boxes、加、异或操作。此外，有密钥的迭代使用32-bit密钥乘法、数据相倚旋转和密钥加法。混合与核心迭代都被修改为Feistel结构的迭代，其中，1/4的数据块用于标识其它3/4的数据块。

约定:

D[] :存放4个32位明文的容器,在加密操作完成后用于存放密文

K[]:存放40个32位密钥的容器

S[]:s-box,512个32位的不同数组成,其中前256个由S0指出,后256个由S1指出

所有的数组下标从0开始计数.

本文中提及的加法是模232加,减法是模232减,乘法是模232乘

<<<表示循环左移

^ 表示按位异或

%取模

2.1密钥的生成

MARS算法支持128~448位变长密钥,定义一个临时容器ULONG32 T[15]用于存放用户输入的密钥,

T[0,1…n] = K[0,1…n]

T[n] = n ;

T[n+1,…14] = 0 ;

其中n是用户输入密钥的长度(4字节为单位).

然后按照下面的算法进行操作:

for ( j = 0 ; j < 4 ; j++)

{

for ( i = 0; i < 15 ;i++)

{

/*T[i] ^= ((T[(i-7)%15]^T[(i-2)%15])

最后我们需要修正那些在E-Fun操作中用作乘数的密钥也就是子密钥数组中的K[5],K[7],K[9],…K[35],要求他们的二进制表示形式中没有连续10个以上(含10个)的0或1.

需要修正的密钥为K[i] = K0K1K2…K30K31

保留K[i]的最低两位的值 n = K[i]&0x3,

把K[i]的最低两位置1 w = K[i] | 0x3 ,

产生掩码M:

最低两位置1后的K的二进制表示中如果含有10以上连续的0或1,那么将这些连续位置1,其他的位置0,然后把最低的两位和最高位置0,最后把连续位(1或0单独算)的起始位和中止位置0.

例如:

产生掩码后,我们利用n值作为s-box的索引取得一个替代值,这个s-box含有4个32位的元素,每个元素的二进制表示不含7个(含7个)连续的1或0,MARA算法推荐的s-box为

ULONG32 B[4] = { 0xa4a8d57b , 0x5b5d193b , 0xc8a8309b , 0x73f9a978 }

然后利用如下算式得出K[i]:

K[i] = w ^ (( B[n] <<< ( low 5 bits of K[i-1]) & M)

2.2明文加密

2.2.1 第一步前向混合

输入的128位明文分成四块D[0],D[1],D[2],D[3],选取生成的40个密钥的前四个分别与上述四块数据进行加操作

D[0] += K[0];

D[1] += K[1];

D[2] += K[2];

D[3] += K[3];

结果作为第一轮操作的输入数据.

第一轮:

D[0]

D[1]

D[2]

D[3]

FirstTarget

SecondTarget

ThirdTarget

输入的四块数据D[0],D[1],D[2],D[3],其中D[0]作为源数据(Source),剩下的3个作为目标数据,把32位的源数据D[0]分成8位的四块b0,b1,b2,b3

b0和b2作为数组下标从S0中寻找s-box替换数:S0[b0],S0[b2]

b1和b3作为数组下标从S1中寻找s-box替换数:S1[b1],S1[b3]

对FirstTarget的操作:

FirstTarget按位异或S0[b0]后的加上S1[b1]的结果返回给FirstTarget

对SecondTarget的操作:

SecondTarget加上S0[b2]的结果返回给SecondTarget

对ThirdTarget的操作:

ThirdTarget按位异或S1[b3]的结果返回给ThirdTarget.

对Source的操作:

Source循环右移24位后的结果返回给Source.

把D[0],D[1],D[2],D[3]合并成128位的数据,循环左移32位后作为下一轮的输入.

下图显示了移位前后的对比.

FirstTarget

SecondTarget

ThirdTarget

移动前

D[0]

D[1]

D[2]

D[3]

移动后

D[1]

D[2]

D[3]

D[0]

这样本轮的Source变成了下一轮的ThirdTarget

本轮的FirstTarget成了下一轮的Source

本轮的SecondTarget成了下一轮的FirstTarget

本轮的ThirdTarget成了下一轮的SecondTarget

本步骤共进行8轮,在第一轮和第五轮中对Source作循环右移24位操作前先作Source加上ThirdTarget的结果然后返回给Source的操作.在第二轮和第六轮中对Source作循环右移24位操作前先作Source加上FirstTarget的结果然后返回给Source的操作.

2.2.2第二步密码核

把输入的128位数据分成四块D[0],D[1],D[2],D[3] ,其中D[0]作为源数据(Source),剩下的3个作为目标数据

D[0]

D[1]

D[2]

D[3]

Source

FirstTarget

SecondTarget

ThirdTarget

该步骤中有一个称为E-Fun(见下一节)的操作,把Source和对应两个子密钥(从第5个子密钥开始递增,本轮的输入子密钥K[4],K[5]下一轮的子密钥就是K[6],K[7])作为参数输入,返回三个操作输出L,M,R,然后把这三个输出结果和三个目标数进行加法或异或操作,然后把Source循环左移13位,合并D[0],D[1],D[2],D[3]形成128位数据,循环左移32位后作为下一轮的输入.

本步骤共进行16轮,假定E-Fun的第一个输出数为L,第二个输出数为M,第三个输出数为R

前8轮中,

FirstTarget 和 L相加的结果返回给FirstTarget

SecondTarge和M相加的结果返回给SecondTarget

ThirdTarget和R按位异或的结果返回给ThirdTarget

后8轮中:

FirstTarget 和 R按位异或的结果返回给FirstTarget

SecondTarge和M相加的结果返回给SecondTarget

ThirdTarget和L相加的结果返回给ThirdTarget

2.2.3 E-Fun操作

该操作利用输入的"种子"数据-D,和两个加密子密钥K1和K2生成3个输出数据.

定义三个临时变量L,M,R