DES 编程与实现

---

DES 密码学

算法描述及实现

二进制矩阵变换

• 算法思路
  DES加密算法用多次运用到基于二维矩阵的二进制变换,所以可以实现一个统一的变换函数,每次使用不同的矩阵用于变换处理即可.实现的时候只需留意代码中的数组的下标是从0开始的,而提供的二维矩阵的数据是从1开始计数的,稍作处理即可.

• 实现代码

void transform(bool *Out, bool *In, const char *Table, int len)
{
    static bool Tmp[256];
    for(int i = 0; i < len; i++)
    {
        Tmp[i] = In[ Table[i] - 1 ];
    }
    memcpy(Out, Tmp, len);
}

---

子密钥生成

• 算法思路
  DES 的密钥长度是56位,实际长度是64位的,因为第8的倍数位为奇偶校验码,不参与DES运算.经过缩小选择换位表1的变换后,密钥的位数由64位变成了56位,此56位分为C0、D0两部分,各28位，然后分别进行第1次循环左移,得到C1、D1,将C1(28位)、D1(28位)合并得到56位,再经过缩小选择换位2,从而便得到了密钥K0(48位).依此类推,便可得到K1、K2、...K15，不过需要注意的是,16次循环左移对应的左移位数要依据下述规则进行:

  循环左移位数: 1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1

• 实现代码

void DesSetKey(const char Key[8])
{
    static bool K[64], *KL = &K[0], *KR = &K[28];
    // 字节组转换成位组
    byteToBit(K, Key, 64);
    // 变换
    transform(K, K, PC1_Table, 56);
    for(int i=0; i<16; i++)
    {
        // 循环左移
        rotateL(KL, 28, LOOP_Table[i]);
        // 循环左移
        rotateL(KR, 28, LOOP_Table[i]);
        // 变换
        transform(SubKey[i], K, PC2_Table, 48);
    }
}

---

S盒实现

• 算法思路
  把48位的数分成8组,每组6位.在其输入b1,b2,b3,b4,b5,b6中,计算出x=b1*2+b6, y=b5+b4*2+b3*4+b2*8,再从Sbox表中查出x 行,y 列的值Sxy,将Sxy化为二进制,即得Si盒的输出.

• 实现代码

const static char S_Box[8][4][16] = {
    // S1
    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,
    //S2
    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,
    //S3
    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,
    //S4
    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,
    //S5
    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,
    //S6
    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,
    //S7
    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,
    //S8
    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
};

void sFunc(bool Out[32], const bool In[48])
{
    for(char i=0,j,k; i<8; i++,In+=6,Out+=4)
    {
        j = (In[0]<<1) + In[5];
        k = (In[1]<<3) + (In[2]<<2) + (In[3]<<1) + In[4];
        byteToBit(Out, &S_Box[i][j][k], 4);
    }
}

---

加解密实现

• 算法思路
  按顺序进行16轮 Feistel 迭代即可.以上的算法都是基于64位以下内容加密的,由于 DES 是分组加密的,所以将明文逐8个字符分组进行加密处理即可.

• 实现代码

void DesRun(char Out[8], char In[8], bool Type)
{
    static bool M[64], Tmp[32], *Li = &M[0], *Ri = &M[32];
    // 字节组转换成位组
    byteToBit(M, In, 64);
    // 变换
    transform(M, M, IPTable, 64);
    if( Type == ENCRYPT ){
        for(int i=0; i<16; i++) {
            memcpy(Tmp, Ri, 32);
            fFunc(Ri, SubKey[i]);
            // 异或
            xor(Ri, Li, 32);
            memcpy(Li, Tmp, 32);
        }
    }else{
        for(int i=15; i>=0; i--) {
            memcpy(Tmp, Li, 32);
            fFunc(Li, SubKey[i]);
            // 异或
            xor(Li, Ri, 32);
            memcpy(Ri, Tmp, 32);
        }
    }
    // 变换
    transform(M, M, IPRTable, 64);
    bitToByte(Out, M, 64);
}

---

相关模块实现

• F函数

void fFunc(bool In[32], const bool Ki[48])
{
    static bool MR[48];
    // 变换
    transform(MR, In, eTable, 48);
    // 异或
    xor(MR, Ki, 48);
    // S 盒代替
    sFunc(In, MR);
    // 变换
    transform(In, In, P_Table, 32);
}

• 异或

void xor(bool *InA, const bool *InB, int len)
{
    for(int i = 0; i < len; i++)
    {
        InA[i] ^= InB[i];
    }
}

• 循环左移

