C#入门实践：Windows桌面加密器 CryptoSharp
Step 2 DES/Bit Operation
by Pixel Frame
GitHub: CryptoSharp
0x00 DES
DES的加密过程相比AES而言显然要简单不少，之前已经用C++实现过了一遍，改写到C#难度也不大。DES算法的流程分为轮密钥分配和数据加密两块。
数据处理
DES的输入和密钥均为64bit数据，我们可以直接使用ulong类型进行处理，出于习惯使用QWORD代指ulong，即添加using QWORD=System.Uint64;。
明文数据需要经过一次IP置换并分为前后32bit两部分，称作L和R，同理用DWORD(uint)来存储。然后通过16轮轮密钥加密和交换操作，即
DWORD temp = R;
R = f(R, Ki) ^ L;
L = temp;
其中Ki为下文的轮密钥分配中产生的轮密钥。f(R, Ki)为
- 对
R进行替换扩展至48bit； - 将上步结果与
Ki异或； - 将上步结果分为8段6bit数据进行S盒替换，结果为8段4bit数据；
- 将上步结果组合为
DWORD并进行P替换即为32bit结果。
即
Swap_P(Swap_S(Expand_R(R)^Ki));
16轮后对LR再做一次调换并结合成64bit数据，对其再进行逆IP置换即为加密结果。
轮密钥分配
首先对输入的64bit密钥进行PC1置换，产生56位数据并分为前后28bit两部分，称作C和D，当然我们不能创造56bit和28bit的类型，所以依然使用QWORD和DWORD存储数据，高位留空以方便强制类型转换，因为C#的强制类型转换和C++相同都是去高位保留低位。然后要按轮数对C,D进行28bit的循环左移，在1，2，9，16轮移1位，其余轮移2位，由于判断轮数比较麻烦，所以用一个移位表来确定每轮的移位数。
int[] shiftTable =
{
1, 1, 2, 2,
2, 2, 2, 2,
1, 2, 2, 2,
2, 2, 2, 1
};
对DWORD进行低28bit循环位移也需要特别注意，会在下一节作说明。
每一轮进行位移后将C,D组合成56bit数据进行PC2置换，结果即为48bit轮密钥Ki。
解密过程
解密过程与加密过程不同之处只在于R和L的交换过程，而密钥产生和f(R, Ki)则是完全相同的，再次异或之后就进行了逆操作。因此本质上没有太大区别。
有一点是，加密过程中每一轮的密钥可以在每一轮处理数据的同时产生，解密则必须事先生成好16轮密钥。这是因为解密时数据处理的第1轮用到的是第16轮密钥。
0x01 置换与位操作
置换
*下文中部分位置异或(^)与或(|)的效果相同（即与0作运算时），不作区分
置换主要分为普通替换和S盒替换两类，当然前者还能细分为输入输出类型相同和不同两种。
普通置换即为遍历替换表，输出的当前位为输入的对应位，如：替换表中第一个数为18，则输出的第1位为输入的第18位。因此我们需要做的就是将QWORD或DWORD中的对应bit提取出来并放入新的数据中，bit不是数组我们只能进行移位再或运算的方式来完成。举例如下：
输入数据为input = 10110010，替换表为{ 2, 3, 5, 1, 4, 8, 7, 6 }
-
output = 0x00； - 提取出对应位的数据，通过与运算保留需要的位，如替换表第一项
2，则mask = input & (0x80 >> (2 - 1))； - 将替换表数与当前位置相减得出需要的移位，如当前位置为
1，替换表项为2，则需将mask左移1位； - 将
mask与output进行或运算，回到2. 进行下一位替换。
IP置换举例如下
public static QWORD Swap_IP(QWORD input)
{
QWORD output = 0;
for (int i = 0; i < 64; ++i)
{
QWORD Mask = Mask64(input, IP[i] - 1);
int shift = IP[i] - 1 - i;
if (shift > 0) Mask <<= shift;
else Mask >>= (0 - shift);
output = output ^ Mask;
}
return output;
}
private static QWORD Mask64(QWORD num, int pos)
{
QWORD Mask = 0x8000000000000000;
Mask = Mask >> pos;
num = Mask & num;
return num;
}
考虑性能优化时，可以将input和num作为引用传入减小内存开销。
其他置换包括R的48bit扩展均可以如此完成。S盒置换的特殊性在于需要将输入分割为8个6bit数据进行操作，将6bit的第1、6位组合为S盒的行，中间4位组合为列，将S盒中对应位置的4bit数据作为结果。
首先分割出的6bit数据用byte保存，同样高位留空。
seg = (byte)(input >> (56 - 6 * i));
作为矩阵索引的row和col为int，所以我们要将seg的对应位取出移至最低位，值得一提的是&和>>操作符会隐式的将byte转换为int，因为另一个操作数是int。
int row = ((seg & 0x80) >> 6) | ((seg & 0x04) >> 2);
int col = (seg & 0x78) >> 3;
最后从S盒中取出对应数据，移位至对应位，与output进行或运算保存。
output ^= (DWORD)(S[i, row, col] << (4 * (7 - i)));
28bit循环位移
- 对
DWORD输入进行普通左移k位； - 将输入进行
28-k位普通右移； - 最后，将前两次结果进行或运算并清空前4个bit得到循环左移结果，当然如果不会用到前4个bit不作清空也不会有问题。
废话时间：
由于高级语言的类型限制（当然也不能说是语言限制，应该说是CPU寄存器的限制），加密算法中的bit操作实现起来相当繁琐，要说DES本身其实就是做了各种各样的替换而已。网上有不少实现都使用string/数组等保存1bit数据，那么内存消耗是显然的翻倍。
为了详细描述bit操作的过程直接导致了本篇的拖延（搞这么麻烦干什么啊，画图什么的真的不想干了（そだよ
其实写完本篇的时候DES的大部分和RSA的基础功能都已经完成了~
次回予告：分组操作模式/随机数发生
END_OF_PART_2
