第二讲 密码学

1第2讲信息保密技术与应用

理工学院生慧2主要内容

♦密码学基本知识

♦对称密码学

♦公钥密码学

♦信息加密应用技术

♦网络通信中的加密方式3一、密码学基本知识4主要内容&&&密码学概述密码学历史古典密码学7密码学概述

密码学是一门研究通信安全和保护信息资源 的既古老而又年青的科学和技术。 密码学包含两方面内容：密码编码学、密码 分析学。

密码编码学是对信息编码以隐蔽信息的一门学问。 密码分析学是研究分析破译密码的学问。

这二者既相互对立又相互促进，共同推动密 码学的发展。12密码学的历史

发展史

早在4000多年以前，古埃及人就在墓志铭中使用过类似于 象形文字那样奇妙的符号； 公元前约50年，凯撒密码－一种简单的字符替换－被认为 是最早的正式算法； 双轨式密码、网格式密码、字典编号密码； 传统密码学、现代密码学、量子密码学。

应用领域

军事、外交、情报 商业、个人通信18

密码学的起源和发展三个阶段：•••1949年之前 密码学作为一种技艺，是一门艺术，而不是一种科学 古典加密1949～1975年 shannon的“communicationtheoryofsecrecysystem”《保密系统的信息理论》

密码学成为科学 主要技术：单密钥的对称密钥加密算法1976年以后 Diffie,Hellman发表“newdirectionsincryptography”

密码学的新方向——公钥密码学10Alice加密机解密机Bob安全信道

密钥源♦密码学的目的：Alice和Bob两个人在不安全的信道上 进行通信，而破译者Oscar不能理解他们通信的内容。Shannon模型

Oscarxyxk9加解密过程示意图明文明文密文加密算法

解密算法

密钥密钥8

密码学基本概念♦明文：需要秘密传送的消息。♦密文：明文经过密码变换后的消息。♦加密：由明文到密文的变换。♦解密：从密文恢复出明文的过程。♦破译：非法接收者试图从密文分析出明文的过程。♦加密算法：对明文进行加密时采用的一组规则。♦解密算法：对密文进行解密时采用的一组规则。♦密钥：加密和解密时使用的一组秘密信息。

密文Ciphertext解密Decryption明文Plaintext加密Encryption密钥key11密码学基本概念

密码系统

一个密码系统可以用以下数学符号描述：

S={P，C，K，E，D}

P=明文空间

C=密文空间

K=密钥空间

E=加密算法

D=解密算法

当给定密钥k∈K时，加解密算法分别记 作Ek、Dk，密码系统表示为

Sk={P，C，k，Ek，Dk} C=Ek（P）

P=Dk（C）=Dk（Ek（P））13

密码算法分类-i♦按照保密的内容分:

受限制的（restricted)算法:算法的保密性 基于保持算法的秘密。

基于密钥（key-based)的算法:算法的保 密性基于对密钥的保密。14

密码算法分类-ii♦基于密钥的算法，按照密钥的特点分类：

对称密码算法（symmetriccipher)：又称传统密码算法 （conventionalcipher)，就是加密密钥和解密密钥相同，或 实质上等同，即从一个易于推出另一个。又称秘密密钥算 法或单密钥算法。

非对称密钥算法（asymmetriccipher):加密密钥和解密密钥 不相同，从一个很难推出另一个。又称公开密钥算法 （public-keycipher)。♦公开密钥算法用一个密钥进行加密,而用另一个进行解密.其 中的加密密钥可以公开,又称公开密钥（publickey)，简称 公钥.解密密钥必须保密,又称私人密钥（privatekey)私钥.简 称私钥。15

密码算法分类-iii♦按照明文的处理方法：

分组密码（blockcipher):将明文分成固定长度的组， 用同一密钥和算法对每一块加密，输出也是固定长度 的密文。

