现代密码学之密码协议.ppt

现代密码学之密码协议.ppt

《现代密码学之密码协议.ppt》由会员分享，可在线阅读，更多相关《现代密码学之密码协议.ppt（59页珍藏版）》请在冰点文库上搜索。

国家级精品课程,现代密码学,灾备技术国家工程实验室北京邮电大学信息安全中心,上一讲内容回顾,有特殊性质的签名方案盲签名群签名与环签名多重签名聚合签名代理签名不可否认签名一次签名失败即停签名,3,密码协议,现代密码学第十讲,4,本章主要内容,密码协议概念比特承诺公平抛币协议安全多方计算电子货币电子选举匿名协议,5,本章主要内容,密码协议概念比特承诺公平抛币协议安全多方计算电子货币电子选举匿名协议,密码协议概念,协议是一系列步骤，它包括两方或多方，设计它的目的是要完成一项任务。

一般包含了三个方面的含义：

协议需要二个或二个以上的主体参与。

参与者按照一定的次序交替地执行一系列的步骤，在前一步尚未完成之前，后面的步骤不能被执行。

参与者必须能够协同地完成某项任务，或达成某种意向。

密码协议概念,密码协议的目的是参与协议的各方根据协议中采用的密码算法，执行一系列规定的步骤和操作，最终完成某项任务或达成一致的意向。

8,本章主要内容,密码协议概念比特承诺公平抛币协议安全多方计算电子货币电子选举匿名协议,比特承诺,生活实例股市预测Alice想对Bob承诺一个比特（也可以是一个比特序列），但不告诉Bob她的承诺，也就是不向Bob泄露她承诺的比特值，直到某个时间以后才提示（或公开）她的承诺；另一方面，Bob可证实在Alice承诺后，她没有改变她的承诺。

比特承诺,实例Alice把消息（承诺）放在一个箱子里并将它（只有Alice有钥匙）锁住送给Bob等到Alice决定向Bob证实消息时，Alice把消息及钥匙给BobBob能够打开箱子并验证箱子里的消息同Alice出示的消息相同，且Bob确信箱子里的消息在他保管期间没有被篡改。

比特承诺,基于对称密码算法的比特承诺方案如下：

Alice和Bob共同选定某种对称加密算法。

Bob产生一个随机比特串并发送给Alice。

Alice随机选择一个密钥，同时生成一个她欲承诺的比特串（也可以是一个比特），然后利用对称加密算法对“和”加密，最后将加密后的结果发送给验证者Bob。

当需要Alice承诺时，她将密钥和承诺的比特发送给Bob。

Bob利用密钥解密，并利用他的随机串检验比特的有效性。

比特承诺,利用基于单向函数的比特承诺方案如下：

Alice和Bob共同选定一个单向函数，如Hash函数Alice生成两个随机数和承诺比特串，计算单向函数值并将结果（哈希值）和其中一个随机数发送给Bob。

当Alice向Bob出示消息时，她把承诺比特串与另一个随机数一起发送给Bob。

Bob计算hash值，并与第步收到的值做比较以检验消息的有效性。

13,本章主要内容,密码协议概念比特承诺公平抛币协议安全多方计算电子货币电子选举匿名协议,公平掷币协议,分蛋糕问题：

Alice切蛋糕，Bob优先选，所以Alice要把蛋糕分得尽量均匀抛币：

Alice抛币Bob猜测是花还是字如果由一个人来完成，他可以作弊,公平掷币协议,不能见面的两个人通过网络或者电话完成Alice和Bob各有50%的机会获胜；任何一方欺骗则认为其在博弈中失败；协议执行结束后，Alice和Bob都知道结果,公平掷币协议,1）Alice发送一对大素数p,q的乘积n=p*q给Bob.2）Bob在中随机选取一个小于n/2的x,然后发送给Alice.3）Alice校验是否是模n的二次剩余，即是否满足勒让德符号和，若满足则计算的四个根：

，其中。

