《数据加密与PKI应用（微课版）》 课件 Chapter03-流加密算法

数据加密与PKI应用第3章流加密算法流加密算法即流密码（StreamCipher），又被称为序列密码，是对称加密体制中的一类加密算法。由于流加密算法的研究具有坚实的数学基础和丰富的研究成果，因而被广泛应用于军事、外交等重要部门的保密通信领域。目录013.1有限域上的多项式运算023.2流加密算法的基本原理033.3反馈移位寄存器043.4典型流加密算法

G是定义了一个二元运算“+”的集合，如果这个运算满足下列性质，那么G就被称为一个群（Group），记为(G,+)。

(1)封闭性：如果a和b都属于G，那么a+b也属于G；

(2)结合律：对于G中的任意元素a、b和c，都有(a+b)+c=a+(b+c)成立；

(3)单位元：G中存在单位元e，对于G中任意元素a，都有a+e=e+a=a成立；

(4)逆元：对于G中的任意元素a，G中都存在元素a'，使得a+a'=a'+a=e成立。

【例3-1】试分析整数集合Z4={0,1,2,3}对于“模4加法”运算，是否构成一个群。

(1)由于集合中任意两个元素进行“模4加法”运算，结果仍然是该集合中的元素，所以这个集合符合“封闭性”。

(2)该集合中的任意3个元素的运算满足结合律。(3)该集合中存在单位元e=0。

(4)集合中每个元素都可以在该集合中找到它的逆元，使得该元素与其逆元进行“模4加法”运算的结果为单位元0。

由于这个集合在“模4加法”运算中满足封闭性、结合律，存在单位元，每个元素都存在逆元，所以这个集合对于“摸4加法”运算构成一个群。群1)交换群：如果群(G,+)中的运算“+”还满足交换律，即对G中的任意元素a和b，都有a+b=b+a成立，则称(G,+)为一个交换群，或者阿贝尔群（AbelianGroup）。2)群的阶：如果一个群中的元素是有限的，则称这个群为有限群，否则这个群是一个无限群。有限群中元素的个数称为群的阶。3)循环群与生成元：重复使用群中的运算，即构成该群的“幂”运算，例如，a3=a+a+a，并且规定a0=e，即群中元素的0次幂的结果等于单位元。如果一个群的所有元素都是a的幂ak（k为整数），则称这个群是一个循环群，a被称为这个群的生成元。4)群中元素的阶：对于群G中的元素a，满足ai=e的最小正整数i称为元素a的阶。群

R是定义了两个二元运算“+”和“×”的集合，如果这两个运算满足下列性质，那么R就被称为一个环（Ring），记为(R,+,×)。

(1)(R,+)是一个交换群；

(2)“×”运算具有封闭性：如果a和b都属于R，那么a×b也属于R；

(3)“×”运算满足结合律：对于R中的任意元素a、b和c，都有(a×b)×c=a×(b×c)成立；

(4)两个运算满足分配律：对于R中的任意元素a、b和c，都有(a+b)×c=a×c+b×c和c×(a+b)=c×a+c×b成立。

【例3-2】试分析整数集合Z4={0,1,2,3}对于“模4加法”运算和“模4乘法”运算，是否构成一个群。

(1)对于交换群的分析可知，该整数集合对于“模4加法”运算构成一个交换群。

(2)由于该集合中任意两个元素进行“模4乘法”运算的结果仍然是该集合中的元素，所以这个集合的“模4乘法”运算具有封闭性。

(3)该集合中任意3个元素的“模4乘法”运算满足结合律。

(4)该集合中任意3个元素的“模4加法”运算和“模4乘法”运算满足分配律。

该集合上的“模4加法”和“模4乘法”构成一个环。环1)交换环：如果环(R,+,×)对于“×”运算满足交换律，即对R中的任意元素a和b，都有a×b=b×a成立，则称R为一个交换环。2)整环：对于一个交换环(R,+,×)，如果存在一个“×”运算的单位元s，即对R中任意元素a，使得a×s=s×a=a成立；同时，该环无零因子，即对于R中任意两个元素a和b，如果a×b的结果是“+”运算的单位元，那么a或b中一定存在一个“+”运算的单位元。此时，称R为一个整环。

另外，环中任意两个元素a和b，如果a×b=0（0是该环中“+”运算的单位元），那么要么a为0，要么b为0，即该环无零因子，所以这个环也是一个整环。环

如果F是定义了两个二元运算“+”和“×”的集合，如果这两个运算满足下列性质，那么F就被称为一个域（Field），记为(F,+,×)。

(1)(R,+)是一个交换群；

(2)非0元的“×”运算构成交换群；

(3)满足分配律。

