基本的安全协议课件

1基本的安全协议1基本的安全协议2秘密分割设想你已发明了一种新的调味料，你只能告诉最信赖的雇员各种成分准确的调合，但如果他们中的一个背叛到对手方时怎么办呢？这种情况就要求秘密分割。（1）Trent产生一随机比特串R。（2）Trent用R异或M得到S：M⊕R=S（3）Trent把R给Alice，将S给Bob。（4）重构消息：Alice和Bob将他们的消息异或就可得到此消息R⊕S=M.如何在多个人中分割一消息？秘密分割的缺点是什么?2秘密分割设想你已发明了一种新的调味料，你只能告诉最信赖的33

秘密共享是一种将秘密分割存储的密码技术，目的是阻止秘密过于集中，以达到分散风险和容忍入侵的目的，是信息安全和数据保密中的重要手段。背景

重要的秘密不能都由一个人管理，势必造成权力过于集中比起相信一个人更容易相信多数人机密性与强健性秘密共享

把一个秘密消息分成n块，分割给m个参与者每个参与者只拥有其中的一块

只有所有消息块组合在一起才能恢复秘密

每一块对其拥有者来说是没用的.秘密共享33秘密共享秘密共享4s1s2s3sn1…shares…23n-1nsn-1…parties…12…KeyHoles…t-1t秘密共享4s1s2s3sn1…shares…23n-1nsn-15秘密共享

有缺陷的秘密共享方案简单秘密共享方案(秘密分割)

秘密s=b1

b2…bn-1bn

1)选择随机数b1,….,bn-1

2)计算

bn=b1

b2…bn-1spasswordpasswordFlawedN个消息块组合在一起才能恢复秘密

s

(不健全)5秘密共享有缺陷的秘密共享方案passwordpasswo6门限秘密共享

方案

假设

Coca-Cola公司的董事会想保护可乐的配方.该公司总裁应该能够在需要时拿到配方，但在紧急的情况下，12位董事会成员中的任意3位就可以揭开配方。

这可以通过一个秘密共享方案实现t=3、

n=15,其中3股给总统，1股给其他每个董事会成员

安全问题机密性:抵抗任何不当行为强健性：对任何可能出现的错误的可靠性

6门限秘密共享方案7(t,n)

秘密共享(t<n)秘密K被拆分为n个份额的共享秘密利用任意t（2≤t≤n）个或更多个共享份额就可以恢复秘密K任何m–1或更少的共享份额是不能得到关于秘密SK的任何有用信息强健性：暴露一个份额或多到m–1个份额都不会危及密钥，且少于m–1个用户不可能共谋得到密钥，同时若一个份额被丢失或损坏，还可恢复密钥

Shamir秘密共享,Blakley

秘密共享根据t和n的选择，权衡安全性和可靠性。高

t，提供高安全性，低可靠性低t，提供低安全性，高可靠性门限秘密共享7(t,n)秘密共享(t<n)门限秘密共享8Shamir秘密共享

(t,n)秘密共享秘密信息

K

把一个信息（秘密地秘方，发射代码等）分成n部分(P1,…,Pn)，每部分叫做它的“影子”或共享使用

t-1次任意系数的随机多项式Step1.构造多项式：交易商选择了一个共享秘密,K

(<p:随机素数)为常数项，

F(x)=K+a1x+a2x2+…+ak-1xt-1modp为t-1

次任意系数的随机多项式。Step2.秘密分割：分配

F(i)(i=1,…,n)

安全共享

Pi。Step3.秘密恢复：当

t

共享

=(K1,K2,…,Kt)其中t是给定的,使用拉格朗日差值多项式方案恢复K。

8Shamir秘密共享(t,n)秘密共享9例如：(3,5)秘密共享

K=11,p=17构造

2次随机多项式

F(x)=K+a1x+a2x2modpa1=8,a2=7F(x)=11+8x+7x2mod17秘密分割

K1=F(1)=712+81

+119mod17K2=F(2)=722+82

+114mod17K3=F(3)=732+83

+1113mod17K4=F(4)=742+84

+112mod17K5=F(5)=752+85

+115mod17（K1,K2,K3,K4,K5

）=(P1,…,P5)Shamir秘密共享9例如：Shamir秘密共享10

解方程恢复秘密：

由

K2,K3,K4,我们可以得到

K=11

a

22+b2

+K

4mod17 a

32+b3

+K

13mod17 a

42+b4

+K

2mod17

解

3个变量的多项式方程

获得

K.利用拉格朗日插值

