简介
Feistel 加密算法，或者叫做 Feistel 网络，是一种块加密（block cipher）模型，很多常见的加密算法都具有 Feistel 结构，如 DES、blowfish 等。
Feistel 将明文分割成固定大小(block size)的块（如 32bit、64bit），然后对于每个块进行若干轮操作，每轮操作需要用到一个 key，因此总计需要循环轮数个 key。解密时需要用相同的 keys，因此这是一种对称加密算法。
加密步骤
- 将明文转换为 8-bit 二进制形式
- 根据块大小(block size)分割成若干个数据块，不足整数块时需要加 padding
- 生成轮数(rounds)个 key 的 keys 数组
- 对于每个数据块进行若干轮操作，具体如下：
- 在每轮操作中都将数据块分成相等的左右两部分(L1, R1)
- 将右半部分(R1)与keys[n]进行加密函数f运算，记为f1
- 然后将f1与左半部分进行异或（XOR）操作的结果作为下一轮输入的左半部分(L2)
- 将本轮左半部分(L1)作为下一轮输入的右半部分(R2)
- 下一轮的输入为L2 + R2, 再进行下一轮操作
- 在最后一轮结束后将左半部分（Ln）和右半部分(Rn)对调（这样可以使用同一个循环进行加密和解密）
解密步骤
- 将密文使用相同的 keys 进行与加密过程相同的循环，不过 key 的顺序与加密时相反（加密时使用 key[1], key[2], ..., key[n], 解密时使用 key[n], key[n-1], ..., key[1]）
- 组合数据块并按照 8bit 进行分割
- 根据 ASCII 码转换为明文
Python 实现
首先定义一些变量
plain_text = 'Hello world!' # 为了便于取整，选择8bit block_size = 8 rounds = 16 keys = []
生成随机的 keys
def rand_key(n): res = '' for i in range(n): bit = random.randint(0, 1) res += str(bit) return res # length 是key的长度，可以根据需要调整 def generate_keys(length, rounds): for i in range (rounds): keys.append(rand_key(length)) return res
定义每一轮循环的操作
def exor(a, b): n = len(a) res = '' for i in range(n): if a[i] == b[i]: res += '0' else: res += '1' return res def round(str, key): n = len(str) // 2 L1 = str[0:n] R1 = str[n:] # 这里的f函数选择exor操作 # 可以替换为其他的加密函数 f1 = exor(R1, key) R2 = exor(f1, L1) L2 = R1 return L2 + R2
加密过程
def feistel_encode(s, rounds): res = '' # 将密文转为8bit二进制表示 str_ascii = [ord(x) for x in s] str_bin = [format(x, '08b') for x in str_ascii] str_bin = ''.join(str_bin) # 选择block size的一半最为key length是因为将f函数定义为xor操作 # 保证长度和block size的一半相等，在执行时就不需要补padding # 实际的key length会更长，一般不会少于128bit避免被快速爆破 key_length = block_size // 2 generate_keys(key_length, rounds) res_bin = '' for n in range(0, len(str_bin), block_size): temp = str_bin[n:n + block_size] for i in range(rounds): temp = round(temp, keys[i]) # 最后一轮循环后交换左右部分 temp = temp[key_length::] + temp[0:key_length] res_bin += temp # 将密文转为ASCII字符表示 for i in range(0, len(res_bin), 8): bin_data = res_bin[i: i + 8] decimal = int(bin_data, 2) res += chr(decimal) return res
解密过程
def feistel_decode(s): res = '' str_ascii = [ord(x) for x in s] str_bin = [format(x, '08b') for x in str_ascii] str_bin = ''.join(str_bin) res_bin = '' for n in range(0, len(str_bin), block_size): temp = str_bin[n:n + block_size] for key in reversed(keys): # 确保使用反向密钥 temp = round(temp, key) key_length = len(keys[0]) # 最后一轮循环后交换左右部分 temp = temp[key_length::] + temp[0:key_length] res_bin += temp # 转为ASCII字符 for i in range(0, len(res_bin), 8): bin_data = res_bin[i: i + 8] decimal = int(bin_data, 2) res += chr(decimal) return res
最后测试一下
def main(): print('plain_text: ', plain_text) # plain_text: Hello world! cipher_text = feistel_encode(plain_text, rounds) print('cipher_text: ', cipher_text) # cipher_text: yààÓlKÓàh} decode_text = feistel_decode(cipher_text) print('decode_text: ', decode_text) # decode_text: Hello world! if __name__ == "__main__": main()
总结
- 本文中为了方便演示将block size和key size设置较小，实际一般会更长，如果不满整个block则需要补padding(用0填充)
- 加密和解密使用相同的循环，但是注意不要忘记需要在加/解密的最后一轮循环后交换左、右部分
- 动手实现时可以将round设为1或2，单步观察每一轮循环的结果
- 时间复杂度 O(n)
- 额外空间 O(n)
