现代密码学09---安全协议.ppt

《现代密码学09---安全协议.ppt》由会员分享，可在线阅读，更多相关《现代密码学09---安全协议.ppt（76页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,现代密码学,安全协议,第,9,章,2,本章内容,3,9.1,安全协议概述,9.2,认证协议,9.3,秘密共享,9.4,零知识证明,9.1,安全协议概述,4,5,两个或两个以上的参与者为完成某项特定任务而采取的一系列步骤,什么是协议,在日常生活中，几乎所有的事情都有非正式的协议,电话订货,下棋、玩扑克,选举投票,没有人认真考虑过

2、这些协议，它们随时间的推移而发展，人们都知道怎样使用它们，而且它们也很有效,6,协议自始至终是个有序的过程，每个步骤必须执行，在前一步没,有执行完之前，后面的步骤不可能执行,协议至少需要两个参与者,通过协议必须能够完成某项任务,协议的主要特点,参与者必须了解协议，并且预先知道所要完成的所有步骤,参与者必须同意遵循协议,每一步必须明确定义，并且不会引起误解,必须是完整的，对每种可能的情况必须规定具体的动作,协议的其他特点,7,协议必须把所有,不利条件,事先都估计到，而,不能假定,一切都是正常的和非常理想的。,看一个协议是否正确，不能光看在正常情况下是否正确，而且还必须非常仔细地检查这个协议,能否

3、应付各种异常情况,。,协议很复杂,考虑不利条件,不能假定,一切正常,能否应付,异常情况,8,明日正午进攻，如何？,同意,收到,“,同意,”,收到,：,收到,“,同意,”,这样的协议无法实现！,两军问题（拜占庭将军问题）,9,结论,这样无限循环下去，两边的蓝军都始终无法确定自己最后发出的电文对方是否已经收到。,没有一种协议能使蓝军,100%,获胜。,有些问题考虑太全面,则无法解决,10,庄子,盗跖,：尾生与女子期于梁下，女子不来，水至不去，抱梁柱而死。,有些问题考虑不全面,会导致严重后果,11,又称密码协议，使用密码技术完成某项特定任务，并满足安全需求的协议。,什么是安全协议,在安全协议中，经常

4、使用对称密码、公钥密码、,Hash,函数、伪随机序列发生器等密码工具。,12,机密性,完整性,认证性,非否认性,公平性,匿名性,安全协议的安全性要求,这些要求根据应用,场合不同进行组合,13,安全协议的应用,电子商务,信用卡交易,电子支票,电子货币,电子拍卖,网上银行,电子政务,电子选举,14,安全协议中的角色,协议参与者,攻击者,内部,/,外部攻击者,被动,/,主动攻击者,可信第三方,(TTP,Trusted Third Party),用户都信任的实体，通常与每个用户共享密钥,功能：使用户之间确认彼此身份 或 共享会话密钥,15,Dolev-Yao,攻击者模型,攻击者能做哪些事，不能做哪些事

5、,在设计和分析安全协议时，必须明确一点：,16,攻击者能做到的事：,能截获经过网络的任何消息,以合法参与者身份，发起与任何用户的对话,有机会成为任何主体发出消息的接收者,能够冒充任何别的主体给任意主体发消息,17,攻击者不能做到的事：,不能猜到从足够大的空间中选出的随机数,没有正确的密钥，不能由给定的密文恢复出明文；也不能从给定的明文构造出正确的密文,不能从公钥计算出相应的私钥,不能控制计算环境中的许多私有区域，如离线的存储器,18,在现实世界中，,你会交给陌生人一叠现金替你买东西吗？,你没看到别人洗牌和发牌，会和他玩三国杀吗？,没有匿名的保证，你会在选举中投反对票吗？,网络上的协议参与者可能