For=(K1,K2,K3)Shamir秘密共享10解方程恢复秘密：For=(K1,K2,K11可验证的秘密共享

如何知道你共享的秘密是正确的

?Feldman的可验证秘密共享

(VSS)承诺系数验证其共享份额的正确性

f(i)11可验证的秘密共享如何知道你共享的秘密是正确的?承诺系12在同一平面的两平行线相交于同一点

.不在同一平面三非平行线在空间相交于同一点

.更一般地，任何n维超平面相交于一个特定的点

秘密可能被编码作为任何一个坐标交点。

Blakley秘密共享12在同一平面的两平行线相交于同一点.Blakley秘密共13门限密码阈值加密方案

一个消息是使用公钥加密为了解密密文，需要超过阈值的共享份额合作来解密

门限签名方案

为了签名，需要超过阈值的共享份额合作来签名

.签字可以使用公钥验证公布公钥，但相应的私钥在多方共享

.13门限密码阈值加密方案公布公钥，但相应的私钥在多方共享14时间戳服务在很多情况中，人们需要证明某个文件在某个时期存在。版权或专利争端即是谁有产生争议的工作的最早的副本，谁就将赢得官司。对于纸上的文件，公证人可以对文件签名，律师可以保护副本。如果产生了争端，公证人或律师可以证明某封信产生于某个时间。在数字世界中，事情要复杂得多。没有办法检查窜改签名的数字文件。他们可以无止境地复制和修改而无人发现。14时间戳服务在很多情况中，人们需要证明某个文件在某个时期存15时间戳服务仲裁解决方法Alice将文件的副本传送给TrentTrent将他收到文件的日期和时间记录下来，并妥善保存文件的副本存在问题没有保密性数据库本身将是巨大的存在潜在错误。传送错误或Trent的中央计算机中某些地方的电磁炸弹引爆可能有些运行时间标记业务的人并不像Trent那样诚实15时间戳服务仲裁解决方法16时间戳服务改进的仲裁解决方法Alice产生文件的单向Hash值。Alice将Hash值传送给Trent。Trent将接收到Hash值的日期和时间附在Hash值后，并对结果进行数字签名。Trent将签名的散列和时间标记送回给Alice。存在问题可能有些运行时间标记业务的人并不像Trent那样诚实16时间戳服务改进的仲裁解决方法17时间戳服务链接协议:将Alice的时间标记同以前由Trent产生的时间标记链接起来。由于Trent预先不知道他所接收的不同时间标记的顺序，Alice的时间标记一定发生在前一个时间标记之后。并且由于后面来的请求是与Alice的时间标记链接，那么她必须出现在前面。Alice的请求正好夹在两个时间之间。如果有人对Alice的时间标记提出疑问，她只需要和她的前后文件的发起者In-1和In+1接触就行了17时间戳服务链接协议:将Alice的时间标记同以前由Tre18时间戳服务分布式协议:人死后，时间标记就会丢失。在时间标记和质询之间很多事情都可能发生，以至Alice不可能得到In-1的时间标记的副本，这个问题可以通过把前面10个人的时间标记嵌入Alice的时间标记中得到缓解，并且将后面10个人的标识都发给Alice。这样Alice就会有更大的机会找到那些仍有他们的时间标记的人。18时间戳服务分布式协议:人死后，时间标记就会丢失。在时间标阈下信道阈下信道是指在基于公钥密码技术的数字签名、认证等应用密码体制的输出密码数据中建立起来的一种隐蔽信道，除指定的接收者外，任何其他人均不知道密码数据中是否有阈下消息存在。19阈下信道阈下信道是指在基于公钥密码技术的数字签名、认证等应用20阈下信道假设Alice和Bob被捕入狱。他将去男牢房，而她则进女牢房。看守Walter愿意让Alice和Bob交换消息，但他不允许他们加密。Walter认为他们可能会商讨一个逃跑计划，因此，他想能够阅读他们说的每个细节。Alice和Bob建立一个阈下信道，即完全在Walter视野内的建立的一个秘密通信信道。通过交换完全无害的签名的消息，他们可以来回传送秘密信息，并骗过Walter，即使Walter正在监视所有的通信。20阈下信道假设Alice和Bob被捕入狱。他将去男牢房，而21阈下信道简易的阈下信道（缺点是无密钥）可以是句子中单词的数目。句子中奇数个单词对应“1”，而偶数个单词对应“0”。可以是一幅画。如一棵苹果树，苹果的个数代表一定的约定GustavusSimmons发明了传统数字签名算法中阈下信道的概念。Walter看到来回传递的签名的无害消息，但他完全看不到通过阈下信道传递的信息。21阈下信道简易的阈下信道（缺点是无密钥）22使用阈下信道的基本过程（1）Alice产生一个无害消息，最好随机；（2）用与Bob共享的秘密密钥，Alice对这个无害信息这样签名，她在签名中隐藏她的阈下信息；（3）Alice通过Walter发送签名消息给Bob；（4）Walter读这份无害的消息并检查签名，没发现什么问题，他将这份签了名的消息传递给Bob；（5）Bob检查这份无害消息的签名，确认消息来自于Alice；（6）Bob忽略无害的消息，而用他与Alice共享的秘密密钥，提取阈下消息。22使用阈下信道的基本过程（1）Alice产生一个无害消息，23阈下信道的用途阈下信道的最显见的应用是在间谍网中。用一个阈下信道，Alice可以在受到威胁时安全地对文件签名。她可以在签名文件时嵌入阈下消息，说“我被胁迫”。别的应用则更为微妙，公司可以签名文件，嵌入阈下信息，允许它们在文档整个文档有效期内被跟踪。政府可以“标记”数字货币。恶意的签名程序可能泄露其签名中的秘密信息。其可能性是无穷的。23阈下信道的用途阈下信道的最显见的应用是在间谍网中。24EIGamal签名方案的阈下信道公钥：p:素数，

g<p（p,g可由一组用户共享）

y=gx(modp)私钥：x<p签名：k:随机选取，与p-1互素，a（签名）=gkmodp，b（签名）满足

M=(xa+kb)mod(p-1)(即有：b=(M-xa)k-1mod(p-1))验证：如果yaab(modp)=gM(modp)，则签名有效。24EIGamal签名方案的阈下信道公钥：p:素数，g<p25控制单向函数的输出比特搜索选择适当的k，使得a=gkmodp中的某些位为阈下信息。EIGamal签名方案的阈下信道25控制单向函数的输出比特EIGamal签名方案的阈下信道26RSA数字签名的阈下信道签名者取两个随机大素数p和q（保密），计算公开的模数r=pq(公开)，计算秘密的欧拉函数(r)=（p-1）(q-1)（保密）。随机选取整数e，满足gcd(e,(r))=1(公开e，验证密钥)计算d，满足de≡1(mod(r))(签名密钥)签名：y=H(x)d(modr),把x||y发送给验证者验证：检查下式是否成立yd=H(x)(modr).选择x的不同表达方式，使得H(x)中的某些位为阈下信息26RSA数字签名的阈下信道签名者取两个随机大素数p和q（27RSA数字签名的阈下信道27RSA数字签名的阈下信道比特承诺比特承诺(BitCommitment，BC)是密码学中的重要基础协议，其概念最早由1995年图灵奖得主Blum提出。可用于构建零知识证明、可验证秘密分享、硬币投掷等协议，同时和茫然传送一起构成安全双方计算的基础，是信息安全领域研究的热点。28比特承诺比特承诺(BitCommitment，BC)是密码29比特承诺Alice，这位令人惊异的魔术天才，正表演关于人类意念的神秘技巧。Alice将在Bob选牌之前猜中Bob将选的牌！Alice在一张纸上写出她的预测。Alice很神秘地将那张纸片装入信封中并封上。Alice将封好的信封随机地递给一观众。“取一张牌，Bob，任选一张”。他看了看牌而后将之出示给Alice和观众。是方块7。现在Alice从观众那里取回信封，并撕开它。在Bob选牌之先写的预测，也是：方块7！全场欢呼！

29比特承诺Alice，这位令人惊异的魔术天才，正表演关于30比特承诺这个魔术的要点在于，Alice在戏法的最后交换了信封。然而，密码协议能够提供防止这种花招的方法。承诺方案:Alice想对Bob承诺一个预测（即1bit或bit序列），但直到某个时间以后才揭示她的预测。而另一方面，Bob想确信在Alice承诺了她的预测后，她没有改变她的想法。

30比特承诺这个魔术的要点在于，Alice在戏法的最后交换31基本思想 承诺者Alice向接收者Bob承诺一个消息，承诺过程要求，Alice向Bob承诺时，Bob不可能获得关于被承诺消息的任何信息；经过一段时间后，Alice能够向Bob证实她所承诺的消息，但是Alice无法欺骗Bob。

.

协议Alice把消息m放在一个箱子里并锁住（只有Alice有钥匙可以打开箱子）送给Bob；当Alice决定向Bob证实消息时，Alice会把消息m及钥匙给Bob；Bob能够打开箱子并验证箱子里的消息与Alice出示的消息相同，并且Bob确信箱子里的消息在他的保管期间没有被篡改。

比特承诺31基本思想比特承诺32比特承诺方案具有两个重要性质隐蔽性:即接收者不能通过接收的箱子来确定承诺值m约束性:发送者不能改变箱子中的承诺值m

构造比特承诺使用单向函数:哈希函数,公钥加密比特承诺32比特承诺方案具有两个重要性质比特承诺33比特承诺Alice承诺b（使用对称密码算法）（1）Bob产生一个随机比特串R，并把它发送给Alice。（2）Alice生成一个由她想承诺的比特b组成的消息（b实际上可能是几个比特），以及Bob的随机串。她用某个随机密钥K对它加密，并将结果EK（R，b）送回给Bob。Alice揭示b当到了Alice揭示她的比特的时候，协议继续：（1）Alice发送密钥给Bob；（2）Bob解密消息以揭示比特。他检测他的随机串以证实比特的有效性。33比特承诺Alice承诺b（使用对称密码算法）34比特承诺Alice承诺b（使用单向函数的比特承诺）（1）Alice产生两个随机比特串，R1和R2。（2）Alice产生消息，该消息由她的随机串和她希望承诺的比特组成。（R1，R2，b）。（3）Alice计算消息的单向函数值，将结果以及其中一个随机串发送给Bob。H（R1，R2，b），R1。当到了Alice揭示她的比特的时候，协议继续：（1）Alice将原消息发给Bob。（R1，R2，b）；（2）Bob计算消息的单向函数值，并将该值及R1与原先第（3）步收到的值及随机串比较。如匹配，则比特有效。34比特承诺Alice承诺b（使用单向函数的比特承诺）35比特承诺Alice承诺（使用伪随机序列发生器的比特承诺）（1）Bob产生随机比特串RB，并送给Alice。（2）Alice为伪随机比特发生器生成一个随机种子。然后，对Bob随机比特串中的每一比特，她回送Bob下面两个中的一个：(a)如果Bob比特为0，发生器的输出；(b)如果Bob的比特为1，发生器输出与她的承诺比特的异或。当到了Alice揭示她的比特的时候，协议继续：（1）Alice将随机种子送给Bob；（2）Bob确认Alice的行动是合理的。35比特承诺Alice承诺（使用伪随机序列发生器的比特承诺36抛硬币游戏

假设

Alice和Bob要离婚，讨论谁得到什么...并且俩人谁也不想见谁...在谁拥有车这个问题上有争议。最后他们决定抛硬币…

问题:

如果他们相互不信任，又如何能在电话里抛硬币决定？

Head,AliceTail,Bob36抛硬币游戏假设Head,AliceTail,37公平的硬币抛掷首先，Bob确定一个比特，将它写在纸上，并装入信封中。Alice公布她选的比特。Alice和Bob从信封中取出Bob的比特并计算随机比特。只要至少一方诚实地执行协议，这个比特的确是真正随机的。应用：掷币协议能让Alice和Bob产生随机会话密钥，以便双方都不能影响密钥生成的结果。37公平的硬币抛掷首先，Bob确定一个比特，将它写在纸上，并38公平的硬币抛掷利用比特承诺协议（1）Alice利用比特承诺方案，对一个随机比特承诺。（2）Bob试图去猜测这个比特。（3）Alice出示这个比特给Bob，如果Bob正确地猜出这个比特，他就赢得了这次抛币。38公平的硬币抛掷利用比特承诺协议39公平的硬币抛掷采用单向函数的抛币协议（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）。39公平的硬币抛掷采用单向函数的抛币协议40公平的硬币抛掷公开密钥密码抛币协议要求加密算法满足交换律(如RSA)。(1)Alice和Bob都产生一个公开/私钥密钥对。(2)Alice产生两个消息，其一指示正面，另一个指示反面。这些消息中包含有某个唯一的随机串，以便以后能够验证其在协议中的真实性。Alice用她的公开密钥将两个消息加密，并以随机的顺序把他们发给Bob(3)Bob随机地选择一个。他用他的公开密钥加密并回送给Alice(4)Alice用她的私钥解密并回送给Bob，即(5)Bob用他的私钥解密消息，得到抛币结果。他将解密后的消息送给Alice。(6)Alice读抛币结果，并验证随机串的正确性。(7)Alice和Bob出示他们的密钥对以便双方能验证对方没有欺诈40公平的硬币抛掷公开密钥密码抛币协议41公平的硬币抛掷掷币入井协议注意到在所有这些协议中，Alice和Bob不能同时知道掷币的结果。每个协议有一个点，在这个点上其中一方知道掷币结果，但不能改变它。然而，这一方能推迟向另一方泄露结果。这被称作掷币入井协议。设想一口井，Alice在井的旁边，而Bob远离这口井。Bob将币扔进井里去，币停留在井中，现在Alice能够看到井中的结果，但她不能到井底去改变它。Bob不能看到结果，直到Alice让他走到足够近时，才能看到结果。这个协议的实际应用是会话密钥生成。掷币协议能让Alice和Bob产生随机会话密钥，以便双方都不能影响密钥生成的结果41公平的硬币抛掷掷币入井协议42智力扑克Alice与Bob想通过网络玩牌Alice与Bob互不信任他们如何公平地发牌?42智力扑克Alice与Bob想通过网络玩牌43智力扑克(1)Alice生成52个消息M1，M2，，M52,加密后送给Bob。(2)Bob随机选取5张牌，用他的公开密钥加密，然后回送给Alice。(3)Alice解密消息并回送给Bob。(4)Bob解密以确定他的一手牌。然后，Bob随机地选择第(1)步剩下的47个消息中的另外5个消息，并发给Alice。(5)Alice解密它们，变成她的一手牌。在游戏结束时，Alice和Bob双方出示他们的牌和密钥对使得任意一方确信另一方没有作弊。已经证明，如果使用RSA算法，那么这些扑克协议会泄漏少量的信息(可标记牌)43智力扑克(1)Alice生成52个消息M1，M2，44智力扑克AB5255544智力扑克AB5255545三方智力扑克(1)Alice生成52个消息M1，M2，，M52,加密后送给Bob。(2)Bob随机选取5张牌，用他的公开密钥加密，然后回送给Alice,Bob将余下的47张牌EA(Mn)送给Carol。(3)Carol随机选取5张牌，用她的公开密钥加密，然后回送给Alice(4)Alice解密消息并回送给Bob和Carol。(5)Bob和Carol解密以确定他的一手牌。然后，Carol随机地选择剩下的42个消息中的另外5个消息，并发给Alice。(6)Alice解密它们，变成她的一手牌。在游戏结束时，Alice,Bob和Carol双方出示他们的牌和密钥对使得任意一方确信另一方没有作弊。45三方智力扑克(1)Alice生成52个消息M1，M2，46三方智力扑克ABC52547555546三方智力扑克ABC525475555不经意传输协议不经意传输协议，是一种可保护隐私的双方通信协议，能使通信双方以一种选择模糊化的方式传送消息。密码学的一个基本协议，他使得服务的接收方以不经意的方式得到服务发送方输入的某些消息，这样就可以保护接受者的隐私不被发送者所知道。应用：安全多方计算，电话投币协议，电子合同的钱数，秘密信息检索等47不经意传输协议不经意传输协议，是一种可保护隐私的双方通信协议481-out-2不经意传输Rabin的OT协议是一个双方协议，发送方以1/2的概率传输一个比特的秘密s给B。A选择Blum整数n=pq，并随机的选择tZn*，将(n，(-1)st2)发送给BB选择xZn*，计算a=x2(modn)，并将a发送给AA求出a的四个平方根，并随机的选择一个记为b，发送给BB收到b后，检查b=x或-x(modn)是否成立。若成立，B什么也得不到；否则，B利用可以分解Blum整数n，并计算s481-out-2不经意传输Rabin的OT协议是一个双方协49不经意传输Alice将发送给Bob两份消息中的一份。Bob将收到其中一条消息，并且Alice不知道是哪一份。（1）Alice产生两个公开密钥/私钥密钥对。她把两个公开密钥发送给Bob。（2）Bob选择一个对称算法（例如DES）密钥。他选择Alice的一个公开密钥并用它加密他的DES密钥。他把这个加了密的密钥发送给Alice，且不告诉她他用的是她的哪一个公开密钥加密的DES密钥。

49不经意传输Alice将发送给Bob两份消息中的一份。Bo50不经意传输（3）Alice解密Bob的密钥两次，每次用一个她的私钥来解密Bob的密钥。在一种情况下，她使用了正确的密钥并成功地解密Bob的DES密钥。在另一种情况下，她使用了错误的密钥，只是产生了一堆毫无意义，而看上去又象一个随机DES密钥的比特。由于她不知道正确明文，故她不知道哪个是正确的。50不经意传输51不经意传输（4）Alice加密她的两份消息，每一份用一个不同的在上一步中产生的DES密钥（一个真的和一个毫无意义的），并把两份消息都发送给Bob。（5）Bob收到一份用正确DES密钥加密的消息及一份用无意义DES密钥加密的消息。当Bob用他的DES密钥解密每一份消息时，他能读其中之一，另一份在他看起来是毫无意义的。51不经意传输（4）Alice加密她的两份消息，每一份用一个52不经意传输Bob现在有了Alice两份消息中的一份，而Alice不知道他能读懂哪一份。很遗憾，如果协议到此为止，Alice有可能进行欺骗。另一个步骤必不可少。(6)在协议完成，并且知道了两种可能传输的结果后，Alice必须把她的私钥给Bob，以便他能验证她没有进行欺骗。毕竟，她可以用第（4）步中的两个密钥加密同一消息。 当然，这时Bob可以弄清楚第二份消息。52不经意传输Bob现在有了Alice两份消息中的一每一次的加油，每一次的努力都是为了下一次更好的自己。11月-2211月-22Saturday,November5,2022天生我材必有用，千金散尽还复来。02:27:1002:27:1002:2711/5/20222:27:10AM安全象只弓，不拉它就松，要想保安全，常把弓弦绷。11月-2202:27:1002:27Nov-2205-Nov-22得道多助失道寡助，掌控人心方位上。02:27:1002:27:1002:27Saturday,November5,2022安全在于心细，事故出在麻痹。11月-2211月-2202:27:1002:27:10November5,2022加强自身建设，增强个人的休养。2022年11月5日2:27上午11月-2211月-22扩展市场，开发未来，实现现在。05十一月20222:27:10上午02:27:1011月-22做专业的企业，做专业的事情，让自己专业起来。十一月222:27上午11月-2202:27November5,2022时间是人类发展的空间。2022/11/52:27:1002:27:1005November2022科学，你是国力的灵魂；同时又是社会发展的标志。2:27:10上午2:27上午02:27:1011月-22每天都是美好的一天，新的一天开启。11月-2211月-2202:2702:27:1002:27:10Nov-22人生不是自发的自我发展，而是一长串机缘。事件和决定，这些机缘、事件和决定在它们实现的当时是取决于我们的意志的。2022/11/52:27:10Saturday,November5,2022感情上的亲密，发展友谊；钱财上的亲密，破坏友谊。11月-222022/11/52:27:1011月-22谢谢大家！每一次的加油，每一次的努力都是为了下一次更好的自己。11月-54基本的安全协议1基本的安全协议55秘密分割设想你已发明了一种新的调味料，你只能告诉最信赖的雇员各种成分准确的调合，但如果他们中的一个背叛到对手方时怎么办呢？这种情况就要求秘密分割。（1）Trent产生一随机比特串R。（2）Trent用R异或M得到S：M⊕R=S（3）Trent把R给Alice，将S给Bob。（4）重构消息：Alice和Bob将他们的消息异或就可得到此消息R⊕S=M.如何在多个人中分割一消息？秘密分割的缺点是什么?2秘密分割设想你已发明了一种新的调味料，你只能告诉最信赖的5656

秘密共享是一种将秘密分割存储的密码技术，目的是阻止秘密过于集中，以达到分散风险和容忍入侵的目的，是信息安全和数据保密中的重要手段。背景

重要的秘密不能都由一个人管理，势必造成权力过于集中比起相信一个人更容易相信多数人机密性与强健性秘密共享

把一个秘密消息分成n块，分割给m个参与者每个参与者只拥有其中的一块

只有所有消息块组合在一起才能恢复秘密

每一块对其拥有者来说是没用的.秘密共享33秘密共享秘密共享57s1s2s3sn1…shares…23n-1nsn-1…parties…12…KeyHoles…t-1t秘密共享4s1s2s3sn1…shares…23n-1nsn-158秘密共享

有缺陷的秘密共享方案简单秘密共享方案(秘密分割)

秘密s=b1

b2…bn-1bn

1)选择随机数b1,….,bn-1

