密码学协议 门限

这是以前在Matrix67的博客上看到的，补充些我自己的理解

背景

设想:老大某天想要向某人传送一封密信,为了避免一个特工被抓了送信就失败了,于是他把密文加密,把密文和密钥都给了几个特工----这样挂了一个或者被抓了一个也没关系,只要还有别的特工送到就行了.但是,情报虽然是能比较大概率的送到了,由于这个情报是秘密情报,老大不希望它被泄漏在别人手里.一旦某个特工被抓了,或者叛变了,情报不久泄漏了吗?所以,他想到把按特工的人数把密钥平均分成几份,每个特工各拿一份,这样即使特工被抓或者叛变,情报也不会泄漏出去.但是,这又走到了另外一个极端:只要有一个特工被抓了,情报就不能送出去了.所以他就想:有没有这么一个办法,我送出去n个特工,只要有其中任意的m个人或以上到达,就能把情报送出去.但是只要少于m个人到达,哪怕是m-1个,情报都不能被收到呢?

这样的问题就叫(m,n)门限

解决方案

要解决的问题可以转化成:

组合数学的解决办法

1. 分出来的每份密钥应该分给至少多少个特工?

2. 怎么决定每个特工受手上有那些密钥?

3. 到底要把密钥分成多少份?

虽然这个问题的顺序是有点反直觉的顺序,怎么能先决定怎么分配,再决定要把密钥分成几份呢?事实上,这三个问题的顺序确实是我们第一个解决方案的思考顺序(至少我是这么思考这个问题的)

什么是鸽笼原理(抽屉原理)

通俗的说,就是基于这么一个事实:现在有8只鸽子,但是只有5个笼子,要把鸽子全部放进鸽笼里面,那么至少有一个笼子装2只或两只以上的笼子.

思路

现在有n个特工,但是希望只要有其中大于等于m个特工到达就能获得完整的密钥,把秘密情报解密出来.所以对于分出来的每一份密钥,从n个特工中任意选出的m个特工的手中,都至少要有一份.根据鸽笼原理,只要每份密钥都至少准备n-m+1份就可以了.因为这意味这受伤没有这份密钥的特工人数有n-(n-m+1)=m-1人,最坏的情况下,前面到达m-1个人都是没有这份密钥的,那么第m个到达的特工必然手中有这份密钥.

现在来解决第二个问题.划分的依据就是,不希望两个不同密钥完全相同的被分配在几个不同的特工手里.意思就是避免这种情况跟出现(这里以(3,5)门限为例,&代表特工的编号):

&1: 2 4
&2: ...
&3: 2 4
&4: 2 4
&5: ...

这样,第2号密钥就和4号密钥完全相同的被分配在2,3,4特工手上,这样就会导致2号密钥出现4号密钥必然出现,2号密钥出现4号密钥必然不出现,这样2号密钥和4号密钥就完全没有必要分离开来.这样,第二个问题也解决了.

还剩下最后一个问题.先假设每份钥匙准备的数量就是n-m+1份(稍候就会说明为什么要如此假设).根据第二个问题的结论:不能有两个不同的密钥完全相同的被分配在几个不同的特工手里,对于(n,m)门限,最多可以分成C(n-m+1,n)=C(n-(n-m+1),n)=C(m-1,n)个密钥.下面就来证明密钥的数量少于C(m-1,n)是不行的.假设分少了一把钥匙,再一次根据第二个问题的结论:不会除向恋歌不同的密钥完全相同的被分配在几个不同的特工手里,这说明,对于原本手里没有着把密钥的m-1个特工来说,其他密钥都至少有一个特工有(以(3,5)门限为例,0表示没有.1表示有).

1 2 3 4 5 6 7 8 9 10
&1 1 1 1 1 1 1 0 0 0 0
&2 1 1 1 0 0 0 1 1 1 0
&3 1 0 0 1 1 0 1 1 0 1
&4 0 1 0 1 0 1 1 0 1 1
&5 0 0 1 0 1 1 0 1 1 1

如果少了10号密钥,那么对于1号特工和2号特工,对于1-9号密钥两个人都至少有一个人有,所以这就不满足必须要m个特工到齐才能把密钥凑齐这个前提条件.同时,如果分少的钥匙不仅仅一份,那么只要这m-1个特工到齐,就更可以凑齐密钥的所有部分了.因此,当每份钥匙准备的数量为n-m+1分时,必须分成C(m-1,n)分密钥才行.

那么,每份密钥准备的数量能不能大于 n-m+1份呢?

答案是否定的

从上面的分析可知,在到达密钥数量冗余的临界点之前,密钥数量的增加会导致对到达特工数量的要求的增加.所以,每份密钥准备的数量为n-m+k(k>1且为整数),准备C(m-k,n)份密钥的时候,对安全到达的特工的数量要求最高.在这种情况下,对于任意一把密钥,没有它的特工人数有m-k个人,也就是说,如果分少了这一把密钥,只要有原本没有这把密钥的这m-k个人到达就可以解出情报了,这是在剩下的n-m+k个人中增加这把钥匙,只要有n-m+k中的任意一个人到达就可以解开了,所以总的来说只需要m-k+1个人到达就可以了,又因为k>1,所以m-k+1 < m,也就说不满足必须要m个或以上的特工人数到达才能解开情报.

至此,我们就完美解决了(m,n)门限的问题了.做法是只需要把密钥分成C(m-1,n)分,每个人持有C(m-1,n)*(n-m+1)/n=C(m-1,n-1)份密钥就行了.

空间几何

这是一个十分美的解决办法.还是先从个上面的(3,5)门限的例子来说把,只要把密钥编码成空间中的一个点,每个特工手上拿着一个平面方程.所有特工所持有的平面方程全部都交于一个点.因为只有三个或以上的平面才能交于一个点,所以,只要有三个特工到达,拿出他们手里的平面方程一解,答案就是密钥.用这种解决办法,对于(m,n)门限,只要把空间的维数相应的改变成m就可以了~

多项式

对于一个n阶的多项式f(x)=a[1]x^n+a[2]x^(n-1)+...+a[n-1]x^2+a[n]x+a[n+1]来说,只需要知道这个函数图像上面的n+1个点就可以把这个多项式接出来.可以利用这一点,对于(m,n门限),把密钥编码成一个m-1次的多项式,只要有m个特工到达,就可以把多项式解出来,而少了一个任是不能还原处这个多项式的.

其实这两个解决办法我认为本质上是一样的,可是听起来就更喜欢第上一个

数论

什么是中国剩余定理

思路

基于中国剩余定理,对于密钥x,(m,n)门限,我们可以构造出这么一种情况,任意m-1个a[i]的乘积都小于x,但是任意m个a[i]的乘积都比x大.每个特工拿着一个a[i]和b[i].这样的话,任意m-1个特工到达都算不出正确的x,但是任意m个特工到达都能算出x

最后

如果仅仅是实体世界的话....直接造一个密码箱....每个特工都拿着相同的钥匙....但是只有m把钥匙同时戳进去拧才能打开就行了嘛.....

关键字：密码学, 特工, 密钥, #m-1#

版权声明

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击 举报 进行投诉反馈！