6、是完全信任的人，也可能是攻击者和完全不信任的人。,假设使用网络的人都是诚实的想法，是天真的。天真的想法还有：,假设网管是诚实的，假设网络设计者是诚实的。,19,安全协议设计与分析的困难性,安全目标本身的微妙性,表面上十分简单的目标，实际上十分微妙,运行环境的复杂性,实际上,当安全协议运行在一个十分复杂的公开环境时,攻击者处处存在,攻击者模型的复杂性,必须形式化地描述攻击者的能力，对攻击者和攻击行为进行分类和形式化的分析,安全协议本身具有,“,高并发性,”,20,好的安全协议应满足的条件,满足目标,(,应用目标,安全目标,),易于实现,各参与者所需计算量小、存储量小,通信负载小,(,延迟小,占用

7、带宽小,),交互轮数少,9.2,认证协议,21,22,认证的分类,实体认证,(,身份认证,),数据源认证,(,消息认证,),确认通信实体的真实身份,确认数据发送者的真实身份,23,实体认证,目的,向别人证明你是谁？,弄清楚他是谁？,24,实体认证,实体认证可分为：,单向认证,：通信一方认证另一方的身份,双向认证,：通信双方彼此认证身份,25,实体认证,方法,Know sth:,他知道什么可用于识别他的东西,?,Have sth,：他拥有什么可用于识别他的东西,?,Be sth,：他有什么特征？,26,实体认证,know sth,口令是最常用的认证机制，但安全性较差,易受到泄露、猜测、窃听、社会

8、工程学等形式的攻击,什么是弱口令？,短口令,常见单词,生日,电话号码,系统预设口令,27,口令管理措施,口令应具有一定的长度，包含多种字符类型,口令不应使用易猜测的数字或字母组合,口令应具有一定的生存期,口令不应使用一定时间内的历史口令,用户登录不同系统应使用不同的口令,系统应设定口令登录失败次数限制,口令空间,口令时间,口令保护,28,与,“,基于口令的加密,(PBE),”,的区别,基于口令的加密：利用口令推导出密钥,基于口令的认证：利用口令进行实体认证,例如：登录电子邮箱、进入网上银行,实体认证,know sth:,基于口令的认证机制,29,需解决的关键问题,口令的存储,直接明文存储口令？

9、,一旦得到存储口令的数据库，就可得到全体人员的口令。,风险很大！,常用解决方法,Needham,口令认证协议,(,利用,Hash,函数存储口令,),一次性口令机制,30,原理,利用,Hash,函数存储口令，防范攻击者偷取数据库后得到口令,简单有效，广泛应用于各种系统中,UNIX,：使用,DES,代替,Hash,函数,Discuz,！,实体认证,know sth:Needham,口令认证协议,31,用户名,口令散列值,zhang,xtR$42,Alice,6tT$2%,数据库,password,H,6tT$2%,比较,username,Alice,缺点,无法防范攻击者在线窃听口令,无法防范离线字

10、典攻击,32,为防范在线窃听口令，可使用一次性口令机制,每次认证使用不同的口令,要求用户和系统共享很多口令,但管理和保护大量的口令在技术上很困难,为克服这一缺点，,Lamport,提出利用多次,Hash,的方法实现一次性口令机制,实体认证,know sth:,一次性口令机制,33,方法举例,系统保存,P100,用户保存,P99,、,P98,、,P97,认证过程,用户提交,P99,系统计算,if,（,P100=Hash(P99),）,验证通过,;,保存,P99;,用户丢弃,P99,初始秘密值,w,P1=H(w),P2=H(P1),P100=H(P99),系统保存,计算完销毁,用户保存,实体认证,

11、know sth:Lamport,的一次性口令机制,34,Lamport,方案的缺点,必须保持同步,但可能因为不可靠信道或死机出现丢失同步的情况,(,有可能是攻击者的破坏所致,),35,在,WEB,应用中，可以利用,SSL,建立安全信道，再进行基于口令的认证,方法,先使用,HTTPS,协议，与服务器建立安全连接,(,服务器必须支持,HTTPS),再将用户名和口令传送到服务器进行认证,应用方便，安全保护对用户透明,比如：用浏览器登录电子邮件服务器,实体认证,know sth:,利用,SSL,建立安全信道传输口令,36,点击,“,登录,”,，浏览器地址栏会闪过一个以,“,https,”,开头的地址

12、，这说明正用,SSL,安全连接传送用户名和口令,37,实体认证,have sth.,存储卡：,在磁卡上保存用户信息；与,PIN,配合使用,智能卡：,由一个或多个集成电路芯片组成，包含,CPU,和存储器，具有数据存储能力和逻辑处理功能,38,实体认证,be sth.,生物特征,指纹、掌纹、虹膜、视网膜、手形、面部特征、声音特征,动态特征,签名特征,键盘特征,39,扩展阅读,对实体认证协议的典型攻击,中间人攻击,旧消息重放,交错攻击,平行会话攻击,反射攻击,40,9.3,秘密共享,41,宝藏问题,海盗们把宝藏藏在一个安全的地方，只有用地图才能找到。但地图如何分配呢？,各拿一份地图肯定不行，因为他们