void rotateL(bool *In, int len, int loop)
{
    static bool Tmp[256];
    memcpy(Tmp, In, loop);
    memcpy(In, In+loop, len-loop);
    memcpy(In+len-loop, Tmp, loop);
}

• 字节转换为位

void byteToBit(bool *Out, const char *In, int bits)
{
    for(int i = 0; i < bits; i++)
    {
        Out[i] = (In[i/8] >> (i%8)) & 1;
    }
}

• 位转换位字节

void bitToByte(char *Out, const bool *In, int bits)
{
    memset(Out, 0, (bits+7)/8);
    for(int i = 0; i < bits; i++)
    {
        Out[i/8] |= In[i] << (i%8);
    }
}

• UI 实现

- (void)applicationDidFinishLaunching:(NSNotification *)aNotification
{
    // Insert code here to initialize your application
    self.tf_plainText.stringValue = @"qwertyuiop";
    self.tf_key.stringValue = @"12345678";
    self.tf_encryption.stringValue = @"";
    self.tf_decryption.stringValue = @"";
}
- (IBAction)runDES:(id)sender {
#if 0
    //明文合法性判断
    if ([self.tf_plainText.stringValue length] > 8) {
        self.tf_plainText.stringValue = @"The string is too long!";
        return;
    }
#endif
    if ([self.tf_plainText.stringValue length] <= 0) {
        self.tf_plainText.stringValue = @"The string is too short!";
    }
    //密钥合法性判断
    if ([self.tf_key.stringValue length] != 8) {
        self.tf_key.stringValue = @"Wrong key length!";
//        self.tf_key.placeholder = @"Wrong Key Length!";
        return;
    }
    //数据初始化
    const char *const_key = [self.tf_key.stringValue UTF8String];
    const char *const_str = [self.tf_plainText.stringValue UTF8String];
    int keyLength = (int)[self.tf_key.stringValue length];
    int strLength = (int)[self.tf_plainText.stringValue length];
    char *key = (char *)malloc(sizeof(char)*(keyLength+1));
    memcpy(key, const_key, keyLength);
    key[[self.tf_key.stringValue length]] = '\0';
    char *str = (char *)malloc(sizeof(char)*(strLength+1));
    memcpy(str, const_str, strLength);
    str[strLength] = '\0';
    if (strLength <= 8) {
        //DES 加密
        puts("Before encrypting:");
        puts(str);
        DesSetKey(key);
        DesRun(str, str, ENCRYPT);
        puts("After encrypting:");
        puts(str);
        //    self.tf_encryption.stringValue = [NSString stringWithUTF8String:str];
        self.tf_encryption.stringValue = @"Some chars can't print.";
        //DES 解密
        puts("After decrypting:");
        DesRun(str, str, DECRYPT);
        puts(str);
        self.tf_decryption.stringValue = [NSString stringWithUTF8String:str];
    } else {
        //
        puts("Before encrypting:");
        puts(str);
//        char resultEn[strLength];
//        char resultDe[strLength];
        char *resultEn = (char *)malloc(sizeof(char)*strLength);
        char *resultDe = (char *)malloc(sizeof(char)*strLength);
        for (int i = 0; i <= ((strLength-1)/8); i++) {
            int startIndex = i * 8;
            int offset = (i+1)*8 < (strLength-1) ? 8:(strLength-i*8);
            char *groupKey = (char *)malloc(sizeof(char)*offset);
            memcpy(groupKey, str+startIndex, offset);
            DesRun(groupKey, groupKey, ENCRYPT);
            strcat(resultEn, groupKey);
            DesRun(groupKey, groupKey, DECRYPT);
            strcat(resultDe, groupKey);
        }
        puts("After encrypting:");
        puts(resultEn);
        puts("After decrypting:");
        puts(resultDe);
//        self.tf_decryption.stringValue = [NSString stringwth]
        self.tf_encryption.stringValue = @"Some chars can't print.";
        self.tf_decryption.stringValue = [NSString stringWithUTF8String:str];
        free(resultEn);
        free(resultDe);
    }
}

---

结果演示

• 控制台输入日志
  

  Before encrypting:
  qwertyuiop
  After encrypting:
  JUp\246\302ĺϱ\376\214\212\357\326,
  After decrypting:
  qwertyuiop

由于输出字符的显示是用ASCII表中读取的,尽管一个字符是8位,取值范围是0~255,但是ASCII表中的内容只有0~127,而且这128个内容中也不全是字符内容,有一部分是特殊控制字符, 所以不能直接输入.

• 效果图