PBOC/EMV之DES算法

文章出處：http://bookmouse.cn 作者： 人氣： 發(fā)表時(shí)間：2012年02月19日

    Des是在金融電子領(lǐng)域用的比較多的一種加解密算法, 比如POS,ATM,智能IC卡等領(lǐng)域. 這個(gè)算法網(wǎng)上可以找到很多, 這篇文章只是自己整理一個(gè)版本，加入了一些自己的理解和注釋.

    關(guān)于什么是des算法以及歷史由來(lái)等知識(shí)就不在這里廢話了，直接入正題.

    首先從一個(gè)高的層次理解des的原理. 
    Result = Des(data, key, mode);
    把des看成一個(gè)函數(shù), 它有三個(gè)入?yún)?
    1 data, 是要加密或解密的數(shù)據(jù), 它是一個(gè)8字節(jié)的數(shù)據(jù), 如果不是8字節(jié)，可以通過(guò)補(bǔ)位的方式，補(bǔ)成8字節(jié)的倍數(shù).然后就可以分成多個(gè)數(shù)據(jù)段分別進(jìn)行加密或解密. 
    2 key, 這個(gè)是用來(lái)加密或解密的密鑰，它一定是一個(gè)8字節(jié)的數(shù)據(jù). 
    3 mode, 這個(gè)指示Des的工作模式，即加密或者解密
    而函數(shù)返回的result就是最終加密或解密的結(jié)果，這的長(zhǎng)度和data是一致的.

    下面就可以深入剖析一下Des具體做什么了. 它有兩個(gè)數(shù)據(jù)要處理，一個(gè)是data,一個(gè)是key.先來(lái)看看如何處理key

    Key是一個(gè)8字節(jié)的密鑰，在銀行系統(tǒng)中，這個(gè)key一般由一個(gè)主密鑰通過(guò)一個(gè)分散因子分散而來(lái)的. 可以表示如下:
    Key=k1k2k3…k64
    這個(gè)數(shù)據(jù)的第8, 16, 24, 32, 40, 48, 56, 64位(也就是每個(gè)字節(jié)的最高位)是用來(lái)做奇偶校驗(yàn)的，所以真正有效的密鑰位數(shù)只有56位.我們把奇偶校驗(yàn)位去掉, 剩下56位，新的key表示成如下:
    Key=k1k2k3…k56
    然后，把key分成相等的兩部分，A和B，即
    A=k1k2…k28
    B=k29k30..k56
    接著把A，B中的位的位置分別換一下,換位的規(guī)則按照下面的表

    也就是說(shuō)，A的第一位換成原來(lái)輸入的密鑰的第57位, 第二位換成輸入密鑰的第49位等等，同理B也是.
    最后的結(jié)果如下:
    A=k57k49…k36
    B=k65k55…k4
    A和B的位數(shù)沒(méi)變，還是28位

    下面要做的操作是把A，B進(jìn)行移位，循環(huán)左移，移動(dòng)的位數(shù)按照下面的表格進(jìn)行:

    Des的密鑰是經(jīng)過(guò)16次迭代生成的一組16個(gè)密鑰. 上面的表格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)在假設(shè)第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個(gè)位重新得到一個(gè)Key(i).

    也就是說(shuō)生成的密鑰key(i)的第1位，為原來(lái)C(i)的56位密鑰的第14位，key(i)的第2位，是原來(lái)C(i)的56位密鑰的第17位等，最終，生成一個(gè)48位的key(i)=k(i)1k(i)2….k(i)48.
    因?yàn)橐还灿?6次迭代, 所以共有key(0), key(1), key(2),….key(16)， 16組key.

    現(xiàn)在你知道了，最初傳入的8字節(jié)(64位)的密鑰最終會(huì)生成16個(gè)48位的密鑰.先不理這些密鑰怎么用, 下面自然會(huì)用到.

    說(shuō)完了key,該說(shuō)說(shuō)輸入的數(shù)據(jù)了. 數(shù)據(jù)也是8字節(jié)的數(shù)據(jù). 實(shí)際應(yīng)用中，數(shù)據(jù)往往不會(huì)剛好是8字節(jié)，這時(shí)可以把數(shù)據(jù)補(bǔ)齊成8的倍數(shù)，然后分段加密.

    假設(shè)輸入數(shù)據(jù)表示成如下:
    Data=d1d2d3….d64
    首先把64個(gè)位的位置換一下, 換位的規(guī)則按照下面的表:

    也就是說(shuō),新數(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

    迭代標(biāo)志:
    下面的操作要進(jìn)行迭代了，為了描述方便，前面加了一個(gè)迭代標(biāo)志. 
    然后，left不變，把right由32位擴(kuò)展為48位, 擴(kuò)展的規(guī)則由下面的表格指定:

    你可能奇怪為什么可以換一下位置怎么會(huì)由32位擴(kuò)展到48位呢，其實(shí)可以看到表格里有一些數(shù)據(jù)是重復(fù)的，也就是說(shuō)，48位的數(shù)據(jù)里有一些重復(fù)的. 新生成的right可表示如下:
    Right=d32d1d2….d1
    還記得前計(jì)算出的16組key嗎, 把key(1)取出來(lái)，跟right異或, 得到一個(gè)新的right,表示成如下:
    Right=r1r2r3…r48

    接著要把這個(gè)48位的right還原成32位，也就是進(jìn)行數(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