嘘~这是我们的秘密!——一起来学《密码学》,第二弹

发表于2016-05-07
评论0 1.9k浏览

想免费获取内部独家PPT资料库?观看行业大牛直播?点击加入腾讯游戏学院游戏程序行业精英群

711501594

不知不觉,一个多月过去了。经过了五一小长假和青年节的半天假的假期时光后,是时候收心到工作和学习上了。

本期探讨的重点是流密码。比较常用的两种流密码是:RC4和A5。

流密码的基本思想是利用密钥产生一个密钥流,并使用如下规则对明文串加密:。密钥流由密钥流发生器产生:,这里是加密中的记忆元件(存储器)在时刻的状态,是由密钥产生的函数。通俗地讲,将密钥经过密钥流发生器产生一个密钥流,然后将密钥流与明文串逐位地经过变换生成密文串。相应地,密钥流和密文串逐位地经过运算的逆变换生成明文串

流密码的滚动密钥由函数、密钥和指定的初态完全确定。此后,由于输入加密器的明文可能影响加密器中内部记忆元件的存储状态,因而)可能依赖于等参数。

根据加密器中记忆元件的存储状态是否依赖于输入的明文字符,流密码可进一步分成同步和自同步两种。独立于明文字符的称为同步流密码,否则称为自同步流密码。疏于自同步流密码的密钥流的产生与明文有关,因而较难从理论上进行分析。目前大多数研究成果都是关于同步流密码的。

在同步流密码中,由于与明文字符无关,因而此时密文字符也不依赖于此前的明文字符。因此,可将同步流密码的加密器分成密钥流产生器和加密变换器两个部分。相应地,解密器可分成密钥流产生器和解密变换器两个部分。

同步流密码的模型如下:



同步流密码的加密变换可以有多种选择,只要保证变换是可逆的即可。实际使用的数字保密通信系统一般都是二元系统,因而在有限域(关于有限域,后续会详细介绍,有兴趣的同学可先行了解)上讨论的二元加法流密码是目前最为常用的流密码体制,其加密变换可表示为,其模型如下:



因此可见,对于这种同步流密钥而言,用于生成密钥流的密钥流发生器成为该加密算法的核心。

下面将着重讲解RC4和A5的密钥流生成算法。RC4首先说明下RC4算法中所使用符号所代表的意义

-- RC4使用的一个字节的长度(实际中一般取

-- 长度为的一个字节能够显示的值的总量,即

-- RC4的内部状态,每一个中有比特长度的值

-- 一个参数,

-- 参数时的内部状态

-- 参数时对应的两个指针,指向内部状态中的两个值

-- 中指针指向的值

-- 密钥

-- 密钥包含的字节数,即

-- 每一个对应的密钥生成器的输出值

RC4算法是参数决定的一系列算法,在每一个中包含比特字节,,包含2个比特字节的指针。这样,占用内存大小为

RC4算法包含两个部分,伪随机数生成算法PRGA和密钥方案算法KSA。

PRGA首先将两个指针初始化为0,作为两个随机变化的指针,然后变换状态指向的值,该过程的输出值为位置的值。具体过程如下:

初始化:

生成过程:

KSA包含步操作,每一步操作与PRGA非常相似,该过程将内部状态初始化,并将指针位置设为0。具体过程如下:

初始化:

操作过程:


A5算法是用于GSM系统的流密码算法。其初始化向量是64比特的会话密钥和22比特的帧序列号,生成228比特的密钥流,加密与解密各114比特。会话密钥在通话期间被使用,但是帧序列号在通话期间会改变。

A5算法可分成三个阶段:

第一阶段,3个移位寄存器初始全部设置为0,然后在64个周期内,将每个线性反馈移位寄存器都移位64次,每次移位后将密钥与每个线性反馈移位寄存器的最低位比特异或,之后在22个时钟周期内,将每个线性反馈移位寄存器都移位22次,每次移位后将22比特帧序列与每个线性反馈移位寄存器的最低位比特异或。记此时的内部状态为

第二阶段,由状态出发,按照钟控规则移位100个周期,与第一阶段不同的是,不进行异或操作,舍弃密钥流。记此时的内部状态为

第三阶段,由状态出发,按照钟控规则对进行移位操作,的最高位异或生成228比特的密钥流。 

上面提到一个名词:线性反馈移位寄存器(Linear Feedback Shift Register, LFSR)。它是反馈移位寄存器(Feedback Shift Register, FSR)中的一种。FSR是由移位寄存器和反馈函数组成,其中移位寄存器是一个序列,位是移位寄存器长度的单位。如果是位长,则为-位移位寄存器。每次运算时得到一位,此时移位寄存器中全部向左移动一位。这样最左端的位被舍去,最右端的位需要更新,根据寄存器中其他位经过反馈函数计算得到最右端的位。最后,移位寄存器输出一位,一般为的值。如图:



而LFSR的反馈函数为异或运算,如图:


 

下面,我们用一个4位LFSR来举例说明其工作原理:


如上图所示,反馈函数的输入为第4位和第1位,假设初始值为1111,在输出序列重复之前(输出序列从开始到重复前的长度称为周期),能够产生的状态序列是:

1111,1110,1101,1010,0101,1011,0110,1100,1001,0010,0100,1000,0001,0011,0111

则输出序列(状态序列的最高位)为:111101011001000。

对于一个-位LFSR有种内部状态(全部是0的状态除外,因为运算结果不能产生别的内部状态),即-位LFSR在重复之前,能够产生位长的伪随机序列。而-位LFSR能够产生种内部状态是需要某种抽头序列(选择寄存器某些位参与计算)。为了能够有最大周期的LFSR,则要求抽头序列加1后的多项式(多项式的阶是移位寄存器的长度)是本原多项式模2(一个阶本原多项式是不可约多项式,它能够整除,不能整除是能够整除)。

假设LFSR的长度是32,抽头位置是1、2、3、5、7,则通过产生的多项式为(它能够整除,不能整除是能够整除)。 

A5算法中有三个LFSR:,长度分别为19、22、23。它们的抽头序列的多项式分别为:

 PS:附件为RC4的C++实现

 

 

 

 

如社区发表内容存在侵权行为,您可以点击这里查看侵权投诉指引

游戏学院公众号二维码
腾讯游戏学院
微信公众号

提供更专业的游戏知识学习平台