第七章 密码协议.ppt

1、第七章 密码协议,认证协议,Authentication Protocols,相互认证,A，B双方在建立共享密钥时需要考虑保密性和实时性。 保密性：会话密钥应以密文传送，因此双方应事先共享密钥或者使用公钥 实时性:防止重放 序列号方法 时戳 询问应答,序列号方法,对交换的每一条消息加上序列号，序列号正确才被接收 要求每个用户分别记录与其他每一用户交互的序列号，增加用户负担，因而很少使用,时戳法,A收到消息中包含时戳，且A看来这一时戳充分接近自己的当前时刻，A才认为收到的消息是新的并接收 要求各方时间同步,询问应答,用户A向B发出一个一次性随机数作为询问，如果收到B发来的应答消息也包含一正确的一

2、次性随机数，A就认为消息是新的并接受之。,各种方法的比较,时戳法不适用于面向连接的应用过程 要求不同的处理器之间时间同步，所用的协议必须是容错的以处理网络错误 协议中任何一方时钟出现错误失去同步，则敌手攻击的可能性增加 网络中存在延迟，不能期待保持精确同步，必须允许误差范围,各种方法的比较,询问应答不适合于无连接的应用过程 在传输前需要经过询问应答这一额外的握手过程，与无连接应用过程的本质特性不符。 无连接应用最好使用安全时间服务器提供同步,NeedhamSchroeder协议,2.,4.,KDC,A,B,1. IDA| IDB |N1,3.,5.,如果敌手获得了旧会话密钥，则可以冒充A重放3

3、，并且可回答5，成功的欺骗B,NeedhamSchroeder改进协议（1）,2.,4.,KDC,A,B,1. IDA| IDB,3.,5.,以时戳替代随机数，用以向A，B保证Ks的新鲜性,|ClockT|t1+t2 Clock:本地时钟 t1：本地时钟与KDC时钟误差估计值 t2 ：网络延迟时间,要求各方时钟同步 如果发方时钟超前B方时钟，可能导致等待重放攻击,NeedhamSchroeder改进协议（2）,KDC,A,B,3.,1.,4.,2.,会话密钥的截止时间,NeedhamSchroeder改进协议（2）,A,B,1.,2.,3.,有效期内可不通过KDC直接认证,公钥加密体制,AS,

4、A,B,1. IDA| IDB,2.,3.,时戳防止重放，要求时钟同步,公钥加密体制,AS,A,B,2.,1. IDA| IDB,3.,4.,6,7,单向认证,不需要双方同时在线（电子邮件） 邮件接收者希望认证邮件的来源以防假冒 分为单钥加密方法和公钥加密方法,单钥加密,2.,KDC,A,B,1. IDA| IDB |N1,3.,不要求B同时在线，保证只有B能解读消息，提供对A的认证。不能防止重放攻击。,公钥加密,对发送消息提供保密性,对发送消息提供认证性,对发送消息提供保密和认证性,A的证书,身份证明技术,身份证明技术,传统的身份证明：一般是通过检验“物”的有效性来确认持该物的的身份。徽章、

5、工作证、信用卡、驾驶执照、身份证、护照等，卡上含有个人照片(易于换成指纹、视网膜图样、牙齿的X适用的射像等)。信息系统常用方式：用户名和口令,交互式证明,两方参与示证者P(Prover)，知道某一秘密，使V相信自己掌握这一秘密；验证者V(Verifier)，验证P掌握秘密；每轮V向P发出一询问，P向V做应答。V检查P是否每一轮都能正确应答。,交互证明与数学证明的区别,数学证明的证明者可自己独立的完成证明 交互证明由P产生证明，V验证证明的有效性来实现，双方之间要有通信 交互系统应满足 完备性：如果P知道某一秘密，V将接收P的证明 正确性：如果P能以一定的概率使V相信P的证明，则P知道相应的秘密

6、,Fiat-Shamir身份识别方案,参数： 选定一个随机模m=pq。产生随机数v，且使s2=v，即v为模m的平方剩余。 m和v是公开的，s作为P的秘密,Fiat-Shamir身份识别方案,(1) P取随机数r(m)，计算x= r 2 mod m，送给V； (2) V将一随机bit b送给P； (3) 若b=0，则P将r送给V；若b=1，则P将y=rs送给V； (4) 若b=0，则V证实x=r 2 mod m，从而证明P知道，若b=1，则B证实 xv=y2 mod m，从而证明A知道。这是一次证明，A和B可将此协议重复t次，直到B相信A知道s为止。,Fiat-Shamir身份识别方案,完备性

