计算机安全技术第八讲信息保密技术

第裕信息保密枝木(2)

分组密码的分析方法（续）

■一种攻击的复杂度可以分为两部分：数据复杂

度和处理复杂度。

-数据复杂度是实施该攻击所需输入的数据量。

-处理复杂度是处理这些数据所需的计算量。

■对某一攻击通常是以这两个方面的某一方面为

主要因素，来刻画攻击复杂度O

【例如】

-穷举攻击的复杂度实际就是考虑处理复杂度；

.差分密码分析其复杂度主要是由该攻击所需的明密

文对的数量来确定。

几种常见的攻击方法

1,强力攻击

强力攻击可用于任何分组密码，且攻击的复杂度

只依赖于分组长度和密钥长度，严格地讲攻击所

需的时间复杂度依赖于分组密码的工作效率（包

括加解密速度、密钥扩散速度以及存储空间

等）。

强力攻击常见的有：穷举密钥搜索攻击、

字典攻击、查表攻击和时间-存储权衡攻击等。

几种常见的攻击方法（续）

2,线性密码分析

本质：一种已知明文攻击方法。

基本思想：通过寻找一个给定密码算法的有效的

线性近似表达式来破译密码系统。

对已知明文密文和特定密钥，寻求线性表示式

（Q.x）㊉（6.y）=（d•x）

式中，（。也"层攻击参数。对所有可能密钥，此表

达式以概率5=1/2成立。对给定的密码算法，

使|2-1/2|极大化。为此对每一盒的输入和输

出构造统计线性路线，并最终扩展到整个算法。

分组密码的工作模式

-常用的分组密码工作模式有4种:

L电子密码本即ECB模式

2.密码分组连接模式(CBC)模式

3.密码反馈模式(CFB)模式

4.输出反馈模式(OFB)模式。

ECBfElectronicCodeBook)

加密过程

解密过程

CBC(CipherBlockChaining)

Pn

I]

IV----►㊉4.㊉

]

|?|k—►|DES|I?|

C2C“

加密过程

c”

»|DES|k-»|DES|

—^1DESI

I

IV----►㊉A㊉---►㊉

IJ

PlP2Pn

解密过程

CFB(CipherFeedBack)

加密过程

解密过程

OFB(OutputFeedBack)

加密过程

解密过程

2.3公钥加密技术

■本节提示

2.3.1基本概念

2.3.2RSA公钥密钥算法

2.3.3EIGamal算法

2.3,4椭圆曲线算法

2.3.1基本概念

■1976年，W.Diffie和MEHellman发表了“密码学的新

方向(NewDirectionsinCryptography)”一文，提由了

公栩密码学(Public-keycryptography)的思想，在公

钥密码体制(Public-keycryptosystem)中加密密朝和

解密密钥是不同的，加密密钥可以公开传播而不会危

及密码体制的安全性。

-通信的一方利用某种数学方法可以产生一个密钥对，

一个称为公转(Public-key),另外一个称为私钥

(Private-key)o该密钥对申的公钥与私钥是不同的，

但又是相互对应的，并且由公钥不能推导出对应的私

钥。选择某种算法(可以公开)能做到：用公钥加密

的数据只有使用与该公钥配对的私钥才能解密。

基本概念（续）

■公钥加密算法的核心——单向陷门函数，即从

一个方向求值是容易的。但再逆向计算却很困

难，从而在实际上成为不可行。

■定义L设/是一个函数，如果对任意给定的工,

计算y，使得》=/（、）是容易计算的，但对于任意

给定的y，计算x，使得工二厂（丁屋难解的，

即求/的逆函数是难解的，则称/是一个单向

函数。

基本概念（续）

■定义2.设/是一个函数，t是与/有关的

一个参数。对于任意给定的x,计算y,

使得y='是容易的。如果当不知参数/

时，计算/的逆函数是难解的，但当知

道参数，时，计算函数/的逆函数是容

易的，则称/是一个单向陷门函数，参

数,称为陷门。

2.3.2RSA公钥密码算法

■RSA是Rivet,Shamir和Adleman于1978年在美

国麻省理工学院研制出来的，它是一种比较典

型的公开密钥加密算法。

■基础

大数分解和素性检测——将两个大素数相乘在

计算上很容易实现，但将该乘积分解为两个大

素数因子的计算量是相当巨大的，以至于在实

际计算中是不能实现的。

RSA公钥密码算法(续)

