《高级密码协议》PPT课件.ppt

安全协议与标准,2007,11,高级密码协议,密码协议和数学难解问题D-H、RSA、秘密分享、门限密码比特承诺和网络棋牌游戏安全多方计算ECC量子计算与密码学侧信道攻击,协议,（算法）协议是一系列步骤，它包括两方或多方，设计它的目的是要完成一项任务。（1）协议中的每人都必须了解协议，并且预先知道所要完成的所有步骤。（2）协议中的每人都必须同意遵循它。（3）协议必须是无歧意的，每一步必须明确定义，并且不会引起误解。（4）协议必须是完整的，对每种可能的情况必须规定具体的动作。,密码学算法和协议的背景：某些数学难解问题,大数分解难题IFP-Integer factorization problem离散对数难题DLP-Discrete logarithm problemECDLP,Diffie-Hellman密钥交换协议,DH76，Diffie-Hellman基于DLP问题步骤选取大素数q和它的一个生成元g，这些参数公开A选择随机数Xa，B选择随机数Xb A计算YagXa mod q，B计算YbgXb mod q 交换Ya，YbA计算KYbXa mod q，B计算KYaXb mod q 事实上，KK,RSA算法,找素数，选取两个512bit的随机素数p,q计算模n pq，Euler函数(n)=(p-1)(q-1)找ed1 mod(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,Diffie-Hellman problem,Given an element g and the values of gx and gy,what is the value of gxy?Computational Diffie-Hellman assumptionIt 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.Decisional Diffie-Hellman assumption(ga,gb,gab)?(ga,gb,gc),秘密(密钥)分割,秘密分割（多人共同持有秘密）0.秘密K需要t个人联合打开1.产生随机数R1、R2、Rt-1、Rt=KR1R2Rt-12.t个人分别持有Ri3.恢复秘密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中的三个(x、y)点即重构f(x),门限密码学(Threshold Cryptography),一组人用门限方法共同持有一个私钥，要对某个消息签名:(1)可以恢复私钥，然后签名。这样私钥就公开暴露在组人面前，以后就不能用了。(2)不恢复私钥而签名。这样私钥可以继续使用。,时间戳服务,在很多情况中，人们需要证明某个文件在某个时期存在。版权或专利争端即是谁有产生争议的工作的最早的副本，谁就将赢得官司。对于纸上的文件，公证人可以对文件签名，律师可以保护副本。如果产生了争端，公证人或律师可以证明某封信产生于某个时间。在数字世界中，事情要复杂得多。没有办法检查窜改签名的数字文件。他们可以无止境地复制和修改而无人发现。在计算机文件上改变日期标记是轻而易举的事，没有人在看到数字文件后说：“是的，这个文件是在1952年12月4日以前创建的。”-Applied Cryptography,Second Edition权威机构：CA、公证处,in PGP fmt,实验：时间戳服务,“联合信任”公司的时间戳服务,盲签名 Blind Signature,A持有消息m，B持有私钥d，计算s md mod n，但是不泄露各自的输入。A让B签署经随机盲化掩饰后的消息m m*re mod nB计算s md mod nA从而仍可得到B对m的签名s s*reverse(r)(m*re)d*r-1 md*red-1 md mod n,信息隐藏学/隐写术 Steganography,演示软件 DstegoGoogle(“Dstego”)能把秘密藏到声音、图像，甚至可执行文件中阈下信道 Subliminal channel数字水印 Digital watermarking,网络游戏,棋类游戏很容易网络化牌类游戏则需要处理额外问题如何洗牌/发牌？一个简单的操作：掷色子更简单的：抛硬币,抛硬币,Alice和Bob想抛掷一个公平的硬币，但又没有实际的物理硬币可抛。Alice提出一个用思维来抛掷公平硬币的简单方法。“首先，你想一个随机比特，然后我再想一个随机比特，我们将这两个比特进行异或。”Alice建议道。,好的思路,首先，Bob确定一个比特，但这次他不立即宣布，只是将它写在纸上，并装入信封中。接下来，Alice公布她选的比特。最后，Alice和Bob从信封中取出Bob的比特并计算随机比特。只要至少一方诚实地执行协议，这个比特的确是真正随机的。,信封,加密这种技术叫比特承诺（Bit Commitment）投币入井协议（Flipping Coins into a Well）“金簪子掉进井里”,采用单向函数的抛币协议,如果Alice和Bob对使用一个单向函数达成一致意见，协议非常简单：（1）Alice选择一个随机数x，她计算y=f（x），这里f（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,k1Alice产生52个消息(可验证的唯一的随机串)，每个代表一副牌中的一张牌。Alice用她的公钥加密所有这些消息，并将它们发送给Bob。Bob，由于不能阅读任何消息，他随机地选择5张牌。他用他的公钥加密，并把它们回送给Alice。Bob将余下的47张牌送给Carol。Carol，由于不能阅读任何消息，也随机选5个消息。她用她的公钥加密，并把它们送给Alice。,-,Alice也不能阅读回送给她的消息，她用她的私钥对它们解密，然后送给Bob或Carol（依据来自谁而定）。Bob和Carol用他们的密钥解密并获得他们的牌。Carol从余下的42张牌中随机取5张，把它们发送给Alice。Alice用她的私钥解密消息获得她的牌。在游戏结束时，Alice，Bob和Carol都出示他们的牌以及他们的密钥，以便每人都确信没有人作弊。,百万富翁问题,百万富翁问题两个百万富翁想知道谁更富有，但不想泄露有关财富多少的任何信息。如果不借助于第三方，他们自己能做到吗？“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演绎,军棋(暗棋)普通军棋需要第三人为裁判网络军棋使用服务器(可信第三方)为裁判?能否避免使用第三方,*专利：自裁判军棋,自裁判军棋此军棋可实现不用裁判即可下暗棋的功能，能达到与网络军棋相同的效果专利样本,年龄比较,概念假设A、B年龄a,b，且无意于撒谎准备适当多的(比如100个)信封顺序排好B回避，A把前a个信封中做记号A回避，B把第b个信封取出，把其余信封收起来A和B共同打开此信封，有记号则说明a=b，无记号则ba,比较是否相等,a.比较两个大文件是否等同比如网络文件共享或同步，避免传输而比较两个大文件内容是否一致(BT/eMule)方法是比较两个文件的Hash值(如果不想泄露自己大文件的Hash值，归为b)b.比较两个小文件(短消息)不能公布内容，也不能公布Hash值如果公布其Hash值，则容易受到枚举攻击参见 应用密码学6.2 保密的多方计算-协议#3”保密的多方计算约会服务（Secure Multiparty Computation Dating Service）”,求和/平均值,一群人怎样才能计算出他们的平均薪水，而又不让任何人知道其他人的薪水呢？Alice在她的薪水上加一个秘密随机数，然后把它送给BobBob把他的薪水加上，并把它送给Carol。Carol把她的薪水相加，并把它送给Dave。Dave把他的薪水相加，并把它送给Alice。Alice减去那个随机数以恢复每个人薪水之总和。Alice把这个结果除以人数(4)，并宣布结果。,to check if they love each other,Alice有保密输入a，Bob有保密输入b:a:=1 若A喜欢B/否则0b:=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得到输出YiPi不知道Xi/Yi之外的其他值假设各方输入时是诚实的。如果有可信第三方，则可以让它来帮助计算。但是安全多方计算考虑不用可信第三方时的情况，并考虑抵抗部分成员合谋试图知道其他人的输入。,所有密码协议都是多方安全计算的特例,门限签名/解密、群密钥协商、身份鉴别、传输加密等。电子商务中的问题，比如拍卖、投票、电子现金等。在互联网上保护隐私方面。,对密文查询,比如Gmail可以存放3G的邮件，Google公司显然企图从中搜集用户喜好和动向（他们叫数据挖掘），从而发送定向广告。为了挫败Gmail的企图以及其他的安全考虑，使用PGP处理邮件。问题是如何查询？查找某封信，只记得该信内容是讨论如何做“酸菜鱼”的。标签label,如何保护用户隐私,Google可能会记录用户的查询关键字历史，从而服务于。如何保护自己的查询关键字不被记录。Private Information Retrieval(PIR)查询数据库，而不暴露查询的具体项另一种形式允许查询数据库，而不暴露数据库,CED：DLP,Alice想让Bob帮忙计算e，而不泄露x和e x ge mod pA计算x x*gr mod pB求e x ge mod pA计算e=(e-r)mod p-1因为 x ge mod p x*gr ge mod p x g(e-r)mod p,一般思路,借助别人的计算能力，计算自己的函数，而不泄漏某些相关的信息。自己计算F(X)X-F(X)-Y如果借助另外的帮助X-g(X)h(Y)-Y|X-F(X)-Y,RSA提速,利用外部计算能力加密C=Me解密M=CdM=1For each bit of D=dkd2d1if di=1 then M=M*C%NC=C2%NEnd For,椭圆曲线,*寻找离散对数问题的背景群：从Zp*到ECElliptic Curvey2axybyx3cx2dxe其中a、b、c、d、e是满足某个简单条件的实数另有O点被定义为无穷点/零点点加法，PQR定义为过P、Q和椭圆曲线相交的第三点的X轴对称点R,EC图示,P+Q=RO点累加P+P=2PP+P+P=3PP+P=kP,素域上的EC,在有限域Zp上的简化ECy2x3axb 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/AESECDSA，基于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(P1363.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 factorization(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 with 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(even 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 framework 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 techniques from which applications may select,the relevant number-theoretic background,andextensive 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 authentication.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 brute-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 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 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 for 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 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 curves to protect US and allied government information.whuecc,Lattice-based,phD,Lattice-based,量子技术,量子量子比特(qubit)量子通信量子密码学量子计算机1994年，彼得秀尔（Peter Shor）提出量子质因子分解算法1994年，贝尔实验室的专家彼得修尔（Peter Shor）证明量子电脑能做出对数运算,纠缠 Quantum entanglement,光子有一奇异的特性“混杂”特性，即从同一个光 源分出的光束具有相同的物理性质，尤如“双胞胎”一样。1982年，法国奥赛光学研究所的科学家就在实验室实现了光子“混杂”，1997年，他们又使用光纤再次完成了这一实验。瑞士研究人员在近期也进行了类似的实验，他们将聚集在一个非线性晶体上的激光束分成两束，第一束被导向一个实验室，另一束则通过一个2公里长的光纤、被导向另一个实验室，两个实验室相距55米。研究人员在一个实验室内将第三束光与“双胞胎”光束中的一束相互作用，他们观察到在另一个实验室的另一束光也发生着这种变化。这一实验证实了光子的“混杂”特性：一个唯一、相同的物体同时处于两个不同的地方，使得在一个地方对光子的操作可以反射到处于另一个地方的“双胞胎”光子上并表现出来。实验的成功，使光子“混杂”特性从实验室研究走向实际应用迈出了新的一步，使量子远距离输运变成可能。,测不准,海森堡测不准原理在一个量子力学系统中，一个粒子的位置和它的动量不可被同时确定。（测量手段必然引入干扰）,量子密钥分发协议,BB84B92,一次一密(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,