信息的加密课件

《信息的加密课件》由会员分享，可在线阅读，更多相关《信息的加密课件（62页珍藏版）》请在金锄头文库上搜索。

1、管理信息学 杨善林 刘业政编著第6章 信息的加密1信 息 加 密 计算机和通信网络的广泛应用，一方面为人们的生活和工作带来了极大的方便，但另一方面也带来了许多亟待解决的问题，信息安全就是一个突出问题。密码技术是保证信息安全的关键技术。信息安全性主要有两个方面：信息的保密性和认证性。保密的目的是防止对手破译系统中的机密信息。认证的目的有两个，一个是验证信息发送者是真的而不是冒充的；另一个是验证信息的完整性，在处理过程中没有被窜改等。管理信息学 杨善林 刘业政编著第6章 信息的加密26.1 密码学的基本概念 密码学由密码编码学与密码分析学两个分支组成。密码编码学是研究如何保证信息保密性与认证性的方

2、法，密码分析学是研究如何破译密码或制造伪信息。 信息加密的目的：未授权者不能得到信息。称待加密的信息为明文，加密后的信息为密文或密码；称将明文变换成密文的过程为加密，将密文译成明文的过程为解密；称将明文变换成密文的运算方法为加密算法，将密文译成明文的运算方法为解密算法。管理信息学 杨善林 刘业政编著第6章 信息的加密36.1 密码学的基本概念 称用来控制加密算法和解密算法的密钥为加密密钥与解密密钥。根据密钥的特点，密码体制分为私钥密码体制与公钥密码体制。在私钥密码体制中，加密密钥与解密密钥是相同的或从一个容易推出另一个；在公钥密码体制中，加密密钥与解密密钥不同或从一个很难推出另一个。根据加密的

3、方式不同，又可将密码分为流密码和分组密码。在流密码中，将明文按字符一个一个地加密；在分组密码中，将明文分成若干个组，每组含多个字符，一组一组地加密。管理信息学 杨善林 刘业政编著第6章 信息的加密46.1 密码学的基本概念 非法攻击密码被动攻击：未授权者通过各种可能的手段获取密文，并通过各种分析手段推断出明文的过程(破译)。主动攻击：非法入侵者通过各种手段进入密码通信系统，并通过可能的方法删改、伪造信息以达到破坏密码的通信系统。 破译或攻击密码的方法：穷举法是指用各种可能的密钥去试译密文，直到得到有意义的明文的方法。分析方法是指通过数学关系式或统计规律找出明文或与明文相关的有用信息的破译方法。

4、管理信息学 杨善林 刘业政编著第6章 信息的加密56.1 密码学的基本概念 可破密码：如果一个密码在规定的时间内，通过密文能确定明文或密钥，或通过一定量的明文与密文的对应关系能确定密钥，则称这个密码是可破的；否则，称密码是不可破的。 破译或攻击类型 惟密文攻击(Cipher-Text-Only Attack)：密码分析者有一个或更多的用同一个密钥加密的密文，通过对这些截获的密文进行分析得出明文或密钥。 管理信息学 杨善林 刘业政编著第6章 信息的加密66.1 密码学的基本概念 已知明文攻击(Know Plaintext Attack)：除要破译的密文外，密码分析者有一些明文和用同一密钥加密这些

5、明文所对应的密文。 选择明文攻击(Chosen Plaintext Attack)：密码分析者可得到所需要的任何明文所对应的密文，这些密文与要破译的密文是用同一个密钥加密得来的。 选择密文攻击(Chosen Cipher-Text Attack)：密码分析者可得到所需要的任何密文所对应的明文，解密这些密文所使用的密钥与要破译的密文的密钥是相同的。 管理信息学 杨善林 刘业政编著第6章 信息的加密76.1 密码学的基本概念四种攻击类型的强度按序递增，惟密文攻击最弱，选择密文攻击最强。选择密文攻击主要用于公钥密码体制。 密码通信系统明文m加密器：密文c=Ek1(m)非法入侵者密码破译者加密密钥源解

6、密密钥源解密器：m=Dk2(c) 明文mmmk1k2ccc1管理信息学 杨善林 刘业政编著第6章 信息的加密86.1 密码学的基本概念 认证系统：防止消息被攻击者删改或伪造。使发送的信息具有被验证的能力，使接受者或第三者能够识别和确认信息的真伪。 管理信息学 杨善林 刘业政编著第6章 信息的加密96.2 密码学的复杂性理论 密码学的复杂性理论由算法复杂性与问题复杂性两方面组成，它是比较不同的密码技术与算法的复杂性与安全性的理论依据。1. 算法复杂性 时间复杂性和空间复杂性。由算法所需要的最大时间T和最大存储空间V度量，它们依赖于解决实例时所需要输入数据的长度n，一般表示为T(n)与V(n)。在