【例3-3】试分析整数集合Z4={0,1,2,3}对于“模4加法”运算和“模4乘法”运算，是否构成一个域。

(1)这个集合对于“模4加法”运算构成一个交换群；

(2)假设该集合的非0集合为Z4*，即Z4*={1,2,3}。对于“模4乘法”运算，这个集合单位元e=1，元素1的逆元是1；元素3的逆元是3；元素2没有逆元。

(3)满足分配律。

由于元素2对于“模4乘法”运算没有逆元，所以这个定义了“模4加法”和“模4乘法”运算的集合Z4={0,1,2,3}不是一个域，它只能构成一个环。域

如果F是定义了两个二元运算“+”和“×”的集合，如果这两个运算满足下列性质，那么F就被称为一个域（Field），记为(F,+,×)。

(1)(R,+)是一个交换群；

(2)非0元的“×”运算构成交换群；

(3)满足分配律。

【例3-4】试分析整数集合Z5={0,1,2,3,4}对于“模5加法”运算和“模5乘法”运算，是否构成一个域。

(1)这个集合对于“模5加法”运算构成一个交换群；

(2)假设该集合的非0集合为Z5*，即Z5*={1,2,3,4}。对于“模5乘法”运算，这个集合单位元e=1，元素1的逆元是1；元素2的逆元是3；元素3的逆元是2；元素4的逆元是4。

(3)这个集合满足分配律。

所以这个定义了“模5加法”和“模5乘法”运算的集合Z5={0,1,2,3,4}是一个域。域

当q为素数时，整数集合Zq={0,1,2,...,q-1}对于“模q加法”和“模q乘法”运算就构成了一个域，记为GF(q)；当q不是素数时，只能构成一个环。

如果一个域中的元素是有限的，则称这个域是有限域。有限域也被称为伽罗瓦域（GaloisField），在密码学中主要使用有限域。GF(2)={0,1}是一个包含两个元素“0”和“1”的有限域，该有限域中定义的两个运算分别是“模2加法”和“模2乘法”。

有限域F中非零元组成的集合F*关于乘法组成的群称为有限域的乘法群。假设Fq是一个含有q个元素的有限域，其乘法群Fq*=Fq\{0}是一个循环群，此时Fq*的生成元称为Fq的本原元，并且Fq中共有

个本原元。有限域和本原元

设R是整数环，x为变量，则R上形式如下所示的元素称为R上的多项式。anxn+an-1xn-1+...+a1x+a0，ai∈R

设f(x)=anxn+...+a1x+a0（an≠0）是整数环R上的多项式，则称多项式f(x)的次数为n，记为degf=n。

如果多项式f(x)=anxn+an-1xn-1...+a1x+a0，多项式g(x)=bnxn+bn-1xn-1+...+b1x+b0，那么多项式加法、乘法公式如下：f(x)+g(x)=(an+bn)xn+(an-1+bn-1)xn-1+...+(a1+b1)x+(a0+b0)f(x)·g(x)=(an·bn)xn+n+(an·bn-1)xn+(n-1)+..+(an-1·bn)x(n-1)+n+...+(a0·b0)

举例：设f(x)=x7+x+1，g(x)=x6+x4+x2+x+1，并且f(x)∈F2(x)，g(x)∈F2(x)，计算f(x)+g(x)和f(x)·g(x)的结果。多项式整数环设f(x)和g(x)是整数环R上的任意两个多项式，其中g(x)≠0。如果存在一个多项式q(x)，使得f(x)=q(x)·g(x)成立，则称g(x)整除f(x)，或者f(x)被g(x)整除，记作g(x)|f(x)，g(x)被称为f(x)的因式。设f(x)是整数环R上的非常数多项式，如果除了1和f(x)外，f(x)没有其他非常数因式，那么f(x)被称为不可约多项式，否则f(x)被称为合式。

【例3-6】多项式x2+1在整数域、复数域和F2(x)中是否可约。在整数域中，该多项式除了1和它本身，没有其它非常数因式，所以不可约，即它是不可约多项式。在复数域中，x2+1=(x+i)·(x-i)，所以可约，该多项式是合式。在F2(x)中，x2+1=(x+1)·(x+1)，所以可约，该多项式是合式。多项式整除与不可约多项式

设f(x)=anxn+an-1xn-1+...+a1x+a0和g(x)=bmxm+bm-1xm-1+...+b1x+b0是整数环R上的两个多项式，则一定存在多项式q(x)和r(x)，使得：

f(x)=q(x)·g(x)+r(x),degr<degg

其中q(x)称为f(x)被g(x)除所得的不完全商，r(x)称为f(x)被g(x)除所得的余式。【例3-7】设f(x)=x4+x+1和g(x)=x2+1是F2(x)多项式，求q(x)和r(x)。r0(x)=f(x)-x2·g(x)=x2+x+1