流密码（streamcipher):又称序列密码.序列密码每次 加密一位或一字节的明文，也可以称为流密码。 序列密码是手工和机械密码时代的主流古典加密技术代替密码置换密码代替密码代替密码（substitutioncipher）：明文中的每个字符被替换成密文中的另一个字符。简单代替，即单字母密码，如Caesar密码；多码代替密码；多字母代替密码；多表代替密码，如Vigenère密码。置换密码置换密码（permutationcipher）：又称换位密码（transpositioncipher），并没有改变明文字母，只改变了这些字母的出现顺序。Vigenère密码构成明文：每个字符惟一对应一个0~25间的数字。密钥：一个字符串，其中每个字符同明文一样对应一个数字，代表位移值，如a表示位移0，b表示位移1，c表示位移2，......）。加密过程：将明文数字串依据密钥长度分段，并逐一与密钥数字串相加（模26），得到密文数字串；最后，将密文数字串转换为字母串。1．维吉尼亚密码一种以移位代换为基础的周期代换密码，为1858年法国密码学家维吉尼亚提出。首先构造一个维吉尼亚方阵：它的基本阵列是26行26列的方阵.方阵的第一行是按正常顺序排列的字母表,第二行是第一行左移循环1位得到的,依此类推,得到其余各行.然后在基本方阵的最上方附加一行,最左侧附加一列,分别依序写上a到z26个字母,表的第一行与与附加列上的的字母a相对应,表的第二行与附加列上的字母b相对应..最后一行与附加列上的字母z相对应.分别构成了左移0位，1位，2位…，25位的26个单表代换加同余密码的密文序列。加密时，按照密钥字的指示，决定采用哪一个单表。AABCDEFGHIJ...YZBBCDEFGHIJK...ZACCDEFGHIJKL...ABDDEFGHIJKLM...BCEEFGHIJKLMNCDFFGHIJKLMNODEGGHIJKLMNOPEFHHIJKLMNOPQFGZZABCDEFGHI...XY维吉尼亚密码引入了“密钥”的概念，即根据密钥来决定用哪一行的密表来进行替换，以此来对抗字频统计Kerckhoffs假设1883

假定：密码分析者知道对方所使用的密码系统包括明文的统计特性、加密体制（操作方式、处理方法和加/解密算法）、密钥空间及其统计特性。不知道密钥。在设计一个密码系统时，目标是在Kerckhoffs假设的前提下实现安全。24密码分析♦假设破译者Oscar是在已知密码体制的前提下来破译

Bob使用的密钥。这个假设称为Kerckhoff（克尔克霍夫

）原则（1883年Kerchoffs第一次明确提出了编码的原则:加密算法应建立在算法的公开不影响明文和密钥的安全的基础上.）。最常见的破解类型如下：

1.唯密文攻击：Oscar具有密文串y. 2.已知明文攻击:Oscar具有明文串x和相应的密文y. 3.选择明文攻击：Oscar可获得对加密机的暂时访问， 因此他能选择明文串x并构造出相应的密文串y。

4.选择密文攻击:Oscar可暂时接近密码机,可选择密文串

y，并构造出相应的明文x.

这一切的目的在于破译出密钥或密文25

密码破译♦密码破译的原则:遵循观察与经验♦方法:采用归纳与演绎♦步骤:分析、假设、推测和证实♦三大要素：

语言的频率特征：e

连接特征:q…u,Iex,

重复特征:th,tion,tious英文中字母的相对频率26

密码破译已知密文信息如下：UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ

其字母相对频率（百分比）如下：P=13.33，Z=11.67，S=8.33，U=8.33，O=7.50，M=6.67，H=5.83D=5.00，E=5.00，V=4.17，X=4.17，F=3.33，W=3.33，Q=2.50，T=2.50

3.51.254.25A=1.67，B=1.67，G=1.67，Y=1.67，I=0.83，J=0.83，C=K=L=N=R=0

12.75323.57.750.250.53.75 2.757.757.52.750.58.569.2531.51.50.52.25 0.25042610 87.251412ABECDFGHIJKLMNOPQRSTUWXVYZ27

密码破译破译过程：第一步：P和Z很可能是明文字母e和t，字母S、U、O、M和H可能在集合{r,n,i,o,a,s}中，字母

A、B、G、Y、I、J可能在集合{w,v,b,k,x,q,j,z}中。第二步：最常见的双字母组合是“th”，密文中双字母组合频率“ZW”常见，因而可以假设：Z=t，W=h，根据第一步的判定可设P=e，第三步：ZWP出现在密文中，可以将该序列转换为“the”（英语中出现频率最高的3字母组 合）。第四步：在密文第一行中有序列“ZWSZ”，如果它们是一个词，则有“th_t”，其中的“S”有可 能是字母“a”。至此，有如下初步的破译结果：UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZtaeeteathateeaaVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXettathaeeeaethtaEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQeeetatetheet进行进一步的分析，完整的明文信息如下：ItwasdisclosedyesterdaythatseveralinformalbutDirectcontactshavebeenmadewith politicalRepresentativesofthevietconginmoscow28密码算法的安全性••无条件安全（Unconditionallysecure） 无论破译者有多少密文,他也无法解出对应的明文,即使他解出了,他也无法验证结果的正确性.

一次一密（One-TimePad)系统计算上安全（Computationallysecure）破译的代价超出信息本身的价值破译的时间超出了信息的有效期.29小结

&密码学由密码编码学和密码分析学组成

&按加解密密钥是否相同，密码学分为对 称密码学和公钥密钥学

&古典密码算法包括置换密码、代替密码 等30二、对称密码学31主要内容&对称密码学概述&分组密码&数据加密标准（DES）&流密码32对称密码学概述

加密：EK（M）=C