2)计算

bn=b1

b2…bn-1spasswordpasswordFlawedN个消息块组合在一起才能恢复秘密

s

(不健全)5秘密共享有缺陷的秘密共享方案passwordpasswo59门限秘密共享

方案

假设

Coca-Cola公司的董事会想保护可乐的配方.该公司总裁应该能够在需要时拿到配方，但在紧急的情况下，12位董事会成员中的任意3位就可以揭开配方。

这可以通过一个秘密共享方案实现t=3、

n=15,其中3股给总统，1股给其他每个董事会成员

安全问题机密性:抵抗任何不当行为强健性：对任何可能出现的错误的可靠性

6门限秘密共享方案60(t,n)

秘密共享(t<n)秘密K被拆分为n个份额的共享秘密利用任意t（2≤t≤n）个或更多个共享份额就可以恢复秘密K任何m–1或更少的共享份额是不能得到关于秘密SK的任何有用信息强健性：暴露一个份额或多到m–1个份额都不会危及密钥，且少于m–1个用户不可能共谋得到密钥，同时若一个份额被丢失或损坏，还可恢复密钥

Shamir秘密共享,Blakley

秘密共享根据t和n的选择，权衡安全性和可靠性。高

t，提供高安全性，低可靠性低t，提供低安全性，高可靠性门限秘密共享7(t,n)秘密共享(t<n)门限秘密共享61Shamir秘密共享

