's Blog 主页归档标签Ducky大黄鸭
Python实现LFSR+Geffe密钥流生成器
字数总计: 1.8k|阅读时长: 7 分钟

概述

使用Python实现一个流密码的密钥流生成器，本文采用LFSR(线性反馈移位寄存器)+Geffe序列的组合方式实现。（同样的也可用LFSR+J-K触发器的组合方式）

密钥流生成器的目的是由一个短的随机密钥（也称实际密钥或种子密钥）生成一个长的密钥流，用这个长的密钥流对明文加密或对密文解密，从而使一个短的密钥可用来加密更长的明文或解密更长的密文的目的。

——摘录自百度百科

流密码密钥流生成器的基本构造为一个线性的反馈移位寄存器(LFSR)加上一个非线性的组合子系统，这样的组合能够实现消耗不多的性能以及有较好的安全性的平衡。

下面分别简单介绍线性反馈移位寄存器(LFSR)和Geffe序列

线性反馈移位寄存器(LFSR)

线性反馈移位寄存器（为方便阅读，以下直接使用英文缩写LFSR），可以理解为一个由我们设定的盒子，每次运算会输出一位二进制值，下面用一个十分经典的图来配合讲解：

图中ana_n~a1a_1一共n位，称为LFSR的级数（n级），每运算一次，ana_n~a1a_1序列集体向右移一位，将a1a_1直接输出。然后通过一个函数来计算得出新的最左边的第一位（新ana_n），该计算函数称为反馈函数，表达式为：

cna1⊕cn−1a2⊕⋅⋅⋅⋅⋅⋅⊕c2an−1⊕c1anc_n a_1⊕c_{n-1} a_2⊕ ······ ⊕c_2 a_{n-1}⊕c_1 a_n

由公式可以看出，cic_i就像一个开关，决定其对应的an+1−ia_{n+1-i}是否参与异或运算。若将上式所有常数为1的a（即cic_i=1对应的an+1−ia_{n+1-i}）抽取出来，其组成的序列在某些文献中也称为抽头序列

因此当我们定义一个LFSR时，我们需要给出该LFSR的级数(多少个a)、初始状态(ana_n~a1a_1的初始值)以及反馈函数的常数C序列(cnc_n~c1c_1的值)。

Geffe序列

一个非线性的组合子系统是让LFSR产生的密钥流安全性得到提升的一个巧妙方法，通过这样的变换可以使产生的密钥流周期尽可能大、线性复杂度和不可预测性尽可能高。Geffe序列通过搭配三个LFSR来实现，原理图如下：

可理解为一个2选1复用器，LFSR2的值用来选择输出LFSR1还是LFSR3。真值表为：

LFSR2 输出值
0 LFSR3
1 LFSR1

逻辑表达式表示为：(LFSR1∧LFSR2)⊕(¬LFSR1∧LFSR3)

具体实现代码

使用Python实现的代码如下

import re


# 检查输入的二进制数
def check_bin_input(input_str, bin_len):
    while re.search(r"[^01]", input_str):
        input_str = input("输入错误，请输入二进制数：")
    while not len(input_str) == bin_len:
        input_str = input("输入长度错误，请输入长度为{}的二进制数：".format(bin_len))
    return input_str


# （输出一个密钥位后）返回进行移位之后的下一轮初始状态
def get_next_initial_bin(lfsr_initial_bin, feedback_f_c_bin):
    not_first = False  # 标记是否已经得到异或运算的第一个位的值
    gf_current_int = 0  # 初始化
    if not len(lfsr_initial_bin) == len(feedback_f_c_bin):
        print("*Error in get_next_initial_bin: data length not equal")
        exit()
    for index in range(len(feedback_f_c_bin)-1, -1, -1):
        coefficient_c = int(feedback_f_c_bin[index])
        # 因为得到第一个异或运算的值后not_first会变为True
        # 所以使用not_first的这两个if判断的先后顺序有讲究
        if (not_first is True) and (coefficient_c == 1):
            # 当前异或（GF(2)）运算的结果
            gf_current_int = int(gf_current_int) ^ int(lfsr_initial_bin[index])  
        # 首先要得到进行异或运算的第一个位的值
        if (not_first is False) and (coefficient_c == 1):
            # 异或（GF(2)）运算的第一个值
            gf_current_int = int(lfsr_initial_bin[index])  
            not_first = True
    return str(gf_current_int) + lfsr_initial_bin[0:len(lfsr_initial_bin) - 1]


# Geffe序列生成器
def geffe_generator(lfsr1_int, lfsr2_int, lfsr3_int):
    if lfsr2_int == 1:
        return (lfsr1_int & 1) ^ (lfsr3_int & 0)
    elif lfsr2_int == 0:
        return (lfsr1_int & 0) ^ (lfsr3_int & 1)