r1(x)=r0(x)-1·g(x)=x所以，q(x)=x2+1，r(x)=x，即x4+x+1=(x2+1)·(x2+1)+x。设r-2(x)=f(x),r-1(x)=g(x)，反复运算多项式Euclid除法，则：r-2(x)=q0(x)·r-1(x)+r0(x),r-1(x)=q1(x)·r0(x)+r1(x),r0(x)=q2(x)·r1(x)+r2(x),......,rk-3(x)=qk-1(x)·rk-2(x)+rk-1(x),rk-2(x)=qk(x)·rk-1(x)+rk(x),此时rk(x)=0，gcd(f(x),g(x))=rk-1(x)。rk-1(x)是多项式Euclid除法中最后一个非零除式。将上述过程反过来计算，则可以找到s(x)和t(x)：s(x)·f(x)+t(x)·g(x)=gcd(f(x),g(x))多项式欧几里得除法多项式欧几里得除法

设p是任意给定的素数，n是任意一个正整数。如果f(x)是域Zp上的一个n次不可约多项式，则Zp[x]/f(x)是一个域。域Zp[x]/f(x)包含pn个元素。Zp[x]/f(x)={a0+a1x+...+an-1xn-1}将GF(pn)[x]标记为Zp[x]/f(x)，则GF(pn)[x]={a0+a1x+...+an-1xn-1}，其系数的加法和乘法相当于模p的加法和乘法，多项式的加法和乘法相当于模f(x)的加法和乘法。【例3-9】计算有限域Z2[x]/(x2+x+1)中元素的加法和乘法运算的结果。有限域的构造有限域的表示目录013.1有限域上的多项式运算023.2流加密算法的基本原理033.3反馈移位寄存器043.4典型流加密算法流加密技术的历史

流加密技术使用了一种特殊的二进制位运算，“异或”运算，异或运算相当于运算数进行模2加运算。

流加密算法的基本原理非常简单，就是将明文与一个随机密钥序列进行异或运算来产生密文。基于异或运算的特性，将密文与同一个密钥序列进行异或运算就可以恢复明文。ci=mi⊕ki,i=1,2,...mi=ci⊕ki,i=1,2,...

密算法的加密和解密都非常简单，易于实现，非常适合于计算资源有限的系统，例如移动电话、小型嵌入式系统等。密钥流生成器

由异或运算的特性可知，如果使用一个“真随机数生成器”得到一个密钥序列并且只使用1次，则可以实现“一次一密”加密，达到无条件安全性。

采用一个密钥流生成器，利用一个短的种子密钥来生成一个与明文长度相同的密钥序列作为加密密钥。这样，只要在发送者和接收者之间使用相同的密钥流生成器和种子密钥，就可以在他们之间产生相同的密钥序列。

当然，这样产生的密钥序列不是真正的随机序列，而是一种伪随机序列，只要这个伪随机序列满足真正随机序列的特性，那么就可以用来安全加密通信。目录013.1有限域上的多项式运算023.2流加密算法的基本原理033.3反馈移位寄存器043.4典型流加密算法线性反馈移位寄存器

生成密钥流的的基本部件是反馈移位寄存器（FSR,FeedbackShiftRegister）。反馈移位寄存器的组成：n个寄存器一个反馈函数f(a1,a2,...,an)

ai表示第i级寄存器（1≤i≤n），ai的取值为0或1。

在任一时刻，这些寄存器的内容构成了反馈移位寄存器的一个状态。每一个状态实际上对应着一个n维向量(a1,a2,...,an)，总共有2n个状态向量。线性反馈移位寄存器

如果反馈函数f(a1,a2,...,an)是a1,a2,...,an的线性函数，则称这样的移位寄存器为线性反馈移位寄存器（LFSR,LinearFeedbackShiftRegister）。反馈函数：f(a1,a2,...,an)=b1·a1⊕b2·a2⊕...⊕bn·an

由于系数bi的值是二进制数值，所以系数可以被看作是“开关”。

如果反馈函数的系数恒为零（b1，b2，...，bn都为0），则无论初始状态如何，在n个时钟脉冲后，每个寄存器的内容都必然为0，以后的输出也将全部为0，因此，通常假设系数b1，b2，...，bn不全为0。线性反馈移位寄存器

【例3-11】一个3级线性反馈移位寄存器的初始状态(a1,a2,a3)=(1,0,1)，反馈函数为f(a1,a2,a3)=a1⊕a3，计算这个3级线性反馈移位寄存器的状态和输出结果。

