《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,一般思路,借助别人的计算能力，计算自己的函数
18、，而不泄漏某些相关的信息。 自己计算F(X) X-F(X)-Y 如果借助另外的帮助 X-g(X) h(Y)-Y | | X-F(X)-Y,RSA提速,利用外部计算能力加密 C=Me 解密 M=Cd M=1 For each bit of D=dkd2d1 if di=1 then M=M*C % N C=C2 % N End For,椭圆曲线,* 寻找离散对数问题的背景群：从Zp*到EC Elliptic Curve y2axybyx3cx2dxe 其中a、b、c、d、e是满足某个简单条件的实数 另有O点被定义为无穷点/零点 点加法，PQR定义为 过P、Q和椭圆曲线相交的第三点的X轴对称点R,
19、EC图示,P+Q=R O点 累加 P+P=2P P+P+P=3P P+P=kP,素域上的EC,在有限域Zp上的简化EC y2x3axb mod p 其中4a327b2 mod p 0 这是一个离散点的集合 * 直观解释 把开放二维平面折叠到pp的方框内，并且只考虑整数点,y2x318x15 mod 23,ECDLP,在D-H密钥交换中(群Zp*中) 使用了ygx mod p中x的计算困难性 在EC点加法群中 QkP中的k计算也是极其困难的 (kP表示k个P相加：P + + P),ECDSA,DSA/DSS，基于DLP问题的签名算法/标准 Lucifer/DES，Rijndael/AES ECD
20、SA，基于ECDLP问题的DSA算法,P1363,IEEE P1363 is an IEEE standardization project for public-key cryptography. It includes specifications for: * Traditional public-key cryptography (IEEE Std 1363-2000 and 1363a-2004) * Lattice-based public-key cryptography (P1363.1) * Password-based public-key cryptography (P1
21、363.2) * Identity-based public-key cryptography using pairings (P1363.3),1363/a,the underlying computationally difficult problem: discrete logarithm in the group of remainders modulo a prime (DL) discrete logarithm in the group of points on an elliptic curve over a finite field (EC) integer factoriz
22、ation (IF) For the DL family, the standard will include: Diffie-Hellman key agreement allowing up to two key pairs from each party Menezes-Qu-Vanstone key agreement, which requires two key pairs from each party DSA Signatures, with SHA-1 and RIPEMD-160 as hash functions Nyberg-Rueppel Signatures wit
23、h appendix, with SHA-1/ RIPE-160 as hash functions For the EC family, the standard will mirror the DL family; For the IF family, the standard: RSA encryption with Optimal Asymmetric Encryption Padding (OAEP) RSA signature with appendix using a hash function and ANSI X9.31 padding Rabin-Williams (eve
24、n exponent) equivalents of the above RSA signatures,P1363.1,IEEE P1363.1 will specify cryptographic techniques based on hard problems over lattices. It is also intended that P1363.1 provide a second-generation framework for the description of cryptographic techniques, as compared to the initial fram
25、ework provided in 1363-2000 and draft P1363a. It is not the purpose of this project to mandate any particular set of public-key techniques or security requirements (including key sizes) for this or any family. Rather, the purpose is to provide: a reference for specification of a variety of technique
26、s from which applications may select, the relevant number-theoretic background, and extensive discussion of security and implementation considerations so that a solution provider can choose appropriate security requirements for itself.,P1363.2,Memorized secrets are an important factor in human authe
27、ntication. P1363.2 will specify public-key cryptographic techniques specifically designed to securely perform password-based authentication and key exchange. These techniques provide a way to authenticate people and distribute high-quality cryptographic keys for people, while preventing off-line bru
28、te-force attacks associated with passwords. Rather, the purpose is to provide: (1) a reference for specification of a variety of techniques from which applications may select, (2) the appropriate theoretic background, and (3) extensive discussion of security and implementation considerations so that
29、 a solution provider can choose appropriate security requirements.,P1363.3,IEEE P1363.3 will specify Identity-Based Cryptographic techniques based on Pairings. These offer advantages over classic public key techniques specified in IEEE 1363. Examples are the lack of a requirement to exchange or look
30、 up public keys of a recipient and the simplified use of short-lived keys. It is not the purpose of this project to mandate any particular set of identity-based public-key techniques, or particular attributes of public-key techniques such as key sizes. Rather, the purpose is to provide a reference f
31、or specifications of a variety of techniques from which applications may select.,Certicom,Certicom Corp. is a cryptography company founded in 1985 by Gordon Agnew. The Certicom intellectual property portfolio includes over 350 patents and patents pending worldwide that cover key aspects of elliptic
32、curve cryptography (ECC): software optimizations, efficient hardware implementations, methods to enhance the security, and various cryptographic protocols. The National Security Agency (NSA) has licensed 26 of Certicoms ECC patents as a way of clearing the way for the implementation of elliptic curv
33、es to protect US and allied government information. whuecc,Lattice-based,phD,Lattice-based,量子技术,量子 量子比特(qubit) 量子通信 量子密码学 量子计算机 1994年，彼得秀尔（Peter Shor）提出量子质因子分解算法 1994年，贝尔实验室的专家彼得修尔（Peter Shor）证明量子电脑能做出对数运算,纠缠 Quantum entanglement,光子有一奇异的特性“混杂”特性，即从同一个光 源分出的光束具有相同的物理性质，尤如“双胞胎”一样。 1982年，法国奥赛光学研究所的科学家就
34、在实验室实现了光子“混杂”，1997年，他们又使用光纤再次完成了这一实验。 瑞士研究人员在近期也进行了类似的实验，他们将聚集在一个非线性晶体上的激光束分成两束，第一束被导向一个实验室，另一束则通过一个2公里长的光纤、被导向另一个实验室，两个实验室相距55米。研究人员在一个实验室内将第三束光与“双胞胎”光束中的一束相互作用，他们观察到在另一个实验室的另一束光也发生着这种变化。这一实验证实了光子的“混杂”特性：一个唯一、相同的物体同时处于两个不同的地方，使得在一个地方对光子的操作可以反射到处于另一个地方的“双胞胎”光子上并表现出来。实验的成功，使光子“混杂”特性从实验室研究走向实际应用迈出了新的一
35、步，使量子远距离输运变成可能。,测不准,海森堡测不准原理 在一个量子力学系统中，一个粒子的位置和它的动量不可被同时确定。（测量手段必然引入干扰）,量子密钥分发协议,BB84 B92,一次一密(one-time pad) vs. 量子计算,按照信息论观点，one-time pad能抵抗量子计算,TODO：量子计算,量子计算机 For a quantum computer, however, Peter Shor discovered an algorithm in 1994 that solves it in polynomial time. 量子密码学 “海森堡测不准” “单量子不可复制” 实验室阶段,侧信道攻击,TODO,Q & A,