解密：DK（C）=M等效于DK（EK（M））=M数学变换 函数密钥K

明文密文数学变换 函数明文密钥K

密文33网络信息M对称密码算法密文C

对称密码学概述

密钥K用户A用户B信息M对称密码算法密文C 密钥K34对称密码学分类

块密码（分组密码）

一次若干位一组地对明文进行操作和运算

流密码（序列密码）

每次一位地对明文进行操作和运算35分组密码

工作方式

将明文分成固定长度的组（块），如 64bit一组，用同一密钥和算法对每一快加密， 输出也是固定长度的密文。

主要算法

DES、3DES、IDEA、RC2、AES等。36

数据加密标准（DES）的产生-i♦1973年5月15日,NBS（美国国家标准局，现名NIST， 是美国商业部下属的一个机构，1988年改为现名。） 开始公开征集标准加密算法,并公布了它的设计要求:(1)算法必须提供高度的安全性(2)算法必须有详细的说明,并易于理解(3)算法的安全性取决于密钥,不依赖于算法(4)算法适用于所有用户(5)算法适用于不同应用场合(6)算法必须高效、经济(7)算法必须能被证实有效(8)算法必须是可出口的37

数据加密标准（DES）的产生-ii♦1974年8月27日,NBS开始第二次征集,IBM提交了算法

LUCIFER，该算法由IBM的工程师在1971~1972年研 制♦♦♦♦1975年3月17日,NBS公开了全部细节1976年,NBS指派了两个小组进行评价1976年11月23日，采纳为联邦标准，批准用于非军事场合的各种政府机构1977年1月15日,“数据加密标准”FIPSPUB46发布38

DES的应用♦1979年，美国银行协会批准使用♦1980年，美国国家标准局赞同DES作为私人使用的标 准,称之为DEA（ANSIX.392）

1983年，国际化标准组织ISO赞同DES作为国际标准， 称之为DEA-1♦该标准规定每五年审查一次，计划十年后采用新标准♦最近的一次评估是在1994年1月，已决定1998年12月以 后，DES将不再作为联邦加密标准。39

DES的原理♦现代密码设计基本思想

混乱(confusion)：即在加密变换过程中使明文、密钥及密 文之间的关系复杂化。用于掩盖明文和密文间的关系。

散布(diffusion)：即将每一位明文信息的变化尽可能地散 布到多个输出的密文信息中，即改变一个明文尽可能 多的改变多个密文，以便隐蔽明文信息的统计特性。为避免密码分析者对密钥逐段破译，密码的设计应该保证密钥的每位数字能够影响密文中的多位数字 单独用一种方法，容易被攻破。 流密码只依赖于混淆；分组密码两者都用。40

数据加密标准（DES）算法

该算法分三个阶段实现1.给定明文X，通过一个固定的初始置换IP来排列X中的位，得到X0。

X0=IP（X）=L0R0

其中L0由X0前32位组成，R0由X0的后32位组成。