(t,n)秘密共享秘密信息

K

把一个信息（秘密地秘方，发射代码等）分成n部分(P1,…,Pn)，每部分叫做它的“影子”或共享使用

t-1次任意系数的随机多项式Step1.构造多项式：交易商选择了一个共享秘密,K

(<p:随机素数)为常数项，

F(x)=K+a1x+a2x2+…+ak-1xt-1modp为t-1

次任意系数的随机多项式。Step2.秘密分割：分配

F(i)(i=1,…,n)

安全共享

Pi。Step3.秘密恢复：当

t

共享

=(K1,K2,…,Kt)其中t是给定的,使用拉格朗日差值多项式方案恢复K。

8Shamir秘密共享(t,n)秘密共享62例如：(3,5)秘密共享

K=11,p=17构造

2次随机多项式

F(x)=K+a1x+a2x2modpa1=8,a2=7F(x)=11+8x+7x2mod17秘密分割

K1=F(1)=712+81

+119mod17K2=F(2)=722+82

+114mod17K3=F(3)=732+83

+1113mod17K4=F(4)=742+84

+112mod17K5=F(5)=752+85

+115mod17（K1,K2,K3,K4,K5

）=(P1,…,P5)Shamir秘密共享9例如：Shamir秘密共享63

解方程恢复秘密：

