A5的原理及python实现

最近要做密码学课程设计，每做一个密码就当复习一下，把算法原理啥的都过一遍吧

简介

这个是用于GSM系统的序列密码算法，A5的特点是效率高，适合硬件上高效实现。

加密过程

1. A5 / 1基于三个线性反馈移位寄存器LFSR的组合，三个寄存器的长度分别为 19 22 23位，然后产生一个114位的秘钥流。因此首先输入8个字节的秘钥去填充三个寄存器的总长也就是64位。
2. 每次获取各寄存器的最后一位相互异或一下再与明文进行异或。从这一点还是可以看出关键点在于秘钥，异或了两遍原信息一致，所以加密解密都是一样的算法了。
3. 然后根据寄存器的某一位决定是否需要对某个储存器进行移位，存在的数据多的决定

引用维基百科的一个图，这个图很好的揭示了加密的流程

总结要注意的加密的几个点：

产生秘钥流

1. 根据8位秘钥产生的64位二进制填充寄存器
2. 输出秘钥流，每一位都遵循Z1[18]^Z2[21]^Z3[22]这样的流程，我们需要注意的是这里讲序列密码的时候用+表示的都是异或
3. 然后就经过114轮迭代，就可以产生114位秘钥啦

寄存器反馈

遵循“服从多数”的原则，从每个寄存器里面取出一个中间位(上图标黄的位置)进行运算，取出的3个中间位里面至少有两个1，则中间位为1的就进行移位，为0的就不移位，反之至少两个为0，则为0的进行一次位移，为1的就不移位了，保证了每次至少有了两个LFSR被驱动移位了。

生成的补充值

补充值由某些抽头位进行异或运算的结果决定，运算结果为1则补充为1，否则补充0,3个LFSR里的抽头位如下图，但是补充的前提是又寄存器反馈决定的

python实现：

# -*- coding: utf-8 -*-
# Author:0verWatch

X = \'\'
Y = \'\'
Z = \'\'

import base64
import re


def str2bin(str_mess):
    res = \"\"
    for i in str_mess:
        tmp = bin(ord(i))[2:].zfill(8)
        res += tmp
    return res



def bin2str(bin_mess):
    res = \"\"
    tmp = re.findall(r\'.{8}\',bin_mess)
    for i in tmp:
        res += chr(int(i,2))
    return res


def LFSRinit(): #用64bit密钥初始3个移位寄存器,分别是19,22,23位
    global X
    global Y
    global Z
    key = input(\"请输入8位秘钥\\n\")
    while len(key) != 8:   #限定只能是8位，然后生成64位的二进制流
        key = input(\"请输入8位秘钥\\n\")
    key_bin_str = \"\"
    for i in key:
        tmp = bin(ord(i))[2:].zfill(8)
        key_bin_str += tmp
    X = key_bin_str[0:19]
    Y = key_bin_str[19:41]
    Z = key_bin_str[41:]
    # print(\"X\"+X)
    # print(\"Y\"+Y)
    # print(\"Z\"+Z)



def xor(bin_str,bin_key): #输入的字符串的二进制流
    res = \"\"
    for i in range(len(bin_str)):
        if bin_str[i] == bin_key[i]:
            res += \'0\'
        else:
            res += \'1\'
    return res


def create_key():
    global X
    global Y
    global Z
    LFSRinit()
    res = \"\"
    for i in range(114):   # A5 / 1用于为每个突发产生114比特的密钥流序列
        # a = X[-1]
        # b = Y[-1]
        # c = Z[-1]
        g  = int(X[-1]) ^ int(Y[-1]) ^ int(Z[-1])
        res += str(g)  #用最后一位异或产生秘钥流
        x =  str(int(X[13]) ^  int(X[16]) ^ int(X[17]) ^ int(X[18]) ^ 1)               #候选位的值
        y =  str(int(Y[20]) ^ int(Y[21]) ^ 1)
        z = str(int(Z[7]) ^ int(Z[20]) ^ int(Z[21]) ^ int(Z[22]) ^ 1)
        #选择的钟控位
        c_x = int(X[8])
        c_y = int(Y[10])
        c_z = int(Z[10])
        if (c_x + c_y + c_z) >= 2:#多数的占优
            choice = \'1\'
        else:
            choice = \'0\'
        if str(c_x) == choice:
            X = x + X[:-1] #隐式位移，这里是不包含最后一位的
        if str(c_y) == choice:
            Y = y + Y[:-1]
        if str(c_z) == choice:
            Z = z + Z[:-1]
        # print(\"X\"+X)
        # print(\"Y\"+Y)
        # print(\"Z\"+Z)
    # print(res)
    return res

def a5_encode(mess):
    bin_mess = str2bin(mess)
    bin_key = create_key()
    bin_cipher = \"\"
    #print(len(bin_mess))
    if len(bin_mess) % 114 == 0:
        for i in range(0, len(bin_mess), 114):
            bin_cipher += xor(bin_mess, bin_key)
    elif len(bin_mess) > 114:
        j = 0
        for i in range(len(bin_mess)):
            bin_cipher += str(int(bin_mess[i]) ^ int(bin_key[i]))
            j += 1
            if j == 114:
                j = 0
    else:
        for i in range(len(bin_mess)):
            bin_cipher += str(int(bin_mess[i]) ^ int(bin_key[i]))
    print(\"二进制密文\" + bin_cipher)
    print(\"十六进制密文\"+hex(int(bin_cipher,2)))
    str_cipher = bin2str(bin_cipher)
    print(base64.b64encode(str_cipher.encode(\'utf-8\')))





def a5_decode(bin_mess):
    bin_key = create_key()
    bin_cipher = \"\"
    # print(len(bin_mess))
    if len(bin_mess) % 114 == 0:
        for i in range(0, len(bin_mess), 114):
            bin_cipher += xor(bin_mess, bin_key)
    elif len(bin_mess) > 114:
        j = 0
        for i in range(len(bin_mess)):
            bin_cipher += str(int(bin_mess[i]) ^ int(bin_key[i]))
            j += 1
            if j == 114:
                j = 0
    else:
        for i in range(len(bin_mess)):
            bin_cipher += str(int(bin_mess[i]) ^ int(bin_key[i]))
    str_cipher = bin2str(bin_cipher)
    print(\"解密后的结果:\"+str_cipher)



def get_info():
    choice = input(\"1.加密\\n2.解密\\n\")
    if choice == \'1\':
        message = input(\"输入你的信息\\n\")
        a5_encode(message)
    elif choice == \'2\':
        bin_message = input(\"输入你的信息\\n\")
        a5_decode(bin_message)
    else:
        print(\"请重新输入\")

if __name__ == \'__main__\':
    while True:
        get_info()

安全性

其实这个算法的关键点还是落在了秘钥的长度，体现在其寄存器的长度上，太短了，所以现在已知明文攻击法对这个算法的攻击是先确定其中两个寄存器的初始值再计算出另外一个，所以要想改进就是采用更长的线性反馈寄存器了。。。。。