Single

[DDCTF2019]联盟决策大会(Shamir算法)1 min read

为了共同的利益,【组织1】和【组织2】成立了联盟,并遵守共同约定的协议。为了让协议的制定和修改更加公 平,组织1和组织2共同决定:当三位以上【组织1】成员和三位以上【组织2】成员同意时,才可以制定或修改协 议。为了实现这一功能,联盟的印章被锁在密码保险柜中,而保险柜的密码只通过Shamir秘密分享方案分享给【组织 1】和【组织2】的每一位成员。 现在,【组织1】的【成员1】、【成员2】、【成员4】,【组织2】的【成员3】、【成员4】、【成员5】一致同 意制定新的协议。请还原出这套方案的设计思路,按照这套方案的思路恢复出保险柜密码,取出印章吧!

题目下载

(k,n)秘密分享算法将秘密分为n份,任意k个子秘密可以恢复出S。本体要求分为两个组织,组织1,2都必须有三人以上同意才能得到秘密。

组织1的成员(1,2,4 )恢复出来组织1的秘钥,组织2的成员( 3,4,5) 恢复出来组织2的秘钥,再用这两个算出总秘密z,期间可以使用同一个p,最后z和p算出最终秘密。

a1(x-2)(x-4)/(1-2)(1-4)+a2(x-1)(x-4)/(2-1)(2-4)+a4(x-1)(x-2)/(4-1)(4-2)
化简为 f(x)=ax^2+bx+c1 c1为密钥
第二组同理,获取c2
c1与c2需要模q
c1(x-1)/(1-2)+c2(x-2)(2-1)
化简为 f(x)=ax^2+bx+c c为flag

p = 0xC53094FE8C771AFC900555448D31B56CBE83CBBAE28B45971B5D504D859DBC9E00DF6B935178281B64AF7D4E32D331535F08FC6338748C8447E72763A07F8AF7

A1 = 0x30A152322E40EEE5933DE433C93827096D9EBF6F4FDADD48A18A8A8EB77B6680FE08B4176D8DCF0B6BF50000B74A8B8D572B253E63473A0916B69878A779946A

A2 = 0x1B309C79979CBECC08BD8AE40942AFFD17BBAFCAD3EEBA6B4DD652B5606A5B8B35B2C7959FDE49BA38F7BF3C3AC8CB4BAA6CB5C4EDACB7A9BBCCE774745A2EC7

A4 = 0x1E2B6A6AFA758F331F2684BB75CC898FF501C4FCDD91467138C2F55F47EB4ED347334FAD3D80DB725ABF6546BD09720D5D5F3E7BC1A401C8BD7300C253927BBC

B3 = 0x300991151BB6A52AEF598F944B4D43E02A45056FA39A71060C69697660B14E69265E35461D9D0BE4D8DC29E77853FB2391361BEB54A97F8D7A9D8C66AEFDF3DA

B4 = 0x1AAC52987C69C8A565BF9E426E759EE3455D4773B01C7164952442F13F92621F3EE2F8FE675593AE2FD6022957B0C0584199F02790AAC61D7132F7DB6A8F77B9

B5 = 0x9288657962CCD9647AA6B5C05937EE256108DFCD580EFA310D4348242564C9C90FBD1003FF12F6491B2E67CA8F3CC3BC157E5853E29537E8B9A55C0CF927FE45

c1=(A1*8-A2*6+A4)/3

c2=B3*10-B4*15+B5*6

print hex(c1*2-(c2%p))[2:-1].decode('hex')