本文示例源代码或素材下载

　　一、背景知识

　　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单独算)的起始位和l止位置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],其中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位后作为下一轮的输入.

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

　　

D[0]				D[1]	D[2]	D[3]
b0	b1	b2	b3	FirstTarget	SecondTarget	ThirdTarget

	b0	b1	b2	b3	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

　　◆ 把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]
b0	b1	b2	b3	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作为数组下标从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.</p>

　　对Source的操作:

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

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

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

　　

	b0	b1	b2	b3	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轮,在第3轮和第7轮进行任何操作前先作Source减去ThirdTarget的结果然后返回给Source的操作. 在第4轮和第8轮进行任何操作前先作Source减去FirstTarget的结果然后返回给Source的操作.

　　2.2.5 密文的输出

　　进行完上述的操作后,对生成的密文D[0],D[1],D[2],D[3]与对应的最后4个子密钥进行减法操作形成最终的密文.

　　D[0] -= K[36]; D[1] -= K[37];

　　D[2] -= K[38]; D[3] -= K[39];

　　(待续...)