■算法内容

⑴公钥

选择两个互异的大质数p和q，使〃=夕?，可〃)=(p-1)(9-1)0(〃)是

欧拉函数，选择一个正数e，使其满足(自押1,

贝IJ将K°=(〃,e)(乍为公钥。

(2)私钥

求出正数d使其满足e*d=1mod0卜7)d)>1，则将

酌=(。，)，夕)作为私钥。

(3)加密变换

府明文河作变换，使C=£K,,(M)=〃emod〃，从而得到密文C。

(4)解密变换「

将密文C作变换，使M=OKs(C)=C，mod”，从而得到明文

RSA公钥密码算法（续）

■如果A要发送信息M给B,A和B之间用以

下方式进行通信：

计算密文C=一发送C给B-从A

接收C-计算明文M=OK£C）.

■一般要求p,q为安全质数，现在商用的

安全要求为n的长度不少于1024位。

■应用：PEM,PGP

RSA公钥密码算法(续)

-算法的安全性分析

1.如果密码分析者能分解〃的因子夕和q,他就可以

求出。(〃)和解密的密钥d,从而能破译RSA,因此破

译RSA不可能比因子分解难题更困难。

2.如果密码分析者能够不对〃进行因子分解而求得，则

可以根据de=1mod0(H)

求得解密密钥d,从而破甲RSA。因为

P+q=n-。⑺+1p_q=/p+q)2—4孔

所以知道。⑺和〃就可以容嘉地表得,和9，从而成

功分解〃，因此，不对〃进行因子分解而直接计算

。(〃)并不比对〃进行因子分解更容易。

RSA公钥密码算法（续）

3.如果密码分析者既不能对n进行因子分解，也不

能求放⑺而直接求得第甯密钥d，则他就可以

计算是的倍数。而且利用

M的倍数可以容易地分解出n的因子。因此

直接计算解密密钥d并不比对n进行因子分解

更容易。

■注意问题

■p和q的长度相差不能太多.

■p-1和q-1都应该包含大的素因子。

■p-1和q-1的最大公因子要尽可能小。

2.4流密码技术

-本节友情提示

2.4.1流密码基本原理

2.4.2二元加法流密码

2.4.3几种常见的流密码算法

2.4流密码技术

■在单钥密码体制中，按照加密时对明文处理方

式的不同，可分为分组密码和流密码。

■流密码亦称为序列密码，是将待加密的明文分

成连续的字符或比特，然后用相应的密钥流对

之进行加密，密钥流由种子密钥通过密钥流生

成器产生。

■密钥流可以方便地利用以移位寄存器为基础的

电路来产生。

-特点：实现简单，加密速度快，错误传播低。

2.4.1流密码基本原理

■原理

通过随机数发生器产种子密钥K

生性能优良的伪随机

序列（密钥流），使随机数发生器

用该序列加密信息流

（逐比特加密），得密钥流Ki

到密文序列。

明文流777/>加密变换一密文流Ci

2.4.2二元加法流密码

符号描述与示例

加密操作：黑?操作：

密'钥流：k］,k2,■■■-笛钥流:k],k2,k2,■■■

㊉㊉㊉㊉㊉㊉

密?文流：C],C2,C3,・・・

明文流：nipm2,m3,...