2.计算函数F的16次迭代,根据下述规则来计算LiRi(1<=i<=16）

Li=Ri-1,Ri=Li-1⊕F(Ri-1,Ki)

其中Ki是长为48位的子密钥。子密钥K1，K2，…，K16是作为 密钥K（56位）的函数而计算出的。

3.对比特串R16L16使用逆置换IP-1得到密文Y。

Y=IP-1（R16L16）41

数据加密标准（DES）算法图示♦DES利用56比特串长度的密钥K来加密长度为64位的 明文，得到长度为64位的密文

输入64比特明文数据 初始置换IP

在密钥控制下

16轮迭代 交换左右32比特 初始逆置换IP-1

输出64比特密文数据

DES算法框图42数据加密标准（DES）算法图示

输入64位比特明文 IP置换表L0R0迭代16次

Li=Ri-1

Ri=Li⊕f(Ri-1,Ki)（i=1,2,…16）

IP逆置换表 输出64位比特密文43数据加密标准（DES）Li-1Ri-1F+LiRiKi一轮加密的简图44

数据加密标准（DES）F函数说明

F（Ri-1,Ki）函数F以长度为32的比特串A=R（32bits）作第一个输入，以长度为48的比特串变元J=K(48bits)作为第二个输入。产生的输出为长度为32的位串。(1)对第一个变元A，由给定的扩展函数E，将其扩展成48位串E（A）;(2)计算E（A）+J，并把结果写成连续的8个6位串,B=b1b2b3b4b5b6b7b8;(3)使用8个S盒，每个Sj是一个固定的4×16矩阵，它的元素取0~15的整数。给定长度为6个比特串，如Bj=b1b2b3b4b5b6,计算Sj(Bj)如下：b1b6两个比特确定了Sj的行数,r(0<=r<=3);而b2b3b4b5四个比特确定了Sj的列数c（0<=c<=15）。最后Sj(Bj)的值为S-盒矩阵Sj中r行c列的元素（r,c）,得Cj=Sj(Bj)；(4)最后，进行固定置换P。45DES的F函数J=K(48bits)A=R(32bits)

EE(A)为48bits+

异或写成8个6比特串B1B2B3B4B5B6B7B8S1S2S3S4S5S6S7S8C1C2C3C4C5C6C7C8

P 32bitsF(A,J)46DES密钥产生过程(1)给定64位的密钥K，放弃奇偶校验位（8，16，…，64）并根据固定置换PC1来排列K中剩下的位。我们写

PC1(K)=C0D0其中C0由PC1(K)的前28位组成；D0由后28位组成;(2)对1<=i<=16，计算

Ci=LSi(Ci-1) Di=LSi(Di-1) LSi表示循环左移2或1个位置，取决于i的的值。i=1,2,9和16时移1个位置，否则移2位置;(3)Ki=PC2(CiDi),PC2为固定置换。47DES密钥产生图示

64位密钥字符串K PC1变换LS16

C16

C0LS1

C1LS2

C2LS16

D16PC2变换PC2变换48位K1648位K148位K256比特28比特

28比特

D0LS1

D1LS2

D248数据加密标准（DES）DES加密的一个例子＊

取16进制明文X：0123456789ABCDEF＊取密钥K为：133457799BBCDFF1＊去掉奇偶校验位（K8K16…K64）以二进制形式表示的密钥是00010010011010010101101111001001101101111011011111111000＊应用初始置换IP，我们得到：

L0=11001100000000001100110011111111 L1=R0=11110000101010101111000010101010＊然后进行16轮加密。＊最后对L16,R16使用IP-1得到密文：

85E813540F0AB40549

数据加密标准（DES）

DES密钥长度太小

DES迭代次数可能太少50

数据加密标准（DES）DES的破解

DES的实际密钥长度为56-bit，就目前计算机的计算机能力而言，DES不能抵抗对密钥的穷举搜索攻击。 1997年1月28日，RSA数据安全公司在RSA安全年会上悬赏10000美金破解DES，克罗拉多州的程序员Verser在Inrernet上数万名志愿者的协作下用96天的时间找到了密钥长度为40-bit和48-bit的DES密钥。 1998年7月电子边境基金会（EFF）使用一台价值25万美元的计算机在56小时之内破译了56-bit的DES。 1999年1月电子边境基金会（EFF）通过互联网上的10万台计算机合作，仅用22小时15分就破解了56-bit的DES。DES的安全性互补性。DES算法具有下述性质。若明文组x逐位取补，密钥k逐位取补，即y=DESk(x),则有这种互补性会使DES在选择明文破译下所需的工作量减半。弱密钥和半弱密钥。DES算法在每次迭代时都有一个子密钥供加密用。如果给定初始密钥k，各轮的子密钥都相同，即有k1=k2=…=k16就称给定密钥k为弱密钥(Weakkey)。DES的安全性若k为弱密钥，则有DESk(DESk(x))=xDESk-1(DESk-1(x))=x即以k对x加密两次或解密两次都可恢复出明文。其加密运算和解密运算没有区别。弱密钥下使DES在选择明文攻击下的搜索量减半。如果随机地选择密钥，弱密钥所占比例极小，而且稍加注意就不难避开。因此，弱密钥的存在不会危及DES的安全性。DES的安全性密文与明文、密文与密钥的相关性。

Meyer[1978]详细研究了DES的输入明文与密文及密钥与密文之间的相关性。表明每个密文比特都是所有明文比特和所有密钥比特的复合函数，并且指出达到这一要求所需的迭代次数至少为5。Konheim[1981]用2检验证明，迭代8次后输出和输入就可认为是不相关的了。DES的安全性S盒设计。

DES靠S盒实现非线性变换。密钥搜索机。

对DES安全性批评意见中，较为一致的看法是DES的密钥短了些。IBM最初向NBS提交的建议方案采用112bits密钥，但公布的DES标准采用64bits密钥。有人认为NSA故意限制DES的密钥长度。采用穷搜索对已经对DES构成了威胁．二重DES用DES进行两次加密，但这是否就意味着两重DES加密的强度等价于112bit密钥的密码的强度？答案是否定的。

中途相遇攻击法(Meet-in-the-MiddleAttack)由Diffie和Hellman[1977]最早提出，可以降低搜索量其基本想法如下。若有明文密文对(xi,yi)满足

yi=Ek2[Ek1[xi]]则可得z=Ek1[xi]=Dk2[yi]

二重DES

图4-14-1中途相遇攻击示意图

zEEDDxiyixizyi

k1

k1k2k2中途相遇攻击给定一已知明密文对(x1,y1)，可按下述方法攻击。以密钥k1的所有256个可能的取值对此明文x1加密，并将密文z存储在一个表中；从所有可能的256个密钥k2中依任意次序选出一个对给定的密文y1解密，并将每次解密结果z在上述表中查找相匹配的值。一旦找到，则可确定出两个密钥k1和k2；以此对密钥k1和k2对另一已知明文密文对(x2,y2)中的明文x2进行加密，如果能得出相应的密文y2就可确定k1和k2是所要找的密钥。中途相遇攻击对于给定明文x，以两重DES加密将有264个可能的密文。可能的密钥数为2112个。所以，在给定明文下，将有2112/264=248个密钥能产生给定的密文。用另一对64bits明文密文对进行检验，就使虚报率降为248-64=2-16。这一攻击法所需的存储量为256×8Byte，最大试验的加密次数2×256=257。这说明破译双重DES的难度为257量级。三重DES加密加密：y=Ek1[Dk2[Ek1[x]]]解密：x=Dk1[Ek2[Dk1[y]]]称其为加密-解密-加密方案，简记为EDE(encrypt-decrypt-encrypt)。此方案已在ANSIX9.17和ISO8732标准中采用，并在保密增强邮递(PEM)系统中得到利用。破译它的穷举密钥搜索量为21125×1035量级，而用差分分析破译也要超过1052量级。此方案仍有足够的安全性。51

其他分组算法♦3DES♦IDEA（国际数据加密算法）♦RC5♦CAST-128♦AES算法52

三重DES♦使用三（或两）个不同的密钥K1,K2,K3对数据块进行三次（或两次）加密，密钥长度为168（56×3）,加密一次要比进行普通加密的三次要快♦在DES的标准报告FIPS46-3中推荐使用K1=K3,这时三重DES的强度大约和112-bit的密钥强度相当♦三重DES有四种模型

DES-EEE3使用三个不同密钥顺序进行三次加密变换 DES-EDE3使用三个不同密钥依次进行加密-解密-加密变换 DES-EEE2其中密钥K1=K3顺序进行三次加密变换 DES-EDE2其中密钥K1=K3依次进行加密-解密-加密变换♦到目前为止还没有人给出攻击三重DES的有效方法53IDEA

InternationalDataEncryptionAlgorithm； 由瑞士联邦理工学院的XuejiaLai和JamesMassey

于1990年提出(西电，瑞士，上交大) IDEA是对称、分组密码算法，输入的明文为64位， 密钥为128位，生成的密文为64位；

IDEA是一种相对较新的算法，有坚强的理论基础， 已被证明可对抗差分分析和线性分析；目前还没 有发现明显的安全漏洞，应用十分广泛。 著名的电子邮件安全软件PGP就采用了IDEA进行 数据加密。54

RC5

RC5

由RonRivest研制，明文分组长度可调（16～64），循环次数(0～255)可调，密钥长度可调(0～2040)，能适应不同字长的CPU。适合于硬件及软件实现，快速。

RC5已经被做进RSA数据安全公司（RSADataSecurity)的主要产品中，如BSAFE，JSAFE以及S/MAIL。56