7、如果P和V遵守协议，且P知道s，则应答rs是应是模m下xv的平方根，V接收P的证明，所以协议是完备的。 正确性 P不知道s，他也可取r，送x=r2 mod m给V，V送b给P。P可将r送出，当b=0时则V可通过检验而受骗，当b=1时，则V可发现P不知s，B受骗概率为1/2，但连续t次受骗的概率将仅为2-t V无法知道P的秘密，因为V没有机会产生(0,1）以外的信息，P送给V的消息中仅为P知道v的平方根这一事实。,零知识证明,最小泄露证明和零知识证明：以一种有效的数学方法，使V可以检验每一步成立，最终确信P知道其秘密，而又能保证不泄露P所知道的信息。,零知识证明的基本协议,例Quisquater

8、等1989 。,设P知道咒语， 可打开C和D之间的秘密门，不知道者 都将走向死胡同中。,A,B,C,D,零知识证明的基本协议,(1) V站在A点；(2) P进入洞中任一点C或D；(3) 当P进洞之后，V走到B点；(4) V叫P：(a)从左边出来，或(b)从右边出来；(5) P按要求实现(以咒语，即解数学难题帮助)；(6) P和V重复执行 (1)(5)共n次。若A不知咒语，则在B点，只有50 %的机会猜中B的要求，协议执行n次，则只有2-n的机会完全猜中，若n=16，则若每次均通过B的检验，B受骗机会仅为1/65 536,零知识证明的基本协议,哈米尔顿回路图论中有一个著名问题，对有n个顶点的全连

9、通图G，若有一条通路可通过且仅通过各顶点一次，则称其为哈米尔顿回路。Blum1986 最早将其用于零知识证明。当n大时，要想找到一条Hamilton回路，用计算机做也要好多年，它是一种单向函数问题。若A知道一条回路，如何使B相信他知道，且不告诉他具体回路？,(1) A将G进行随机置换，对其顶点进行移动，并改变其标号得到一个新的有限图H。因 ，故G上的Hamilton回路与H上的Hamilton回路一一对应。已知G上的Hamilton回路易于找出H上的相应回路；(2)A将H的复本给B；(3) B向A提出下述问题之一：(a) 出示证明G和H同构，(b) 出示H上的Hamilton回路；(4) A执

10、行下述任务之一：(a) 证明G和H同构，但不出示H上的Hamilton回路，(b) 出示H上的Hamilton回路但不证明G和H同构；(5) A和B重复执行 (1)(4)共n次。,其他密码协议,智力扑克,A和B通过网络进行智力扑克比赛，不用第三方做裁判，发牌者由任一方担任，要求发牌过程满足 任一副牌是等可能的 发给A，B的牌没有重复 每人知道自己手中的牌，不知道别人的牌 比赛结束后，每一方都能发现对方的欺骗行为 为满足要求，A,B方需要加密一些信息，比赛结束前，这些机密算法都是保密的。,智力扑克,A和B的加密解密算法记为EA，EB，DA，DB，满足EA( EB(m)= EB( EA(m) A,

11、B协商好用以表示52张牌的w1,w52,2.随机选5个 EB(wi)3.另选5个 EB(wi)，以EA加 密 以DA解密,1.洗牌，用EB对 52个wi加密解密，作为发给 自己的牌以DB解密,52个EB（wi）,5个随机的EB（wi）,5个的EA(EB(wi),5个的EA(wi),完后公开所有加密变换,A,B,掷硬币协议,某些密码协议中要求通信双方在无第三方协助情况下，产生一个随机序列，因为A，B之间不存在信任关系，因此不能由一方产生在通过网络或电话告诉另一方,掷硬币协议,利用单向函数掷硬币 A，B都知道某一单向函数f(x)，但都不知道逆函数 B选择一个随机数x，求yf(x)并发给A A猜测x

12、的奇偶性，并将结果告诉B B告诉A猜测正确不正确，并将x发给A 安全性 A不知道f(x)的逆函数，无法由y求x，只能猜 B若在A猜测后改变x，A可以通过y=f(x)?检查出来,不经意传输,设A有一个秘密，想以1/2的概率传递给B，即B有50概率收到该秘密 协议执行完后，A不知道B是否收到这个秘密,基于大数分解的不经意传输协议,A想通过不经意传输协议传给B大数n的因子分子 如果已知某数在模n下的两个不同的平方根，就可以分解n B随机选一数x，将发给A A（掌握n的分解）计算x2mod n 的四个平方根x ,y,将其中之一发给B B检查收到的数是否与x 在模n下同余，如果是，B没有得到任何新的信息，否则B掌握了x2mod n 的两个不同的平方根，从而可以分解n，而A确不知道究竟是哪种情况,