c - S-DES 实现 : how to work with the individual bits?

Question

我有一个作业要求我们实现 S-DES(简化 DES)，该算法包括很多位排列、移位以及异或运算。

显然，最快的实现方式是使用位操作，例如:

char CLS(char key, int shift){
    char skey;
    skey = (key << shift) | (key >> (8 - shift)) 
    return skey;
}

/* Get 8-bit subkey from 10-bit key */
char permute(short int key){
    short int i;
    short int k1[] = { BIT_6, BIT_3, BIT_7, BIT_4, BIT_8, BIT_5, BIT_10, BIT_9 }; // SDES spec
    char sk1 = '\0';

    for(i = 0; i < 8; i++){
        sk1 = (sk1 << 1) | (key & k1[i]);
    }
}

...

这很简单。但是，如何有效地获取这些位？使用 fread() 之类的东西，我可以一次至少读取 1 个字节并将其提供给 SDES 算法，但这严重地未充分利用 CPU，因为我不仅要读取而且一次只加密 1 个字节，我也会一次将 1 个字节的加密数据写入磁盘!肯定有更好的方法。

我能想到的唯一替代方法是将每个字节视为一个 char 数组并以这种方式操作位，但这不仅会增加内存开销:我仍然一次只能处理 1 个字节和我将无法使用移位操作，而是需要使用临时数组和数组索引。

我希望稍微改进这种行为，但我所能想到的就是将更大的 block 放入内存中。例如，我可以使用 fread() 将 4K 数据 block 读入 char 数组 [4096]，然后使用它，而不是从磁盘中逐个读取 4096 字节。

但是，鉴于这是一个简单的算法，我不确定这是否是我所能做的全部。是否可以进行进一步的改进，或者这已经差不多好了？

如果有人想看一下，here是S-DES算法的规范。

Answer 1

如果您想加速您的算法，您可以在字节数组上并行加密，例如使用 OpenMP。正如 DarkSquirrel42 在评论中指出的那样，为了提高速度，您还应该将置换函数替换为使用查找表的函数:

#define LUT_SIZE 1024
static char lookup_table[LUT_SIZE];

/* Get 8-bit subkey from 10-bit key */
char permute(short int key)
{
    // SDES spec
    short int k1[] = { BIT_6, BIT_3, BIT_7, BIT_4, BIT_8, BIT_5, BIT_10, BIT_9 }; 
    char sk1 = '\0';

    for (short int i = 0; i < 8; i++) {
        sk1 = (sk1 << 1) | (key & k1[i]);
    }
    return sk1;
}

void init_lut()
{
    for (short int i = 0; i < LUT_SIZE; i++) {
        lookup_table[i] = permute(i);
    }
}

char permute_fast(short int key)
{
    if (key < 0 || key >= LUT_SIZE) {
        //error handling
        return 0;
    }
    return lookup_table[key];
}