PBOC/EMV之DES密钥算法

文章出处：http://www.singbon.com 作者：中国一卡通网 收编   人气： 发表时间：2011年10月09日

    Des是在金融电子领域用的比较多的一种加解密算法, 比如POS,ATM,智能IC卡等领域. 这个算法网上可以找到很多, 这篇文章只是自己整理一个版本，加入了一些自己的理解和注释.

    关于什么是des算法以及历史由来等知识就不在这里废话了，直接入正题.

    首先从一个高的层次理解des的原理.
    Result = Des(data, key, mode);
    把des看成一个函数, 它有三个入参:
    1 data, 是要加密或解密的数据, 它是一个8字节的数据, 如果不是8字节，可以通过补位的方式，补成8字节的倍数.然后就可以分成多个数据段分别进行加密或解密.
    2 key, 这个是用来加密或解密的密钥，它一定是一个8字节的数据.
    3 mode, 这个指示Des的工作模式，即加密或者解密
    而函数返回的result就是最终加密或解密的结果，这的长度和data是一致的.

    下面就可以深入剖析一下Des具体做什么了. 它有两个数据要处理，一个是data,一个是key.先来看看如何处理key

    Key是一个8字节的密钥，在银行系统中，这个key一般由一个主密钥通过一个分散因子分散而来的. 可以表示如下:
    Key=k1k2k3…k64
    这个数据的第8, 16, 24, 32, 40, 48, 56, 64位(也就是每个字节的最高位)是用来做奇偶校验的，所以真正有效的密钥位数只有56位.我们把奇偶校验位去掉, 剩下56位，新的key表示成如下:
    Key=k1k2k3…k56
    然后，把key分成相等的两部分，A和B，即
    A=k1k2…k28
    B=k29k30..k56
    接着把A，B中的位的位置分别换一下,换位的规则按照下面的表 

    也就是说，A的第一位换成原来输入的密钥的第57位, 第二位换成输入密钥的第49位等等，同理B也是.
    最后的结果如下:
    A=k57k49…k36
    B=k65k55…k4
    A和B的位数没变，还是28位

    下面要做的操作是把A，B进行移位，循环左移，移动的位数按照下面的表格进行: 

    Des的密钥是经过16次迭代生成的一组16个密钥. 上面的表格i表示是第几次迭代，下面的数据表示该次迭代密钥循环左移的位数. 比如第1次迭代循环左移1位，第3次迭代循环左移2位等. 而第i次迭代用的输入数据是第i-1次迭代的结果. 如果用&(i)表示第i次循环左移操作，则可用如下的公式表示迭代操作:
    第一次:
    A(1)=&(1)A
    B(1)=&(1)B 
    第i次:
    A(i)=&(i-1)A 
    B(i)=&(i-1)B

    现在假设第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.

    现在你知道了，最初传入的8字节(64位)的密钥最终会生成16个48位的密钥.先不理这些密钥怎么用, 下面自然会用到.



说完了key,该说说输入的数据了. 数据也是8字节的数据. 实际应用中，数据往往不会刚好是8字节，这时可以把数据补齐成8的倍数，然后分段加密.

假设输入数据表示成如下:
Data=d1d2d3….d64
首先把64个位的位置换一下, 换位的规则按照下面的表: 

    也就是说,新数据的第1位是原数据的第58位, 新数据的第2位是原数据的第50位，依次类推. 新生成的数据如下:
    Data=d58d50d42….d7
    为了方便继续下面的步骤，把上面的数据表示为:
    changeData=d1d2d3….d64
    把changeData分成相等的两部分，即left, right.
    Left=d1d2…d32
    Right=d33d34…d64
 
    迭代标志:
    下面的操作要进行迭代了，为了描述方便，前面加了一个迭代标志.
    然后，left不变，把right由32位扩展为48位, 扩展的规则由下面的表格指定: 

    你可能奇怪为什么可以换一下位置怎么会由32位扩展到48位呢，其实可以看到表格里有一些数据是重复的，也就是说，48位的数据里有一些重复的. 新生成的right可表示如下:
    Right=d32d1d2….d1
    还记得前计算出的16组key吗, 把key(1)取出来，跟right异或, 得到一个新的right,表示成如下:
    Right=r1r2r3…r48 

    接着要把这个48位的right还原成32位，也就是进行数据的压缩,压缩的步骤如下:
    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位，表示成整数范围为0~63, 所以把它们换成整数都能在上面各自对应的表格中找到一个4位的值. 举个例子:
    a=57, 在表1中找到57对应的位置是0x3, 则a=0x3.
    经过这样变换后，a~h都从原来的6位变为4位，再把它们拼起来，生成一个32的数,表示为
    Right=r1r2…r32
    再把这个32位的数，各个位换一下位置，换位的规则按照下面的表格: 

    也就是新数据的第1位为原数据的16位，依次类推. 新生成的数据为:
    Right=r16r7…r25
    然后，把这个right和left异或，结果给right, right原来的值给left. 这样得到一对新的left和right.

    还记得前面的<迭代标志>吗，用新计算的left和right重新回到<迭代标志>,做同样的操作，一共迭代16次, 每一次都是用前一次得到的left和right, 但要记得中间有一步要用到key(i)做异或, 这个i就是迭代的次数.
    假设第16迭代后，得到的分别是left(16), right(16), 则新的数据为
    Data=right(16)left(16), 注意这里不是left(16)right(16).
    新的data是一个64位的数, 按照下面的表格，调整一下各个位的位置,

    Data=d40d8…d25.
    这个data就是加密后的数据。

    最后说一下如何解密，des是一种对称的加密算法，也就是加密，解密是同一人密钥, 算法也相同，唯一不同的就是, 在数据迭代时，第一次用key(16),第二次用key(15),依次类推，一直到key(1). 

    另外，现在有一些des算法的变种，也比较流行，典型的一个就是3des.它的原理可以简单描述如下:
    有三个56位长度的密钥(8字节), 分别为key1, key2, key3.
    第一步，用key1对数据加密.
    第二步，用key2解密.
    第三步, 用key3加密

    三个key如果不相等, 相当于密钥长度是168位，这样就更加安全。