然后Alice随机猜测Bob选取的是中的哪一个，并把猜测结果0或1发送给Bob（事先规定大的用1表示，小的用0表示）.,N应该为Blum数,公平掷币协议,4）Bob收到后0或1后将第2）步中选择的发送给Alice.5）Alice检验是否属于，是否属于，现在Alice根据第3）步和接收到x的可以知道她的猜测是否正确，然后将p,q值传送给Bob.6）Bob检验p,q是否是两个不同的素数，且验证n=p*q是否成立。

然后根据和计算出，现在Bob也知道他和Alice的博弈最终是谁赢了.,公平掷币协议,例：

1）Alice选择p=11,q=19,然后把n=11*19=209发送给Bob.2）Bob在中随机选取x=31（209/2）,计算并把a=125发送给Alice.3）因为和，所以a是模p的二次剩余，同时也是模q的二次剩余，所以Alice验证得出a是模n的二次剩余；求出的四个根是假设Alice猜测Bob选取的是，则把1发送给Bob.,公平掷币协议,4）Bob收到1后将第2）步中选择的发送给Alice.5）Alice检验x属于，且，现在Alice知道她的猜测是错误的，也就是说在博弈当中Alice失败了，然后Alice将p=11,q=19传送给Bob.6）Bob检验p,q是两个不同的素数，且满足n=p*q=11*19=219.Bob根据3）步Alice传给他的数值1知道Alice猜测错了.,20,本章主要内容,密码协议概念比特承诺公平抛币协议安全多方计算电子货币电子选举匿名协议,安全多方计算,安全多方计算就是指在无可信第三方的情况下，安全地计算一个约定的函数的值。

在一个安全多方计算协议中，参与方之间一般是互不信任的，他们各自都有一个不想让其它任何人了解的秘密数，但是他们要利用这些秘密数来求得大家都信任的值或答案。

确切地讲，安全多方计算就是满足下述三个条件的密码协议：

安全多方计算,一群参与者要利用他们每个人的秘密输入来计算某个多变量复合函数的值。

参与者希望保持某种安全性，如机密性与正确性等。

协议即要保持在发生非协议参与者攻击行为下的安全性，也要保持在发生协议参与者攻击行为下的安全性，但不包括协议参与者的主动欺骗行为，即故意输入错误的秘密数据的情况。

安全多方计算典型例,百万富翁问题：

每个人都不想告诉对方自己的财富，但希望知道谁更富有。

平均薪水问题：

每个员工都不想让其他人知道自己的薪水，但希望知道他们的平均薪水。

共同兴趣问题：

Alice喜欢XXX，Bob则喜欢YYY，他们想找到一个有共同喜好的伙伴，但并不愿意招惹推销商。

加密数据计算：

Alice希望Bob替她计算f（x），但是不想让Bob知道x。

不经意传输不可思议的读写：

Alice读取Bob拥有的秘密中的一个且不知其余，而Bob并不知道Alice买走了哪一个。

百万富翁问题,假设A拥有i百万，B拥有j百万，且即1i,jN。

两人执行如下协议：

A和B共同协商一种公钥加密体制。

不妨设B的公钥和私钥分别为KUB和KRB。

A随机选择一个大随机数x,用B的公钥加密c=EKUB（x）,然后将c-i发送给B。

B首先计算N个数：

yu=DKRB（c-i+u）,u=1,2,N。

然后随机选择一个大素数p,再计算N个数：

zu=yumodp,u=1,2,N。

接着验证对于所有的0abN-1,是否都满足|za-zb|2？

若不满足，则重新选择大素数p重新验证。

最后，B将以下的N+1个数串发送给A:

z1,z2,zj,zj+1+1,zj+2+1,zN+1和p。

设A收到N+1个数串m的第i个数是mi，若满足mixmodp，则结论是ij;否则ij。

A将最终的结论告诉B。

平均薪水问题,平均薪水问题,共同兴趣问题,假设Alice与Bob已协商好各种嗜好编码和某个单向函数：

1）Alice使用一个单向函数，将自己的嗜好编码映射为7位数字2）Alice用这7位数字作为电话号，拨号。

若有人接听，则Alice给Bob留下一条消息；若无人接听，则Alice将这7位数代入单向函数再找下去，直到有人接听。

