现代密码学-第7章密码协议

1现代密码学21世纪高等学校计算机规划教材ModernCryptography彭代渊信息科学与技术学院[e-mail]2009.9-2010.1作者：何大可彭代渊唐小虎何明星梅其祥出版社：人民邮电出版社2现代密码学ModernCryptography彭代渊信息科学与技术学院[e-mail]2009年12月第7章密码协议3第7章密码协议7.1密码协议概述7.2实体认证协议7.3密钥认证协议7.4比特承诺协议7.5零知识证明与身份识别协议47.1密码协议概述协议(Protocol)基本概念两个或两个以上的参与者为完成某项特定任务而采取的一系列步骤。三层含义协议是有序的过程，每一步必须依次执行协议至少需要两个参与者通过执行协议必须能够完成某项任务57.1密码协议概述协议(Protocol)特点协议的参与方必须了解协议，明确协议执行的所有步骤协议的参与方都承诺按协议步骤执行协议协议必须清楚、完整，对每种可能的情况必须规定明确、具体的动作基本要求有效性公平性完整性67.1密码协议概述密码协议（安全协议）具有安全功能的协议——安全协议安全协议的设计必须采用密码技术——密码协议具体意义：密码协议是建立在密码体制基础上的一种交互通信的协议，它运行在计算机通信网或分布式系统中，借助于密码算法来达到安全功能密码技术：随机数生成、加密/解密算法、Hash运算、数字签名等安全功能：密钥建立、密钥分配、消息鉴别、身份认证应用系统：电子选举、电子拍卖、公平电子交易等。77.1密码协议概述密码协议分类—按协议执行的轮数分2轮协议3轮协议，……，n轮协议密码协议分类—按协议功能分身份认证协议密钥分配协议密钥协商协议秘密共享协议不经意传输协议，……87.1密码协议概述密码协议分类—按协议应用目标分选举协议拍卖协议支付协议，……密码协议分类—按协议的交互性分交互协议非交互协议密码协议分类—按协议第三方性质分仲裁协议裁决协议自动执行协议9第7章密码协议7.1密码协议概述7.2实体认证协议7.3密钥认证协议7.4比特承诺协议7.5零知识证明与身份识别协议107.2实体认证协议认证：一个实体向另一个实体证明某种声称的过程认证协议：主要目标是确认某个主体的真实性，确保信息的安全性认证协议分类消息认证协议：验证消息与其主体的一致性实体认证协议：验证消息发送者所声称的身份密钥认证协议（认证的密钥建立协议）：生成、获得加（解）密密钥117.2实体认证协议身份认证协议：验证用户知道什么（如口令等）、验证用户拥有什么（如IC卡等）或验证用户具有什么特征（如指纹、掌纹、虹膜、DNA等）身口令认证协议（PAP，PasswordAuthenticationProtocol）：通过验证用户口令来进行身份认证单向口令身份认证协议协议7.1简单口令身份认证协议协议7.2动态口令身份认证协议协议7.3基于口令的智能卡认证协议双向口令身份认证协议协议7.4基于Hash函数的双向口令身份认证协议协议7.5基于对称密码的双向认证协议协议7.6基于非对称密码的双向认证协议12第7章密码协议7.1密码协议概述7.2实体认证协议7.3密钥认证协议7.4比特承诺协议7.5零知识证明与身份识别协议137.3密钥认证协议密钥认证协议：对通信主体A和B及建立的密钥K进行认证只有A、B（或可信第三方TTP）能够知道KA和B确认对方知道KA和B确认K是最新建立的147.3密钥认证协议KK会话密钥K157.3密钥认证协议基于对称密码技术的密钥认证协议Needham-Schroeder协议密钥分配中心KDC(keydistributioncenter)安全地分发一个会话密钥Ks给用户A和B。协议步骤1122(1)AKDC:||||(2)KDCA:[||||||[||]](3)AB:[||](4)BA:[](5)AB:[()]ABBSSABKsBKSAKSAKKIDIDNEKIDNEKIDEKIDENEfN167.3密钥认证协议基于对称密码技术的密钥认证协议Needham-Schroeder协议重放攻击假定攻击方C已经掌握A和B之间一个旧的会话密钥，且可以中途阻止第(4)步的执行'11'22(1)AKDC:||||(2)KDCA:[||||||[||]](3)AB:[||](4)BA:[](5)AB:[()]ABBSSABKsBKSAKSAKKIDIDNEKIDNEKIDEKIDENEfN177.3密钥认证协议基于对称密码技术的密钥认证协议Denning改进协议：运用时间戳T协议步骤22(1)AKDC:||(2)KDCA:[||||||[||]](3)AB:[||||](4)BA:[](5)AB:[()]ABBSSABKsBKSKSAKKIDIDEKIDTEKTEKIDTENEfN187.3密钥认证协议基于对称密码技术的密钥认证协议Denning改进协议：运用时间戳T协议步骤抑制重放攻击如果发送者的时钟比接收者的时钟要快，攻击者就可以从发送者窃听消息，并在以后当时间戳对接收者来说成为当前时重放给接收者。克服抑制重放攻击的方法•强制各方定期检查自己的时钟是否与KDC的时钟同步。•采用临时随机数(nonce)技术197.3密钥认证协议基于对称密码技术的密钥认证协议KEHN改进协议协议步骤(1)AB:||(2)BKDC:||||[||||](3)KDCA:[||||||]||[||||]||(4)AB:[||||]||[]BABBSAABBKAABKBASBKASBBKASBKBIDNIDNEIDNTEIDNKTEIDKTNEIDKTEN该协议可抵抗前两个协议可能遭受的攻击207.3密钥认证协议基于非对称密码技术的密钥认证协议Diffie-Hellman密钥交换协议(DH-KEP)协议步骤•公开参数：大素数p,p的本原根a•共享密钥：KpYKpaYpXAAAXBXAAmodmod计算计算随机选择用户pYKpaYpXBBBXAXBBmodmod计算计算随机选择用户217.3密钥认证协议基于非对称密码技术的密钥认证协议Diffie-Hellman密钥交换协议(DH-KEP)协议步骤•公开参数：大素数p,p的本原根a•共享密钥：K合理性证明.modmod)mod(mod)(modmod)mod(modpYppapapappapYKBBABAABABAXAXXXXXXXXXB安全性基础攻击者只能得到a,p,YA,YB，要想求出K,必须先求出XA或XB，这是离散对数问题227.3密钥认证协议基于非对称密码技术的密钥认证协议Diffie-Hellman密钥交换协议(DH-KEP)例子：设p=97，a=5(1)A选择XA=36，计算YA=aXA=536=50mod97，将YA发送给B.(2)B选择XB=58，计算YB=aXB=558=44mod97，将YB发送给B.(3)A计算共享密钥K=(YB)XA=4436=75mod97.(4)B计算共享密钥K=(YA)XB=5058=75mod97.237.3密钥认证协议基于非对称密码技术的密钥认证协议Diffie-Hellman密钥交换协议(DH-KEP)中间人攻击ZzZZZXZXAZAXBZBXpY=amodpK=YmodpK=YmodpAAAXAXAZZAXpY=amodpK=YmodpBBBXBXZBZBXpY=amodpK=YmodpYAYZYZYB247.3密钥认证协议基于非对称密码技术的密钥认证协议加密的密钥交换协议(EKE)(协议7.11)Kerberos协议(协议7.12)主要目的是解决分布式网络环境下，客户访问网络资源的安全认证问题。实现用户与服务器之间的相互认证；向每个实体证实另一个实体的身份；产生会话密钥，供客户和服务器(或两个客户之间)使用。V5于1994年作为RFC1510公布257.3密钥认证协议基于非对称密码技术的密钥认证协议Kerberos协议(协议7.12)四个主体：客户C，应用服务器V，认证服务器AS，票证授予服务器TGS。认证服务器与票证授予服务器又统称为密钥分配中心（KDC）。详细步骤见教材267.3密钥认证协议对协议的攻击类型重放攻击(ReplayAttacks)重放攻击是指入侵者捕获以前协议运行或当前协议运行中的消息用于对当前协议运行的攻击已知密钥攻击（Known-keyattack)对手从用户以前用过的密钥确定新的密钥的攻击伪装攻击（Impersonationattack）对手扮演合法实体进行的攻击字典攻击(Dictionaryattack)主要针对口令的一种按某种顺序进行搜索的攻击277.3密钥认证协议对协议的攻击类型交错攻击(Interleavingattack)把前面一次或多次（或者并行）执行协议的信息有选择地组合在一起所实施的攻击。选择挑战攻击（Chosen-textattack）在挑战应答协议中对手巧妙地选择挑战消息，试图得到所需的信息。反射攻击（Reflectionattack）正在执行的协议中，一方把对方发送过来的消息再发回给对方28第7章密码协议7.1密码协议概述7.2实体认证协议7.3密钥认证协议7.4比特承诺协议7.5零知识证明与身份识别协议297.4比特承诺协议股票预测大师问题股票预测大师经常在讲座中给股民推荐股票，可股民按照大师推荐买股票却常常赚不了钱，然而预测大师却生意红火。为什么？因为预测大师没有对股民给出一个明确的承诺，尤其在股民选择股票买进时间和卖出时间上。往往在股民亏本后与预测大师论理时，预测大师总可以用偷换预测的前提和条件（时间）来“说服”股民相信大师预测的正确性307.4比特承诺协议安全比特承诺协议的直观描述A把比特b放入一个箱子，用一把只有用A自己的钥匙才能开启的锁锁上这个箱子，然后把这个箱子交给B；当时机成熟时，A把比特b和打开箱子的钥匙交给B，B通过打开箱子可以验证比特b的内容没有改动，因为箱子在B的控制之下。317.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)。327.4比特承诺协议比特承诺的两个安全性要求：屏蔽性（Concealing）：A可用一个概率多项式时间算法F(r,b)将二进位b屏蔽起来，只有A本人才能打开。即二进位b一旦被屏蔽起来便不能被对方B预测。约束性(Binding)：A根据二进位b及其屏蔽算法，可从屏蔽体中用概率多项式时间算法打开屏蔽，显露出惟一的二进位b,并让B进行验证。即二进位b一旦被屏蔽起来便不能再被屏蔽者修改。337.4比特承诺协议例：由Goldwasser-Micali公钥概率加密系统构造一种比特承诺协议令n=pq,p，q是长度相同的大素数，选择模n非二次剩余m。（1）A随机选择rZn*,b{0,1},计算y=F(r,b)=mbr2modn.并发送给B。（2）其后A通过揭示b,r来打开y。B只需验证y=mbr2modn.只要求解模n二次剩余问题是困难的，则从y=F(r,b)计算出b也是困难的。即由y不能泄露b的任何信息，所以该方案具有屏蔽性。该方案具有约束性。347.4比特承诺协议抛币落井协议（Flippingcoinsintowell）设想有一口清澈见底的深水井，A站在水井的旁边，而B远离这口