由

K2,K3,K4,我们可以得到

K=11

a

22+b2

+K

4mod17 a

32+b3

+K

13mod17 a

42+b4

+K

2mod17

解

3个变量的多项式方程

获得

K.利用拉格朗日插值

For=(K1,K2,K3)Shamir秘密共享10解方程恢复秘密：For=(K1,K2,K64可验证的秘密共享

如何知道你共享的秘密是正确的

?Feldman的可验证秘密共享

(VSS)承诺系数验证其共享份额的正确性

f(i)11可验证的秘密共享如何知道你共享的秘密是正确的?承诺系65在同一平面的两平行线相交于同一点

.不在同一平面三非平行线在空间相交于同一点

.更一般地，任何n维超平面相交于一个特定的点

秘密可能被编码作为任何一个坐标交点。

Blakley秘密共享12在同一平面的两平行线相交于同一点.Blakley秘密共66门限密码阈值加密方案

一个消息是使用公钥加密为了解密密文，需要超过阈值的共享份额合作来解密

门限签名方案

为了签名，需要超过阈值的共享份额合作来签名

.签字可以使用公钥验证公布公钥，但相应的私钥在多方共享

.13门限密码阈值加密方案公布公钥，但相应的私钥在多方共享67时间戳服务在很多情况中，人们需要证明某个文件在某个时期存在。版权或专利争端即是谁有产生争议的工作的最早的副本，谁就将赢得官司。对于纸上的文件，公证人可以对文件签名，律师可以保护副本。如果产生了争端，公证人或律师可以证明某封信产生于某个时间。在数字世界中，事情要复杂得多。没有办法检查窜改签名的数字文件。他们可以无止境地复制和修改而无人发现。14时间戳服务在很多情况中，人们需要证明某个文件在某个时期存68时间戳服务仲裁解决方法Alice将文件的副本传送给TrentTrent将他收到文件的日期和时间记录下来，并妥善保存文件的副本存在问题没有保密性数据库本身将是巨大的存在潜在错误。传送错误或Trent的中央计算机中某些地方的电磁炸弹引爆可能有些运行时间标记业务的人并不像Trent那样诚实15时间戳服务仲裁解决方法69时间戳服务改进的仲裁解决方法Alice产生文件的单向Hash值。Alice将Hash值传送给Trent。Trent将接收到Hash值的日期和时间附在Hash值后，并对结果进行数字签名。Trent将签名的散列和时间标记送回给Alice。存在问题可能有些运行时间标记业务的人并不像Trent那样诚实16时间戳服务改进的仲裁解决方法70时间戳服务链接协议:将Alice的时间标记同以前由Trent产生的时间标记链接起来。由于Trent预先不知道他所接收的不同时间标记的顺序，Alice的时间标记一定发生在前一个时间标记之后。并且由于后面来的请求是与Alice的时间标记链接，那么她必须出现在前面。Alice的请求正好夹在两个时间之间。如果有人对Alice的时间标记提出疑问，她只需要和她的前后文件的发起者In-1和In+1接触就行了17时间戳服务链接协议:将Alice的时间标记同以前由Tre71时间戳服务分布式协议:人死后，时间标记就会丢失。在时间标记和质询之间很多事情都可能发生，以至Alice不可能得到In-1的时间标记的副本，这个问题可以通过把前面10个人的时间标记嵌入Alice的时间标记中得到缓解，并且将后面10个人的标识都发给Alice。这样Alice就会有更大的机会找到那些仍有他们的时间标记的人。18时间戳服务分布式协议:人死后，时间标记就会丢失。在时间标阈下信道阈下信道是指在基于公钥密码技术的数字签名、认证等应用密码体制的输出密码数据中建立起来的一种隐蔽信道，除指定的接收者外，任何其他人均不知道密码数据中是否有阈下消息存在。72阈下信道阈下信道是指在基于公钥密码技术的数字签名、认证等应用73阈下信道假设Alice和Bob被捕入狱。他将去男牢房，而她则进女牢房。看守Walter愿意让Alice和Bob交换消息，但他不允许他们加密。Walter认为他们可能会商讨一个逃跑计划，因此，他想能够阅读他们说的每个细节。Alice和Bob建立一个阈下信道，即完全在Walter视野内的建立的一个秘密通信信道。通过交换完全无害的签名的消息，他们可以来回传送秘密信息，并骗过Walter，即使Walter正在监视所有的通信。20阈下信道假设Alice和Bob被捕入狱。他将去男牢房，而74阈下信道简易的阈下信道（缺点是无密钥）可以是句子中单词的数目。句子中奇数个单词对应“1”，而偶数个单词对应“0”。可以是一幅画。如一棵苹果树，苹果的个数代表一定的约定GustavusSimmons发明了传统数字签名算法中阈下信道的概念。Walter看到来回传递的签名的无害消息，但他完全看不到通过阈下信道传递的信息。21阈下信道简易的阈下信道（缺点是无密钥）75使用阈下信道的基本过程（1）Alice产生一个无害消息，最好随机；（2）用与Bob共享的秘密密钥，Alice对这个无害信息这样签名，她在签名中隐藏她的阈下信息；（3）Alice通过Walter发送签名消息给Bob；（4）Walter读这份无害的消息并检查签名，没发现什么问题，他将这份签了名的消息传递给Bob；（5）Bob检查这份无害消息的签名，确认消息来自于Alice；（6）Bob忽略无害的消息，而用他与Alice共享的秘密密钥，提取阈下消息。22使用阈下信道的基本过程（1）Alice产生一个无害消息，76阈下信道的用途阈下信道的最显见的应用是在间谍网中。用一个阈下信道，Alice可以在受到威胁时安全地对文件签名。她可以在签名文件时嵌入阈下消息，说“我被胁迫”。别的应用则更为微妙，公司可以签名文件，嵌入阈下信息，允许它们在文档整个文档有效期内被跟踪。政府可以“标记”数字货币。恶意的签名程序可能泄露其签名中的秘密信息。其可能性是无穷的。23阈下信道的用途阈下信道的最显见的应用是在间谍网中。77EIGamal签名方案的阈下信道公钥：p:素数，

g<p（p,g可由一组用户共享）

y=gx(modp)私钥：x<p签名：k:随机选取，与p-1互素，a（签名）=gkmodp，b（签名）满足

M=(xa+kb)mod(p-1)(即有：b=(M-xa)k-1mod(p-1))验证：如果yaab(modp)=gM(modp)，则签名有效。24EIGamal签名方案的阈下信道公钥：p:素数，g<p78控制单向函数的输出比特搜索选择适当的k，使得a=gkmodp中的某些位为阈下信息。EIGamal签名方案的阈下信道25控制单向函数的输出比特EIGamal签名方案的阈下信道79RSA数字签名的阈下信道签名者取两个随机大素数p和q（保密），计算公开的模数r=pq(公开)，计算秘密的欧拉函数(r)=（p-1）(q-1)（保密）。随机选取整数e，满足gcd(e,(r))=1(公开e，验证密钥)计算d，满足de≡1(mod(r))(签名密钥)签名：y=H(x)d(modr),把x||y发送给验证者验证：检查下式是否成立yd=H(x)(modr).选择x的不同表达方式，使得H(x)中的某些位为阈下信息26RSA数字签名的阈下信道签名者取两个随机大素数p和q（80RSA数字签名的阈下信道27RSA数字签名的阈下信道比特承诺比特承诺(BitCommitment，BC)是密码学中的重要基础协议，其概念最早由1995年图灵奖得主Blum提出。可用于构建零知识证明、可验证秘密分享、硬币投掷等协议，同时和茫然传送一起构成安全双方计算的基础，是信息安全领域研究的热点。81比特承诺比特承诺(BitCommitment，BC)是密码82比特承诺Alice，这位令人惊异的魔术天才，正表演关于人类意念的神秘技巧。Alice将在Bob选牌之前猜中Bob将选的牌！Alice在一张纸上写出她的预测。Alice很神秘地将那张纸片装入信封中并封上。Alice将封好的信封随机地递给一观众。“取一张牌，Bob，任选一张”。他看了看牌而后将之出示给Alice和观众。是方块7。现在Alice从观众那里取回信封，并撕开它。在Bob选牌之先写的预测，也是：方块7！全场欢呼！

29比特承诺Alice，这位令人惊异的魔术天才，正表演关于83比特承诺这个魔术的要点在于，Alice在戏法的最后交换了信封。然而，密码协议能够提供防止这种花招的方法。承诺方案:Alice想对Bob承诺一个预测（即1bit或bit序列），但直到某个时间以后才揭示她的预测。而另一方面，Bob想确信在Alice承诺了她的预测后，她没有改变她的想法。

30比特承诺这个魔术的要点在于，Alice在戏法的最后交换84基本思想 承诺者Alice向接收者Bob承诺一个消息，承诺过程要求，Alice向Bob承诺时，Bob不可能获得关于被承诺消息的任何信息；经过一段时间后，Alice能够向Bob证实她所承诺的消息，但是Alice无法欺骗Bob。

.

协议Alice把消息m放在一个箱子里并锁住（只有Alice有钥匙可以打开箱子）送给Bob；当Alice决定向Bob证实消息时，Alice会把消息m及钥匙给Bob；Bob能够打开箱子并验证箱子里的消息与Alice出示的消息相同，并且Bob确信箱子里的消息在他的保管期间没有被篡改。

比特承诺31基本思想比特承诺85比特承诺方案具有两个重要性质隐蔽性:即接收者不能通过接收的箱子来确定承诺值m约束性:发送者不能改变箱子中的承诺值m

构造比特承诺使用单向函数:哈希函数,公钥加密比特承诺32比特承诺方案具有两个重要性质比特承诺86比特承诺Alice承诺b（使用对称密码算法）（1）Bob产生一个随机比特串R，并把它发送给Alice。（2）Alice生成一个由她想承诺的比特b组成的消息（b实际上可能是几个比特），以及Bob的随机串。她用某个随机密钥K对它加密，并将结果EK（R，b）送回给Bob。Alice揭示b当到了Alice揭示她的比特的时候，协议继续：（1）Alice发送密钥给Bob；（2）Bob解密消息以揭示比特。他检测他的随机串以证实比特的有效性。33比特承诺Alice承诺b（使用对称密码算法）87比特承诺Alice承诺b（使用单向函数的比特承诺）（1）Alice产生两个随机比特串，R1和R2。（2）Alice产生消息，该消息由她的随机串和她希望承诺的比特组成。（R1，R2，b）。（3）Alice计算消息的单向函数值，将结果以及其中一个随机串发送给Bob。H（R1，R2，b），R1。当到了Alice揭示她的比特的时候，协议继续：（1）Alice将原消息发给Bob。（R1，R2，b）；（2）Bob计算消息的单向函数值，并将该值及R1与原先第（3）步收到的值及随机串比较。如匹配，则比特有效。34比特承诺Alice承诺b（使用单向函数的比特承诺）88比特承诺Alice承诺（使用伪随机序列发生器的比特承诺）（1）Bob产生随机比特串RB，并送给Alice。（2）Alice为伪随机比特发生器生成一个随机种子。然后，对Bob随机比特串中的每一比特，她回送Bob下面两个中的一个：(a)如果Bob比特为0，发生器的输出；(b)如果Bob的比特为1，发生器输出与她的承诺比特的异或。当到了Alice揭示她的比特的时候，协议继续：（1）Alice将随机种子送给Bob；（2）Bob确认Alice的行动是合理的。35比特承诺Alice承诺（使用伪随机序列发生器的比特承诺89抛硬币游戏

假设

Alice和Bob要离婚，讨论谁得到什么...并且俩人谁也不想见谁...在谁拥有车这个问题上有争议。最后他们决定抛硬币…

问题:

如果他们相互不信任，又如何能在电话里抛硬币决定？

Head,AliceTail,Bob36抛硬币游戏假设Head,AliceTail,90公平的硬币抛掷首先，Bob确定一个比特，将它写在纸上，并装入信封中。Alice公布她选的比特。Alice和Bob从信封中取出Bob的比特并计算随机比特。只要至少一方诚实地执行协议，这个比特的确是真正随机的。应用：掷币协议能让Alice和Bob产生随机会话密钥，以便双方都不能影响密钥生成的结果。37公平的硬币抛掷首先，Bob确定一个比特，将它写在纸上，并91公平的硬币抛掷利用比特承诺协议（1）Alice利用比特承诺方案，对一个随机比特承诺。（2）Bob试图去猜测这个比特。（3）Alice出示这个比特给Bob，如果Bob正确地猜出这个比特，他就赢得了这次抛币。38公平的硬币抛掷利用比特承诺协议92公平的硬币抛掷采用单向函数的抛币协议（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）。39公平的硬币抛掷采用单向函数的抛币协议93公平的硬币抛掷公开密钥密码抛币协议要求加密算法满足交换律(如RSA)。(1)Alice和Bob都产生一个公开/私钥密钥对。(2)Alice产生两个消息，其一指示正面，另一个指示反面。这些消息中包含有某个唯一的随机串，以便以后能够验证其在协议中的真实性。Alice用她的公开密钥将两个消息加密，并以随机的顺序把他们发给Bob(3)Bob随机地选择一个。他用他的公开密钥加密并回送给Alice(4)Alice用她的私钥解密并回送给Bob，即(5)Bob用他的私钥解密消息，得到抛币结果。他将解密后的消息送给Alice。(6)Alice读抛币结果，并验证随机串的正确性。(7)Alice和Bob出示他们的密钥对以便双方能验证对方没有欺诈40公平的硬币抛掷公开密钥密码抛币协议94公平的硬币抛掷掷币入井协议注意到在所有这些协议中，Alice和Bob不能同时知道掷币的结果。每个协议有一个点，在这个点上其中一方知道掷币结果，但不能改变它。然而，这一方能推迟向另一方泄露结果。这被称作掷币入井协议。设想一口井，Alice在井的旁边，而Bob远离这口井。Bob将币扔进井里去，币停留在井中，现在Alice能够看到井中的结果，但她不能到井底去改变它。Bob不能看到结果，直到Alice让他走到足够近时，才能看到结果。这个协议的实际应用是会话密钥生成。掷币协议能让Alice和Bob产生随机会话密钥，以便双方都不能影响密钥生成的结果41公平的硬币抛掷掷币入井协议95智力扑克Alice与Bob想通过网络玩牌Alice与Bob互不信任他们如何公平地发牌?42智力扑克Alice与Bob想通过网络玩牌96智力扑克(1)Alice生成52个消息M1，M2，，M52,加密后送给Bob。(2)Bob随机选取5张牌，用他的公开密钥加密，然后回送给Alice。(3)Alice解密消息并回送给Bob。(4)Bob解密以确定他的一手牌。然后，Bob随机地选择第(1)步剩下的47个消息中的另外5个消息，并发给Alice。(5)Alice解密它们，变成她的一手牌。在游戏结束时，Alice和Bob双方出示他们的牌和密钥对使得任意一方确信另一方没有作弊。已经证明，如果使用RSA算法，那么这些扑克协议会泄漏少量的信息(可标记牌)43智力扑克(1)Alice生成52个消息M1，M2，97智力扑克AB5255544智力扑克AB5255598三方智力扑克(1)Alice生成52个消息M1，M2，，M52,加密后送给Bob。(2)Bob随机选取5张牌，用他的公开密钥加密，然后回送给Alice,Bob将余下的47张牌EA(Mn)送给Carol。(3)Carol随机选取5张牌，用她的公开密钥加密，然后回送给Alice(