第二十二讲秘密享与游戏

第二十二讲 秘密分享与游戏 秘密分享方案是与密钥建立相关的多方协议。秘密分享的原始动机是：为了保证密码密钥不丢失，希望产生密钥备份，但是越多的密钥备份，密钥泄露的可能就越大；越少的密钥备份，密钥丢失的可能就越大。秘密分享方案就是用来提高密钥可靠性而不增加泄露风险的方法。现代密码学的一个主要成就在于高级安全协议的发展。这些协议可以让用户在网上解决现实世界中许多问题，进行各种游戏，也能执行各种有趣而复杂的分布任务。电话投币和扑克协议将在这一讲中做简要介绍。本讲提要q 秘密分享的应用 q 秘密分割q 门限方案q 电话投币协议q 电话扑克协议1 秘密分享的应用 1.1 秘密分割 假定你发明了一种烹饪食物方法。这一方法比目前已知的方法都好。对方法保密在市场竞争激烈的环境下十分重要。你可能仅会告诉最为信任的雇员具体方法，但雇员如果为竞争对手收买该怎么办？可能人人都可以按照这一方法烹饪食物。1.1 秘密分割(续)这就需要秘密分割。方法是将一个消息分割成碎片，每一个碎片没有任何意义，但是合在一起就可以重现消息。有了秘密分割技术烹饪方法可以作为消息，而每个雇员只能拿到一个碎片，仅当他们联合才能恢复出烹饪方法。如果任何雇员离职，他带走的仅是自己的一个碎片，这一信息本身并无用处。但是，这仍然存在问题：如果任意一个碎片丢失，则消息无法恢复。如果一个雇员有烹饪方法的一个碎片而他去为竞争对手工作并将其碎片带走，那么其他雇员就没有那么幸运了。离职雇员虽然不能产生烹饪方法，但他可以不在参与恢复烹饪方法。他的碎片与其它碎片一样对恢复消息至关重要。1.2 关于门限方案 你在为核导弹安装发射程序。你想确信一个疯子是不能启动发射，也不希望两个疯子就能启动发射。在你允许发射前，五个军官至少有三个是疯子。这是一个容易解决的问题。做一个机械发射控制器，给五个军官每个人一把钥匙，并且只有在至少三个军官的钥匙插入适合的槽中才允许他们起爆。我们甚至可以把问题变得更为复杂。也许将军和两个上校被授权发射导弹，但如果将军正在打高尔夫球，那么启动发射需要五名上校。制造一个发射控制器，该发射控制器需要5把钥匙。给将军3把，给每位上校1把。将军和任意两名上校，或者五名上校一起都可以发射导弹，然而，将军和一名上校，或四名上校就不能。一个称为门限方案(threshold scheme)的更复杂的秘密分享方案，可以在数学上做到这些甚至更多。起码，可以取任意消息(秘密配方，发射代码，洗衣价目表)并把它分成n部分，每个部分叫它的影子或分享，它们中的任何m部分能够用来重构消息。我们可以将烹饪方法分给Alice，Bob，Carol，和Dave，这样把他们中的任意三个影子放在一起就能重构消息。如果Carol正在渡假，那么Alice，Bob，和Dave可以考虑做这件事情；如果Bob被汽车撞了，那么Alice，Carol，和Dave可以考虑做这件事情。然而，如果Bob被汽车撞了并且Carol正在渡假，Alice和Dave 就不可能重构消息。2 秘密分割2.1 使用模加的二重控制。即可恢复出之和模设备，它们分别将他们的数值输入和。和分别交给实体和，并将数值个随机数一个可信第三方产生一下方案。使用如知道这个数字，则可以可信第三方以外除不希望任何单独个人但是由于操作的原因，例如，一个种子密钥备个整数，必须输入到设是某，这里，如果一个秘密数字SmBABAmSSSmSmmSS )(mod1 1)()(1 0 1112.1 使用模加的二重控制(续)需要两人共同触发。以看作二重控制的操作可。任何对秘密识在两个人之间做分割的知子，其将对秘密这是知识分割方案的例之间的一个随机数。到拥有的只是在的信息，这是由于两人道任何知不存在串谋，则没有人和如果可以相信SSmSBA)2(10 (1)评述.评述.2.2使用模加的一致同意控制恢复。秘密可以通过。得到，每人一个。实体到分别交给实体到。，个相互独立的随机数产生下：可信第三方。方法如参与才能恢复个用户，只有全部用户分割给以推广，将秘密二重控制方案很容易加)(mod)(mod 1 11 0 1 1111111mSSmSSSPPPSStimSStTStSitiitittttii2.2 使用模加的一致同意控制(续)次测试。比特的数据，则需要做如果每个实体得到一个次测试，然而，索都只需要做比特，每个实体穷举搜的秘密，如果两个实体各得到和的安全强度。例如，好比特相比，这将提供更份每份比特秘密为与分割一个全长度的。，个人的秘密应该是完在一个分割控制方案中比特长度。都是固定和代，其中使用的数值替操作都可以由异或操作的模本方案和二重控制方案562822562282 56 /)2(log(1)trtrtrmSSmi评评述述.3 门限方案的优势。信息论意义下密导出秘所知的攻击者更多的推提供比任何对分享一无能或更少分享的掌握都不备的门限方案是任何对。一个完能恢复出或更少分享的用户组不仅知道，但任何分享就可以恢复出或更多用户提交他们的满足下面条件：任何，而分享安全的分配给用户，并将，计算秘密分享可信方从原始的秘密是一种方法：一个门限方案，一个)(11 1 )()(StStStSPSniSSntntiiii1 1 定义定义而不访问秘密的本身。看到特定行为被触发，需要对于每个参与者而言只系统目标是分享控制，适合于备来计算秘密。这非常而是使用一个可信的设秘密，员直接访问他们恢复的一种方法是阻止组内成制机制。推出其他用户分享的控就需要一个阻止参与者性，反复使用而不降低安全如果需要一个门限方案门限方案的实例。，一个而一致同意控制方案是门限方案的实例，一个二重控制方案可以看作)2()(2)(2(1)tt评述.评述.3.1 Shamir的门限方案。上的随机多项式：这样可以定义一个在，个随机相互独立的系数选择。，并定义，选择一个素数个用户。并希望分给有一个秘密可信方建立。秘密分享就可以恢复个用户的组提交他们的结果：任何一个个用户。的分享给摘要：可信方分配秘密门限方案，的10110)(10 ,1(1.2)(max (1.1)0 .(1)(Shamir tjjjpjtxaxfZpaaatTSanSpTnSTStnSnt1 1 机机制制3.1 Shamir的门限方案(续)。这样秘密就是，的系数有多项式插值法，可以计算出所，通过，个不同的点们的分享提供了的分享。他或更多个用户提交他们任何恢复秘密。给用户的公开指标以及相应并且安全的传递分享，同的点个不或者任意，计算续门限方案，的SaftjaxfSiyxttPiSpiinnipifSTntjiiii (0)1 1 )(Lagrange)()(.(2)1)1 (1 )(mod)(1.3)()(Shamir 01 1 机制机制3.1 Shamir的门限方案(续)。，这里：共享的秘密可以表示为，由于。唯一确定，如下：插值公式可以由，则多项式，如果给定点而系数未知的多项式对于次数小于插值关于ijtjjijitiiiijtjjijtiiiixxxcycSSafxxxxyxfxftiyxxft11011 (0)(Lagrange)(1 )()(.Lagrange3.1 Shamir的门限方案(续)预先计算出这个常数。个用户的组，用户可以确定这意味着对于一个是一个不保密的常数，由于。秘密计算出个分享其掌握的任何一组用户可以通过解释tcSytii (2)(1).3.1 Shamir的门限方案(续)。，人分配如下一个对：个。因此，我们可以给每，这里，个人给出对为。我们可以。现在可以使用成多项式并形模和。随机选择数字选择一个素数。数字门限方案。假定秘密是，建立一个147)1039110787(8 28)9734416803(7 73)8521360505(6 82)6751938978(5 55)4426152222(4 92)1544000236(3 326)1045116192(2 91)6456279478(1 8 2 1)(86651206749628394829430288201905031805)()(1131234567890201905031805-8)(3 222121iSixxxfxaxaSxfpaapSi例子1例子13.1 Shamir的门限方案(续)。秘密的常数项他们所关心的只是代表。到进行约减得并用模，代替因此，他们可以用。由于，。个点：的到如下多项式通过他们项式，他们可以计算得插值多用希望联合确定秘密。应，和，假定用户201905031805 6651206749628394829430288201905031805 1/5807407407340)(mod18074074073405 )5/7931095476582(42719861927514728/520705602143Lagrange73 2 )续(22xxppxx 例例子子1 13.1 Shamir的门限方案(续)。，这也可以得到，就需要解如下方程：，他们选择采用线性系统方法，和，如果用户密。以重建多项式并得到秘同样地，任何三个人可)6651206749628 394829430288 201905031805()()1131234567890(mod2897344168039215440002363261045116192 4971931421 73 2)续(2121aaSaaS 例子1例子13.1 Shamir的门限方案(续)(3)(2)1 01(1).Shamir的用户。算分配并且不影响现有可以容易的计给新用户新的分享对新用户的扩展。长度相等。分享的数据长度与秘密理想。有相等的可能性。取值享的秘密或更少的分享，所有共完备。给出任意的门限方案的性质pSt3.1 Shamir的门限方案(续)。数论困难问题例如，设于任何未经证明的假该方案的安全性不依赖不同于许多密码方案，无不能证明的假设。影响方案恢复秘密机制，而这样的安排不会更多的恢复秘密的能力单个秘密分享的用户分享，其就有相对只有密假如单个用户有多个秘多种层次控制。)(5)(4)3.2 向量方案可以决定秘密。个超平面的交点则刚好何面。任维的包括这个点的超平分享是一个维空间的点。每个秘密定义为一个门限方案。的点的发明了一个使用平面上ttt1)(Blakley George3.2 向量方案(续)作为分享。给每个面平，并安全的传输对应超设定，的系数个相互独立模随机选择。，维空间定义一个点的并在模，的随机数选择模。选择一个素数个用户。并希望分给有一个秘密可信方建立。密分享就可以恢复秘个用户的组提交他们的结果：任何个用户。的分享给摘要：可信方分配秘密门限方案，的 )(mod 1 1(1.2)(1.1).(1)(Blakley 20120120121012100iitjjijttjjijtiitittPyxaxpsasyniaaptTssssQtpssspTspTnsSTStnSnt机机制制2 23.2 向量方案(续)0)(mod111 1 )(.(2)()(Blakley 02111010212011101210。矩阵。恢复的秘密就是就是可逆，矩阵模不等于只要矩阵的行列式模。阵们的超平面可以产生矩。他，个用户。例如，点个不同的超平面来计算他们的分享提供了的分享。或更多个用户提交他们任何恢复秘密续门限方案，的SspppyyysssaaaaaatiPtssssQttntttttit机机制制2 23.2 向量方案(续)。：得到如下超平面：，他们可以，个人假定有。门限方案。令，考虑建立一个491934E161257D186536C102752B68194AEDCBA5735)(3 102102102102102xxxxxxxxxxxxxxxp 例子2例子23.2 向量方案(续)。个就可以联合恢复秘密中的，。同样地，任何是，因此，秘密就，解是。解想恢复秘密，他们可以，如果SxSxxxxxx3EDCBA4257)29(42)()73(mod18106816536127521194 CBA)续(0210210例例子子2 23.2 向量方案(续)。，方案是而，信息，即这个方案是方案保存更多的相对这个方案需要每个用户，使得矩阵总是可逆。，择系数当然，也有方法可以选有非常大的可能可逆。能确保矩阵可逆，但的值通常很大，虽然不由于一定的优势。将给攻击者找到秘密以况下，在得到部分分享的情秘密被存放于多个坐标果可以用来存放秘密。如注意只有一个坐标分量)(Shamir)(Shamir(3)2(1)2020yxyaaaapiitiiti评述.评述.3.3 存在骗子的秘密分享 上校Alice，Bob，和Carol在某个隔离区很深的地下掩体中。一天，他们从总统那里得到密码消息：“发射导弹，我们要根除邪恶国家。”Alice，Bob，和Carol出示他们的分享，但Carol拿出的只是一个随机数。她实际是一个和平主义者，不想发射导弹。由于Carol的错误输入信息，他们恢复出来错误的秘密。导弹还停留在发射井里。更糟糕的是，没人知道究竟是谁在其中捣鬼。3.3 存在骗子的秘密分享(续)。是，也就，但是这个秘密不正确，也就是，的秘密，可以恢复出一个合法，和，从个参与者意味着第个参与者。这里，欺骗来欺骗第，可以伪造新的分享仅有小概率，个参与者。任何，假定秘密SSsSSSSSSttSSSiiitsStttiiiiiiit 1 1 0 0 11 1 0 121121121性性质质1 1 3.3 存在骗子的秘密分享(续)。，这里，。计算得到，个不同的元素上选择，均匀随机的从。上定义随机多项式，在模，个系数并随机独立选择定义。，选择任意一个素数。任意骗的概率小于的方案使得不能发现欺修改摘要：门限方案，的修改)()()(1 2 1(3)(10 1(2)1)/1)(max(1)0 Shamir)(Shamir 2110110iiiiintjjjjtxqddxSxxxnpxaxqppaaatSanttspnt机制3机制33.3 存在骗子的秘密分享(续)。被欺骗的概率不多于。因而，参与者者的概率欺骗参与都可以以多项式。任何其中一个个应因此，伪造可以产生相个是合法但不正确的，有，这里的概率最多就是且有式项中的元素。任何一个多，是一个在我们知道。和仅当秘密可以建立一个不正确的者个点。参与至多相交与，这样的多项式果。如点可以决定一个多项式以上连同，形成点，。每个可能的秘密发给参与者，伪造值，假定参与者)/(1()1()/(1(11)/(1()()(1 2 1)()(1)()()(1)(01 1 0 ),()()(.112211121tptsiitptsstptSSxqxqpxSSxqxqSitxqxqSSxqtSsSidxdxdxiiittiiSiiiStSStiiiiiitttttttt证证明明4 电话投币协议 4.1 应用实例 一个朋友没有意识到Alice和Bob不在一个地方，留给他们了一辆汽车。他们将怎样决定汽车的归属呢？Bob打个电话给Alice建议由他投币来决定。Alice说选择“背面”，但Bob说我投出的是“正面”。于是车归了Bob。这里Alice完全有理由怀疑Bob的诚实。下一次，她可能选择别的办法决定这一问题。4.2 一个解决方法 这里有一个思路，就是Alice随机的选择一个比特b1发给Bob，Bob也随机的选择一个比特b2发给Alice，投币的结果就是b1 b2。问题就是随先发送，如果Alice先，Bob将可以选择b2来控制投币的结果。这并不公平。4.3 公平投币的要求 (1)Bob必须在听到Alice猜测之前就已经投币。(2)Bob不能够在听到Alice猜测之后重复投币。(3)Alice不能在其猜测之前得到投币结果。4.4 使用平方根的投币赢。，她赢。如果告诉，如果。，并发给选择一个，假定为。她任意，的平方根模个计算和使用她的。给但发送保密。他将并计算随机选择一个整数。发给保密，而将和型。她将余，都为模和选择两个大的随机素数如下步骤在每次投币会话中执行赢得投币猜测。或结果：条消息。在公共信道上交互和摘要：用户使用平方根的投币协议Bob)(mod AliceBob)(mod (4)Bob4Alice(3)Alice)(modBob(2)Bob34Alice(1).BobAlice 4BobAlice 2nxbnxbbbanyqpyx nxyxqpnqpqp 协议1协议1AliceBobqpnyb)(Bobor )(Alicexbxb 赢赢n2xy yba224.4 使用平方根的投币(续)4.4 使用平方根的投币(续)确实没有欺骗。的分解来验证其提交可以要求。和因子得到信息。因此，他不可能以外，没有获得更多的发送的数字除了，的是发送给。如果发送的值不是的原因只能是和因子能得到在计算上不可能，则由此可知如果分解的一个非平凡因子。给出了，。也就是分解个平方根，因此，可以的全部知道，则并且给发送如果解释nqpnxxqpnnnbxnny naxbBobAlice AliceBob BobAliceAlice Bob)(4)(mod Bob)(modBobAlice.4.4 使用平方根的投币(续)。或个根剩余定理将据此得到。中国和。因此，她可以得到和计算。将其发送给，计算选择。给。她发送和选择)od23334103(m937850352661867688910121037374)(mod 325656728)(mod 1701899961)(mod 325656728)(mod 1701899961 AliceAlice)od55491705(m36327860103730950481414213562BobBob9917719372426317299 1190494759 2038074743Alice1)/4(1)/4(2nx qxpxqy pynxyxqpnqpqp例子3例子34.4 使用平方根的投币(续)来支持自己的结论。，并且可以计算宣布自己赢，则给发送赢。假如只能宣布，因此，这里是给发送假定1190494759)2333410393785035262373090548(141421356BobBob233341039378503526AliceAliceBob)(mod Bob 86768891012103761Alice)续(nnx 例例子子3 34.4 使用平方根的投币(续)这样做。的分解，因此，她不会种都会导致对种选择，有有，个平方根。这种情况下的得到将三个素数的乘积。但这通过发送给种情况是的分解。另一在游戏之后出示可以要求当然，。素数的乘积给发一个素数而不是两个如果发来的数字。同余来验证否与可以通过平方是。但是，分解，则可以阻止的平方根给发一个随机数字而不是欺骗如果安全考虑nynyny34Alice8Bob AliceAliceBobBobAlice(2)AliceBobBobBobBobAlice(1).4.4 使用平方根的投币(续)的平方数。提供的模她知道的信息仅仅是将无从判断这一点因为。他已经有的值发来的就是宣称故意输掉猜测。他可以决定疵。假定在这一过程中有一个瑕续安全考虑nxBobAliceAliceBob(3).(5电话扑克协议 一个类似于公平投币的协议就是电话扑克协议，它允许Alice和Bob在电话两端玩扑克。不同于处理“正面”和“反面”两条消息，Bob需要处理分别代表每一张牌的52个数字c1，c2，.，c52。如何保证在游戏中没有欺诈？5.1 思想 Bob用自己的加密密钥加密牌c1，c2，.，c52发送给Alice。Alice随机选择5张牌，用自己的加密密钥加密，发还给Bob。Bob解密这些牌后发还给Alice，她再解密决定自己手中的5张牌。Alice再随机选择5张牌发给Bob。Bob解密它们得到自己的5张牌。5.1思想(续)在游戏的过程中，剩下的牌可以按照同样的方法发出。在游戏结束后，Alice和Bob都公布自己的牌和密钥对以确定没有人在游戏中欺骗。5.2 基于离散对数的扑克。给，并发送它们，这里计算表示。，不同数字个预先双方确认的模张牌用。，和，中要选用不同的在每次不同的扑克游戏。满足并计算，满足选择一个秘密整数。满足，并计算，满足秘密整数选择一个。协商一个适当的素数和扑克会话执行如下步骤张牌。到结果：两个游戏者各得条消息。在公共信道交互和摘要：游戏者克协议基于离散对数问题的扑Alice521)(mod Bob 5252(2)()1(1mod1)1(Bob)1(1mod1)1(Alice Bob Alice(1).54 BobAlice 5221ipcbcccpppppppii协议2协议25.2 基于离散对数的扑克(续)手中的牌。这些就是。，这里计算。给，并发送它们，个数字再随机选择手中的牌。次幂。这些就是对这些数字做。次幂，并将它们发还给对这些数字做。并发送这些数字给，这里，计算，个数字选择续克协议基于离散对数问题的扑Bob 51)(modBobBob 5Alice(5)Alice AliceAlice Bob(4)Bob 51)(mod 5Alice(3)(521521jpbbbbjpbbbbjjkkkkiiii协议2协议2AliceBob521)(mod ipcbii这里，51 jbjk，这里)(mod)(pbcjjii)(mod)(pbjk51)(mod jpbji这里，51)(mod)(jpbji，这里5.2 基于离散对数的扑克(续)5.2 基于离散对数的扑克(续)。同余模现在计算。计算，计算。选择一个秘密整数，选择一个秘密整数。令素数为。，变成双方认可的数字游戏者发一张牌。将牌的游戏。每个，张牌：考虑一个简单的只有111222580910305 233799654011091407 743901031721050514 150729877010010311 914012224200514 )(Bob200508901 Bob 024062734Alice 7654321Bob1234567Alice 239627199110305A11091407K1721050514Q10010311J20051401A K Q J 105pp例子4例子45.2 基于离散对数的扑克(续)。因此，她的牌就是。次幂：现在计算。：次幂并将其送还计算。：并发送给次幂，张计算的牌，例如，第现在在其中选择一张她。，：洗牌后将这些数字发给10)(mod2005141700536007 Alice)(mod17005360071230896099 AliceBob)(mod1230896099914012224 Bob4Alice74390103 914012224 2337996540 1112225809 1507298770AliceBob)续(ppp 例子4例子45.2 基于离散对数的扑克(续)10AliceBob K AliceBobAliceJ)od10010311(m1507298770 BobBob1507298770 BobAlice)续(。拿到的是并展示可以很快的计算。试图声称自己选择的是如果。和接下来公布他们的秘密和为了防止欺骗，。因此，他的牌就是。计算。并发还给例如，发来的牌中再选一张，从现在p 例子4例子45.2 基于离散对数的扑克(续)是一个二次非剩余。如果，是一个二次剩余如果，剩余：是二次剩余还是二次非方法判断一个数我们知道有一个简单的是求解离散对数问题。但这个方程需要解方程味着。这意所对应的未加密的牌试图猜测加密的牌的牌。她可以应该很难推导出看上去安全考虑cpcpc pcpbccbpijii )(mod1 )(mod1 )(mod0(2)(modAliceBobAlice(1).21 5.2 基于离散对数的扑克(续)子。例的优势。看下面的一个使用这一结果获得对可以次幂。和的对牌的结论也适合于是二次剩余。相应是二次剩余当且仅当这说明。，并且有加密成是奇数。一张牌和。因此，和，注意我们要求续安全考虑BobAlice )(mod 1)1(1)1()(.212121cccpcccccppppp5.2 基于离散对数的扑克(续)的牌都是二次剩余。是二次非剩余，而其它因此，只有，上，的选择并不随机。事实例子。素数让我们回到前面的简单A110305 111091407 11721050514 110010311 1200514 2121212121pppppp 例子5例子55.2 基于离散对数的扑克(续)。牌一定就是解密。当然，她得到的用自己的。解密并发回给用。加密并发送给。她用自己的是这告诉她。她计算选择自己的牌的时候，当AAliceAliceBobBob1112225809A174390103 1914012224 12337996540 11112225809 11507298770 Alice)续(2121212121ppppp 例子5例子5谢谢!