MARS加密算法

MARS加密算法是IBM公司提供的一个候选加密算法。那么接下来，我就给大家简单的介绍一下MARS加密算法。

一、MARS加密算法算法原理

密钥增加作为预白化处理，经8轮无密钥的向前混合，8轮有密钥的向前变换，8轮有密钥的向后变换，8轮无密钥的向后混合，以及作为后白化处理的密钥减法。16轮有密钥的转换称为密码核（cryptographic core），无密钥的迭代使用两个8x32 bit S-boxes、加、异或操作。此外，有密钥的迭代使用32-bit密钥乘法、数据相倚旋转和密钥加法。混合与核心迭代都被修改为Feistel结构的迭代，其中，1/4的数据块用于标识其它3/4的数据块。

二、密钥的生成

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

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)

三、明文加密

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]b0b1b2b3FirstTargetSecondTargetThirdTarget

输入的四块数据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位后作为下一轮的输入。

2、第二步密码核

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

D[0]D[1]D[2]D[3]SourceFirstTargetSecondTargetThirdTarget

该步骤中有一个称为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。

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操作的第一,第二,第三输出数返回.

4、第三步后向混合

把输入的128位数据分成四块D[0]，D[1]，D[2]，D[3]第一轮：

D[0]D[1]D[2]D[3]b0b1b2b3FirstTargetSecondTargetThirdTarget

输入的四块数据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位后作为下一轮的输入。

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]；

四、密文解密

用于密文解密的40个子密钥的生成和明文加密时的40个子密钥的生成方法相同。

1、第一步前向混合

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

D[0] += K[36]；

D[1] += K[37]；

D[2] += K[38]；

D[3] += K[39]；

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

第一轮：

D[0]D[1]D[2]D[3]b0b1b2b3FirstTargetSecondTargetThirdTarget

把D[0]，D[1]，D[2]，D[3]合并成128位的数据，循环左移32位后分成四块D[0]，D[1]，D[2]，D[3]其中D[0]作为源数据(Source)，剩下的3个作为目标数据，把D[0]循环右移24位后的结果返回给D[0]。

把32位的源数据D[0]分成8位的四块b0，b1，b2，b3

b0b1b2b3FirstTargetSecondTargetThirdTarget移动前D[0]D[1]D[2]D[3]移动后D[1]D[2]D[3]D[0]

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按位异或S0[b1]后加上S1[b2]的结果返回给ThirdTarget。

本步骤共进行8轮，在第一轮和第五轮中操作结尾处添加将Source加上FirstTarget的结果返回给Source的操作。在第二轮和第六轮中操作结尾处添加将Source加上ThirdTarget的结果返回给Source的操作。

2、第二步密码核

把输入的128位数据循环左移32位后分成四块D[0]，D[1]，D[2]，D[3]，其中D[0]作为源数据(Source)，剩下的3个作为目标数据，把Source循环右移13位的结果返回给Source，

D[0]D[1]D[2]D[3]SourceFirstTargetSecondTargetThirdTarget

把Source和对应两个子密钥(从第34个子密钥开始递减,本轮的输入子密钥K[34]，K[35]下一轮的子密钥就是K[32]，K[33])作为E-Fun(同加密)操作的输入参数，返回三个操作输出L，M，R，然后把这三个输出结果和三个目标数进行减法或异或操作，然后，合并D[0]，D[1]，D[2]，D[3]形成128位数据作为下一轮的输入。

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

前8轮中：

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

SecondTarge和M相减的结果返回给SecondTarget；

ThirdTarget和L相减的结果返回给ThirdTarget。

后8轮中：

FirstTarget 和 L相减的结果返回给FirstTarget；

SecondTarge和M相减的结果返回给SecondTarget；

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

3、第三步后向混合

把输入的128位的数据，循环左移32位后分成四块D[0]，D[1]，D[2]，D[3]。

D[0]D[1]D[2]D[3]b0b1b2b3FirstTargetSecondTargetThirdTarget

其中D[0]作为源数据(Source)，剩下的3个作为目标数据，把D[0]循环左移24位后的结果返回给D[0]，把32位的源数据D[0]分成8位的四块b0，b1，b2，b3。

b0b1b2b3FirstTargetSecondTargetThirdTarget移动前D[0]D[1]D[2]D[3]移动后D[1]D[2]D[3]D[0]

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

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

对FirstTarget的操作：

将FirstTarget减去S1[b1]后再按位异或S0[b0]的结果返回给FirstTarget。

对SecondTarget的操作：

SecondTarget减去S0[b2]的结果返回给SecondTarget。

对ThirdTarget的操作：

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

本步骤共进行8轮，在第3轮和第7轮的128位数据循环左移32位操作之后添加将Source减去FirstTarget的结果返回给Source的操作，.在第4轮和第8轮128位数据循环左移32位操作之后添加将Source减去ThirdTarget的结果返回给Source的操作。

4、 明文的输出

进行完上述的操作后,对生成的D[0]，D[1]，D[2]，D[3]与对应的起始4个子密钥进行减法操作还原成明文。

D[0] -= K[0]; D[1] -= K[1]；

D[2] -= K[2]; D[3] -= K[3]。