PBOC/EMV之DES密鑰算法
文章出處：http://m.botanicstilllife.com 作者：中國一卡通網(wǎng) 收編 人氣： 發(fā)表時間：2011年10月09日
Des是在金融電子領(lǐng)域用的比較多的一種加解密算法, 比如POS,ATM,智能IC卡等領(lǐng)域. 這個算法網(wǎng)上可以找到很多, 這篇文章只是自己整理一個版本，加入了一些自己的理解和注釋.
關(guān)于什么是des算法以及歷史由來等知識就不在這里廢話了，直接入正題.
首先從一個高的層次理解des的原理.
Result = Des(data, key, mode);
把des看成一個函數(shù), 它有三個入?yún)?
1 data, 是要加密或解密的數(shù)據(jù), 它是一個8字節(jié)的數(shù)據(jù), 如果不是8字節(jié)，可以通過補位的方式，補成8字節(jié)的倍數(shù).然后就可以分成多個數(shù)據(jù)段分別進行加密或解密.
2 key, 這個是用來加密或解密的密鑰，它一定是一個8字節(jié)的數(shù)據(jù).
3 mode, 這個指示Des的工作模式，即加密或者解密
而函數(shù)返回的result就是最終加密或解密的結(jié)果，這的長度和data是一致的.
下面就可以深入剖析一下Des具體做什么了. 它有兩個數(shù)據(jù)要處理，一個是data,一個是key.先來看看如何處理key
Key是一個8字節(jié)的密鑰，在銀行系統(tǒng)中，這個key一般由一個主密鑰通過一個分散因子分散而來的. 可以表示如下:
Key=k1k2k3…k64
這個數(shù)據(jù)的第8, 16, 24, 32, 40, 48, 56, 64位(也就是每個字節(jié)的最高位)是用來做奇偶校驗的，所以真正有效的密鑰位數(shù)只有56位.我們把奇偶校驗位去掉, 剩下56位，新的key表示成如下:
Key=k1k2k3…k56
然后，把key分成相等的兩部分，A和B，即
A=k1k2…k28
B=k29k30..k56
接著把A，B中的位的位置分別換一下,換位的規(guī)則按照下面的表
也就是說，A的第一位換成原來輸入的密鑰的第57位, 第二位換成輸入密鑰的第49位等等，同理B也是.
最后的結(jié)果如下:
A=k57k49…k36
B=k65k55…k4
A和B的位數(shù)沒變，還是28位
下面要做的操作是把A，B進行移位，循環(huán)左移，移動的位數(shù)按照下面的表格進行:
Des的密鑰是經(jīng)過16次迭代生成的一組16個密鑰. 上面的表格i表示是第幾次迭代，下面的數(shù)據(jù)表示該次迭代密鑰循環(huán)左移的位數(shù). 比如第1次迭代循環(huán)左移1位，第3次迭代循環(huán)左移2位等. 而第i次迭代用的輸入數(shù)據(jù)是第i-1次迭代的結(jié)果. 如果用&(i)表示第i次循環(huán)左移操作，則可用如下的公式表示迭代操作:
第一次:
A(1)=&(1)A
B(1)=&(1)B
第i次:
A(i)=&(i-1)A
B(i)=&(i-1)B
現(xiàn)在假設第i次迭代后, 生成的A,B如下:
A(i)=A(i)1A(i)2….A(i)28
B(i)=B(i)1B(i)2….B(i)28
然后，把A,B合并, 即
C(i)=A(i)B(i), 顯然，C(i)有56位, 然后按照下面的表格，取出這56位中的48個位重新得到一個Key(i).
也就是說生成的密鑰key(i)的第1位，為原來C(i)的56位密鑰的第14位，key(i)的第2位，是原來C(i)的56位密鑰的第17位等，最終，生成一個48位的key(i)=k(i)1k(i)2….k(i)48.
因為一共有16次迭代, 所以共有key(0), key(1), key(2),….key(16)， 16組key.
現(xiàn)在你知道了，最初傳入的8字節(jié)(64位)的密鑰最終會生成16個48位的密鑰.先不理這些密鑰怎么用, 下面自然會用到.
說完了key,該說說輸入的數(shù)據(jù)了. 數(shù)據(jù)也是8字節(jié)的數(shù)據(jù). 實際應用中，數(shù)據(jù)往往不會剛好是8字節(jié)，這時可以把數(shù)據(jù)補齊成8的倍數(shù)，然后分段加密.
假設輸入數(shù)據(jù)表示成如下:
Data=d1d2d3….d64
首先把64個位的位置換一下, 換位的規(guī)則按照下面的表:
也就是說,新數(shù)據(jù)的第1位是原數(shù)據(jù)的第58位, 新數(shù)據(jù)的第2位是原數(shù)據(jù)的第50位，依次類推. 新生成的數(shù)據(jù)如下:
Data=d58d50d42….d7
為了方便繼續(xù)下面的步驟，把上面的數(shù)據(jù)表示為:
changeData=d1d2d3….d64
把changeData分成相等的兩部分，即left, right.
Left=d1d2…d32
Right=d33d34…d64
迭代標志:
下面的操作要進行迭代了，為了描述方便，前面加了一個迭代標志.
然后，left不變，把right由32位擴展為48位, 擴展的規(guī)則由下面的表格指定:
你可能奇怪為什么可以換一下位置怎么會由32位擴展到48位呢，其實可以看到表格里有一些數(shù)據(jù)是重復的，也就是說，48位的數(shù)據(jù)里有一些重復的. 新生成的right可表示如下:
Right=d32d1d2….d1
還記得前計算出的16組key嗎, 把key(1)取出來，跟right異或, 得到一個新的right,表示成如下:
Right=r1r2r3…r48
接著要把這個48位的right還原成32位，也就是進行數(shù)據(jù)的壓縮,壓縮的步驟如下:
1 把right分成8部分,每部分6位,表示如下:
a=r1r2…r6
b=r7r8..r12
c=r13r14..r18
d=r19r20…r24
e=r25r26..r30
f=r31r32..r36
g=r37r38..r42
h=r43r44..r48
下面再給出8個表格:
上面這8個表格，分別對應a~h, 注意a~h都是6位，表示成整數(shù)范圍為0~63, 所以把它們換成整數(shù)都能在上面各自對應的表格中找到一個4位的值. 舉個例子:
a=57, 在表1中找到57對應的位置是0x3, 則a=0x3.
經(jīng)過這樣變換后，a~h都從原來的6位變?yōu)?位，再把它們拼起來，生成一個32的數(shù),表示為
Right=r1r2…r32
再把這個32位的數(shù)，各個位換一下位置，換位的規(guī)則按照下面的表格:
也就是新數(shù)據(jù)的第1位為原數(shù)據(jù)的16位，依次類推. 新生成的數(shù)據(jù)為:
Right=r16r7…r25
然后，把這個right和left異或，結(jié)果給right, right原來的值給left. 這樣得到一對新的left和right.
還記得前面的<迭代標志>嗎，用新計算的left和right重新回到<迭代標志>,做同樣的操作，一共迭代16次, 每一次都是用前一次得到的left和right, 但要記得中間有一步要用到key(i)做異或, 這個i就是迭代的次數(shù).
假設第16迭代后，得到的分別是left(16), right(16), 則新的數(shù)據(jù)為
Data=right(16)left(16), 注意這里不是left(16)right(16).
新的data是一個64位的數(shù), 按照下面的表格，調(diào)整一下各個位的位置,
Data=d40d8…d25.
這個data就是加密后的數(shù)據(jù)。
最后說一下如何解密，des是一種對稱的加密算法，也就是加密，解密是同一人密鑰, 算法也相同，唯一不同的就是, 在數(shù)據(jù)迭代時，第一次用key(16),第二次用key(15),依次類推，一直到key(1).
另外，現(xiàn)在有一些des算法的變種，也比較流行，典型的一個就是3des.它的原理可以簡單描述如下:
有三個56位長度的密鑰(8字節(jié)), 分別為key1, key2, key3.
第一步，用key1對數(shù)據(jù)加密.
第二步，用key2解密.
第三步, 用key3加密
三個key如果不相等, 相當于密鑰長度是168位，這樣就更加安全。
