五千年(敝帚自珍)

主题:如何分摊秘密(一)——从《鹿鼎记》中的四十二章经说起 -- 明日枯荷包

共:💬63 🌺987
全看树展主题 · 分页首页 上页
/ 5
下页 末页
家园 居然得宝了!

乐坏我了

恭喜:你意外获得【通宝】一枚

鲜花已成功送出,消耗 铢钱 1 个,可能得宝。可通过工具取消

提示:此次送花为【有效送花赞扬,加乐善、声望、帖得花总数】。

家园 我不得不说

好复杂啊.看到最后一段已经彻底晕菜的数学小白默默吐血中...

家园 如何分摊秘密(六)——无需所有人都同意

回到三个人分摊一个6位账户密码的问题来,如果说只要其中两个人同意就可以推出账户密码来,该怎么分摊秘密?

有个很简单的方法,还是按老规矩把账户密码拆成三个6位数,只有拿到所有这三个6位数才能推导出最终的密码。假设这三个数是A,B和C,老板让甲拿A和B,乙拿B和C,丙拿A和C。

很显然,任何单个人都无法通过自己手上的那两个数获得任何关于账号密码的知识,但是任何两个人在一起,总能凑齐ABC三个数字,从而得知账户密码。

这个办法也可以推广到一般的N个人只要有超过M个人同意(N>=M>0)就可以得知最终秘密的情况。想法就是把最终秘密拆成许多份,而每个人都拿其中的若干份,然后想办法保证让少于M个人在一起,一定凑不齐所有的份数,而如果M个人在一起则一定能凑足所有的份数。

