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明文加密
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位后作為下一輪的輸入.

下圖顯示了移位前后的對比.



這樣本輪的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個作為目標數據



該步驟中有一個稱為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],其中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位后作為下一輪的輸入.
下圖顯示了移位前后的對比.



這樣本輪的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];




2.3 密文解密

用于密文解密的40個子密鑰的生成和明文加密時的40個子密鑰的生成方法相同.

2.3.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]合并成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

 

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.3.2第二步密碼核

　　把輸入的128位數據循環左移32位后分成四塊D[0],D[1],D[2],D[3],其中D[0]作為源數據(Source),剩下的3個作為目標數據, 把Source循環右移13位的結果返回給Source,



　　把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