13、彼此不信任,各拿地图的一部分也不行，因为有人丢失他那份的话，就无法复原地图,如何解决,秘密共享技术,42,秘密共享是什么,将秘密分割存储的密码技术,秘密共享的目的,防止秘密过于集中，以达到分散风险和容忍入侵的目的,43,提出时间,Shamir 1979,年,(m,n),门限方案,将秘密,SK,拆成,n,份,任意,m(mn),份或更多份都可以恢复,SK,任何少于,m,份都不能得到关于,SK,的任何有用信息,其中，每一份都称为一个,share,（或,shadow,）,门限方案,解决秘密共享问题最常用的方法,44,(3,5),门限方案,SK,SK,3,SK,5,SK,SK,SK,1,SK,2,SK,

14、4,45,拉格朗日插值多项式,给定有限域,F,p,中互不相同的整数,x,1,x,n+1,和任意不全为零的整数,k,1,k,n+1,，公式,满足,f(x,i,)=k,i,，,i=1,n+1,f(x),是一个,n,次多项式，称为拉格朗日插值多项式,Shamir,的门限方案,基于拉格朗日插值多项式,46,方案描述,分割秘密,设待共享秘密为,K,令,a,0,=K,随机产生,m-1,次多项式,f(x)=(a,m-1,x,m-1,+,+a,1,x+a,0,)mod p,依次计算,k,i,=f(x,i,),，,i=1,n,易知,K=f(0),且每一对,(x,i,k,i,),都是,f(x),函数曲线上的一个点

15、,k,i,是每个参与者的,share,必须保密,(x,i,无需保密,),47,重构,f(x),给定,k,1,k,2,k,m,共,m,个,share,，对应的分别是,x,1,x,2,x,m,。,f(x),可由拉格朗日插值多项式给出：,恢复秘密,K=f(0),48,安全性原理,对于,m-1,次多项式，只需给出,m,个点就可以唯一地重构，少于,m,个,share,则不能。,由此保证,K,可从,m,个,share,中获得，而少于,m,个办不到。,49,举例：,(3,5),的门限方案,设,m=3,，,n=5,，,p=17,，,K=13,，,分割秘密,构造随机多项式,f(x),(2x,2,+10 x+,1

16、3,)mod 17,k,1,=f(1)=(2+10+13)mod 17=8,k,2,=f(2)=(8+20+13)mod 17=7,k,3,=f(3)=(18+30+13)mod 17=10,k,4,=f(4)=(32+40+13)mod 17=0,k,5,=f(5)=(50+50+13)mod 17=11,k,1,k,5,便是,share,每个用户一人一个,50,重构,f(x),给定,k,1,=8,k,3,=10,k,5,=11,重构如下：,恢复,K=f(0)=13,51,门限方案的图形化,视觉密码,提出者,Shamir,等,目的,将写有秘密信息的图片拆分成,n,张,至少,m,张,(mn),

17、才能恢复原来的图片,优点,安全性高：相当于,“,一次一密,”,计算开销低：恢复原图片时，用幻灯机即可，无需计算机参与,52,(2,3),的视觉密码方案,写有秘密信息,的原图片,天王盖地虎,宝塔镇河妖,53,一个实际的例子,9.4,零知识证明,54,55,Peter,：我知道瑞士银行计算机系统的口令,Victor,：我才不信，你不知道,Peter,：我就知道,Victor,：拉倒吧，别忽悠,Peter,：我确实知道,Victor,：你怎么证明,Peter,悄悄说出了口令,Victor,：艾玛，现在我也知道了，我去告诉小红,Peter,一脸黑线,-_-|,一个小故事,56,我知道某个秘密,我想向别

18、人证明,“,我确实知道这个秘密,”,除此之外，我不想让别人获得 关于该秘密的任何知识,应该怎么办？,零知识证明,57,什么叫,“,获得知识,”,：,本来有些事,Victor,自己干不了，但通过与,Peter,的交流，在不需要别人参与的情况下，这些事,Victor,自己可以干了，就称,“,Victor,从,Peter,那里获得了知识,”,相反的，与,Peter,交流之后，这些事,Victor,自己还是干不了，就称,“,Victor,从,Peter,那里没获得知识,”,(Victor,所能干的事情并没有因为与,Peter,交流而变得更多,),58,零知识证明协议应满足三个特性：,完备性：诚实证明者