def main():
    # LFSR反馈函数的常数c
    feedback_f_c_bin_array = [0, 0, 0]
    # 三个LFSR的初始状态，及目前处理的状态
    lfsr_initial_bin_array = ['0', '0', '0']
    current_lfsr_bin_array = ['0', '0', '0']
    # n_level=线性反馈移位寄存器的级数
    n_level = int(input("请输入LFSR的级数："))
    while (not isinstance(n_level, int)) or (n_level <= 0):
        n_level = int(input("输入错误，请输入大于0的整数："))
    for i in range(3):
        feedback_f_c_bin_array[i] = input("请输入LFSR{0}反馈函数常数c的序列Cn~C1，为{1}位二进制数：".format(i + 1, n_level))
        feedback_f_c_bin_array[i] = check_bin_input(feedback_f_c_bin_array[i], n_level)
    for i in range(3):
        lfsr_initial_bin_array[i] = input("请输入LFSR{0}寄存器的初始状态An~A1，为{1}位二进制数：：".format(i + 1, n_level))
        current_lfsr_bin_array[i] = lfsr_initial_bin_array[i] = check_bin_input(lfsr_initial_bin_array[i], n_level)

    # 开始移位输出密钥流
    output_len = int(input("\n-----输出密钥流-----\n请输入需要输出的密钥流长度："))
    while (not isinstance(output_len, int)) or (output_len <= 0):
        output_len = int(input("输入错误，请输入大于0的整数："))
    output_str = ''  # 储存输出的密钥流
    for i in range(output_len):
        lfsr1_int = int(current_lfsr_bin_array[0][n_level-1])
        lfsr2_int = int(current_lfsr_bin_array[1][n_level-1])
        lfsr3_int = int(current_lfsr_bin_array[2][n_level-1])
        output_str = output_str + str(geffe_generator(lfsr1_int, lfsr2_int, lfsr3_int))
        # 更新寄存器中的初始状态
        for j in range(3):
            current_lfsr_bin_array[j] = get_next_initial_bin(current_lfsr_bin_array[j], feedback_f_c_bin_array[j])
    # 输出结果
    print(output_str)

    # 加密
    plaintext_input = input("\n-----加密-----\n明文：")
    ciphertext_output = ''
    key_output = ''
    # #初始化密钥流生成器
    for i in range(3):
        feedback_f_c_bin_array[i] = feedback_f_c_bin_array[i]
    for i in range(3):
        current_lfsr_bin_array[i] = lfsr_initial_bin_array[i] = lfsr_initial_bin_array[i]
    # #逐位加密
    for i in range(len(plaintext_input)):
        lfsr1_int = int(current_lfsr_bin_array[0][n_level - 1])
        lfsr2_int = int(current_lfsr_bin_array[1][n_level - 1])
        lfsr3_int = int(current_lfsr_bin_array[2][n_level - 1])
        key = int(geffe_generator(lfsr1_int, lfsr2_int, lfsr3_int))
        ciphertext_output = ciphertext_output + str(int(plaintext_input[i]) ^ key)
        key_output = key_output + str(key)
        # 更新寄存器中的初始状态
        for j in range(3):
            current_lfsr_bin_array[j] = get_next_initial_bin(current_lfsr_bin_array[j], feedback_f_c_bin_array[j])
    # #输出结果
    print("密钥：" + key_output)
    print("密文：" + ciphertext_output)

    # 解密
    ciphertext_input = input("\n-----解密-----\n密文：")
    plaintext_output = ''
    key_output = ''
    # #初始化密钥流生成器
    for i in range(3):
        feedback_f_c_bin_array[i] = feedback_f_c_bin_array[i]
    for i in range(3):
        current_lfsr_bin_array[i] = lfsr_initial_bin_array[i] = lfsr_initial_bin_array[i]
    # #逐位解密
    for i in range(len(ciphertext_input)):
        lfsr1_int = int(current_lfsr_bin_array[0][n_level - 1])
        lfsr2_int = int(current_lfsr_bin_array[1][n_level - 1])
        lfsr3_int = int(current_lfsr_bin_array[2][n_level - 1])
        key = int(geffe_generator(lfsr1_int, lfsr2_int, lfsr3_int))
        plaintext_output = plaintext_output + str(int(ciphertext_input[i]) ^ key)
        key_output = key_output + str(key)
        # 更新寄存器中的初始状态
        for j in range(3):
            current_lfsr_bin_array[j] = get_next_initial_bin(current_lfsr_bin_array[j], feedback_f_c_bin_array[j])
    # #输出结果
    print("密钥：" + key_output)
    print("明文：" + plaintext_output)


if __name__ == '__main__':
    main()

运行

运行效果像这样：

# 以5级LFSR为例，运行时参照提示输入以下值进行初始化：
请输入LFSR的级数：5
请输入LFSR1反馈函数常数c的序列Cn~C1，为5位二进制数：01100
请输入LFSR2反馈函数常数c的序列Cn~C1，为5位二进制数：11100
请输入LFSR3反馈函数常数c的序列Cn~C1，为5位二进制数：10101
请输入LFSR1寄存器的初始状态An~A1，为5位二进制数：：01010
请输入LFSR2寄存器的初始状态An~A1，为5位二进制数：：11001
请输入LFSR3寄存器的初始状态An~A1，为5位二进制数：：10001

# 先选择输出100位观看效果
-----输出密钥流-----
请输入需要输出的密钥流长度：100
0001000100101110000110101101111100110110101001011100110111110001000010100111100010111101011100101110

# 尝试使用上面模型的密钥流来加解密
-----加密-----
明文：011011010010101010001111
密钥：000100010010111000011010
密文：011111000000010010010101

-----解密-----
密文：011111000000010010010101
密钥：000100010010111000011010
明文：011011010010101010001111
文章作者:
文章链接: https://crushonu.top/python实现lfsr-geffe密钥流生成器-2/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 's Blog！
密码学