高级加密标准（AES）♦1997年4月15日美国国家标准和技术研究所NIST 发起了征集AES算法的活动并成立了专门的AES工 作组

目的是为了确定一个非保密的公开披露的全球免费使 用的分组密码算法用于保护下一世纪政府的敏感信息 并希望成为秘密和公开部门的数据加密标准♦1997年9月12日在联邦登记处公布了征集AES候选 算法的通告AES的基本要求是

比三重DES快或至少和三重DES一样 安全分组长度128比特，密钥长度为128/192/256比特♦1998年8月20日NIST召开了第一次候选大会并公 布了15个候选算法57高级加密标准（AES）－续

♦1999年3月22日举行了第二次AES候选会议从中 选出5个算法

MARSRC6SerpentTwofishRijndael

♦2000年10月，美国国家技术标准委员会(NIST) 选定比利时的“Rijndael”为AES

♦Rijndael是迭代分组密码，其分组长度和密钥 长度都是可变的；

♦为了满足AES的要求，分组长度为128bit，密 码长度为128/192/256bit，相应的轮数r为 10/12/14。

♦加密、解密过程不完全对称，使用了不同的代 码和S-盒，所以实现起来占用资源相对多一些。二、分组密码的运行模式

主要工作模式

即使有了安全的分组密码算法，也需要采用适当的工作模式来隐蔽明文的统计特性、数据的格式等，以提高整体的安全性，降低删除、重放、插入和伪造成功的机会。电子码本(ECB)密码反馈链接(CBC)密码反馈(CFB)输出反馈(OFB)。

电码本ECB模式直接利用加密算法分别对分组数据组加密。在给定的密钥下同一明文组总产生同样的密文组。这会暴露明文数据的格式和统计特征。

