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

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])<<<3)^(4*i+j);*/}for ( r = 0 ; r < 4 ; r++){for ( i = 0; i < 15 ;i++){/*T[i] = T[i]+ S[low 9 bits of T[(i-1)%15]])<<<9;*/}}for ( i = 0 ; i < 10 ; i++){/*T[10*j+i] = T[4*i%15];*/}

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

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];
结果作为第一轮操作的输入数据.
第一轮:

这样本轮的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个作为目标数据

2.2.3 E-Fun操作
该操作利用输入的"种子"数据-D,和两个加密子密钥K1和K2生成3个输出数据.
定义三个临时变量L,M,R
◆ 把D(输入的种子数据)循环右移13位后的结果赋给R
◆ 把D和K1加操作的结果赋给M
◆ 取M的低9位作为s-box的索引找到替代数赋给L
◆ 把R和K2乘操作的结果作循环左移5位后的值返回给R
◆ 把L和R按位异或的结果返回给L
◆ 取R的低五位的值,把M循环左移这个值后的结果返回给M
◆ 把R循环左移5位后的结果返回给R
◆ 把L和R按位异或的结果返回给L
◆ 取R的低五位的值,把L循环左移这个值后的结果返回给L
把L,M,R作为E-Fun操作的第一,第二,第三输出数返回.

2.2.4 第三步后向混合
把输入的128位数据分成四块D[0],D[1],D[2],D[3]第一轮:

输入的四块数据D[0],D[1],D[2],D[3],其中D[0]作为源数据(Source),剩下的3个作为目标数据,把32位的源数据D[0]分成8位的四块b0,b1,b2,b3
b0和b2作为数组下标从S1中寻找s-box替换数:S1[b0],S1[b2]
b1和b3作为数组下标从S0中寻找s-box替换数:S0[b1],S0[b3]
对FirstTarget的操作:
FirstTarget按位异或S1[b0]后的结果返回给FirstTarget
对SecondTarget的操作:
SecondTarget减去S0[b3]的结果返回给SecondTarget
对ThirdTarget的操作:
ThirdTarget减去S1[b2]后与S0[b1]按位异或的结果返回给ThirdTarget.
对Source的操作:
Source循环左移24位后的结果返回给Source.
把D[0],D[1],D[2],D[3]合并成128位的数据,循环左移32位后作为下一轮的输入.
下图显示了移位前后的对比.