([(

光?又VIL：5,c?,c2,■■■明文流：m15m2,m3,...

［例］电报内容“专列下午2点到达。”的加密过程如下：

密钥流：78,35,02,E4,B2…

㊉㊉㊉㊉㊉

明文流：D7,A8,CLD0,CF,C2,CE,E7,32,B5E3,B5,BD,B4,EEALA3

密文流：A^9D,C3,34,7D…

元加法流密码（续）

-随机性假设：

■在序列的一个周期内，。与1的个数相差至多

为1;

■在序列的一个周期圈内，长为1的妙数占

总游程数的1/2,长为2的游程数•占总游程数

的，…，长为的游程数占总游程数的

且在等长的游程中0,1游程各占一半；

■序列的异相自相关系数为一个常数。

■满足随机性假设的序列称为伪随机序列。

元加法流密码(续)

■流密码的设计最核心的问题是密钥流生成器的

设计。

■密钥流生成器一般由线性反馈移位寄存器

(LinearFeedbackShiftRegisterLFSR)和一个

非线性组合函数两部分构成，其中，线性反馈

移位寄存器部分称为驱动部分，另一部分称为

非线性组合部分。

驱动部分---------------►非线性______密钥流左

(LFSR)---------------►组合部分

二元加法流密码(续)

■反馈移位寄存器(feedbackshiftregister)

1.组成结构

反馈移位寄存器由n位的寄存器(称为n-级移位寄存

器)和反馈函数(feedbackfunction)组成。移位寄

存器序列的理论由挪威政府的首席密码学家Ernst

Selmer于1965年提出。

反馈函数和〃“j

元加法流密码(续)

■2.工作原理

移位寄存器中所有位右移一位，最

右边移出的位是输出位，最左端的一位

由反馈函数的输出填充，此过程称为进

动一拍。反馈函数f(b1,…,bn)是n元

(bl,…,bn)的布尔函数。移位寄存器根

据需要不断地进动m拍，便有m位的输

出，形成输出序列Ol02…OITI。

元加法流密码(续)

■［例1］如图所示为一个3-级反馈移位寄存器，反馈函数

f(x)=b3。b2,初态为：100o输出序列生成过程如下:

■状态输出位一一一

100一0

110一0

011一1

101一1

110一0(a)移位寄存器结构图

011一1、

101一1初态(011)

因此，对应初态(100)的输出序列为：⑴。)一(1°1)

011011...(周期为3)(b)状态转移图

元加法流密码（续）

3.输出序列的周期

移位寄存器的周期是指输出序列中连续且重复出现部分的长度

（位数）。

如［例1］输出序列中连续且重复出现的序列为：011,则其周期

为3。其输出序列可表示为：0（011）8。将其用图的方式表示出来

称为“序列圈”，如图（c）所示。

4.状态

某一时刻移位寄存器中所有位的值称为一个状态。n-级的

FSR共有2rl个状态。

3-级移位寄存器的状态共有23=8个，它们分别是：

000,001,010,011,100,101,110,1110

但是，并非所有的状态都被用到。如［例1］除初始状态以外，仅有

三个状态周期性地参与了输出序列的产生。

元加法流密码（续）

■当反馈移位寄存器的反馈函数是异或变

换时，这样的反馈移位寄存器叫线性反

馈移位寄存器，如图所示：

元加法流密码（续）

•移位寄存器中存储器的个数称为移位寄存器的

级数，移位寄存器存储的数据为寄存器的状态,

状态的顺序从左到佑依次为从最高位到最低位。

•在所有状态中…叫初态，并且从左到

右依次称为第一级、第二级、・・.、第n级，亦

称为抽头1、抽头2、抽头3、..・・、插头n。n级

线性反馈移位寄存器的有效状态为？小个。它

主要是用来产生周期大，统计性能分的序列。

元加法流密码（续）

■非线性组合部分主要是增加密钥流的复杂程度,

使密钥流能够抵抗各种攻击（对流密码的攻击

手段主要是对密钥流进行攻击）。

■以线性反馈移位寄存器产生的序列为基序列，

经过不规则采样、函数变换等（即非线性变

换），就可以得到实用安全的密钥流。

■不规则采样是在控制序列下，对被罡样序列进

行采样输出，得到的序列称为输出序列。

■控制序列的控制方式有钟控方式、抽取方式等,

函数变换有前馈变换、有记忆变换等。

元加法流密码（续）

■代表性的序列模型

1、钟控模型

当LFSR-1输出1时，时钟信号被采样，即能通

过“与门”驱动LFSR-2进动一拍；当LFSR-1为

。时，时钟信号不被采样，即不能通过“与

门”，此时LFSR-2不进动，重复输出前一位。

钟控发生器的示意图如下：

■2、前馈模型

Geffe发生器是前馈序列的典型模型，其前馈函

数g(x)=(xlx2)㊉(x2x3)为非线性函数，即当

LFSR-2输出1时，g(x)输出位是LFSR-1的输出位;

当LFSR-2输出0时，g(x)输出位是LFSR-3的输出

位。Geffe发生器示意图如下：

2.4.3几种常见的流密码算法

1.A5算法

-法国，欧洲数字蜂窝移动电话系统（GSM）中使用的序列密码加密

算法

■3个LFSR,移位寄存器的长度分别是19、22和23,但抽头都较少

2.Rambutan算法

■英国的算法，由通信电子安全组织设计

-5个LFSR组成，每个LFSR长度大约为80-级，而且有10个抽头。

3.RC4算法

-由RonRivest