明文数据都有固定的格式，需要以协议的形式定义，重要的数据常常在同一位置上出现，使密码分析者可以对其进行统计分析、重传和代换攻击。

电码本ECB模式

xykDESyxkDES-1密码分组链接CBC模式每个明文组xi加密之前，先与反馈至输入端的前一组密文yi-1按位模2求和后，再送至加密算法加密各密文组yi不仅与当前明文组xi有关，而且通过反馈作用还与以前的明文组x1,x2,…,xi-1，有关密码分组链接CBC模式初始矢量IV(InitialVector)：第一组明文xi加密时尚无反馈密文，为此需要在寄存器中预先置入一个。收发双方必须选用同一IV。实际上，IV的完整性要比其保密性更为重要。在CBC模式下，最好是每发一个消息，都改变IV，比如将其值加一。密码分组链接CBC模式

CBC模式xiyikDESyix’kDES-1++64bit存储64bit存储yi-1填充(Padding)

给定加密消息的长度是随机的，按64bit分组时，最后一组消息长度可能不足64bit。可以填充一些数字，通常用最后1字节作为填充指示符（PI）。它所表示的十进制数字就是填充占有的字节数。数据尾部、填充字符和填充指示符一起作为一组进行加密。

数据填充PICBC的错误传播1.明文有一组中有错，会使以后的密文组都受影响，但经解密后的恢复结果，除原有误的一组外，其后各组明文都正确地恢复。2.若在传送过程中，某组密文组yi出错时，则该组恢复的明文x’i和下一组恢复数据x’i+1出错。再后面的组将不会受yi中错误比特的影响。k-比特密码反馈CFB模式若待加密消息必须按字符(如电传电报)或按比特处理时，可采用CFB模式。CFB实际上是将加密算法DES作为一个密钥流产生器，当k＝1时就退化为前面讨论的流密码了。CFB与CBC的区别是反馈的密文长度为k，且不是直接与明文相加，而是反馈至密钥产生器。k-比特密码反馈CFB模式

CFB模式

+

+xixiyiyikkXi64bitXi64bitYi64bitYi64bitDESDES-1选最左边

k位选最左边

k位kbitkbityi-Lyi-2yi-1k-比特密码反馈CFB模式CFB的优点它特别适于用户数据格式的需要。能隐蔽明文数据图样，也能检测出对手对于密文的篡改。CFB的缺点对信道错误较敏感，速度较慢。CFB也需要一个初始矢量，并要和密钥同时进行更换。输出反馈OFB模式将分组密码算法作为一个密钥流产生器，其输出的k-bit密钥直接反馈至分组密码的输入端，同时这k-bit密钥和输入的k-bit明文段进行对应位模2相加。克服了CBC和CFB的错误传播所带来的问题。对于密文被篡改难以进行检测不具有自同步能力，要求系统要保持严格的同步输出反馈OFB模式

OFB模式

+xiyik64bit64bitDES选最左边

k位ki64bit

寄存器kbitkbit

+xiyik64bit64bitDES-1选最左边

k位kbit64bit

寄存器kbitki比较和选用ECB模式，简单、高速，但最弱、易受重发攻击，一般不推荐。CBC适用于文件加密，但较ECB慢。安全性加强。当有少量错误时，也不会造成同步错误。OFB和CFB较CBC慢许多。每次迭代只有少数bit完成加密。在字符为单元的流密码中多选CFB模式。OFB用于高速同步系统，克服差错传播。58

流密码♦流密码（StreamCipher)又称为序列密码。其加密原理 是将明文按顺序与密钥逐个进行模二加（异或）运算。♦特点：加/解密运算只是简单的异或。♦关键：密码强度主要靠密钥流的随机性♦解密过程与加密过程一致♦序列密码的安全性完全依赖于伪随机数的强度♦移位寄存器是产生序列密码的有效方法♦RC4、SEAL（SoftwareOptimizedEncryption Algorithm，软件优化加密算法）59

流密码符号描述与示例

密钥流：k1,k2,k3,…

⊕⊕⊕

明文流：m1,m2,m3,…

↓↓↓

密文流：c1,c2,c3,…

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

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

明文流：D7,A8,C1,D0,CF,C2,CE,E7,32,B5,E3,B5,BD,B4,EF,A1,A3

↓↓↓↓↓密文流：AF,9D,C3,34,7D…60小结

&对称密码学分为分组密码和流密码

&数据加密标准（DES）的算法设计

&高级加密标准（AES）的评选61三、公钥密码学62主要内容&公钥密码学概述&公钥密码算法&公钥密码技术应用63对称密码学中的密钥管理

♦单钥密码技术要求通信双方事先交换密钥。 在实际应用中，一方需要与成千上万的通信 方进行交易，若采用单钥密码技术，每个用 户需要管理成千上万个不同对象通信的密钥。