不过我们也可以从另一个方面考虑,这个考虑方法解释起来比较简单。(其实也就是下面multiple的方法,可我觉得我说得比他详细,比他清楚)(8月23日注:我的方法和multiple兄的方法似乎不同,请看下面我和乌贼兄的讨论:乌贼:按有个疑问

同一个6位数的账号密码可以用不同的随机数拆成不同的分摊方法。比如123456要拆成3份,可以是153607,582149,598710,也可以是405071,951239,877256,等等等等。如果要求在5个人中分摊秘密,使得任何其中3个人同意就可以知道秘密,可以这样做:

找到所有5个人中的“三人组合”,这个我们在中学排列组合课里学过,是5件东西取3件的组合取法,一共有(5,3)=5!/(3!(5-3)!)=10个“三人组合”。对于每个这样的三人组合,我们都把那个账号密码象前面那样用随机数拆成3份,然后给这个三人组合中每人一份。一共会拆出10x3=30个6位数来。每个人当然都会属于好几个三人组合。对一个具体的甲,他分别属于(4,2)=4!/(2!2!)=6个不同的“三人组合”,所以他会拿到6个6位数,其中每个6位数都是其中一个三人组合中分摊给他的那份秘密。5个人一共有5x6=30个6位数,这和上面的结果对上了。

甲拿到属于他的那6个数,会增加他对账号密码的知识吗?不会,其中单独的任何一个数都不会使他增加知识。而这6个数分别是6个分拆中的一部分,这6个分拆之间是独立没有关系的,于是就算拿了这6个数也没法组合起来得到对账号密码的新知识。

如果是两个人合谋,比如甲和乙,那么他们最多能够凑到诸如“甲乙丙”“甲乙丁”之类三人组合中那些分拆里3份中的2份,可这还是不够,因为一定要拿到一个分拆的所有3个部分,才能知道账户密码。

如果有任何三个人在一起,比如甲乙丙,那么他们就凑齐了他们那个三人组合的账户密码分拆的所有3个部分,于是就能知道账户密码。

这个方法很容易推广成一般的N个人中只要有超过M个人同意(N>=M>0)就可以得知最终秘密的情况。N个人中的M人组合有(N,M)=N!(M!(N-M)!)=A个,我们就把秘密对这A个组用A种方法拆分,每种方法都独立地将秘密拆成M份,然后给对应的这个M人组合中每人一份。就象上面的特殊的N=5,M=3的情况看到的,少于M个人在一起是没办法恢复出最终秘密的,但是只要有任何M个人在一起,就可以用为这个M人组合的拆分信息恢复出最终秘密。

于是我们就知道了,从理论上来说,无论N和M是多少,我们总能找到方法来让这N个人分摊秘密,使得少于M个人在一起无法知道最终秘密(不仅如此,是一点新知识都不增加),而M个人以上在一起就能够得知最终秘密。不过从实际上来说,这个方法只能用在N和M不大的情况,比如上面N=5,M=3的情况,每个人记6个6位数,也还好。但是N=100,M=80呢?组合爆炸了。其中的80人组合会有(100,80)=100!/(80!20!)=535983370403809682970个,超过5x10^20个。而每个人得记住(99,79)=99!/(79!20!)=428786696323047746376也就是超过4x10^20个6位数,这得拿多少硬盘才存得下来啊。还不说分拆啊检索啊所需要的时间。而且这还只是要分摊一个6位数,如果是一个大文件,那就更提也别提了。一句话,这种简单的想法不实用。

前面那种“所有人都同意秘密才可揭晓”的情况下,每个人要掌握的秘密的长度都和最终秘密的长度一样,要分摊一个6位数的密码,3个人分摊就会拆成3个6位数,100个人分摊就拆成100个6位数,每个人总是只要记住一个6位数就可以了。如果在“N个人M个同意”的情况下,不管是什么M和N,要求每个人记的数也都只是一个6位数(或者一般地,是和最终秘密一样大小的一个信息),那该有多好啊。

好消息就是,这种方法是有的。坏消息是,我们需要稍微高深一点的数学知识才能理解这个方法。

喘气喘气……

元宝推荐:游识猷, 通宝推:明心灵竹,

本帖一共被 1 帖 引用 (帖内工具实现)
家园 过奖过奖

这部分知识其实属于信息论中“显而易见”或者说凭直觉可以感受的部分,所以可以不用信息论就解释得比较清楚。下面的部分我就不得不介绍点稍微深的数学知识了。

科普有两种,一种是说一下这个学科里有些什么有意思的东西,或者介绍一下某个问题的历史,有点象聊天一样,不说其中机理,读者知道“哦,原来有这么回事”,一种是解释一下简单的机理,读者不但知道有这么回事,还能有点入门的感觉。这两种科普都是必要的,前面这种读起来比较轻松,大家爱读,读了也同样增长知识;而后面这种就需要读者的一定努力才读得下去,当然,作出的努力是有回报的,弄懂一个问题得到的喜悦感会比较强。有些学科比较难作第二种科普,而数学和信息论恰恰是适合这种科普的(八卦也有,但相对较少)。

Threshold Cryptography不打算说了,文章重点在“分摊秘密”上,如果把密码学也拖进来,要解释的东西多了点。

家园 看这种文章最好自己拿张纸写写算算

别人写出来的东西是别人的思路,自己动手写下来画出来的是自己的理解。光一路看下来,是被别人的思路拖着走,要时不时自己歇一歇的。

家园 荷包好人品啊,两个通宝奉上

荷包好人品啊,铁手对您的文章非常赞赏。

谢谢:作者意外获得【通宝】一枚

鲜花已成功送出,消耗 铢钱 1 个,可能得宝。可通过工具取消

提示:此次送花为【有效送花赞扬,加乐善、声望、帖得花总数】。

谢谢:作者意外获得【通宝】一枚

鲜花已成功送出,消耗 铢钱 1 个,可能得宝。可通过工具取消

提示:此次送花为【有效送花赞扬,加乐善、声望、帖得花总数】。

家园 俺搓着手说:嘿嘿嘿,不好意思啊……
家园 俺试试看,花谢指点
家园 是啊,昨晚一直惦记着这贴,

今早一起来就看,害得我脸也没戏牙也没刷蓬头垢面地坐在电脑前写写算算

(我有忍住没Google!)

不过到(六),就超出我这个数学盲的理解能力了,哭

家园 加油加油

千万别挖坑不填啊,老萨那个最多让人惦记点击,你这个要不填了,多人让人费脑子啊~

家园 有宝

谢谢:作者意外获得【通宝】一枚

鲜花已成功送出,消耗 铢钱 1 个,可能得宝。可通过工具取消

提示:此次送花为【有效送花赞扬,加乐善、声望、帖得花总数】。

家园 送花,回帖都是一个技术活,老铁太厉害了

送花 关闭

恭喜:你意外获得【通宝】一枚

鲜花已成功送出,消耗 铢钱 1 个,可能得宝。可通过工具取消

提示:此次送花为【有效送花赞扬,加乐善、声望、帖得花总数】。

送花 关

家园 谢谢好文还有通宝!
家园 人品好呀。"恭喜:你意外获得【通宝】一枚"
家园 逐篇花,连续第三宝!
全看树展主题 · 分页首页 上页
/ 5
下页 末页


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河