100 行代码手把手带你实现 Feisitel 加密算法

2024-07-25
湖南
本文字数：2017 字
阅读完需：约 7 分钟

简介

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!'# 为了便于取整，选择8bitblock_size = 8rounds = 16keys = []

复制代码

生成随机的 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)

作者：justMonika
链接：https://juejin.cn/post/7395069382433456147

发布于: 刚刚阅读数: 5

我再BUG界嘎嘎乱杀

关注

欢迎关注，一起学习，一起交流，一起进步 2020-06-14 加入

公众号：做梦都在改BUG

发布

暂无评论

创作场景

100 行代码手把手带你实现 Feisitel 加密算法

简介

加密步骤

解密步骤

Python 实现

总结

我再BUG界嘎嘎乱杀

评论