♦例如：n个用户之间两两相互通信时，每个 需要保存n-1种密钥，共需保存n(n-1)/2种密 钥。

♦在现实环境中，密钥通常会经常更换，更为 极端的是，每次传送都使用不同的密钥，单 钥密码技术的密钥管理和发布都是远远无法 满足使用要求的。64

对称密码学中的密钥管理♦双方如何交换密钥。通过传统手段，还是通 过因特网，都会遇到密钥传送的安全性问题。

♦网络上原来不相识的用户之间需要通信时， 密钥分发无法解决。

♦无法解决签名及身份认证问题。65公钥密码学中的密钥管理

♦公钥密钥技术解决了密钥的发布和管理问题， 任何一方可以公开其公开密钥，而保留私有 密钥。

♦发送方可以用人人皆知的接收方公开密钥对 发送的信息进行加密，安全的传送给接收方， 然后由接收方用自己的私有密钥进行解密。66

公钥密码学概述♦1976年，美国学者WhitefieldDiffie，Martin Hellman发表了著名论文《密码学的新方向》 （《NewDirectionsinCryptography》），提 出了建立“公开密钥密码体制”：若用户A有加 密密钥ka（公开），不同于解秘密钥ka’（保 密），要求ka的公开不影响ka’的安全。若B要 向A保密送去明文m,可查A的公开密钥ka，若 用ka加密得密文c，A收到c后，用只有A自己 才掌握的解密密钥ka’对x进行解密得到m。67公钥密码学概述

♦WhitefieldDiffie，MartinHellman，《New DirectionsinCryptography》,1976

♦公钥密码学的出现使大规模的安全通信得以实现

–解决了密钥分发问题；

♦公钥密码学还可用于另外一些应用：数字签名、 防抵赖等；

♦公钥密码体制的基本原理–陷门单向函数

(trapdoorone-wayfunction)68

公钥密码学概述

加密：EK1（M）=C

解密：DK2（C）=M等效于DK2（EK1（M））=M数学变换 函数密钥K1

明文密文数学变换 函数明文密钥K2

密文69网络非对码密钥算法密文C

公钥密码学概述

B公钥用户A信息M

非对称密码算法密文C信息M用户B

B私钥70

公开密钥密码的重要特性加密与解密由不同的密钥完成加密:XY:Y=EKU(X)解密:YX:X=DKR(Y)=DKR(EKU(X))知道加密算法,从加密密钥得到解密密钥在计算上是不可行的两个密钥中任何一个都可以用作加密而另一个用作解密

X=DKR(EKU(X))=EKU(DKR(X))71基于公开密钥的加密过程72

用公钥密码实现保密•公钥加密，私钥解密

•用户拥有自己的密钥对(KU,KR)

•公钥KU公开,私钥KR保密•AB:Y=EKUb(X)•B:DKRb(Y)=DKRb(EKUb(X))=X73基于公开密钥的鉴别过程74

用公钥密码实现鉴别•私钥加密，公钥解密•条件:两个密钥中任何一个都可以用作加密而另一个用作解密•鉴别: AALL:Y=DKRa(X) ALL:EKUa(Y)=EKUa(DKRa(X))=X•鉴别+保密: AB:Z=EKUb(DKRa(X)) B:EKUa(DKRb(Z))=X算法加/解密数字签名密钥交换RSA是是是Dieffie-Hellman否否是DSS否是否75

公钥密钥的应用范围•加密/解密•数字签名(身份鉴别)•密钥交换76