该3级线性反馈移位寄存器的输出结果为101001110100111......。从第8行开始，寄存器的状态恢复到了初始状态，寄存器状态和输出开始重复，所以周期为7。输出周期每个线性反馈移位寄存器都有一个关联的特征多项式，该特征多项式与线性反馈移位寄存器的数学结构有关。p(x)=bnxn+bn-1xn-1+...+b1x+1，

如果线性反馈移位寄存器的特征多项式是本原多项式，那么线性反馈移位寄存器的输出序列达到最大周期，其输出序列为m序列。

输出序列的周期取决于寄存器的初始状态和反馈函数。在GF(2)上，对于n级线性反馈移位移位寄存器，最多有2n个不同的状态，去除全0的状态，输出序列的周期最多为2n-1，

周期达到最大值的序列称为m序列。输出周期a对应的特征多项式是一个本原多项式，所以a可以输出m序列，输出序列的周期为7。a的线性反馈函数为：fa(a1,a2,a3)=a3⊕a1。a的初始状态都是全“1”，其输出序列为“1110100”。b对应的特征多项式不是一个本原多项式，所以b不会输出m序列。b的线性反馈函数为：fb(a1,a2,a3,a4)=a4⊕a3⊕a2⊕a1。a的初始状态都是全“1”，其输出序列为“11110”。

【例3-12】a是一个3级线性反馈移位寄存器，其特征多项式为pa(x)=x3+x+1；b是一个4级线性反馈移位寄存器，其特征多项式为pb(x)=x4+x3+x2+x+1。试分析a和b是否输出m序列，给出a和b的线性反馈函数。如果a和b的初始状态都是全“1”，请给出输出序列循环。已知明文攻击【例3-13】设一个流密码算法使用了一个GF(2)上的3级线性反馈移位寄存器作为密钥流生成器，已知明文为0100010001B的密文为1010110110B，试破译该加密算法。

通过明文和密文，可以计算得到密钥序列为：0100010001B

⊕

1010110110B

=

1110100111B，也就是说a1=1，a2=1，a3=1，a4=0，a5=1，a6=0。因此，反馈函数为：非线性反馈移位寄存器

每个线性反馈移位寄存器都产生一个不同的序列：x1(i),x2(i),...,xn(i)。

密钥序列k=(k1,k2,...,kt,...)可以利用一个非线性组合函数：

f(x1(i),x2(i),...,xn(i))，根据每个线性反馈移位寄存器的输出来产生，即：

kt=f(x1(t),x2(t),...,x3(t)),t≥1。

为了获得更好的安全性，可以将多个线性反馈移位寄存器组合起来使用，从而获得非线性特性。非线性反馈移位寄存器∵kt=f(x1(t),x2(t),x3(t)),t≥1∴当x1(1)=0,x2(1)=0,x3(1)=0时，k1=0·0⊕0⊕0·0=0当x1(2)=0,x2(2)=0,x3(2)=1时，k2=0·0⊕0⊕0·1=0当x1(3)=0,x2(3)=1,x3(3)=0时，k3=0·0⊕1⊕0·0=1......

【例3-14】由3个线性反馈移位寄存器组合成一个非线性反馈移位寄存器，其非线性组合函数f(x1(i),x2(i),x3(i))=x1(i)·x3(i)⊕x2(i)⊕x2(i)·x3(i)，试计算该非线性反馈移位寄存器的输出序列。目录013.1有限域上的多项式运算023.2流加密算法的基本原理033.3反馈移位寄存器043.4典型流加密算法A5/1算法概述

A5算法是欧洲GSM(全球移动通信系统)标准中规定的加密算法，用于GSM中移动电话与基站之间的语音加密。其中，A5/1算法为强加密算法，适用于欧洲地区；A5/2算法为弱加密算法，适用于欧洲以外的地区。线性反馈移位寄存器fA()=A[13]⊕A[16]⊕A[17]⊕A[18]fB()=B[12]⊕B[16]⊕B[20]⊕B[21]fC()=C[17]⊕C[18]⊕C[21]⊕C[22]钟控方式“择多”原则：

当A[8]、B[10]和C[10]3个值中有两个“1”时，值为“1”的寄存器对应的线性反馈移位寄存器右移1位，值为“0”的寄存器对应的线性反馈移位寄存器不移位；当这3个值中有两个“0”时，值为“0”的寄存器对应的线性反馈移位寄存器右移1位，值为“1”的寄存器对应的线性反馈移位寄存器不移位。输出结果

每个时钟周期，A5/1算法A[18]、B[21]和C[22]进行异或运算，其结果作为整个算法1比特的密钥输出。非线性反馈移位寄存器的密钥流输出函数为：f(A[18],B[21],C[22])=A[18]⊕B[21]⊕C[22]。RC4算法概述

RC4算法是一种基于非线性数据表变换的流加密算法。它以一个足够大的数据