3）Alice告诉Bob她进行了几次单向函数迭代4）Bob从自己的嗜好出发，进行同样次数的单向函数迭代，将结果的7位数作为电话号，拨号，询问是否有人给他留言分析：

Bob可以进行穷举攻击,加密数据计算问题,对某些f（x）而言，是有办法的，例如盲签名。

离散对数函数：

有大素数p，生成元g，f（x）=loggx（modp）协议如下：

1）Alice随机选择rp2）Alice计算x=xgrmodp，并将x提交给Bob3）Bob计算e=f（x），并将e发送给Alice4）Alice计算f（x）=（e-r）mod（p-1）,不经意传输,情景1：

Alice有一个秘密，想用100元的价格卖给Bob。

而Bob只有50元，秘密又不能分为两半。

两人协商的结果是：

Bob付50元并以50%的几率得到消息，而Alice对Bob是否得到消息并不知情。

Rabin的ObliviousTransfer

（1）A：

取两个素数p,q，计算n=pq，nB

（2）B：

取x，0xn，gcd（x,n）=1，计算a=x2modn，aA（3）A：

因为知道p和q，可以计算x2modn=a的四个根：

x,n-x,y,n-y,从中随机挑选一个送给B（4）B：

若收到y或n-y，则可计算p和q：

gcd（x+y,n）=p或q；若收到x或n-x，则B什么也得不到。

分析：

Bob获得p和q的概率是50%Alice不知道Bob是否解得p和q,国家级精品课程,现代密码学,王励成副教授,灾备技术国家工程实验室北京邮电大学信息安全中心,上节课内容回顾,密码协议比特承诺公平抛币安全多方计算百万富翁问题平均薪水问题共同兴趣问题不经意传输,不经意传输,情景2：

Alice有两个秘密，想用100元的价格卖给Bob。

而Bob只有50元，只能买一个秘密。

两人协商的结果是，Bob付50元并能得到其中任意一个秘密，而Alice对Bob得到的是哪个消息并不知情。

扩展：

Alice传送一组消息给Bob，Bob收到其中一个子集，Alice不知道Bob收到的是哪个子集。

不经意传输,解决情形2的协议：

1）Alice产生两对公钥/私钥，将两个公钥送给Bob2）Bob选择一个对称密码算法（如DES）密钥，并用Alice的某一个公钥加密，将加密密钥发给Alice3）Alice分别用两个私钥解密Bob的加密密钥，分别用两个解密结果加密她的两份消息，将加密结果送给Bob4）Bob用密钥解密两份密文，得到两份消息之一分析：

考虑到Alice可以用解密结果加密同一份消息，而欺骗Bob；Bob如何知道Alice没有欺诈？

解决办法：

Alice将两份私钥发给Bob，以便验证她没有欺诈。

但此时Bob将有能力获得第二份消息，怎么办？

使用仲裁可以解决这个问题。

（注意：

协议结束后引入的仲裁不同于协议当中引入的可信第三方，是可以接受的。

）,34,本章主要内容,密码协议概念比特承诺公平抛币协议安全多方计算电子货币电子选举匿名协议,电子货币,电子货币是指用一定的现金或存款从银行兑换出代表相同金额的数据，并以可读写的电子形式存储起来。

当使用者需要消费时，通过电子方式将该数据直接转移给支付对象，这种数据就称为电子货币。

电子货币,电子现金系统由三个协议组成：

（1）取款协议：

用户从银行自己的帐户上提取电子货币

（2）支付款协议：

用户向商店支付电子货币（3）存款协议：

商店向银行提交用户支付的电子货币要求银行把相应的款存到商店的帐户上,电子货币,电子货币协议满足的性质：

1991年，Okamoto和Ohta提出理想的电子现金方案应满足以下六个标准：

独立性,不可伪造性和不可重用性,离线性,可转移性,可分性,不可跟踪性和不可联系性,目前的技术还很难高效实现上述所有功能,电子货币,1982年，Chaum最早提出一个在线的、基于RSA盲签名的完全电子货币方案；1988年，Chaum，Fait和Naor利用切割-选择和RSA盲签名技术提出一个在线的、完全匿名的电子现金方案；1991年，Okamoto和Ohta采用二叉树结构表示电子现金和利用切割-选择技术的可分电子现金方案；1992年，Brands最早利用限制性盲签名提了一个离线的、完全匿名的电子现金方案，该方案是迄今为止效率最高的方案之一；。