7、实际应用中常用平均时间复杂函数与平均空间复杂函数表示算法的复杂性。 管理信息学 杨善林 刘业政编著第6章 信息的加密106.2 密码学的复杂性理论 算法的复杂性通常用n的数量级表示。如果存在正常数k1, k2及N使得对一切nN有：则称f (n)与h (n)为同数量级的，记为f(n)=O(h(n)。容易证明，当f(n)是n的k次多项式时，则f(n)=O(nk)，即所有低阶项与常数项可忽略不计。 多项式时间算法：f(n)=O(nk) 指数时间算法：f(n)=O(h(n)(1)管理信息学 杨善林 刘业政编著第6章 信息的加密116.2 密码学的复杂性理论例 若一台计算机每秒能执行106条指令，当n=

8、106时，若T(n)=n，则所需计算时间为1秒；若T(n)=n2，则所需计算时间为(106)2/106秒，相当于11.6天；若T (n)= 2n，则所需时间大约为310301016年。由此可见，当n很大时，不同类型的算法的复杂性可能差别很大。2. 问题复杂性 图灵机（Turing Machine）：一种具有无限读写能力并可做无限个并行操作的理想计算机。管理信息学 杨善林 刘业政编著第6章 信息的加密126.2 密码学的复杂性理论 P问题与NP问题：如果图灵机每一步操作结果是惟一确定的，则称它为确定型图灵机；如果每一步操作结果或下一步操作都可能有多种选择，则称该机为不确定型图灵机。在确定型图灵机

9、上可用多项式时间解决的问题，被认为是易解问题，易解问题的全体称为确定型多项式时间可解类，记为P。不确定型图灵机工作分猜测与验证2个阶段，所谓一个问题在不确定型图灵机上可用多项式时间解决，是指若图灵机猜测一个解，则它可以在多项式时间内验证(不是求出)此解正确与否。管理信息学 杨善林 刘业政编著第6章 信息的加密136.2 密码学的复杂性理论 在不确定型图灵机上可以用多项式时间解决的问题，称为非确定性多项式时间可解问题，简称NP问题，NP问题全体称为非确定性多项式时间可解类，仍记为NP。显然，PNP，因为在确定型图灵机上多项式时间可解的任何问题在不确定型图灵机上也是多项式时间可解的，此时无需猜测阶

10、段。管理信息学 杨善林 刘业政编著第6章 信息的加密14例1 背包问题：给定n个整数的集合和一个整数N，决定是否存在一个子集S，使得S中的所有数之和为N。解 因为对于一个给定的子集S，可在多项式时间内验证其和是否为N。然而要找A的一个子集S使其和等于N，其时间复杂性T=O(2n) ，这是因为A共有2n个不同的子集。6.2 密码学的复杂性理论管理信息学 杨善林 刘业政编著第6章 信息的加密151. 流密码 在流密码中，将明文m写成连续的符号m=m1m2，利用密钥流k=k1k2中的第i个元素ki对明文中的第i个元素mi进行加密，若加密变换为E，则加密后的密文c=Ek(m)= Ek1(m1) Ek2

11、(m2)Eki(mi)。设与加密变换E对应的解密变换为D，其中D满足Dki(Eki(mi)=mi, i=1,2,，则通过解密运算可译得明文为m=Dk(c)=Dk1(Ek1(m1)Dk2(Ek2(m2)=m1m2，从而完成一次密码通信。6.3 私钥密码算法管理信息学 杨善林 刘业政编著第6章 信息的加密16例2 设明文、密钥、密文都是F2上的二元数字序列，明文m=m1m2，密钥为k=k1k2，若加密变换与解密变换都是F2中的模2加法，试写出加密过程与解密过程。 6.3 私钥密码算法加密算法E解密算法D明文mi密文ci=Eki(mi)明文mi=Dki(ci )密钥ki密钥ki流密码通信模式框图管理

12、信息学 杨善林 刘业政编著第6章 信息的加密17解 经加密变换得密文C=Ek(m)=Ek1(m1)Ek2(m2)=(k1+m1) (k2+m2)经解密变换得：Dk(c)=Dk (k1+m1)(k2+m2)=(k1+k1+m1)(k2+k2+m2)由于kiF2，则ki+ki=0，i=1，2，故Dk (c)=m1m2=m。 由于密钥k可由明文m与密文C进行模2加获得，易受到已知明文的攻击。用该密码系统通信就要求每发送一条消息都要产生一个新的密钥即“一次一密”。 6.3 私钥密码算法管理信息学 杨善林 刘业政编著第6章 信息的加密18 一次一密系统是无条件安全保密系统，但很不实用。在实际中，人们设计

13、一个密码系统的目标是一个密钥能用来加密很多消息，或一个密钥能用来加密一条更长的明文，只要求计算上是安全的。所谓计算上是安全的,是指利用已有的最好的方法破译该系统所需的努力超过了密码分析者的破译能力(诸如时间、空间和资金等资源)或破译该系统的难度等价于解数学上的某个已知难题。6.3 私钥密码算法管理信息学 杨善林 刘业政编著第6章 信息的加密191. 密钥流生成器如果密钥流经过d个符号之后重复，则称该流密码是周期的。密钥流元素kj的产生由第j时刻流密码的内部状态sj和实际密钥k决定，记为kj=f(k，sj)。加密变换Ekj与解密变换Dkj都是时变的。加密器中存储器的状态s随时间变化而变化，用状态

14、转移函数fs表示。如果fs与输入的明文无关，则密钥流kj与明文无关，j时刻输出的密文cj=Ekj(mj)与j时刻之前的明文也无关，称此种流密码为同步流密码。6.3 私钥密码算法管理信息学 杨善林 刘业政编著第6章 信息的加密20 在同步流密码中，只要发送端和接收端有相同的实际密钥和内部状态，就能产生相同的密钥流，此时发送端和接收端的密钥生成器是同步的。一旦不同步，解密工作立即失败。如果状态转移函数fs与输入的明文符号有关，则称该流密码为自同步流密码。目前应用最广泛的流密码是同步流密码。 密钥流生成器：使用线性变换。密钥流生成器的目的是由一个短的随机密钥k生成一个长的密钥流，再对明文加密或对密文

15、解密。 6.3 私钥密码算法管理信息学 杨善林 刘业政编著第6章 信息的加密21 密钥流不可测性：即要求生成的密钥流具有随机性，从而使密码分析者不可能从截获的i比特子段生成大于i 比特的密码。 构造方法可分为四类：信息论方法、系统论方法、复杂度理论方法和随机化方法。 用已知方法构造出的大多数密钥流生成器已被证明是不安全的，仅有少数还没有被证明是不安全的。但现在被认为是安全的密码，都是基于世界上某个数学难题没有解决，一旦这个数学问题被解决，与之同难度的密码系统就不安全了。 6.3 私钥密码算法管理信息学 杨善林 刘业政编著第6章 信息的加密222. 收缩密钥流生成器移位寄存器n个小方框是n个寄存

16、器，从左到右依序为第1、2、n级寄存器。开始时，若第i级内容是an-i，则此寄存器的初始状态是(a0，a1，an-1)。当加上一个脉冲时同时完成三项工作：（1）各级内容送给运算器f(x0，x1，x n-1) ；（2）每个寄存器的内容移给下一级，第n级内容输出；（3）运算器结果an=f(a0，a1，an-1)反馈到第一级。6.3 私钥密码算法f (x0，x1， ，xn-1)管理信息学 杨善林 刘业政编著第6章 信息的加密23 此时移位寄存器的状态就是(a1，a2， an)，而输出是a0。不断地加脉冲，上述n级移位寄存器的输出就是一个2元(或q元)序列：a0，a1，a2， 在运算器中若f(x0，x

17、1，x n-1)给定，则输出序列完全由初始状态(a0，a1，an-1)确定。当f(x0，x1，x n-1)为线性函数时，称该移位寄存器为n级线性移位寄存器；否则为n级非线性移位寄存器。代数编码中已证明移位寄存器产生的序列都是周期序列，周期都2n。6.3 私钥密码算法管理信息学 杨善林 刘业政编著第6章 信息的加密24例3 给定一个4级线性移位寄存器如图。给定初状态(0001)，求该移位寄存器产生的周期序列。解 易见 f(x0，x1，x2，x3) = x0+x1，因此对k4有 ak=ak-3+a k-4从而该4级移位寄存器产生的序列是周期15的序列：1111 移位寄存器(SR)可由短的序列生成具

18、有一定规律的长序列。这种序列便可以作为密钥流序列，但抗攻击能力较差。6.3 私钥密码算法管理信息学 杨善林 刘业政编著第6章 信息的加密25 通常的密钥流生成器都是由若干个移位寄存器并联，并且与特殊的电子电路组合而成(如图)。可通过SR1的输出选择SR2的输出来生成密钥流。6.3 私钥密码算法收缩密钥流生成器SR1yi(1)yi(2)输出kiSR2管理信息学 杨善林 刘业政编著第6章 信息的加密26 收缩密钥流生成器的工作模式输入：参数：两个移位寄存器的级数及反馈函数 密钥：两个移位寄存器的初始状态 (1) 移位SR1并产生yi(1)；同时移位SR2并产生yi(2)； (2) 如果yi(1)=

19、1，则输出密钥元素ki= yi(2)； 如果yi(1)=0，则删去yi(2)，i=1，2， 。由此收缩生成器产生的密钥流为ki| i1。6.3 私钥密码算法管理信息学 杨善林 刘业政编著第6章 信息的加密273. 分组密码 分组密码是将明文消息编码表示后的数字序列划分成长为m的组x=(x1，x2， xm)，各组分别在密钥k=( k1，k2， kt)的控制下变换成长为n的密文y=( y1，y2， yn)。6.3 私钥密码算法分组密码通信模式框图加密算法解密算法明文x=(x1，x2，xn)密文y=( y1，y2，yn)密钥k=(k1，k2，kt)明文x=(x1，x2，xn)密钥k=(k1，k2，k

20、t)管理信息学 杨善林 刘业政编著第6章 信息的加密28 分组密码与流密码的区别在于输出的每一位数字不是与相应时刻输入的明文数字有关，而是与一组长为m的明文数字有关。分组密码的优点是容易标准化且容易实现同步，缺点是相同的密文组蕴含相同的明文组。在分组密码通信中，通常明文与密文长度相等(=分组长度)。设明文与密文空间均为F2n，密钥空间为Sk，则加密函数y=E(x,k)和解密函数x=D(y,k)都是F2n到F2n的一个置换。好的分组密码应该难破译、易实现，即E(x,k)和D(y,k)都必须很容易计算，但要从方程y=E(x,k)和x=D(y,k)中求出k应该是一个很困难的问题。6.3 私钥密码算法

21、管理信息学 杨善林 刘业政编著第6章 信息的加密29 DES（美国商业部的数据加密标准）算法 DES算法使用长度为56比特的密钥加密长度为64比特的明文，获得长度为64比特的密文，工作程序： 给定一个明文x，通过一个固定的初始变换IP将x变换为x0，记x0=IP(x)=L0R0，这里L0是x0的前32比特，R0是x0的后32比特。 接着进行16轮完全相同的运算，在这里数据与密钥相结合。根据下列规则计算LiRi，i=1，2，16：Li=Ri-1Ri=Li-1f (R i-1，k i) 6.3 私钥密码算法管理信息学 杨善林 刘业政编著第6章 信息的加密30函数f(R i-1,k i)中R i-1

22、是一个长度为32的比特串，k i(i=1,16)是一个长度为48的比特串，是密钥k的函数； f函数值是一个长度为32的比特串；表示两个比特串的异或。 对比特串R16L16应用初始变换IP的逆变换IP-1，即得密文y=IP-1(R16L16)。 DES的解密采用同一算法实现，把密文y作为输入，倒过来使用密钥方案，即以逆顺序k16,k 1使用密钥方案，输出的将是明文x。 6.3 私钥密码算法一轮DES加密过程Li-1Ri-1Li-Rikif+管理信息学 杨善林 刘业政编著第6章 信息的加密31 在私钥密码体制中，解密密钥与加密密钥相同或容易从加密密钥导出。存在的问题： 加密密钥的暴露会使系统变得不

23、安全； 在传送密文前，发送者和接收者必须使用一个安全信道预先通信密钥k，在实际通信中是很困难的。1. 公钥密码体制及其设计的基本原理 在公钥密码中，解密密钥和加密密钥不同，从一个难于推出另一个，解密和加密是可分离的，加密密钥是可以公开的。信息可通过编码被加密在一个NP-完全问题之中，以普通方法破译该密码等价于解一个NP-安全问题。6.4 公钥密码算法管理信息学 杨善林 刘业政编著第6章 信息的加密32 公钥密码体制的基本原理-陷门单向函数(troop-door one-way function) 如果函数f(x)满足：对f(x)的定义域中的任意x，都容易计算函数值f(x)，而对于f(x)的值域

24、中的几乎所有的y，即使已知f要计算f-1(y)也是不可行的，则称f(x)是单向函数。若给定某些辅助信息时又容易计算单向函数f的逆f-1，则称f(x)是一个陷门单向函数。这一辅助信息就是秘密的解密密钥。 公钥密码体制的安全性是指计算安全性，不是无条件的，这是由求f-1的复杂性决定的。6.4 公钥密码算法管理信息学 杨善林 刘业政编著第6章 信息的加密33例 设n是两个大素数p和q的乘积，b是一个正整数，对xZn ，令f(x)xb(mod n)，即f(x)等于被n除所得的余数，人们认为f(x)是一个从Zn到Zn的单向函数2RSA密码体制定义6.1 设m，n是两个整数，如果正整数d满足：(1) d整

25、除m和n，即d|m，d|n;(2) 若d|m且d|n，则d|d。则称d是m与n的最大公因数，记为d=(m，n)。若(m，n)=1，则称m与n互素。6.4 公钥密码算法管理信息学 杨善林 刘业政编著第6章 信息的加密34设n是任一自然数，记1，2，n-1中与n互素的数的个数为(n)，并称(n)为欧拉(Euler)函数。定理6.1 设Z*n=m|(m，n)=1，1mn-1，则对aZ*n，有a(n)1 (modn)设n=pq，其中p与q是不同的素数，则(n)=(p-1)(q-1)定理6.2 设p与q是两个不同的素数，n=pq，则对任意的xZn=0，1，2，n-1及任意的非负整数k，有xk(n)+1x

26、 (mod n)6.4 公钥密码算法管理信息学 杨善林 刘业政编著第6章 信息的加密35 RSA算法 设p，q是两个不同的奇素数，n=pq，则(n)=(p-1)(q-1)，密钥k=(n，p，q，a，b)|ab1(mod (n)，a，bZ*n)对每一个k=(n，p，q，a，b)，定义加密变换为Ek(x)xb(modn)，xZn定义解密变换为Dk(y)ya(modn)，yZn RSA密码体制是公开加密密钥n与b，保密解密密钥a以及辅助信息p与q6.4 公钥密码算法管理信息学 杨善林 刘业政编著第6章 信息的加密36定理6.3 设Ek与Dk分别是RSA体制中的加密变换和解密变换，则对一切xZn有Dk

27、(Ek(x)=x例 设 用 户 A选 择 两 个 素 数 p=5， q=7， 则 n=pq=35， (n)=(5-1)(7-1)=24。A取a=11Z*35，再由Euclidean算法求出b=a-1(mod(n)。A公开n=35和b=11，保密p=5，q=7和a=11。现在用户B想把明文x=2Z35发送给A。B加密明文x=2得密文：y=Ek(x)xb(mod35)211(mod35)=18；B在公开信道上将加密后的密文y=18发送给A，当A收到密文y=18时，A解密可得：ya=18112 (mod35)，从而A得到B发送的明文x=2。 6.4 公钥密码算法管理信息学 杨善林 刘业政编著第6章

28、信息的加密37 RSA算法的安全性是基于分解大整数n的困难性。目前大整数分解算法能力：分解130位的十进制数! 基于安全性考虑，用户选择的素数p和q大约都为100位的十进制数，那么h=pq将是200位的十进制数。 建立过程：(1)找到两个大素数p与q(p与q相差也很大);(2)计算n和(n);(3)随机选择一个数b使得(b,(n)=1,0b (n); (4)利用Euclidean算法计算a=b-1(mod(n);(5)将n与b作为他的公钥直接公开，以便让所有想给他发送想保密的信息加密。 6.4 公钥密码算法管理信息学 杨善林 刘业政编著第6章 信息的加密381. 数字签名方案概述 数字签名：

29、适应信息化需要； 异地签名。 数字签名过程：设厂长使用RSA密码体制，厂长的加密密钥为Ek，是公开的，解密密钥为Dk，只有厂长本人知道，则(1)将附上数据x的合同发给厂长；(2) 厂长用解密密钥Dk对数据x作运算y=Dk(x)，结果为厂长的数字签名；(3)用厂长的公开加密密钥作运算x=Ek(y)，如果x=x，则可证实厂长的签名为真；否则为假。因为Ek(Dk(x)Dk(Ek(x)x(modn)，而Dk是惟一的且只有厂长本人知道。6.5 数字签名方案管理信息学 杨善林 刘业政编著第6章 信息的加密39 一般地，一个数字签名方案主要由签名算法S()和验证算法V()组成。签名者使用一个只有本人知道的S

30、()签一个消息x得S(x)，接受者使用签名者公开的V()验证其签名的真伪。2. RSA签名方案 设p与q是两个不同的素数，n=pq， (n)=(p-1)(q-1)。任取一个与n互素且小于n的数a，由ab1(mod (n)求得唯一的解b，1bn。公开n与a，保密值p，q和b。对xZn，定义签名算法S()为S(x)xb(modn)；对yZn，定义验证算法V()为V(y)ya(modn)，则签名为真的充要条件是V(S(x)x(modn)。由于S()只有签名者一人知道，因此只有他能给出真的签名。 6.5 数字签名方案管理信息学 杨善林 刘业政编著第6章 信息的加密403. OSS签名方案 选择一个大的

31、自然数n，并随机地选择一个自然数k使(k,n)=1，即k与n互素。由h-k-2(modn)计算h。公开n和h，保密k，即n与h是验证密钥，k是签字密钥。签名者对信息x签名时，再随机选择一个与n互素的自然数m，签字算法为：将S1(x)与S2(x)一起作为签名发送给接受方。验证算法为：如果V(S1(x)，S2(x)x(modn)，则签名为真；否则为假。6.5 数字签名方案管理信息学 杨善林 刘业政编著第6章 信息的加密414. 数字签名的发展与挑战 数字签名既可使用私钥密码体制又可使用公钥密码体制，目前研究和使用的都是公钥密码体制。要构造无条件安全的公钥密码体制几乎是不可能的。目前所用的公钥密码体

32、制都是基于以下三种数学疑难问题之一：（1）由Diffie提出的背包问题：给定一个互不相同的数组成的集合，如何找出一个子集，使其元素之和为N。（2）由Gill提出的离散对数问题：设p是素数，k与m是整数，如何找x使下式成立：kxm(modp)6.5 数字签名方案管理信息学 杨善林 刘业政编著第6章 信息的加密426.5 数字签名方案据介绍，具有5000个量子位的量子计算机，可以在30秒内解决传统超级计算机要100亿年才能解决的大数因子分解问题。由于具有强大的并行处理能力，量子计算机将对现有的保密体系产生根本性的冲击 （3）由Knuth提出的因子分解问题：设n是两个不同的大素数乘积，如何分解n?

33、一旦这些数学难题取得突破性进展，将使所有公开密钥体制以及以公开密钥体制为基础的数字签名方案不安全。管理信息学 杨善林 刘业政编著第6章 信息的加密436.6 识 别 协 议1. 识别协议概述 当一个用户A需要在某个信息系统中确认自己身份时，一般的做法是输入自己和计算机都知道的一个密码。由于A每次进入计算机时都要键入这个密码，而能够访问用户A的数据通道的任何人或能访问计算系统的存储器的任何人都可以看到用户A的密码，因此系统存在严重的安全问题。需设计一种方案或协议使用户A既能进入计算机又不泄露用户A的任何识别信息(即身份零知识证明)。管理信息学 杨善林 刘业政编著第6章 信息的加密446.6 识

34、别 协 议一个安全的识别协议至少应满足以下两个条件(智能卡)：(1)用户A能向验证者B证明他的确是A；(2)用户A向验证者B证明自己的身份时，没有让验证者B获得任何有用的信息，B不可能模仿A向其他人证明他是用户A。2. Feige-Fiat-Shamir(FFS)识别协议 FFS识别协议是由一个属于仲裁数字签名方案改进而成的管理信息学 杨善林 刘业政编著第6章 信息的加密456.6 识 别 协 议 FFS识别协议内容 可信仲裁方随机选取一个自然数n，n必须是两个不同的大素数的乘积，为了确保安全，n至少为512位长，最好接近1024位长。这个作为模数的n可以在一组证明者之间共享。可信仲裁方再选取

35、一个自然数v，v必须是模n的平方剩余，即x2v(modn)有小于n的整数解x。而且v-1(modn)存在。v作为用户A(证明者)的公开密钥。再计算：则S作为用户A的秘密密钥。管理信息学 杨善林 刘业政编著第6章 信息的加密466.6 识 别 协 议 FFS识别协议设计及通信过程 用户A随机选一个数r，rn，计算xr2(modn)，并将x发送给验证者； 验证者在0与1两个数中任选一个数a发送给用户A，若a=0，则用户A将r发送给验证者；若a=1，则用户A计算y=rs(modn)并将y发送给验证者； 如果a=0，则验证者验证同余式xr2(modn)是否成立，若成立，则证实用户A知道 ；如果a=1，

36、则验证者验证同余式xvy2(modn)是否成立，如果成立，则证实用户A知道 管理信息学 杨善林 刘业政编著第6章 信息的加密476.6 识 别 协 议如果用户A知道 或 ，则验证者认为用户A为真；否则为假。这个协议是一次签定合格协议。用户A与验证者可以重复这个协议t次，直到验证者确信用户A知道S。(次数太多)3. 改进的FFS识别协议设n是两个不同的大素数的乘积，先选取k个不同的数v1，v2，vk，vi是模n的平方剩余，且vi-1(modn)存在，i=1，k。v1，v2，vk作为用户A的公开密钥。再计算：Si ，i=1，k 则S1，S2，Sk为用户A的秘密密钥。管理信息学 杨善林 刘业政编著第

37、6章 信息的加密486.6 识 别 协 议 设计与通信过程 用户A选择一个随机数r，rn，并计算xr2(modn)，用户A将运算结果x发送给验证者； 验证者随机选取k个数a1,a2,ak ，每个ai可取0或1，并将(a1,a2,ak)发送给用户A，用户A收到(a1,a2,ak)后计算：并将计算结果y发送给验证者； 验证者验证同余式 是否成立，若成立，则证明用户A知道密钥S1,S2,Sk。否则否定用户A。管理信息学 杨善林 刘业政编著第6章 信息的加密496.6 识 别 协 议 改进后的FFS识别协议也可重复多次，直到验证者满意为止。若重复这种识别协议t次，验证者被欺骗的概率为(2-kt),协议

38、设计者建议使用k=9，t=8，此时验证者被欺骗的概率几乎为0。 例 设计一个FFS协议。解 取n=57=35，选择v1=4，v2=11，v3=16，v4=29。注意4，11，16，29满足识别协议的要求，如同余式x24(mod35)有解x=2，x=12，x=23或x=33，且49=1(mod35)，即4-1(mod35)=9存在。11，16，29可类似的验证。管理信息学 杨善林 刘业政编著第6章 信息的加密506.6 识 别 协 议由同余式可计算得S1=3，S2=4，S3=9，S4=8。 执行该协议一轮运算如下： 用户A选择一个随机数r=16，由于162(mod35)=11，从而用户A将11发

39、给验证者； 验证者随机选择一个二元串(a1,a2,a3,a4)=(1100)发送给用户A；用户A收到(1100)后可计算如下：16S11S21S30S40= 1631 419080=1634=19217(mod35)；用户A将17发送给验证者；管理信息学 杨善林 刘业政编著第6章 信息的加密516.6 识 别 协 议 验证者收到17后，计算如下：172V11V21V31V41= 28941111160290=1271611(mod35) 由于此结果与用户A第一次发送的x=11安全一样，因此可确认用户A知道S1，S2，S3，S4.如果有必要，可要求用户A再随机选r为其它数，重复上述步骤若干次，直

40、到确信为止。 值得说明的是，如果用户A将S1，Sk作为数字签名密钥，而将v1，vk作为公开验证密钥便得到的数字签名方案。而该数字签名方案与RSA签名方案相比，运算速度比RSA要快得多。管理信息学 杨善林 刘业政编著第6章 信息的加密526.7 密 钥 管 理1. 密钥管理的意义2. 密钥的分类与产生 密钥的种类主要有用户密钥、会话密钥、密钥加密密钥和主机主密钥。用户密钥(ku)是一对用户在较长时间段内所专用的秘密密钥；会话密钥(ks)是两个通信终端用户在一次通话或交换数据时所用的密钥；密钥加密密钥(ke)是对传送的会话密钥进行加密的密钥；主机主密钥(km)是对密钥加密密钥进行加密的密钥，存储在

41、主机处理器中。管理信息学 杨善林 刘业政编著第6章 信息的加密536.7 密 钥 管 理 密钥生成：关键是安全性，完全取决于产生密钥的算法，因此这种算法应满足如下要求： 生成密钥的算法应当能保证主机主密钥的产生具有随机性，避免可预测性； 在有N个终端的通信网中，即使有一个或数个密钥加密密钥被盗或泄露，生成密钥的算法应当能保证其它用户的密钥加密密钥仍有足够的安全性； 在密钥加密密钥控制下，生成密钥算法可以动态地生成会话密钥。管理信息学 杨善林 刘业政编著第6章 信息的加密546.7 密 钥 管 理3. 密钥的分配 在有N个终端的保密通信网络中，由于任意两个用户必须交换密钥，因此要有 个传送密钥的

42、安全信道，即使借助一个可信中心可将安全信道从 降低到N个，但每个用户必须存储N-1个密钥，但交换密钥的次数仍为 次。当N稍大时传输量与存储量都很大。因此，密钥分配方案应当确保网络的密钥传送次数和每个用户的存储量都尽可能的小，且每一对用户A与B都能独立地计算一个秘密密钥KAB。 管理信息学 杨善林 刘业政编著第6章 信息的加密556.7 密 钥 管 理 Blom密钥分配方案 在有N个用户的保密通信网络中，为了方便起见，假定密钥从集合S中选出，S含有p个元素，p为素数，pN。可信中心给每个用户在一个安全的信道上发送S中两个元素，每两个用户A与B都能计算一个密钥KAB=KBA。安全条件为：任何单个用

43、户x(A，B)不能确定KAB的任何信息。分配方案： 公开一个素数p，每个用户A公开一个元素rAS，这些元素rA互不相同；管理信息学 杨善林 刘业政编著第6章 信息的加密566.7 密 钥 管 理 可信中心随机从S中选择三个元素a，b，c(可以相同)，并构造函数f(x，y)=(a+b(x+y)+cxy)(mod p) 对每个用户A，可信中心计算函数值gA(x)f(x,rA)(mod p)，并将gA(x)在一个安全信道上传送给A； 如果用户A与B想通信，那么A与B分别计算密钥如下：KA，B=f(rA，rB)=gA(rB)(mod p)KB，A=f(rB，rA)=gB(rA)(mod p)由于f(r

44、A，rB)=f(rB，rA)，故他们可使用共同的密钥KAB=KBA通信。 管理信息学 杨善林 刘业政编著第6章 信息的加密576.7 密 钥 管 理 可以证明，没有一个用户能确定另外两个用户的密钥的任何信息，即Blom方案对任何单个用户而言是安全的，但任何两个用户X，YA，B都可以确定KAB，即Blom方案对两个用户而言是不安全的。如果要求Blom方案对k个不同用户都不能确定KAB，1kn-2，Blom方案如下： 可信中心公开一个素数p，并给每个用户在一个安全的信道上发送S中k+1个元素r; 每个用户A公开一个元素rAS，这些元素rA互不相同；管理信息学 杨善林 刘业政编著第6章 信息的加密5

45、86.7 密 钥 管 理 可信中心选择元素aij=ajiS,0ik,0jk,并构造函数并对每个用户A，可信中心计算函数值gA(x)=f(x,rA)(mod p),并将结果gA(x)在一个安全信道上传送给A； 如果A与B想通信，A，B分别计算：KAB=f(rA，rB)=gA(rB)(mod p)KBA=f(rB，rA)=gB(rA)(mod p)由于f(rA,rB)=f(rB,rA),故KAB=KBA,故A与B可用共同的密钥通信管理信息学 杨善林 刘业政编著第6章 信息的加密596.7 密 钥 管 理4. 密钥保护和秘密共享 密钥保护：常采用分级保护管理法，即大量的数据用少量动态产生的数据加密密

46、钥进行保护，而数据加密密钥又用更少量的、相对不变的主机主密钥来保护。只有极少数密钥以明文形式存储在有严密的物理保护的主机密码器件中，其他密钥都以加密后的密码形式存于密码器之外的存储器中，简化了密钥管理，改善了密钥的安全性。为了确保密钥安全，在密码设备中都有防窜扰装置，当密封的关键密码器被撬开时，其主密钥和用户密钥都会自动被清除或启动装置自动引爆。 管理信息学 杨善林 刘业政编著第6章 信息的加密606.7 密 钥 管 理 秘密共享方案：基本要求将密钥k按下述要求分成n个共享k1，k2，kn：(1) 已知任意t个ki值都容易计算出密钥k；(2) 已知任意r (t-1)个ki的值，都无法计算出密钥

47、k。 在秘密共享方案中，将n个共享k1，k2，kn分给n个不同用户，由于要计算出密钥k至少要有t个共享，故即使有r个共享丢失或r个人背叛，都不会危及密钥k的安全；且若有s个共享被丢失或毁坏，只要有t个共享有效，则仍可计算出密钥k，从而恢复密钥。管理信息学 杨善林 刘业政编著第6章 信息的加密616.7 密 钥 管 理 Shamir秘密共享方案(Shamir门限方案)设p是一个素数，共享密钥kK=Zp。可信中心给n(p)个共享者pi(1in)分配共享的过程如下：(1) 可信中心在Zp中选择n个非零的互不相同的元素x1，x2，xn，并公开它们；(2) 可信中心随机选择一个t-1次多项式：f(x)=at-1xt-1+a2x2+a1x+kZpx并计算yi=f(xi)，i=1，2，n管理信息学 杨善林 刘业政编著第6章 信息的加密626.7 密 钥 管 理(3) 可信中心将(x1，y1)，(x2，y2)，(xn，yn)分配给共享者L1，L2，Ln，其中yi是Li的秘密共享，i=1，2，n。 在Shamir秘密共享方案中，如果知道t个共享，不妨设为y1，y2，yt，则利用计算数学中的拉格朗日插值公式可计算出多项式f(x)为：一旦求出f(x)，则k=f(0)，从而计算出密钥k。而已知任何r个共享，rt-1，都无法计算出f(x)，从而无法计算出k。