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];*/} 最后我们需要修正那些在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.1 第一步前向混合
输入的128位明文分成四块D[0],D[1],D[2],D[3],选取生成的40个密钥的前四个分别与上述四块数据进行加操作