电子货币,基于RSA盲签名的在线电子货币系统,设这组参数用于面值为1元的电子钱币存取,电子货币,电子货币,独立性,不可伪造性和不可重用性,离线性,可转移性,可分性,不可跟踪性和不可联系性,42,本章主要内容,密码协议概念比特承诺公平抛币协议安全多方计算电子货币电子选举匿名协议,电子选举,电子投票也包含三个步骤：

（1）注册（Registration）：

投票人向选委会CTF（CentralTabulatingFacility）或身份登记机构CLA（CentralLegimizationAgency）提供其合法的身份信息，CTF或CLA对投票人的身份合法性进行认证；

（2）投票（Casting）：

投票人投出其选票；（3）计票（Tallying）：

CTF对合法选票进行统计，公布计票结果；,电子选举,一般来说，一次公正的投票选举，应满足以下安全特性：

合法性：

只有合格选举人才能参加投票；惟一性：

每个投票人只能投票一次；机密性：

每个投票人的投票对他人是保密的；验证性：

每个投票人都能检验本人的投票是否被统计；完整性：

任何人不能修改他人的投票；不可追踪性：

投票人的投票内容提交到选举委员会后，选举委员会无法由所投的票追踪到投票人。

基于盲签名的电子选举协议,投票者产生10个消息集，每个集合中包含每一种可能的投票结果。

每条消息包含一个随机产生的识别号。

投票者盲化所有消息，并发送给CTF。

CTF检查数据库以保证投票者不曾以他的签名提交过盲化选票。

打开9个消息集检查它们是否正确，并对另1个消息集中的每一个消息签名，再送还投票者，并在数据库中记录投票者名字。

投票者去盲，并选择其中一张选票，用CTF公钥加密。

投票者投出选票。

CTF解密选票，检查签名，检查并记录识别号。

统计选票并公布结果。

基于盲签名的电子选举协议,分析：

制10个消息集选择9个检查：

分割选择协议防止投票者作弊CTF公布选票的识别号清单投票者可以确认自己的选票被统计存在的问题：

CTF可以制造假选票如果投票者发现CTF修改了他的选票，他无法证明,基于同态加密的电子选举,加法同态加密同态：

Enc（x）+Enc（y）=Enc（x+y）保密：

Enc（0）与Enc

（1）不可区分实例：

Paillier密码系统pk:

n=pqsk：

d=（p-1,q-1）,u=1/dmodn;Enc（x）:

c=（1+n）xrnmodn2,r（Z/nZ）*Dec（d;c）:

L（cdmodn2）*umodn,L（x）=（x-1）/n,基于同态加密的电子选举,电子选举选举人i对候选人j投票：

选他投出（i，j，Eij=Enc

（1））不选他投出（i，j，Eij=Enc（0））计票人按候选人收集选票并相加求和：

（j，Ej=E1j+E2j+Emj），（设有m个选举人）唱票人解密合成后的密文，宣布每个候选人的得票数:

第j个候选人的得票数=Dec（Ej）假设：

投票人诚实的，只会投0或者1,49,本章主要内容,密码协议概念比特承诺公平抛币协议安全多方计算电子货币电子选举匿名协议,匿名协议,匿名性概念：

保密性的推广，对信息路径的保密。

匿名性需求：

Authoranonymity:

分享资源的作者的身份不能够被有心人知道，即身份和分享的资源不能够有关连性。

Publisheranonymity:

Publisher的身份不能够和提供的资源有所关连性。

Reader（Requester）anonymity:

同个网络中的资源任何人都可以读取，但读取者的信息不能够被公开或得知。

Serveranonymity:

服务器的信息不能够和提供的资源有任何的关连性。

Documentanonymity:

服务器也不知道储存的内容。

Queryanonymity:

服务器知道请求资源的ID，但是不能够有第三者去确认此ID的正确性。

匿名路由,实现匿名路由的方法匿名代理：

