11-高级密码协议.ppt
《11-高级密码协议.ppt》由会员分享,可在线阅读,更多相关《11-高级密码协议.ppt(60页珍藏版)》请在三一文库上搜索。
1、安全协议与标准, 2007, 11,高级密码协议,密码协议和数学难解问题 D-H、RSA、秘密分享、门限密码 比特承诺和网络棋牌游戏 安全多方计算 ECC 量子计算与密码学 侧信道攻击 ,协议,(算法) 协议是一系列步骤,它包括两方或多方,设计它的目的是要完成一项任务。 (1)协议中的每人都必须了解协议,并且预先知道所要完成的所有步骤。 (2)协议中的每人都必须同意遵循它。 (3)协议必须是无歧意的,每一步必须明确定义,并且不会引起误解。 (4)协议必须是完整的,对每种可能的情况必须规定具体的动作。,密码学算法和协议的背景:某些数学难解问题,大数分解难题 IFP - Integer facto
2、rization problem 离散对数难题 DLP - Discrete logarithm problem ECDLP,Diffie-Hellman密钥交换协议,DH76,Diffie-Hellman 基于DLP问题 步骤 选取大素数q和它的一个生成元g,这些参数公开 A选择随机数Xa,B选择随机数Xb A计算YagXa mod q,B计算YbgXb mod q 交换Ya,Yb A计算KYbXa mod q,B计算KYaXb mod q 事实上,KK,RSA算法,找素数,选取两个512bit的随机素数p,q 计算模n pq,Euler函数(n) =(p-1)(q-1) 找ed1 mod
3、(n) 选取数e,用扩展Euclid算法求数d 发布公钥(e,n),保密私钥(d, n) 加密明文分组m(视为整数须小于n) c=me mod n 解密 m=cd mod n,RSA problem,RSA问题 The RSA problem is to find integer P such that P e C (mod N), given integers N, e and C such that N is the product of two large primes, 2 e N is coprime to (N), and 0 = C N. 开e次方 e=3,65537,Diffi
4、e-Hellman problem,Given an element g and the values of gx and gy, what is the value of gxy ? Computational Diffie-Hellman assumption It is an open problem to determine whether the discrete log assumption is equivalent to CDH, though in certain special cases this can be shown to be the case. Decision
5、al Diffie-Hellman assumption (ga, gb, gab) ? (ga, gb, gc),秘密(密钥)分割,秘密分割(多人共同持有秘密) 0. 秘密K需要t个人联合打开 1. 产生随机数R1、R2、Rt-1、 Rt=KR1R2Rt-1 2. t个人分别持有Ri 3. 恢复秘密 KR1R2Rt-1Rt,秘密的门限共享,(m,n)门限方案 秘密的恢复需要n个人中的m个参与即可 Lagrange插值方案 以(3,n)门限方案为例: 取多项式f(x)=ax2+bx+K,a、b是随机数,K是秘密对于成员i1n,给予f(xi)=axi2+bxi+K,一般取xii恢复秘密时只需n中
6、的三个(x、y)点即重构f(x),门限密码学 (Threshold Cryptography),一组人用门限方法共同持有一个私钥,要对某个消息签名: (1) 可以恢复私钥,然后签名。这样私钥就公开暴露在组人面前,以后就不能用了。 (2) 不恢复私钥而签名。这样私钥可以继续使用。,时间戳服务,在很多情况中,人们需要证明某个文件在某个时期存在。版权或专利争端即是谁有产生争议的工作的最早的副本,谁就将赢得官司。对于纸上的文件,公证人可以对文件签名,律师可以保护副本。如果产生了争端,公证人或律师可以证明某封信产生于某个时间。 在数字世界中,事情要复杂得多。没有办法检查窜改签名的数字文件。他们可以无止境
7、地复制和修改而无人发现。在计算机文件上改变日期标记是轻而易举的事,没有人在看到数字文件后说:“是的,这个文件是在1952年12月4日以前创建的。” - Applied Cryptography, Second Edition 权威机构:CA、公证处,in PGP fmt,实验:时间戳服务,“联合信任”公司的时间戳服务 http:/ Blind Signature,A持有消息m,B持有私钥d,计算s md mod n,但是不泄露各自的输入。 A让B签署经随机盲化掩饰后的消息 m m*re mod n B计算 s md mod n A从而仍可得到B对m的签名 s s* reverse(r) (m*
8、re)d*r -1 md*red-1 md mod n,信息隐藏学/隐写术 Steganography,演示软件 Dstego Google(“Dstego”) 能把秘密藏到声音、图像,甚至可执行文件中 阈下信道 Subliminal channel 数字水印 Digital watermarking,网络游戏,棋类游戏很容易网络化 牌类游戏则需要处理额外问题 如何洗牌/发牌? 一个简单的操作:掷色子 更简单的:抛硬币,抛硬币,Alice和Bob想抛掷一个公平的硬币,但又没有实际的物理硬币可抛。Alice提出一个用思维来抛掷公平硬币的简单方法。“首先,你想一个随机比特,然后我再想一个随机比特,
9、我们将这两个比特进行异或。”Alice建议道。 ,好的思路,首先,Bob确定一个比特,但这次他不立即宣布,只是将它写在纸上,并装入信封中。接下来,Alice公布她选的比特。最后,Alice和Bob从信封中取出Bob的比特并计算随机比特。只要至少一方诚实地执行协议,这个比特的确是真正随机的。,信封,加密 这种技术叫比特承诺(Bit Commitment) 投币入井协议(Flipping Coins into a Well) “金簪子掉进井里”,采用单向函数的抛币协议,如果Alice和Bob对使用一个单向函数达成一致意见,协议非常简单: (1)Alice选择一个随机数x,她计算y=f(x),这里f
10、(x)是单向函数; (2)Alice将y送给Bob; (3)Bob猜测x是偶数或奇数,并将猜测结果发给Alice; (4)如果Bob的猜测正确,抛币结果为正面; 如果Bob的猜测错误,则抛币的结果为反面。Alice公布此次抛币的结果,并将x发送给ob; (5)Bob确信y=f(x)。,三方智力扑克,Alice、Bob和Carol都产生一个公钥/私钥密钥对。 加密可交换性质, 即mk1,k2=mk2,k1 Alice产生52个消息(可验证的唯一的随机串),每个代表一副牌中的一张牌。Alice用她的公钥加密所有这些消息,并将它们发送给Bob。 Bob,由于不能阅读任何消息,他随机地选择5张牌。他用
11、他的公钥加密,并把它们回送给Alice。Bob将余下的47张牌送给Carol。 Carol,由于不能阅读任何消息,也随机选5个消息。她用她的公钥加密,并把它们送给Alice。,-,Alice也不能阅读回送给她的消息,她用她的私钥对它们解密,然后送给Bob或Carol(依据来自谁而定)。 Bob和Carol用他们的密钥解密并获得他们的牌。 Carol从余下的42张牌中随机取5张,把它们发送给Alice。 Alice用她的私钥解密消息获得她的牌。 在游戏结束时,Alice,Bob和Carol都出示他们的牌以及他们的密钥,以便每人都确信没有人作弊。,百万富翁问题,百万富翁问题 两个百万富翁想知道谁更
12、富有,但不想泄露有关财富多少的任何信息。 如果不借助于第三方,他们自己能做到吗? “ Two millionaires wish to know who is richer; however, they do not want to find out inadvertently any additional information about each others wealth. How can they carry out such a conversation? ” - Yao82,网络游戏问题:从 Gold87演绎,军棋(暗棋) 普通军棋需要第三人为裁判 网络军棋使用服务器(可信第三方
13、)为裁判 ? 能否避免使用第三方,*专利:自裁判军棋,自裁判军棋 此军棋可实现不用裁判即可下暗棋的功能, 能达到与网络军棋相同的效果 http:/ 专利样本,年龄比较,概念 假设A、B年龄a, b,且无意于撒谎 准备适当多的(比如100个)信封顺序排好 B回避,A把前a个信封中做记号 A回避,B把第b个信封取出,把其余信封收起来 A和B共同打开此信封,有记号则说明a=b,无记号则ba,比较是否相等,a. 比较两个大文件是否等同 比如网络文件共享或同步,避免传输而比较两个大文件内容是否一致(BT/eMule) 方法是比较两个文件的Hash值 (如果不想泄露自己大文件的Hash值,归为b) b.
14、比较两个小文件(短消息) 不能公布内容,也不能公布Hash值 如果公布其Hash值,则容易受到枚举攻击 参见 应用密码学6.2 保密的多方计算-协议#3”保密的多方计算约会服务(Secure Multiparty Computation Dating Service) ”,求和/平均值,一群人怎样才能计算出他们的平均薪水,而又不让任何人知道其他人的薪水呢? Alice在她的薪水上加一个秘密随机数,然后把它送给Bob Bob把他的薪水加上,并把它送给Carol。 Carol把她的薪水相加,并把它送给Dave。 Dave把他的薪水相加,并把它送给Alice。 Alice减去那个随机数以恢复每个人薪
15、水之总和。 Alice把这个结果除以人数(4),并宣布结果。,to check if they love each other,Alice有保密输入a,Bob有保密输入b: a := 1 若A喜欢B / 否则0 b := 1 若B喜欢A / 否则0 目标(在尽可能保护隐私的前提下)计算 f(a,b) := a b 保护隐私的效果 如果f(a,b)=1,则没有隐私 如果f(a,b)=0,则如果对方是0则其不知道自己是否是1,即保护了自己的隐私。,SMPC问题定义,参与者Pi持有输入Xi 计算函数 (Y1,Y2,Yi,)=F(X1,X2,Xi,) 参与者Pi得到输出Yi Pi不知道Xi/Yi之外的
16、其他值 假设各方输入时是诚实的。 如果有可信第三方,则可以让它来帮助计算。 但是安全多方计算考虑不用可信第三方时的情况,并考虑抵抗部分成员合谋试图知道其他人的输入。,所有密码协议都是多方安全计算的特例,门限签名/解密、群密钥协商、身份鉴别、传输加密等。 电子商务中的问题,比如拍卖、投票、电子现金等。 在互联网上保护隐私方面。,对密文查询,比如Gmail可以存放3G的邮件,Google公司显然企图从中搜集用户喜好和动向(他们叫数据挖掘),从而发送定向广告。 为了挫败Gmail的企图以及其他的安全考虑,使用PGP处理邮件。 问题是如何查询? 查找某封信,只记得该信内容是讨论如何做“酸菜鱼”的。 标
17、签label,如何保护用户隐私,Google可能会记录用户的查询关键字历史,从而服务于。 如何保护自己的查询关键字不被记录。 Private Information Retrieval (PIR) 查询数据库,而不暴露查询的具体项 另一种形式 允许查询数据库,而不暴露数据库,CED:DLP,Alice想让Bob帮忙计算e,而不泄露x和e x ge mod p A计算 x x*gr mod p B求e x ge mod p A计算 e = (e-r) mod p-1 因为 x ge mod p x*gr ge mod p x g(e-r) mod p,一般思路,借助别人的计算能力,计算自己的函数
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 11 高级 密码 协议
链接地址:https://www.31doc.com/p-2877134.html