一、feistel密码结构
二、DES
DES算法简介
DES(Data Encryption Standard)是目前最为流行的加密算法之一。DES是对称的，也就是说它使用同一个密钥来加密和解密数据。
DES还是一种分组加密算法，该算法每次处理固定长度的数据段，称之为分组。DES分组的大小是64位，如果加密的数据长度不是64位的倍数，可以按照某种具体的规则来填充位。
从本质上来说，DES的安全性依赖于虚假表象，从密码学的术语来讲就是依赖于“混乱和扩散”的原则。混乱的目的是为隐藏任何明文同密文、或者密钥之间的关系，而扩散的目的是使明文中的有效位和密钥一起组成尽可能多的密文。两者结合到一起就使得安全性变得相对较高。
DES算法具体通过对明文进行一系列的排列和替换操作来将其加密。过程的关键就是从给定的初始密钥中得到16个子密钥的函数。要加密一组明文，每个子密钥按照顺序（1-16）以一系列的位操作施加于数据上，每个子密钥一次，一共重复16次。每一次迭代称之为一轮。要对密文进行解密可以采用同样的步骤，只是子密钥是按照逆向的顺序（16-1）对密文进行处理。
计算16个子密钥
1）密钥转换表：上面提到DES算法的第一步就是从初始密钥中计算得出16个子密钥。图示1展示了这个过程。DES使用一个56位的初始密钥，但是这里提供的是一个64位的值，这是因为在硬件实现中每8位可以用于奇偶校验，在软件实现中多出的位只是简单的忽略掉。要获得一个56位的密钥，可以执照表1的方式执行密钥转换。解释一下表1，按照从左往右从上往下的方式看，表格中每个位置P包含初始密钥中位在转换后的密钥中所占的位置。比如，初始密钥中的第57位就是转换后的密钥中的第1位，而初始密钥中的第49位则变成转换后的密钥中的第2位，以此类推...。（数据位的计数顺序按照从左到右从1开始的）
表1：DES中密钥的转换表（DesTransform[56]）
2）计算自子密钥：将密钥转换为56位后，接下来计算子密钥。首先，将56位的密钥分为两个28位的组。然后，针对每个子密钥，根据子密钥的序列值（也就是16个子密钥中的第几个）旋转这两组值（旋转的位数见表2），然后重新合并。之后，再按照表3所示对重组后的密钥进行置换，使56位的子密钥缩小为48位（注意表3只有48位，丢弃了8位）。这个排列过程就称为置换选择。
针对16个子密钥，每个子密钥重复一次该过程。这里的目的是保证将初始密钥中的不同位在每一轮排列后应用于加密的数据上。
表2：针对DES子密钥每一轮的旋转次数（Round轮，Rotations旋转次数）(DesRotations)
表3：DES子密钥的置换选择(Despermuted[48])
图1：在DES中计算子密钥的过程
加密和解密数据块
经过上述过程，我们已经准备好了子密钥。接着就可以加密和解密数据块了。图2展示了这个过程。
图2：DES中加密和解密数据块
从表4所示的方式置换64位的数据块开始，该置换过程称为初始置换。该过程并不会增加DES的安全性，但这种做法在16位和32位的总线出现之前将使得数据更容易加载到DES芯片中。虽然这种处理已经不合时宜，但该置换过程仍然保留以满足DES标准。
表4：DES中数据的初始置换（DesInitial[64]）
经过初始置换后，64位的数据块分为两个32位的组，L0和R0。
完成初始置换后，数据块将重复执行16轮一系列的操作。每一轮操作（i）的目的是计算出Li和Ri ，这些结果将用在下一轮操作中直到最终得到数据R16和L16。
每一轮以Li-1和Ri-1开始，然后根据表5所示进行扩展置换，将Ri-1从32位扩展到48位。该置换的主要目的是在加密数据的过程中制造一些雪崩效应，使用数据块中的1位将在下一步操作中影响更多位，从而产生扩散效果。
一旦扩展置换完成，计算出48位的结果值与这一轮子密钥Ki的异或值（XOR，符号计为⊕）。这将产生48位的中间值，记为Rint。
如果将E计为扩展置换的结果，则本轮到目前为止的操作可以表示为：
Rint = E（Ri-1) ⊕ Ki
表5：DES中数据块的扩展置换（DesExpansion[48]）
下一步，Rint 需要通过8个单独的S盒执行8次替换操作。每个S盒（j）从Rint的6j 到 6j+6 的位置取出6位，并为其在表6中查出1个4位的值，将该值写到缓冲区的4j位置处（如图3）。
图3：DES中的8个S盒
读表6，查找S盒（j）。通过前面取出的6位值，根据第1位和最后1位组成的2位值找到表6中的行号，而根据中间剩下的4位来确定表6中的列号。比如，在图3中，Rint中的第3个6位组是101011。因此，在表6中查找到的第3个S盒是9。因为行号等于112 = 3，列号等于01012 = 5（查表时从索引0开始计数）。S盒为数据增加了不确定性，除了给DES带来安全性外，没什么特别的。
表6：DES中数据块的S盒替换
一旦完成了S盒替换，得到的结果又变为一个32位的值。接下来再通过P盒来置换。如下表7所示。
表7：DES中数据块的P盒置换
到目前为止，我们把这一轮的操作想象为一个函数，一般记为f。如果 bj 代表Rint中的第j个6位组，Sj 代表第j个S盒，而P代表P盒置换，则该函数可以定义为：
f = P(S1(b1),S2(b2),...,S8(b8))
每一轮的最后一个操作是计算 f 的32位结果值与传入本轮操作的原始数据的左分组Li-1之间的异或值。
一旦完成，将左右两个分组交换然后开始下一轮。在最后一轮中，不用交换左右分组。把所有的步骤连起来，在每一轮中计算Li和Ri的步骤可以精确表示为：
Li = Ri-1
Ri = Li-1 ⊕ f(Ri-1,Ki)
当全部的16轮操作都结束后，将最后的右分组R16和最后剩下的左分组L16连接起来，组成一个64位的分组R16L16。（回顾一下，在最后一轮中左右分组并没有交换。最后的右分组在左边而最后的左分组在右边。）
最后一步是将R16L16按照表8所示的置换进行置换。简而言之，就是撤消之前的初始置换。 加密数据时，最终结果就是一个64位的密文，而当解密数据时，最终结果就是64位的明文了。
表8：DES中数据块的最终置换
DES的接口定义
des_encipher
void des_encipher(const unsigned char *plaintext, unsigned char *ciphertext, unsigned char *key);
返回值：无
描述：采用DES算法，将明文plaintext的一个64位的明文组加密。在key中指定64位的密钥（最后8位将被忽略掉，实际得到56位的密钥）。ciphertext是返回的64位的密文组。
由调用者负责管理ciphertext所需要的空间。要加密一段较大的数据，可以按照分组加密模式调用des_encipher。为了得到较高的效率，des_encipher可以重用之前的调用中计算出来的子密钥，这可以通过在之后的调用中将NULL传给key，以此来开启这种功能。
复杂度：O（1）
des_decipher
void des_decipher(const unsigned char *ciphertext, unsigned char *plaintext, unsigned char *key);
返回值：无
描述：采用DES算法将密文ciphertext的一个64位分组解密。该函数假设ciphertext包含的是通过des_encipher加密过的密文。在key中指定64位的密钥（最后8位将被忽略掉，实际得到56位的密钥）。plaintext是返回的64位的明文组。由调用者负责管理plaintext所需要的空间。要解密一大段的数据，可以按照分组加密模式调用des_decipher。为了获得较高的效率，des_decipher可以重用之前调用中计算出来的子密钥。可以在随后的调用中将NULL传给key，以此来开启这种功能。
复杂度：O（1）
DES算法的实现
考虑到DES算法中涉及的位操作很多，因此DES算法通常都是在硬件中实现。DES算法中的图表和术语（通过线、框画的流程图，以及诸如S盒、P盒这样的术语）使其更倾向于在硬件中实现，当然，软件实现也有它的价值所在。在软件开发中，通过几种基本的指令操作来帮助实现DES中的各种置换、转换以及替换操作都是很有效的。
des_encipher
函数des_encipher将明文的一个64位的明文分组通过DES算法加密。
由于DES的一个很好的特点是同样的过程既能用来加密数据也能用来解密数据，因此des_encipher只需要简单的调用des_main，而des_decipher同样也只需要调用des_main即可。
函数des_main通过使用其参数direction来确定到参数source提供的数据是明文还是密文。direction参数只是简单地修改子密钥的顺序。
在des_encipher中，direction设置为encipher。
函数des_main()首先检测参数key是否为NULL。这将允许des_encipher的调用者重用上一次调用时计算出来的子密钥。将子密钥数组subkeys声明为static类型。如果key不为NULL，将计算子密钥。
要计算子密钥，可以按照前面介绍过的步骤（计算16个子密钥）来执行。key的转换是通过函数permute来实现的，这里就是根据一个特定的表在一个缓冲区中置换位。假设表中的每个位置（i）上都存在一个值p，函数permute通过将位置p的位移动到位置（i）上来完成对传入的buffer的置换。
要置换密钥，将表Des_Transform（同表1）传给函数permute。必要的旋转操作可以通过调用位操作bit_rot_left来实现。该操作将buffer按照指定的位数向左旋转。每一轮要正确旋转28位的子密钥分组，将表Des_Rotations（同表2）中合适的元素传给bit_rot_left。通过调用permute，并把传入表Des_permuted（同表3），来对每一个子密钥做置换选择。
要加密一个数据块，首先要执行初始置换。为实现这一步，首先调用函数permute并将表Des_Initial（同表4）传入。然后，将数据分为两个32位的分组：lblk以及rblk。回顾一下，加密数据的大部分工作都是将一系列的操作重复执行16轮。每一轮的主要工作都花在计算函数（f）的值上，将值保存在fblk中。
每一轮操作开始时，将对rblk执行一个扩展置换。为了实现这个步骤，将调用函数permute，并把表Des_Expansion（同表5）传入。然后，通过调用位操作bit_xor来计算扩展后的rblk和某个适当的子密钥的异或值。无论是加密还是解密数据，与本轮操作相关的子密钥都需要参与执行。一旦完成了异或计算，将对结果执行一系列的S盒替换操作。Des_Sbox（同表6）定义了8个用于DES算法中的S盒。对于当前fblk中的每个6位分组，第1位和最后1位联合起来确定Des_Sbox中的行号，而中间的4位用来确定列号。最后执行P盒置换来完成函数f的计算。通过调用permute函数并传入表Des_Pbox（同表7）来实现这个步骤。计算出lblk与函数f的值的异或结果，并交换lblk和rblk来结束一轮的操作。
将上述过程重复16次，每轮一次。当全部16轮操作完成后，将rblk拷贝到target的前32位中，将lblk拷贝到之后的32位中（按照要求，最后一轮不交换lblk和rblk）。最终，通过调用permute并把Des_Final（同表8）传入来完成最后的置换操作。
des_encipher的时间复杂度是O（1），因为加密数据块的所有步骤都能在恒定的时间内完成。
des_decipher
函数des_decipher将一个64位的密文分组通过DES算法进行解密。同des_encipher一样，des_decipher实际通过调用des_main来完成解密任务，但这里direction需要设置为decipher。因此，des_decipher的工作方式同des_encipher一样，只是这里的子密钥需要以逆序的方式参与。具体来说，就是在des_main中，针对每一轮i（从0开始计数），参与计算的子密钥为subkeys数组中下标为（15-i）的元素。
des_decipher的时间复杂度为O（1），因为解密数据块中的所有步骤都可以在恒定的时间内完成。
DES处理比特，或者说二进制数字，我们知道，没四个比特构成一个十六进制数。DES加密一组64位的信息，也就是16个16进制数。为了完成加密，DES
DES秘钥获取：
我们取16进制秘钥K为：
K = 133457799BBCDFF1
我们可以得到他的二进制形式（1为0001,3为0011，依次类推，并且将没8位写成一组。这样每组的最后一位都没有被用上。）
K = 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001
创建16个子秘钥，每个长48比特
这个64位的秘钥首先根据表格PC-1进行变换。
表PC-1
| 57 | 49 | 41 | 33 | 25 | 17 | 9 |
| 1 | 58 | 50 | 42 | 34 | 26 | 18 |
| 10 | 2 | 59 | 51 | 43 | 35 | 27 |
| 19 | 11 | 3 | 60 | 52 | 44 | 36 |
| 63 | 55 | 47 | 39 | 31 | 23 | 15 |
| 7 | 62 | 54 | 46 | 38 | 30 | 22 |
| 14 | 6 | 61 | 53 | 45 | 37 | 29 |
| 21 | 13 | 5 | 28 | 20 | 12 | 4 |
由于上表中第一个元素为57，这将使元秘钥的第57位变换为新秘钥K+的第一位。同理，元秘钥的第49位变换为新秘钥的第2位，，，元秘钥的第4位变换为新秘钥的最后一位，注意元秘钥中只有56位会进入新秘钥，上表也只有56个元素。
比如，对于原秘钥：
K = 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001
我们将得到56位新秘钥：
K+ = 1111000 0110011 0010101 0101111 0101010 1011001 1001111 0001111
然后，我们将这个密钥拆分为左右两个部分，C0和D0，每半边都有28位。
比如，对于新密钥，我们得到：
C0 = 1111000 0110011 0010101 0101111
D0 = 0101010 1011001 1001111 0001111
对于相同定义的C0和D0，我们现在创建16个块Cn和Dn 1<=n<=16.
每一对Cn和Dn都是由前一对Cn-1和Dn-1移位而来。具体来说，对于n=1,2,3，。。。，16，在前一轮移位的结果上，进行左移操作。什么叫左移？左移指的是将除第一位外的所有为往左移一位，将第一位移动至最后一位。
这意味着，比如说，C3和D3是C2和D2移位而来的，具体来说，通过2次左移位，C16和D16则是由C15和D15通过1次左移得到的。在所有情况下，一次左移就是将所有比特往左移动一位。使的一位后的比特的位置相较于变换前成为2,3,4，，，28,1.
比如，对于原始字谜要C0和D0，我们得到：
C0 = 1111000011001100101010101111
C1 = 1110000110011001010101011111
C2 = 1100001100110010101010111111
C3 = 0000110011001010101011111111
C4 = 0011001100101010101111111100
C5 = 1100110010101010111111110000
C6 = 0011001010101011111111000011
C7 = 1100101010101111111100001100
C8 = 0010101010111111110000110011
C9 = 0101010101111111100001100110
C10 = 0101010111111110000110011001
C11 = 0101011111111000011001100101
C12 = 0101111111100001100110010101
C13 = 0111111110000110011001010101
C14 = 1111111000011001100101010101
C15 = 1111100001100110010101010111
C16 = 1111000011001100101010101111
D0 = 0101010101100110011110001111
D1 = 1010101011001100111100011110
D2 = 0101010110011001111000111101
D3 = 0101011001100111100011110101
D4 = 0101100110011110001111010101
D5 = 0110011001111000111101010101
D6 = 1001100111100011110101010101
D7 = 0110011110001111010101010110
D8 = 1001111000111101010101011001
D9 = 0011110001111010101010110011
D10 = 1111000111101010101011001100
D11 = 1100011110101010101100110011
D12 = 0001111010101010110011001111
D13 = 0111101010101011001100111100
D14 = 1110101010101100110011110001
D15 = 1010101010110011001111000111
D16 = 0101010101100110011110001111
我们现在就可以得到第n轮的新秘钥Kn（1<=n<=16）了。具体做法是，对每一对拼合后的子秘钥CnDn，按照表PC-2执行变换：
| 14 | 17 | 11 | 24 | 1 | 5 |
| 3 | 28 | 15 | 6 | 21 | 10 |
| 23 | 19 | 12 | 4 | 26 | 8 |
| 16 | 7 | 27 | 20 | 13 | 2 |
| 41 | 52 | 31 | 37 | 47 | 55 |
| 30 | 40 | 51 | 45 | 33 | 48 |
| 44 | 49 | 39 | 56 | 34 | 53 |
| 46 | 42 | 50 | 36 | 29 | 32 |
每对子秘钥有56位，但是PC-2仅仅使用其中48位。
于是，第你轮新秘钥Kn的第一位来自组合秘钥CnDn的第14位，第2位来自第17位，以此类推，知道新秘钥的第48位来自组合秘钥的第32位。
比如：
对于第一轮的组合秘钥，我们有：
C1D1 = 1110000 1100110 0101010 1011111 1010101 0110011 0011110 0011110
通过PC-2的变换后，得到：
K1 = 000110 110000 001011 101111 111111 000111 000001 110010
同理，对于其他秘钥，我们得到：
K2 = 011110 011010 111011 011001 110110 111100 100111 100101
K3 = 010101 011111 110010 001010 010000 101100 111110 011001
K4 = 011100 101010 110111 010110 110110 110011 010100 011101
K5 = 011111 001110 110000 000111 111010 110101 001110 101000
K6 = 011000 111010 010100 111110 010100 000111 101100 101111
K7 = 111011 001000 010010 110111 111101 100001 100010 111100
K8 = 111101 111000 101000 111010 110000 010011 101111 111011
K9 = 111000 001101 101111 101011 111011 011110 011110 000001
K10 = 101100 011111 001101 000111 101110 100100 011001 001111
K11 = 001000 010101 111111 010011 110111 101101 001110 000110
K12 = 011101 010111 000111 110101 100101 000110 011111 101001
K13 = 100101 111100 010111 010001 111110 101011 101001 000001
K14 = 010111 110100 001110 110111 111100 101110 011100 111010
K15 = 101111 111001 000110 001101 001111 010011 111100 001010
K16 = 110010 110011 110110 001011 000011 100001 011111 110101
关于子秘钥的话题我们就到此为止，接下来我们看信息本身。
DES是一个基于组块的加密算法，这意味着无论输入还是输出都是64位长度。也就是说DES产生了一种最多264中的变换方法。每个64位的区块被分为2个32位的部分，左半部分L和右半部分R。
比如明文，M为
M = 0123456789ABCDEF
这里的M是16进制的，将M写成二进制，我们得到一个64位的区块：
M = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
L = 0000 0001 0010 0011 0100 0101 0110 0111
R = 1000 1001 1010 1011 1100 1101 1110 1111
M的第一位是0，最后一位是1，我们从左读到右。
对于明文M，我们计算一下初始变换IP（Initial permutation）。IP是重新变换数据M的每一位产生的。产生过程由下表决定，表格的下标对应新数据的下标，表格的数值x表示新数据的这一位来自旧数据的第x位。
比如，对M的区块，执行初始变换，得到：
M = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
IP = 1100 1100 0000 0000 1100 1100 1111 1111 1111 0000 1010 1010 1111 0000 1010 1010
接着讲变换IP分为32位的左半边L0和右半边R0
比如，对于上例，我们得到：
L0 = 1100 1100 0000 0000 1100 1100 1111 1111
R0 = 1111 0000 1010 1010 1111 0000 1010 1010
我们接着执行16个迭代，对1<=n<=16,使用一个函数f.函数f输入两个区块，一个32位的数据块和一个48位的木曜区块Kn，输出一个32位的区块。定义+表示异或XOR。那么让n从1循环到16，我们计算：
Ln=Rn-1
Rn=Ln-1+f(Rn-1,Kn)
这样我们就得到最终区块，也就是n=16的L16R16.这个过程说白了就是，我们那前一个迭代结果的右边32位作为当前迭代的左边32位。对于当前迭代的右边32位，将它和上一个迭代的f函数的输出执行XOR运算。
比如，对于n=1，我们有：
K1 = 000110 110000 001011 101111 111111 000111 000001 110010
L1 = R0 = 1111 0000 1010 1010 1111 0000 1010 1010
R1 = L0 + f(R0,K1)
剩下就是f函数是如何工作的了，为了计算f，我们首先扩展每个Rn-1，将其从32位扩展到48位，这是通过使用一张表来重复Rn-1中的一位位来实现的。我们称这个过程为函数E。也就是说函数E（Rn-1）输入32位输出48位。
定义E为函数E的输出，将其写成8组，每组6位，这些比特是通过选择输入的某些位来产的，具体选择顺序按照如下表格实现：
| 32 | 1 | 2 | 3 | 4 | 5 |
| 4 | 5 | 6 | 7 | 8 | 9 |
| 8 | 9 | 10 | 11 | 12 | 13 |
| 12 | 13 | 14 | 15 | 16 | 17 |
| 16 | 17 | 18 | 19 | 20 | 21 |
| 20 | 21 | 22 | 23 | 24 | 25 |
| 24 | 25 | 26 | 27 | 28 | 29 |
| 28 | 29 | 30 | 31 | 32 | 1 |
也就是说E(Rn-1)开头的三个比特分别来自Rn-1的第32、1和2位。E(Rn-1)末尾的2个比特分别来自Rn-1的第32位和第1位。
比如：给定R0，我们可以计算出E(R0)：
R0 = 1111 0000 1010 1010 1111 0000 1010 1010
E(R0) = 011110 100001 010101 010101 011110 100001 010101 010101
接着在f函数中，我们对输出E（Rn-1）和秘钥Kn执行XOR运算：
Kn+E(Rn-1)
比如，对K1，E(R0)，我们有：
K1 = 000110 110000 001011 101111 111111 000111 000001 110010
E(R0) = 011110 100001 010101 010101 011110 100001 010101 010101
K1+E(R0) = 011000 010001 011110 111010 100001 100110 010100 100111
到这里我们还没有完成f函数的运算，我们仅仅使用一张表将Rn-1从32位扩展为48位，并且对这个结果和秘钥Kn执行了异或运算。我们现在有了48位的结果，或者说8组6比特数据。我们现在要对每组的6比特执行一些奇怪的操作：
我们将它作为一张被称为“S盒”的表格的地址。每组6比特都将给我们一个位于不同S盒中的地址。在哪个地址里存放着一个4比特的数字。这个4比特的数字将会替换掉原来的6个比特。最终结果就是，8组6比特的数据被转换为8组4比特（一共32位）的数据。
将上一步的48位的结果写成如下形式：
Kn+E(Rn-1)=B1B2B3B4B5B6B7B8
每个Bi都是一个6比特的分组，我们现在计算
S1（B1）S2（B2）S3（B3）S4（B4）S5（B5）S6（B6）S7（B7）S8（B8）
其中，Si（Bi）指的是第i个S盒的输出。
为了计算每个S函数S1，S2，，，S8，取一个6位的区块作为输入，输出一个4位的区块。决定S1的表格如下：
S1Column Number
| Row | ||||||||||||||||
| No. | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 0 | 14 | 4 | 13 | 1 | 2 | 15 | 11 | 8 | 3 | 10 | 6 | 12 | 5 | 9 | 0 | 7 |
| 1 | 0 | 15 | 7 | 4 | 14 | 2 | 13 | 1 | 10 | 6 | 12 | 11 | 9 | 5 | 3 | 8 |
| 2 | 4 | 1 | 14 | 8 | 13 | 6 | 2 | 11 | 15 | 12 | 9 | 7 | 3 | 10 | 5 | 0 |
| 3 | 15 | 12 | 8 | 2 | 4 | 9 | 1 | 7 | 5 | 11 | 3 | 14 | 10 | 0 | 6 | 13 |
如果S1是定义在这张表上的函数，B是一个6位的块，那么计算S1（B）的方法是：B的第一位和最后一位组合起来，的二进制数决定一个介于0和3之间的十进制数（或者二进制00到11之间）。设这个数为i，B的中间4位二进制数代表一个介于0到15之间的二进制数（二进制0000到1111）。设这个数为j。查表找到第i行第j列的那个数，这个是一个介于0和15之间的数，并且它是能由一个唯一的4位区块表示的。这个区块就是函数S1输入B得到的输出S1（B）。比如，对输入B=011011，第一位是0，最后一位是1，决定了行号是01，也就是十进制的1，中间4位是1101，也就是十进制的13，虽有列号是13.查表第一行第13列我们得到数字5.
这就决定了输出；5的二进制是0101，所以输出就是0101，即S1（011011）=0101。
同理，定义这8个函数S1，S2，，，S8：
| 14 | 4 | 13 | 1 | 2 | 15 | 11 | 8 | 3 | 10 | 6 | 12 | 5 | 9 | 0 | 7 |
| 0 | 15 | 7 | 4 | 14 | 2 | 13 | 1 | 10 | 6 | 12 | 11 | 9 | 5 | 3 | 8 |
| 4 | 1 | 14 | 8 | 13 | 6 | 2 | 11 | 15 | 12 | 9 | 7 | 3 | 10 | 5 | 0 |
| 15 | 12 | 8 | 2 | 4 | 9 | 1 | 7 | 5 | 11 | 3 | 14 | 10 | 0 | 6 | 13 |
| 15 | 1 | 8 | 14 | 6 | 11 | 3 | 4 | 9 | 7 | 2 | 13 | 12 | 0 | 5 | 10 |
| 3 | 13 | 4 | 7 | 15 | 2 | 8 | 14 | 12 | 0 | 1 | 10 | 6 | 9 | 11 | 5 |
| 0 | 14 | 7 | 11 | 10 | 4 | 13 | 1 | 5 | 8 | 12 | 6 | 9 | 3 | 2 | 15 |
| 13 | 8 | 10 | 1 | 3 | 15 | 4 | 2 | 11 | 6 | 7 | 12 | 0 | 5 | 14 | 9 |
| 10 | 0 | 9 | 14 | 6 | 3 | 15 | 5 | 1 | 13 | 12 | 7 | 11 | 4 | 2 | 8 |
| 13 | 7 | 0 | 9 | 3 | 4 | 6 | 10 | 2 | 8 | 5 | 14 | 12 | 11 | 15 | 1 |
| 13 | 6 | 4 | 9 | 8 | 15 | 3 | 0 | 11 | 1 | 2 | 12 | 5 | 10 | 14 | 7 |
| 1 | 10 | 13 | 0 | 6 | 9 | 8 | 7 | 4 | 15 | 14 | 3 | 11 | 5 | 2 | 12 |
| 7 | 13 | 14 | 3 | 0 | 6 | 9 | 10 | 1 | 2 | 8 | 5 | 11 | 12 | 4 | 15 |
| 13 | 8 | 11 | 5 | 6 | 15 | 0 | 3 | 4 | 7 | 2 | 12 | 1 | 10 | 14 | 9 |
| 10 | 6 | 9 | 0 | 12 | 11 | 7 | 13 | 15 | 1 | 3 | 14 | 5 | 2 | 8 | 4 |
| 3 | 15 | 0 | 6 | 10 | 1 | 13 | 8 | 9 | 4 | 5 | 11 | 12 | 7 | 2 | 14 |
| 2 | 12 | 4 | 1 | 7 | 10 | 11 | 6 | 8 | 5 | 3 | 15 | 13 | 0 | 14 | 9 |
| 14 | 11 | 2 | 12 | 4 | 7 | 13 | 1 | 5 | 0 | 15 | 10 | 3 | 9 | 8 | 6 |
| 4 | 2 | 1 | 11 | 10 | 13 | 7 | 8 | 15 | 9 | 12 | 5 | 6 | 3 | 0 | 14 |
| 11 | 8 | 12 | 7 | 1 | 14 | 2 | 13 | 6 | 15 | 0 | 9 | 10 | 4 | 5 | 3 |
| 12 | 1 | 10 | 15 | 9 | 2 | 6 | 8 | 0 | 13 | 3 | 4 | 14 | 7 | 5 | 11 |
| 10 | 15 | 4 | 2 | 7 | 12 | 9 | 5 | 6 | 1 | 13 | 14 | 0 | 11 | 3 | 8 |
| 9 | 14 | 15 | 5 | 2 | 8 | 12 | 3 | 7 | 0 | 4 | 10 | 1 | 13 | 11 | 6 |
| 4 | 3 | 2 | 12 | 9 | 5 | 15 | 10 | 11 | 14 | 1 | 7 | 6 | 0 | 8 | 13 |
| 4 | 11 | 2 | 14 | 15 | 0 | 8 | 13 | 3 | 12 | 9 | 7 | 5 | 10 | 6 | 1 |
| 13 | 0 | 11 | 7 | 4 | 9 | 1 | 10 | 14 | 3 | 5 | 12 | 2 | 15 | 8 | 6 |
| 1 | 4 | 11 | 13 | 12 | 3 | 7 | 14 | 10 | 15 | 6 | 8 | 0 | 5 | 9 | 2 |
| 6 | 11 | 13 | 8 | 1 | 4 | 10 | 7 | 9 | 5 | 0 | 15 | 14 | 2 | 3 | 12 |
| 13 | 2 | 8 | 4 | 6 | 15 | 11 | 1 | 10 | 9 | 3 | 14 | 5 | 0 | 12 | 7 |
| 1 | 15 | 13 | 8 | 10 | 3 | 7 | 4 | 12 | 5 | 6 | 11 | 0 | 14 | 9 | 2 |
| 7 | 11 | 4 | 1 | 9 | 12 | 14 | 2 | 0 | 6 | 10 | 13 | 15 | 3 | 5 | 8 |
| 2 | 1 | 14 | 7 | 4 | 10 | 8 | 13 | 15 | 12 | 9 | 0 | 3 | 5 | 6 | 11 |
例子：对弈第一轮，我们得到这8个S盒的输出：
K1+E(R0)=011000 010001 011110 111010 100001 100110 010100 100111
S1（B1）S2（B2）S3（B3）S4（B4）S5（B5）S6（B6）S7（B7）S8（B8）=0101 1100 1000 0010 1011 0101 1001 0111
函数f的最后一步就是对S盒的输出进行一个变换来产生最终值：
f=P（S1（B1）S2（B2）S3（B3）S4（B4）S5（B5）S6（B6）S7（B7）S8（B8））
变换P由如下表格定义。P输入32位数据，通过下表产生32位输出：
16 7 20 21
29 12 28 17
1 15 23 26
5 18 31 10
2 8 24 14
32 27 3 9
19 13 30 6
22 11 4 25
比如对8个S盒的输出：
S1（B1）S2（B2）S3（B3）S4（B4）S5（B5）S6（B6）S7（B7）S8（B8）=0101 1100 1000 0010 1011 0101 1001 0111
我们得到：
f=0010 0011 0100 1010 1010 1001 1011 1011
那么R1=L0+f（R0，K1）
= 1100 1100 0000 0000 1100 1100 1111 1111
+ 0010 0011 0100 1010 1010 1001 1011 1011
= 1110 1111 0100 1010 0110 0101 0100 0100
在下一轮迭代中，我们的L2=R1，这就是我们刚刚计算的结果。之后，我们必须计算R2=L1+f(R1,K2),一直完成16个迭代之后，我们有了区块L16和R16,。接着我们逆转两个区块的顺序得到一个64位的区块：
R16L16
然后，我们对其执行一个最终的IP-1，其定义如下：
| 40 | 8 | 48 | 16 | 56 | 24 | 64 | 32 |
| 39 | 7 | 47 | 15 | 55 | 23 | 63 | 31 |
| 38 | 6 | 46 | 14 | 54 | 22 | 62 | 30 |
| 37 | 5 | 45 | 13 | 53 | 21 | 61 | 29 |
| 36 | 4 | 44 | 12 | 52 | 20 | 60 | 28 |
| 35 | 3 | 43 | 11 | 51 | 19 | 59 | 27 |
| 34 | 2 | 42 | 10 | 50 | 18 | 58 | 26 |
| 33 | 1 | 41 | 9 | 49 | 17 | 57 | 25 |
也就是说，该变换的输出的第一位是输入的第40位，第二位是输入的8位，一直到将输入的第25位作为输出的最后一位。
比如，我们使用上述方法得到了第16轮的左右两个区块：
L16 = 0100 0011 0100 0010 0011 0010 0011 0100
R16 = 0000 1010 0100 1100 1101 1001 1001 0101
我们将两个区块调换位置，然后执行最终变换：
R16L16 = 00001010 01001100 11011001 10010101 01000011 01000010 00110010 00110100
IP-1 = 10000101 11101000 00010011 01010100 00001111 00001010 10110100 00000101
写成16进制得到：
85E813540F0AB405
这就是明文M=0123456789ABCDEF的密文：85E813540F0AB405
解密就是加密的反过程，执行上述步骤，只不过在那16轮迭代中，调转左右子秘钥的位置而已。
代码：数据加密的头文件（DES算法和RSA算法通用头文件）
/*encrypt.h*/
#ifndef ENCRYPT_H
#define ENCRYPT_H
/*在一个安全实现中，Huge 最少要400位10进制数字*/
typedef unsigned long Huge;
/*为RSA公钥定义一个数据结构*/
typedef struct RsaPubKey_
{
Huge e;
Huge n;
}RsaPubkey;
/*为RSA私钥定义一个数据结构*/
typedef struct RsaPriKey_
{
Huge d;
Huge n;
}RsaPriKey;
/*函数声明*/
void des_encipher(const unsigned char *plaintext, unsigned char *ciphertext, const unsigned char *key);
void des_decipher(const unsigned char *ciphertext, unsigned char *plaintext, const unsigned char *key);
void rsa_encipher(Huge plaintext, Huge *ciphertext, RsaPubKey pubkey);
void rsa_decipher(Huge ciphertext,Huge *plaintext, RsaPriKey prikey);
#endif // ENCRYPT_H
示例2：DES算法的实现
/*des.c*/
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include "bit.h"
#include "encrypt.h"
/*定义一个密钥置换的映射*/
static const int DesTransform[56] =
{
57,49,41,33,25,17,9,1,58,50,42,34,26,18,
10,2,59,51,43,35,27,19,11,3,60,52,44,36,
63,55,47,39,31,23,15,7,62,54,46,38,30,22,
14,6,61,53,45,37,29,21,13,5,28,20,12,4
};
/*定义用于计算子密钥的旋转次数*/
static const int DesRotations[16] =
{
1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1
};
/*定义用于子密钥置换选择的映射*/
static const int DesPermuted[48] =
{
14,17,11,24,1,5,3,28,15,6,21,10,
23,19,12,4,26,8,16,7,27,20,13,2,
41,52,31,37,47,55,30,40,51,45,33,48,
44,49,39,56,34,53,46,42,50,36,29,32
};
/*定义用于数据块初始化转换的映射*/
static const int DesInitial[64] =
{
58,50,42,34,26,18,10,2,60,52,44,36,28,20,12,4,
62,54,46,38,30,22,14,6,64,56,48,40,32,24,16,8,
57,49,41,33,25,17,9,1,59,51,43,35,27,19,11,3,
61,53,45,37,29,21,13,5,63,55,47,39,31,23,15,7
};
/*定义用于数据块扩展转换的映射*/
static const int DesExpansion[48] =
{
32,1,2,3,4,5,4,5,6,7,8,9,
8,9,10,11,12,13,12,13,14,15,16,17,
16,17,18,19,20,21,22,23,24,25,
24,25,26,27,28,29,28,29,30,31,32,1
};
/*定义用于数据块中S盒转换的S盒表*/
static const int DesSbox[8][4][16] =
{
{
{14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7},
{0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8},
{4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0},
{15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13},
},
{
{15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10},
{3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5},
{0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15},
{13,8,10,1,3,15,4,2,11,6,7,12,0,5,14,9},
},
{
{10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8},
{13,7,0,9,3,4,6,10,2,8,5,14,12,11,15,1},
{13,6,4,9,8,15,3,0,11,1,2,12,5,10,14,7},
{1,10,13,0,6,9,8,7,4,15,14,3,11,5,2,12},
},
{
{7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15},
{13,8,11,5,6,15,0,3,4,7,2,12,1,10,14,9},
{10,6,9,0,12,11,7,13,15,1,3,14,5,2,8,4},
{3,15,0,6,10,1,13,8,9,4,5,11,12,7,2,14},
},
{
{2,12,4,1,7,10,11,6,8,5,3,15,13,0,14,9},
{14,11,2,12,4,7,13,1,5,0,15,10,3,9,8,6},
{4,2,1,11,10,13,7,8,15,9,12,5,6,3,0,14},
{11,8,12,7,1,14,2,13,6,15,0,9,10,4,5,3},
},
{
{12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11},
{10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8},
{9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6},
{4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13},
},
{
{4,11,2,14,15,0,8,13,3,12,9,7,5,10,6,1},
{13,0,11,7,4,9,1,10,14,3,5,12,2,15,8,6},
{1,4,11,13,12,3,7,14,10,15,6,8,0,5,9,2},
{6,11,13,8,1,4,10,7,9,5,0,15,14,2,3,12},
},
{
{13,2,8,4,6,15,11,1,10,9,3,14,5,0,12,7},
{1,15,13,8,10,3,7,4,12,5,6,11,0,14,9,2},
{7,11,4,1,9,12,14,2,0,6,10,13,15,3,5,8},
{2,1,14,7,4,10,8,13,15,12,9,0,3,5,6,11},
}
};
/*定义用于数据块转换的P盒映射表*/
static const int DesPbox[32] =
{
};
/*定义用于数据块最终转换的映射*/
static const int DesFinal[64] =
{
};
/*定义一个枚举类型，用于选择是加密或是解密数据*/
typedef enum DesEorD_ {encipher,decipher} DesEorD;
/*permute函数 用于转换、改变位序列*/
static void permute(unsigned char *bits, const int *mapping, int n)
{
unsigned char *temp[8];
int i;
/*使用n位映射映射缓冲区*/
memset(temp, 0, (int)ceil(n/8));
for(i=0; i<n; i++)
bit_set(temp, i, bit_get(bits,mapping[i]-1));
memcpy(bits, temp, (int)ceil(n/8));
return;
}
/*des_main函数 加密或解密数据的计算函数*/
static int des_main(const unsigned char *source, unsigned char *target, const char *key, DesEorD direction)
{
static unsigned char subkeys[16][7];
unsigned char temp[8],
lkey[4],
rkey[4],
lblk[6],
rblk[6],
fblk[6],
xblk[6],
sblk;
int row,col,i,j,k,p;
/*如果key等于NULL，重用上次调用时计算出来的子密钥，否则计算子密钥*/
if(key != NULL)
{
/*创建一个key的副本*/
memcpy(temp,key,8);
/*将key转换并压缩至56位*/
permute(temp,DesTransform,56);
/*将key分为两个28位的组*/
memset(lkey,0,4);
memset(rkey,0,4);
for(j=0; j<28; j++)
bit_set(lkey, j, bit_get(temp,j));
for(j=0; j<28; j++)
bit_set(rkey, j, bit_get(temp,j+28));
/*计算每一轮的子密钥*/
for(i=0; i<16; i++)
{
/*根据定义好的位数对每一块进行旋转*/
bit_rot_left(lkey,28,DesRotations[i]);
bit_rot_left(rkey,28,DesRotations[i]);
/*重新合并两个块*/
for(j=0; j<28; j++)
bit_set(subkeys[i],j,bit_get(lkey,j));
for(j=0; j<28; j++)
bit_set(subkeys[i],j+28,bit_get(rkey,j));
/*对子密钥做转换选择并压缩至48位*/
permute(subkeys[i],DesPermuted,48);
}
}
/*创建source参数的副本*/
memcpy(temp, source, 8);
/*初始转换数据块*/
permute(temp, DesInitial, 64);
/*将源数据块分为大小为32位的左右两个数据块*/
memcpy(lblk, &temp[0], 4);
memcpy(rblk, &temp[4], 4);
/*加密或解密源数据*/
for(i=0; i<16; i++)
{
/*开始f缓冲冲的计算*/
memcpy(fblk,rblk,4);
/*置换、扩展右数据块的拷贝，使其达到48位*/
permute(fblk, DesExpansion, 48);
/*根据direction的值来应用适当的子密钥*/
if(direction == encipher)
{
/*加密数据，子密钥组以递增的顺序应用*/
bit_xor(fblk, subkeys[i], xblk, 48);
memcpy(fblk, xblk, 6);
}
else
{
/*解密数据，子密钥组以递减的顺序应用*/
bit_xor(fblk, subkeys[15-i], xblk, 48);
meycpy(fblk, xblk, 6);
}
/*执行S盒替换*/
p=0;
for(j=0; j<8; j++)
{
/*计算出S盒表中的行号和列号*/
row = (bit_get(fblk,(j*6)+0)*2) + (bit_get(fblk,(j*6)+5)*1);
col = (bit_get(fblk,(j*6)+1)*8) + (bit_get(fblk,(j*6)+2)*4) +
(bit_get(fblk,(j*6)+3)*2) + (bit_get(fblk,(j*6)+4)*1);
/*为当前的6位数据块做S盒替换*/
sblk = (unsigned char)DesSbox[j][row][col];
for (k=4; k<8; k++)
{
bit_set(fblk,p,bit_get(&sblk,k));
p++;
}
}
/*为f缓冲区执行P盒替换*/
permute(fblk, DesPbox, 32);
/*计算左数据块与f缓冲区的异或值*/
bit_xor(lblk, fblk, xblk, 32);
/*设置本轮的左数据块*/
memcpy(lblk, rblk, 4);
/*设置本轮的右数据块*/
memcpy(rblk, xblk, 4);
}
/*将目标正文设置为重新连接的左右两个数据块*/
memcpy(&target[0], rblk, 4);
memcpy(&target[4], lblk, 4);
/*执行最终置换*/
permute(target, DesFinal, 64);
return 0;
}
/*des_encipher DES加密数据*/
void des_encipher(const unsigned char *plaintext, unsigned char *ciphertext, const unsigned char *key)
{
des_main(plaintext, ciphertext, key, encipher);
return;
}
/*des_decipher DES解密数据*/
void des_decipher(const unsigned char *ciphertext, unsigned char *plaintext, const unsigned char *key)
{
des_main(ciphertext, plaintext, key, decipher);
return;
}
参考文献
https://www.cnblogs.com/idreamo/p/9333753.html
https://www.cnblogs.com/LoganChen/p/11432092.html
https://www.ichunqiu.com/course/52991
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论