通过匿名代理处理消息，但匿名代理的安全性以及本身是系统瓶颈，易受攻击。

混合中继网mix-net：

通过一组“混合中继”mixrelays结点连接到服务器，核心中继结点是安全隐患（Tor）随机中继：

Freenet，Tarzan（理论上完备细致，但实现极其困难）等。

匿名消息广播,DiningCryptographers（DC）协议：

三个密码员正在他们最喜欢的餐馆准备进餐。

侍者告诉他们这是餐馆特别安排的，是匿名支付账单：

可能是其中某一个密码员正在付账，也可能是由NSA买单。

这三个密码员都尊重彼此匿名付账的权利，但他们希望知道是不是NSA在付账。

代表团体广播消息，但其他人无法得知具体是谁在发布。

匿名消息广播,Chuam的DC解决方案每个密码员和他右边的密码员之间抛掷一个硬币，且结果只有他们两个人能看到。

每个人都大声说他看到的两枚硬币结果是否一致。

若某个密码员付账，则他说相反的结果。

若说“不同”的人有奇数个，则说明某个密码员在付账；若是偶数个，则说明是NSA埋单。

匿名消息广播,基于Chuam的DC协议思想的匿名消息广播用户把他们自己排成一个逻辑圆圈在一定的时间间隔内，相邻的每对用户在他们之间抛掷硬币。

（要使用公平的硬币抛掷协议，防止窃听者。

）在每次抛掷后，每个用户说“相同”或“不同”若Alice希望广播一条二进制消息，则她可以依次对“1”说相反结果，对“0”说正确结果。

若Alice发现协议的所有结果都和她要发送的消息不匹配，则说明有另一个人也在同时发送消息。

她应暂停，等到无人发送后，再等待一个随机延时再重发。

匿名密钥分配,不希望KDC知道它所分配的密钥1）KDC产生密钥序列，逐位用公钥加密并公开2）Alice随机选取一段密钥，用自己的公钥加密3）Alice等待一段时间后（使KDC无法得知她的选择），将加密的密钥送给KDC4）KDC用私钥解密，并将结果送给Alice5）Alice用自己的私钥解密，得到密钥,智力扑克,双方协议：

允许Alice和Bob在网络上玩扑克1.Alice和Bob产生自己的密钥2.Alice产生52个消息M1,M2,M52，加密后传给Bob3.Bob随机选取5张，用他的密钥加密后回送给Alice4.Alice解密后，再送给Bob5.Bob解密后得到自己的5张牌6.Bob从剩下的消息中随机选取5张，回送给Alice7.Alice解密后得到自己的5张牌8.游戏结束后，双方出示自己的牌和密钥来确认没有欺诈重复37步，可以继续发牌,智力扑克,三方协议：

1.Alice，Bob和Carol产生各自的密钥2.Alice产生52个消息，加密后传给Bob：

EA（Mn）3.Bob随机选择5张牌，加密后送给Alice：

EB（EA（Mn）4.Bob将剩下47张牌送给Carol：

EA（M）5.Carol随机选择5张牌，加密后送给Alice：

EC（EA（Mn）6.Alice解密回送的消息，并返回Bob（EB（Mn）及Carol（EC（Mn）7.Bob和Carol各自解密，获得自己的牌8.Carol从剩下的牌中随机取5张，送给Alice：

EA（Mn）9.Alice解密，获得自己的牌10.游戏结束后，各方出示自己的牌和密钥，确认没有欺诈,智力扑克,抗联合欺诈的三方智力扑克1.Alice、Bob和Carol产生各自的私钥2.Alice产生52个消息，加密后传给Bob3.Bob加密后传给Carol4.Carol加密后传给Alice5.三个人依次执行以下步骤：

a）自己随机选取5张牌，交给另两人解密，回传后再自己解密，得到自己的牌b）把剩下的牌传给下一个人6.游戏的最后各方公布自己的牌和密钥，确认没有欺诈,密码协议的安全性质,认证性确认身份，获取信任保密性保护协议消息不泄露给非授权人完整性保护协议消息不被非法篡改、删除或替代非否认性收集参与协议人的证据，使其不可否认,