五千年(敝帚自珍)

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

共:💬63 🌺987
分页树展主题 · 全看首页 上页
/ 5
下页 末页
    • 家园 如何分摊秘密(五)——更多人的秘密

      那么如果是三个人或更多人要分摊秘密怎么办?

      非常方便。仍旧是那个6位数密码,假设现在老板要派三个人甲乙丙去。

      按照原来的老方法,现在老板随机产生两个6位数,比如153607和582149,把它们分别给甲和乙,然后用真正的密码123456去逐位减这两个数字:

      1-1-5 = -5 -->5

      2-5-8 = -11 -->9

      3-3-2 = -2 -->8

      4-6-1 = -3 -->7

      5-0-4 = 1 -->1

      6-7-9 = -10 -->0

      总之如果结果不在0-9中就加减若干个10,使得结果成为一个0-9之间的数。老板得到598710,给丙。

      同样的分析,甲和乙凭手里的那个数能增加他对真正的密码是什么的信息吗?不能,那俩数根本就是随便产生出来的。丙靠他的数也一样不行,和前面两个人的情况中乙的情况差不多。

      如果其中有两人合谋怎么办?比如甲和乙合谋——没用,他们那俩数都是随便产生出来的。甲和丙合谋?每一个可能的最终密码值都对应着一个乙手里的那个数的可能值,可是乙手里的那个数的可能是000000-999999中的任何一个,概率都是1/1000000,于是真正的密码还是在000000-999999中的任何一个,概率还是1/1000000。通过甲和丙的同谋,还是无法带给甲和丙任何他们以前不知道的事情。乙和丙的同谋情况也一样。

      但是如果甲乙丙共同决定要得到密码,只要把他们手上三个数逐位加(可能要减去若干个10使得结果在0-9间)就可以了:

      1+5+5 = 11 ->1

      5+8+9 = 22 ->2

      3+2+8 = 13->3

      6+1+7 = 14->4

      0+4+1 = 5->5

      7+9+0 = 16->6

      人数再多的话,多产生一些随机数即可。N个人产生N-1个随机数,最后一个人则分配给真正密码逐位减这些数字的结果。

      很容易看出来,就算密码位数不是6位,而是非常非常长,这个方法也一样可行。如今啥都是数字化的,一个文件其实就是一个大数字,文字的记录是文本文件(或者Word文件也无所谓),如果是一张地图,或者是拍了些见不得人的照片啥的,就是个图像文件,一段录像是一个视频文件。既然这些文件无非都分别是一个(也许有很多很多位的)数,那么就可以用前面说的这个方法来分摊到若干人上。这个被分摊的秘密也不一定非得表示成10进制的,比如计算机文件一般是以二进制形式储存传送的,也可以看作是十六进制甚至是更大的数字进制的,假设是P进制,那就把前面那个随机数产生器改变一下,让它产生合适范围(0到P-1之间)的数字。这样我们就得到了一个在许多人之间分摊一个任意大小的秘密(大小不是说秘密泄露的严重性,是说内容多少)的方法。这个方法可以保证每个人“掌握”却不“知道”,而且即使是有若干同谋在一起也无法知道最终秘密更多的信息。只有在所有人都同意揭开秘密的时候,大家才能知道这个秘密。

      不过正如前面所言,这个方法好是好,但未免过分严格了一点。要是在100个人中这么分摊秘密,万一有一个人三长两短把他掌握的秘密弄丢了怎么办?大家拿着99份分摊的秘密,可是对知道最终秘密一点用都没有。所以我们还得想出一个办法,能够只要求达到规定的一定人数比如说80个人,而不要求全体都同意,就可以揭开秘密。

      喝水……

      通宝推:明心灵竹,
      • 家园 人品好呀。"恭喜:你意外获得【通宝】一枚"
      • 家园 我不得不说

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

      • 家园 佩服佩服!

        看完分摊秘密不容易(2)后, 我还以为楼主接下来肯定要提到信息论了.

        没想到荷包大才, 没有借助信息论, 也把问题讲的一清二楚. 把科学问题用浅显易懂的语言表达清楚, 需要大智慧啊, 佩服佩服

        是不是接下来会解释Threshold Cryptography的原理?

        逐篇献花, 期待下文.

        • 家园 过奖过奖

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

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

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

分页树展主题 · 全看首页 上页
/ 5
下页 末页


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

Copyright © cchere 西西河