19、可以压倒性概率使校验者接受自己的宣称,正确性：不诚实证明者欺骗校验者的概率可以忽略不计,零知识：校验者无法获得关于秘密的任何知识,59,设,Peter(,证明者,),知道可打开,C,和,D,之间暗门的咒语，不知道者都将走进死胡同,Peter,向,Victor(,校验者,),证明自己知道咒语，但不让,Victor,知道关于咒语的任何知识,A,B,C,D,零知识洞穴,零知识证明概念图解,60,解决咒语问题的零知识证明协议,Victor,站在,A,点,Peter,进入洞中任一点,C,或,D,Peter,进洞后，,Victor,走到,B,点,Victor,随机叫,Peter,：从左边或右边出来,Pet

20、er,按要求执行,(,可借助咒语,),Peter,和,Victor,重复执行共,n,次,A,B,C,D,61,分析：,完备性,如果,Peter,知道咒语，他总能正确回答,Victor,的提问,。,正确性,如果,Peter,不知道咒语，他只能从原路返回到,B,点，因此每一轮他欺骗,Victor,的概率是,1/2,，,n,轮成功欺骗的概率是,1/2,n,是可以忽略的。,零知识,从协议执行可知，与,Peter,交互后，,Victor,无法获得关于咒语的任何知识,62,零知识洞穴问题可以转化为数学问题，,Peter,知道解决某个难题的秘密（相当于咒语），而,Victor,通过与,Peter,交互以验证

21、其真实性。,63,结论,如果单向函数是存在的，任何一个,NP,问题都存在零知识证明,相关论文,Goldwasser,Micali,Rackoff.The knowledge complexity of interactive-proof systems.Proc.of 17th ACM Sym.on Theory of Computation,pp.291-304,1985.,NP,与零知识证明,G0,NP,与零知识证明举例,图同构,证明两个图,G0,和,G1,是同构的（置换为,）,Alice,向,Bob,证明：他知道两个图是如何同构的,也即 证明自己知道,G1,G0,基本原理,G1,G,G,

22、与,G1,的置换？,o,G,与,G0,的置换为,G0,G1,G,C=0 or 1,证明过程如下,G0,G1,C=0 or 1,G,G0,G1,G,C,C=0 or 1,C=0 or 1,G0,G1,G,C=0 or 1,C=0 or 1,x=,if,c=c,x=,o,if cc,x,C,G0,G1,G,C=0 or 1,C=0 or 1,x=,if,c=c,x=,o,if cc,x,C,检查,x,是否是,G,与,G,c,的同构关系,n,轮,G0,G1,72,协议描述：,Alice,如下执行：,Alice,随机选择图,G0,或,G1,(c=0 or 1),Alice,构造其同构图,G,(,置换为

23、,),，并发给,Bob,Bob,随机让,Alice,证明,G,与,G0,或,G1,同构,(c,=0 or 1),Alice,产生,x,，将,x,发送给,Bob,x=,if,c=c,x=,o,if cc,Bob,校验,G,c,是否能在置换,x,的变换下等于,G,重复执行,1-4,共,n,次,73,分析：,完备性,如果,G0,与,G1,确实同构，且,Alice,知道同构置换,，她总能正确回答,Bob,的提问,。,正确性,如果,Alice,不知道,或者,G0,与,G1,不同构，她只能以,1/2,概率正确回答,Bob,的提问，,n,轮成功欺骗的概率是,1/2,n,是可以忽略的。,零知识,Bob,能从交

24、互中获得,的知识吗？,74,分析（续）：,其实，即使不与,Alice,交互，,Bob,也可以自己产生交互数据。,Bob,可以这么做：,随机选择一个,c,=0 or 1,构造图,G,c,的同构图,G,，设同构置换为,x,生成交互数据（,G,c,x,）,这就说明，,“,产生交互数据,”,这件事，即使不与,Alice,交互，,Bob,自己也可以干，所以他没从,Alice,处获得任何知识。,75,扩展阅读,其他协议,比特承诺,公平抛硬币,智力扑克,阈下信道,安全多方计算,不经意传输,76,掌握安全协议的相关概念、,Dolev-Yao,攻击者模型,掌握实体认证的分类方法,掌握,Needham,口令认证协议、,Lamport,的一次性口令机制,掌握秘密共享的基本概念、,Shamir,的方案,掌握零知识证明的基本概念,本章小结,