A5加密算法分析

密码学课程作业

简介

A5/1是用于在GSM蜂窝电话标准中提供无线通信隐私的流密码 一开始很安全 然后因为泄密和逆向工程被公众熟知 这个加密算法有很多弱点

—-wiki https://en.wikipedia.org/wiki/A5/1

今天上了一下Wikipedia 发现竟然在寻求捐赠 快破产了???

算法分析

加解流程密概述

1. A5加密使用三个寄存器 简称为LFSR 来生成 keysteam
2. 三个寄存器的长度分别为 19 22 23位
3. 密钥key(64位 8个字节)用于三个线性反馈移位寄存器的初始填充
4. 每次取每个寄存器的最后一位异或得到keysteam和明文异或得到密文
5. 寄存器的反馈方式也是取特定位置的值异或 反馈分为两步 是否需要移位的判断 和 反馈移位

每个回合步骤可以拆分为：取KEY 反馈多项式（Feedback Polynomial）位移
下图很清晰地解释了keysteam生成的过程 和 寄存器的反馈多项式

生成keysteam

1. 按顺序用key填充寄存器
2. 取(n1[18]+n2[21]+n3[22]) mod 2 也就是 n1[18]^n2[21]^n3[22]
3. 得到keysteam 异或加密明文

移位判断

使用择多原则
三个寄存器中选择三个钟控信号取n1[9] n2[10] n3[10]
两种二进制0,1 必定有0或1数量居多 居多的寄存器需要进行位移操作

流程图里标黄的位置

寄存器反馈

取如下图位置的数据进行异或操作 得到补位候补

python实现

# -- coding: utf-8 --
def Candidate(n, num):  #生成补位候补
    if num == 1:
        return chr((int(n[13]) ^ int(n[16]) ^ int(n[17]) ^ int(n[18]))+48)
    if num == 2:
        return chr((int(n[20]) ^ int(n[21]))+48)
    if num == 3:
        return chr((int(n[7]) ^ int(n[20]) ^ int(n[21]) ^ int(n[22]))+48)

class A5:
    def __init__(self,key,message):
        self.keystream= self.A5_init(key,len(message)*8)
    def A5_init(self,key,lenm):
        keystream=''
        stream = ''
        for i in key:   #寄存器的初始化填充key
            stream += bin(ord(i))[2:].zfill(8)
        n1 = stream[:19]
        n2 = stream[19:41]
        n3 = stream[41:]
        #a=0
        for i in range(lenm):
            keystream+=chr((int(n1[-1])^int(n2[-1])^int(n3[-1]))+48)
            if int(n1[8])+int(n2[10])+int(n3[10])>=2:   #时钟控制判断移位
                More='1'
            else:
                More='0'
            if n1[8]==More: #n1寄存器移位
                #print 1111111111
                n1=Candidate(n1, 1)+n1
                n1 = n1[:-1]
            if n2[10]==More:    #n2寄存器移位
                #print 2222222222
                n2=Candidate(n2, 2)+n2
                n2 = n2[:-1]
            if n3[10]==More:    #n3寄存器移位
                #print 3333333333
                n3=Candidate(n3, 3)+n3
                n3 = n3[:-1]
            '''print n1
            print n2
            print n3
            print
            a+=1
        print a'''
        print 'key:'+keystream
        return keystream    #返回密钥流

    def A5_encode(self,m):
        bin_m=''
        bin_c=''
        for i in m: #按二进制处理message
            bin_m += bin(ord(i))[2:].zfill(8)
        print 'message:'+bin_m
        for i in range(len(bin_m)): #按位异或加密
            bin_c+= chr((int(bin_m[i])^int(self.keystream[i]))+48)
        print 'result:'+bin_c
        return hex(int(bin_c,2))

if __name__=='__main__':
    #加密过程
    key = raw_input("Enter key of 8bytes:") #8位key
    message=raw_input("Enter meaage of any length:")
    a5=A5(key,message)
    c= a5.A5_encode(message)[2:]
    print '16进制密文:'+c #输出16进制密文

    # 解密过程
    key = key
    message =c.decode('hex')
    a5 = A5(key,message)
    c = a5.A5_encode(message)[2:]
    print '16进制明文:'+c #输出16进制明文
    print 'message:'+c.decode('hex')