公钥密码基于的数学难题•背包问题•大整数分解问题（TheIntegerFactorization Problem,RSA体制）•有限域的乘法群上的离散对数问题 (TheDiscreteLogarithmProblem, ElGamal体制）•椭圆曲线上的离散对数问题（TheElliptic CurveDiscreteLogarithmProblem, 类比的ElGamal体制）77

经典例子♦背包算法♦RSA算法♦EIGamal算法♦椭圆曲线密码算法ECC78背包算法

♦第一个公开钥密码算法

♦背包难题：NP完全问题

♦背包算法由RalphMerkle和

MartinHellman开发，只能 用于加解密，后来Shamir将之改进使之能够用于 数字签名79

背包问题♦背包问题描述：

已知一长度为b的背包及长度分别为a1,a2,…an的n

个物品，假定这些物品的直径与背包相同若从这些物 品中选出若干个正好装满这个背包那么究竟是那些 物品，即求解

n

Σaixi=b

i=1

其中ai和b都是正整数 这是一个NP完全问题，解决这个问题所需要的时 间与n呈指数增长80

背包公钥密码♦背包公钥密码

选取正整数a1,a2,…an作为公钥明文位串为

m=m1m2…mn利用公钥加密问题c=a1m1+ a2m2+…+anmn.

从明文c求明文m等价于背包问题81

背包密码系统的意义•是第一个公钥密码系统•有较好的理论价值•在实践过程中，大多数的背包方案都已被破解， 或者证明存在缺陷。目前，背包体制一般不再使 用了。82

RSA算法概述1978年，美国麻省理工学院(MIT)的研究小组成员：李维斯特(Rivest)、沙米尔(Shamir)、艾德曼(Adleman)提出了一种基于公钥密码体制的优秀加密算法——RSA算法。RSA算法是一种分组密码体制算法，它的保密强度是建立在具有大素数因子的合数，其因子分解是困难的。是否是NP问题尚未确定。RSA得到了世界上的最广泛的应用，ISO在1992年颁布的国际标准X.509中,将RSA算法正式纳入国际标准。1999年美国参议院已通过了立法，规定电子数字签名与手写签名的文件、邮件在美国具有同等的法律效力。83RSA算法概述

密码分析者尚不能证明其安全性，但也不能否 定其安全性。

RSA是一种分组密码，其理论基础是一种特殊 的可逆模指数运算，其安全性基于分解大整数 的困难性。 既可以用于加密，也可用于数字签名。 硬件实现时，比DES慢约1000倍。软件实现时 比DES慢约100倍。永远不会比对称钥算法快。 已被许多标准化组织(如ISO、ITU、IETF和

SWIFT等)接纳，目前多数公司使用的是RSA公 司的PKCS系列。 应用最广泛的公钥密码算法 只在美国申请专利，且已于2000年9月到期84

RSA算法数学基础素数：只能被1和它本身整除的自然数；否则为合数。每个合数都可以唯一地分解出素数因子

6=2·3 999999=3·3·3·7·11·13·37 27641=131·121

从2开始试验每一个小于等于√27641的素数。整数n的十进制位数因子分解的运算次数所需计算时间（每微秒一次）50751002003005001.4x10109.0x10122.3x10151.2x10231.5x10291.3x1039

3.9小时

104天

74年

3.8x109年

4.0x1015年

4.2x1025年

85

RSA算法描述1设n是两个不同的大素数之积，即n=pq，计算其欧拉函数值

z=(p-1)(q-1).

选择两个大素数：p=3,q=11,

则n=33,z=(3-1)*(11-1)=202345选择一个整数d，使得d与z互质.

这里选择d＝7随机选一整数e,使e×d=1(modz).

这里选择e＝3，3×7=21=1(mod20)由明文P计算密文C的加密算法：C=Pe(modn)，公钥为（e,n）

假定明文P为2，则密文C=23(mod33)＝8,公钥为（3，33）解密算法:P=Cd(modn),私钥为d

P=87(mod33)=2097152(mod33)=2，私钥为（7，33）

(p,q不再需要，应该被舍弃，但绝不可泄露)86

RSA算法安全性

RSA的安全性是基于加密函数C=Pe(modn)是一个单向函数，所以对人来说求逆计算不可行 密码分析者攻击RSA体制的关键点（陷门）在于如何分解n。若分解成功使n=pq，则可以算出z＝（p-1)(q-1)，然后由公开的e，解出秘密的d。

（猜想：攻破RSA与分解n是多项式等价的。然而，这个猜想至今没有给出可信的证明！！！）87

RSA算法关键技术♦密钥选择

p与q必为足够大的素数，使分析者没有办法在多项式时间内将n

分解出来。位数:1024以上,素性应该证明。

EDI攻击标准使用的RSA算法中规定n的长度为512至1024比特位 之间，但必须是128的倍数。国际数字签名标准ISO/IEC9796中规 定n的长度位512比特位. p-1,q-1有大的素因子

p+1,q+1也要有大的素因子

e的选取，最常用的e值为3，65537（2^16+1），为了提高加密速 度，通常取e为特定的小整数，如EDI国际标准中规定e＝

2^16+1，ISO/IEC9796中甚至允许取e＝3。这时加密速度一般比 解密速度快10倍以上。e＝2^16+1优于e＝3之处在于它能够抵抗 对RSA的小加密指数攻击♦算法实现

软件与硬件结合,并行算法等88

RSA算法练习[练习]设p=5，q=11，并取e=3，求n、z及d。解题步骤： ①n=5×11=55 ②z=(5-1)×(11-1)=40

③已知e=3，通过公式e×d=1mod(40)求出d的方法：

1×40+1=41是否能被3整除？不是，继续： 2×40+1=81是否能被3整除？是，因为3×27=81，并且e≠81，

所以私钥d=27。89

RSA算法练习[练习]设p=5，q=11，并取e=7，求n、z及d。90

RSA算法练习①n=5×11=55②z=(5-1)×(11-1)=40③已知e=7，通过公式e×d=1mod(40)求出d的方法： 1×40+1=41是否能被7整除？不是，继续：