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