密码协议详解课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式日rff,第二级e,第三级f,第四级d,第五级f,*,现代密码学,21世纪高等学校计算机规划教材,Modern,Cryptography,彭代渊,信息科学与技术学院,dypeng,2009.9-2010.1,作 者：何大可 彭代渊 唐小虎 何明星 梅其祥,出版社：人民邮电出版社,1,现代密码学21世纪高等学校计算机规划教材 Modern Cr,现代密码学,Modern,Cryptography,彭代渊,信息科学与技术学院,dypeng,2009年12月,第7章 密码协议,2,现代密码学 Modern Cryptography彭代渊,第7章 密码协议,7.1 密码协议概述,7.2 实体认证协议,7.3 密钥认证协议,7.4 比特承诺协议,7.5 零知识证明与身份识别协议,3,第7章 密码协议7.1 密码协议概述3,7.1 密码协议概述,协议(Protocol),基本概念,两个或两个以上的参与者为完成某项特定任务而采取的一系列步骤。,三层含义,协议是有序的过程，每一步必须依次执行,协议至少需要两个参与者,通过执行协议必须能够完成某项任务,4,7.1 密码协议概述协议(Protocol)4,7.1 密码协议概述,协议(Protocol),特点,协议的参与方必须了解协议，明确协议执行的所有步骤,协议的参与方都承诺按协议步骤执行协议,协议必须清楚、完整，对每种可能的情况必须规定明确、具体的动作,基本要求,有效性,公平性,完整性,5,7.1 密码协议概述协议(Protocol)5,7.1 密码协议概述,密码协议（安全协议）,具有安全功能的协议安全协议,安全协议的设计必须采用密码技术密码协议,具体意义：密码协议是建立在密码体制基础上的一种交互通信的协议，它运行在计算机通信网或分布式系统中，借助于密码算法来达到安全功能,密码技术,：随机数生成、加密/解密算法、Hash运算、数字签名等,安全功能,：密钥建立、密钥分配、消息鉴别、身份认证,应用系统,：电子选举、电子拍卖、公平电子交易等。,6,7.1 密码协议概述密码协议（安全协议）密码技术：随机数生,7.1 密码协议概述,密码协议分类按协议执行的轮数分,2轮协议,3轮协议，,n,轮协议,密码协议分类按协议功能分,身份认证协议,密钥分配协议,密钥协商协议,秘密共享协议,不经意传输协议，,7,7.1 密码协议概述密码协议分类按协议执行的轮数分7,7.1 密码协议概述,密码协议分类按协议应用目标分,选举协议,拍卖协议,支付协议，,密码协议分类按协议的交互性分,交互协议,非交互协议,密码协议分类按协议第三方性质分,仲裁协议,裁决协议,自动执行协议,8,7.1 密码协议概述密码协议分类按协议应用目标分8,第7章 密码协议,7.1 密码协议概述,7.2 实体认证协议,7.3 密钥认证协议,7.4 比特承诺协议,7.5 零知识证明与身份识别协议,9,第7章 密码协议7.1 密码协议概述9,7.2 实体认证协议,认证：一个实体向另一个实体证明某种声称的过程,认证协议：主要目标是确认某个主体的真实性，确保信息的安全性,认证协议分类,消息认证协议：验证消息与其主体的一致性,实体认证协议：验证消息发送者所声称的身份,密钥认证协议（认证的密钥建立协议）：生成、获得加（解）密密钥,10,7.2 实体认证协议认证：一个实体向另一个实体证明某种声称,7.2 实体认证协议,身份认证协议：,验证用户知道什么（如口令等）、验证用户拥有什么（如IC卡等）或验证用户具有什么特征（如指纹、掌纹、虹膜、DNA等）,身口令认证协议,（PAP，Password Authentication Protocol）：通过验证用户口令来进行身份认证,单向口令身份认证协议,协议7.1 简单口令身份认证协议,协议7.2 动态口令身份认证协议,协议7.3 基于口令的智能卡认证协议,双向口令身份认证协议,协议7.4 基于Hash函数的双向口令身份认证协议,协议7.5 基于对称密码的双向认证协议,协议7.6 基于非对称密码的双向认证协议,11,7.2 实体认证协议身份认证协议：验证用户知道什么（如口令,第7章 密码协议,7.1 密码协议概述,7.2 实体认证协议,7.3 密钥认证协议,7.4 比特承诺协议,7.5 零知识证明与身份识别协议,12,第7章 密码协议7.1 密码协议概述12,7.3 密钥认证协议,密钥认证协议：,对通信主体A和B及建立的密钥,K,进行认证,只有A、B（或可信第三方TTP）能够知道,K,A和B确认对方知道,K,A和B确认,K,是最新建立的,13,7.3 密钥认证协议密钥认证协议：对通信主体A和B及建立的,7.3 密钥认证协议,K,K,主密钥,K,A,主密钥,K,B,会话密钥,K,14,7.3 密钥认证协议KK主密钥KA主密钥KB会话密钥K14,7.3 密钥认证协议,基于对称密码技术的密钥认证协议,Needham-Schroeder 协议,密钥分配中心KDC(key distribution center)安全地分发一个会话密钥,K,s,给用户A和B。,协议步骤,15,7.3 密钥认证协议基于对称密码技术的密钥认证协议 15,7.3 密钥认证协议,基于对称密码技术的密钥认证协议,Needham-Schroeder 协议,重放攻击,假定攻击方C已经掌握A和B之间一个旧的会话密钥，且可以中途阻止第(4)步的执行,16,7.3 密钥认证协议基于对称密码技术的密钥认证协议 16,7.3 密钥认证协议,基于对称密码技术的密钥认证协议,Denning改进协议：运用时间戳T,协议步骤,17,7.3 密钥认证协议基于对称密码技术的密钥认证协议 17,7.3 密钥认证协议,基于对称密码技术的密钥认证协议,Denning改进协议：运用时间戳T,协议步骤,抑制重放攻击,如果发送者的时钟比接收者的时钟要快，攻击者就可以从发送者窃听消息，并在以后当时间戳对接收者来说成为当前时重放给接收者。,克服抑制重放攻击的方法,强制各方定期检查自己的时钟是否与KDC的时钟同步。,采用临时随机数(nonce)技术,18,7.3 密钥认证协议基于对称密码技术的密钥认证协议 抑制重,7.3 密钥认证协议,基于对称密码技术的密钥认证协议,KEHN改进协议,协议步骤,该协议可抵抗前两个协议可能遭受的攻击,19,7.3 密钥认证协议基于对称密码技术的密钥认证协议 该协议,7.3 密钥认证协议,基于非对称密码技术的密钥认证协议,Diffie-Hellman密钥交换协议(DH-KEP),协议步骤,公开参数：大素数,p,p,的本原根,a,共享密钥：,K,20,7.3 密钥认证协议基于非对称密码技术的密钥认证协议 20,7.3 密钥认证协议,基于非对称密码技术的密钥认证协议,Diffie-Hellman密钥交换协议(DH-KEP),协议步骤,公开参数：大素数,p,p,的本原根,a,共享密钥：,K,合理性证明,安全性基础,攻击者只能得到,a,p,Y,A,Y,B,，要想求出,K,必须先求出,X,A,或,X,B,，这是离散对数问题,21,7.3 密钥认证协议基于非对称密码技术的密钥认证协议 安全,7.3 密钥认证协议,基于非对称密码技术的密钥认证协议,Diffie-Hellman密钥交换协议(DH-KEP),例子：设,p,=97，,a,=5,(1)A选择,X,A,=36，计算,Y,A,=,a,XA,=5,36,=50 mod 97，将,Y,A,发送给,B,.,(2)B选择,X,B,=58，计算,Y,B,=,a,XB,=5,58,=44 mod 97，将,Y,B,发送给,B,.,(3)A计算共享密钥,K,=(,Y,B,),XA,=44,36,=75 mod 97.,(4)B计算共享密钥,K,=(,Y,A,),XB,=50,58,=75 mod 97.,22,7.3 密钥认证协议基于非对称密码技术的密钥认证协议 22,7.3 密钥认证协议,基于非对称密码技术的密钥认证协议,Diffie-Hellman密钥交换协议(DH-KEP),中间人攻击,Y,A,Y,Z,Y,Z,Y,B,23,7.3 密钥认证协议基于非对称密码技术的密钥认证协议 YA,7.3 密钥认证协议,基于非对称密码技术的密钥认证协议,加密的密钥交换协议(EKE)(协议7.11),Kerberos 协议(协议7.12),主要目的是解决分布式网络环境下，客户访问网络资源的安全认证问题。,实现用户与服务器之间的相互认证；向每个实体证实另一个实体的身份；产生会话密钥，供客户和服务器(或两个客户之间)使用。,V5于1994年作为RFC1510公布,24,7.3 密钥认证协议基于非对称密码技术的密钥认证协议 24,7.3 密钥认证协议,基于非对称密码技术的密钥认证协议,Kerberos 协议(协议7.12),四个主体：客户C，应用服务器V，认证服务器AS，票证授予服务器TGS。认证服务器与票证授予服务器又统称为密钥分配中心（KDC）。,详细步骤见教材,25,7.3 密钥认证协议基于非对称密码技术的密钥认证协议 25,7.3 密钥认证协议,对协议的攻击类型,重放攻击(Replay Attacks),重放攻击是指入侵者捕获以前协议运行或当前协议运行中的消息用于对当前协议运行的攻击,已知密钥攻击（Known-key attack),对手从用户以前用过的密钥确定新的密钥的攻击,伪装攻击（Impersonation attack）,对手扮演合法实体进行的攻击,字典攻击(Dictionary attack),主要针对口令的一种按某种顺序进行搜索的攻击,26,7.3 密钥认证协议对协议的攻击类型26,7.3 密钥认证协议,对协议的攻击类型,交错攻击(Interleaving attack),把前面一次或多次（或者并行）执行协议的信息有选择地组合在一起所实施的攻击。,选择挑战攻击（Chosen-text attack）,在挑战应答协议中对手巧妙地选择挑战消息，试图得到所需的信息。,反射攻击（Reflection attack）,正在执行的协议中，一方把对方发送过来的消息再发回给对方,27,7.3 密钥认证协议对协议的攻击类型27,第7章 密码协议,7.1 密码协议概述,7.2 实体认证协议,7.3 密钥认证协议,7.4 比特承诺协议,7.5 零知识证明与身份识别协议,28,第7章 密码协议7.1 密码协议概述28,7.4,比特承诺,协议,股票预测大师问题,股票预测大师经常在讲座中给股民推荐股票，可股民按照大师推荐买股票却常常赚不了钱，然而预测大师却生意红火。为什么？因为预测大师没有对股民给出一个,明确的承诺,，尤其在股民选择股票买进时间和卖出时间上。往往在股民亏本后与预测大师论理时，预测大师总可以用偷换预测的前提和条件（时间）来“说服”股民相信大师预测的正确性,29,7.4 比特承诺协议股票预测大师问题29,7.4,比特承诺,协议,安全比特承诺协议的直观描述,A 把比特,b,放入一个箱子，用一把只有用A自己的钥匙才能开启的锁锁上这个箱子，然后把这个箱子交给B；当时机成熟时，A把比特,b,和打开箱子的钥匙交给B，B通过打开箱子可以验证比特,b,的内容没有改动，因为箱子在B的控制之下。,30,7.4 比特承诺协议安全比特承诺协议的直观描述30,7.4,比特承诺,协议,7.1(比特承诺)给定随机数,r,和待提交的整数,b,，关于整数,b,的比特承诺就是一个有效算法,F,使得满足如下条件：,从,F,(,r,b,)计算出,b,的难度相当于攻破某计算困难性问题的难度；,比特承诺,F,(,r,b,)的提交者A在以后把比特承诺,F,(,r,b,)以不同的方式打开成为,F,(,r,b,)的概率是可以忽略的，即提交者不能把比特承诺打开成为不同的方式；,在多项式时间内，无法区分对于两个不同数,b,和,b,的,F,(,r,b,)和,F,(,r,b,)。,31,7.4 比特承诺协议7.1(比特承诺)给定随机数r和,7.4,比特承诺,协议,比特承诺的两个安全性要求：,屏蔽性（Concealing）：,A可用一个概率多项式时间算法,F,(,r,b,)将二进位,b,屏蔽起来，只有A本人才能打开。即二进位,b,一旦被屏蔽起来便不能被对方B预测。,约束性(Binding)：,A根据二进位,b,及其屏蔽算法，可从屏蔽体中用概率多项式时间算法打开屏蔽，显露出惟一的二进位,b,并让B进行验证。即二进位,b,一旦被屏蔽起来便不能再被屏蔽者修改。,32,7.4 比特承诺协议比特承诺的两个安全性要求：32,7.4,比特承诺,协议,例：由Goldwasser-Micali公钥概率加密系统构造一种比特承诺协议,令,n,=,pq,p,，,q,是长度相同的大素数，选择模,n,非二次剩余,m,。,（1）A随机选择,r,Z,n,*,b,0,1,计算,y,=,F,(,r,b,)=,m,b,r,2,mod,n.,并发送给B。,（2）其后A通过揭示,b,r,来打开,y,。B只需验证,y,=,m,b,r,2,mod,n.,只要求解模,n,二次剩余问题是困难的，则从,y,=,F,(,r,b,),计算出,b,也是困难的。即由,y,不能泄露,b,的任何信息，所以该方案具有屏蔽性。,该方案具有约束性。,33,7.4 比特承诺协议例：由Goldwasser-Mical,7.4,比特承诺,协议,抛币落井协议（Flipping coins into well）,设想有一口清澈见底的深水井，A站在水井的旁边，而B远离这口水井，A将硬币抛进水井里去，硬币停留在水井中，现在A能够看到水井里的结果，但A不能到水井里去改变硬币的状态（如正反面情况）。当A将硬币抛进水井时，B不能看见水井里的硬币，只有当B猜完硬币的状态后，A才让B走近井边，看到井底的硬币。这个协议满足上面的两条性质。因此称这样的比特承诺协议为抛币落井协议（Flipping coins into well）。,34,7.4 比特承诺协议抛币落井协议（Flipping coi,7.4,比特承诺,协议,采用单向函数的抛币协议,设A和B使用一个安全Hash函数,F,。,(1)A选择一个随机数,r,，并计算,y,=,F,(,r,)；,(2)A将,y,发送给B；,(3)B猜测,r,是偶数（,b,=0）或奇数(,b,=1)，并将猜测结果发送给A；,(4)如果B的猜测正确，抛币结果为正面；如果B的猜测错误，则抛币的结果为反面。A公布此次抛币的结果，并将,r,发送给B；,(5)B确信。,35,7.4 比特承诺协议采用单向函数的抛币协议 35,7.4,比特承诺,协议,采用单向函数的抛币协议,抛币协议的安全性取决于,F,的安全性,抛币协议，具有如下的性质：,A必须在B猜测之前抛币；,在听到B猜测之后A不能再抛币；,B猜测之前不能知道硬币是怎么落地的。,36,7.4 比特承诺协议采用单向函数的抛币协议 36,第7章 密码协议,7.1 密码协议概述,7.2 实体认证协议,7.3 密钥认证协议,7.4 比特承诺协议,7.5 零知识证明与身份识别协议,37,第7章 密码协议7.1 密码协议概述37,7.5 零知识证明与身份识别协议,7.5.1 零知识证明,例子,P要向V证明“P拥有某个房间的钥匙”，有两个方法：,(1)P把钥匙出示给V，V用这把钥匙打开该房间的锁,(2)V确定该房间内有某一物体，P用自己拥有的钥匙打开该房间的门，然后把物体拿出来出示给V,方法(2)属于零知识证明,零知识证明的基本思想,设P是示证者，V是验证者。P需要向V证明他知道某个秘密信息，但示证者P在向验证者V证明他知道某个秘密信息时,不泄露秘密的任何信息,。,38,7.5 零知识证明与身份识别协议7.5.1 零知识证明38,7.5 零知识证明与身份识别协议,Jean-Jacques等打开洞穴之门的故事,C、D之间有一道秘密之门，要打开这道门，需要知道开门的咒语。对任何不知道咒语的人，两边的通道都是死胡同。,今有一示证者P，知道开门的咒语，他不想让其他任何人知道这个咒语，但是又想让V相信他确实能通过这道门这个事实。,即：示证者P向验证者V证明他知道开门的咒语，而在这个过程中P不向验证者V泄漏咒语的任何信息。,39,7.5 零知识证明与身份识别协议Jean-Jacques等,7.5 零知识证明与身份识别协议,零知识证明概念,假设P，V是两个概率图灵机，P有无限的计算能力，V的计算能力是多项式的，若一个交互式证明满足以下三点，就称此证明为,一个零知识交互式证明,。,(1)完备性,(Completeness),：如果P的声明是真的，则V以绝对优势的概率接受P的结论；,(2)有效性,(Soundness),：如果P的声明是假的，则V以绝对优势的概率拒绝P的结论；,(3)零知识性,(Zero-knowledge),：无论V采取任何手段，当P的声明是真的，P不违背协议时，V除了接受P的结论以外，得不到其他额外的信息。,40,7.5 零知识证明与身份识别协议零知识证明概念40,7.5 零知识证明与身份识别协议,基于离散对数的零知识证明协议,P欲向V证明他知道满足,x,=,mod,p,的,x,，即知道离散对数,x,=log,，其中,p,是一个大素数，,x,是与,p,互素的随机数。,和,p,是公开的，,x,是保密的。P在不泄露,x,的信息的情况下向V证明他知道,x,的过程如下：,(1)P选择随机数,r,(0,r,p,1)，计算,h,=,r,mod,p,，将,h,发送给V；,(2)V随机选择一整数或,b,=0或,b,=1，发送给P。,(3)P计算,s,=(,r,+,bx,)mod(,p,1)，并发送给V；,(4)V验证,s,=,h,b,mod,p,；,(5)重复步骤(1)(4),t,次。,P欺骗成功的概率为2,t,。,41,7.5 零知识证明与身份识别协议基于离散对数的零知识证明协,7.5 零知识证明与身份识别协议,7.5.2 身份识别协议,用零知识证明设计身份识别协议,示证者P在证明自己身份时不泄露任何信息，验证者V得不到示证者的任何私有信息，但又能有效证明对方身份的协议。,一个好的身份识别协议应具有以下性质。,(1)完备性（,Completeness,）：在P与V都诚实的情况下，P一定可以让V识别自己，接受P的身份；,(2)有效性（,Soundness,）：如果P的身份是假的，则V以绝对优势的概率拒绝接受P的身份；,(3)不可传递性（Non-transferability）：验证者V不能重新使用识别过程中使用过的消息，向第三者证明自己是P，即证据不可传递。,42,7.5 零知识证明与身份识别协议7.5.2 身份识别协议4,7.5 零知识证明与身份识别协议,Fiat-Shamir识别方案(,Fiat,Shamir,1986),1.参数选取,选定一个随机模,n,=,pq,p,q,是不同的大素数.产生随机数,s,，且使,s,2,=,v,mod,n,.,n,和,v,是公开的，,p,q,s,作为示证者P的秘密。,2.一次证明过程,(1)P取随机数,r,(,n,)，计算,x,=,r,2,mod,n,将,x,发送给验证者V;,(2)V将一随机比特,b,发送给P；,(3)若,b,=0,则P将,r,发送给V；若,b,=1，则P将,y,=,rs,发送给V；,(4)若,b,=0,则V证实,x,=,r,2,mod,n,从而证明P知道,s,;若,b,=1，则V证实,xv,=,y,2,mod,n,从而证明P知道,s,。,3P和V重复执行,t,次过程2，直到V相信P知道,s,为止。,43,7.5 零知识证明与身份识别协议Fiat-Shamir识别,7.5 零知识证明与身份识别协议,Fiat-Shamir识别方案(,Fiat,Shamir,1986),Fiat-Shamir协议性质,完备性：,如果P和V遵守协议，且P知道,s,，则应答,rs,应是模,m,下,xv,的平方根，V接收P的证明，所以协议是完备的,。,有效性：,P不知道s，他也可取,r,，发送给V，V发送,b,给P。P可将,r,送出，当,b,=0时则V可通过检验而受骗，当,b,=1时，则V可发现P不知,s,，B受骗概率为1/2，但连续,t,次受骗的概率将仅为2,t,。,V无法知道P的秘密,44,7.5 零知识证明与身份识别协议Fiat-Shamir识别,7.5 零知识证明与身份识别协议,Feige-Fiat-Shamir身份识别协议(自学）,Schnorr身份识别协议(自学）,45,7.5 零知识证明与身份识别协议Feige-Fiat-Sh,第6章 习 题,PP.176-177,1-11,46,第6章 习 题 PP.176-177,1-1146,