趣说密码学(五)秘密分享——shamir,中国剩余定理,Brickell和Blakley

秘密分享

假如你和你的朋友们正在一起面临某种生存困境,比如在野外迷路了,或是被困在沙漠中,或是核冬天,或是丧尸来袭,你们难以获取食物,只好将剩下的食物的收集到一起放进保险箱。但是有个问题——你们并不相信其他人,其他人很可能趁大家不注意将食物偷走。这时候,保险箱的钥匙应该怎么保管?

第一种情况:交给一个人保管

原来住你隔壁的老王接下这个任务。他看起来似乎值得信任。

第二天新闻头条:已确认某探险队成员全部遇难!原因据查是队员之一黄老板扔下大家不管,带着所有食物跑路了!

第二种情况:交给一些人保管,全部到齐才能打开保险箱

只交给一个人保管钥匙非常不安全。不如交给一些人不同的钥匙,必须要所有的人到齐才能打开。于是你把钥匙分成三份,隔壁老王,对面楼小南和你分别拿到了一份钥匙。这下,隔壁老王不能再自己一个人打开保险箱了。你感到很满意。

第二天新闻头条:已确认某探险队成员全部遇难!现场遇难的探险队员全围着一个锁上的食物箱子,原因据查是保管钥匙的队员之一隔壁老王误将钥匙扔掉,致使全体队员无法打开食物保险箱!

第三种情况:交给一些人保管,其中一部分到齐才能打开保险箱

好吧,隔壁老王也太不靠谱了,如果要全部到齐才能打开,那么其中某人拿不出钥匙将是非常绝望的情形。

于是你想出了一种新的方法,把钥匙分成不同五份,路人甲,街口二愣子,对面楼小南,娄县令以及你分别拿了一份。但现在只需要三个人拿着他们的钥匙就能打开食物保险箱。就算其中一个人将钥匙弄丢,例如二愣子把钥匙吃了,剩下三个人也能打开保险箱。但少于三个人就不能打开保险箱。但具体改怎么做呢?为了制服老王,你的思维开始跳脱起来。

shamir方案

你首先想到了模数。模法是个非常厉害的东西,能解决很多问题和很多提出问题的的人。不管怎样,你想到的sharmir(t,w)方案就是指将w把钥匙给w个人,至少要t把钥匙才能开启。

中国剩余定理(CRT)

还有其他什么办法呢?你把目光又转向了博大精深的中华文化。你发现,孙子他老人家早就知道你现在的处境,为你准备好了解决方法:

Brickell 方案

考虑完模法和中国文化后, 你不再局限于一维方程组,转而思考多维向量。你发现,这不过是shamir的推广。

Blakley 方案

现在你不再满足于地球上的东西,开始思考多维的空间宇宙。发现多维空间的造物主也已经想过同样的事了,准备将毕生绝学传授给你。

然而,这对老王来说并没有什么用。于是:

第二天新闻头条:已确认某探险队成员全部遇难!原因据查是队员之一的老王伪装成食物保管员,用假钥匙想和其他食物保管员合作打开保险箱,虽然没能打开,但老王记下来其他真钥匙的样子,复制出来打开保险箱并带着跑路了。

结语

与隔壁老王的斗争一直在持续。你又设计了一种方案能让老王成功欺骗的概率降到很小的值[2],又设计了一种方案能让队友感受到老王正在欺骗他们[2],又设计了一种方案让某个队员所持的钥匙要比其他钥匙力量更大[2],又设计了一种方案能让逻辑门电路来完成你的要求[3],为了研究出能防止老王对食物做手脚的方案而废寝忘食着——同时,老王还是在午餐时间把你的那份食物吃掉了,于是你只能继续废寝忘食了….

参考

Leave a Reply