数学科普

如何分摊秘密(三)

作者:安迁

三、两人之间分摊秘密

首先要指出的是,从绝对的意义上来说,只要掌握了一部分秘密,就很难不多知道一些秘密。比如说如果我保存了一部分秘密,它的大小只有几个字节,那么整个秘密是《红楼梦》完整手稿的扫描版的可能性就很小。如果我知道只有几个人分摊了秘密,而每个人都只掌握了几个字节大小的秘密,那么就可以排除整个秘密是《红楼梦》手稿的可能性。我们说的若干人分摊秘密时“掌握秘密却不泄露任何秘密”的意思,严格地说来,是要首先固定秘密所在的范围的。

严格地说,我们必须先确定一个足够大的公开的整数N,而所谓的秘密则是某个0到N-1之间的整数(包括0和N-1)。在第二节中两人分摊6位数账号密码的例子中,我们假设账号密码位数不是秘密而是是一个公开的信息,这个N就是1000000。一个局外人也知道账号的密码在0到999999之间,只是对于他来说,这1000000个数字是正确密码的可能性都一样,都是1/1000000。说一个人“不知道秘密”,就是说,对他来说,0到N-1中的任何一个数是秘密的可能性都是1/N,和局外人一样;而一旦对他来说这些可能性变化了,无论变动多么微小,他都知道了一点秘密。

接下来我们讨论两个人之间分摊秘密的方法。就以前面甲乙两人分摊6位数账号密码为例。

拿一个能均匀地随机产生0到999999之间的数字的随机产生器。注意“均匀”这个条件。一个好的骰子就是一个“能均匀地随机产生1到6之间的数字的随机产生器”。骰子有六面,分别标着1到6的数字,因为是“好的”,每掷一次,掷到每个数字的可能性都是一样的,都是1/6。如果那个骰子是灌铅用来出老千的,掷出6的可能性比较大,那就不是好骰子了。现在的计算机程序能产生一些叫“伪随机数”的数字序列,在某些情况下可以看作是随机数。如何产生好的(伪)随机数是密码学中非常重要的技术问题,具体做法因与本文无关,就不多说了,在此只假设这样的随机数产生器存在。

现在老板就让随机数产生器产生出一个0到999999之间的数字a。把这个a给甲,这是甲掌握的秘密。然后老板用密码(真正的秘密)减去a,如果结果大于等于0,那么保持结果不变,如果结果小于0,就把结果加上1000000,得到新的结果。令这个结果是b,把这个b给乙,这是乙掌握的秘密。到要付款的时候,只需将甲乙两人手中数字相加,如果结果小于1000000,则就是账号密码,如大于1000000,那么将结果减去1000000就是账号密码。

举例说明。假设随机产生的a是735049,那么123456-735049=-611593,它小于0,于是再加1000000得到388407,即b。在需付款时,735049+388407-1000000=123456,即账号密码。

让我们来看看还未付款前,甲和乙分别掌握和知道着怎样的秘密。很明显,甲和乙分别掌握着735049和388407,可他们知道什么秘密呢?

甲掌握着735049,但这个数字根本就是老板拿随机产生器产生出来的,跟密码123456没有一点关系,他拿到这个数字,不会增加一点点对密码本身是什么的信息。对他来说,000000-999999之间这1000000种可能的密码的范围没有任何改变,每个都有1/1000000的可能是真正的密码。关于这点,他没拿到735049以前就知道了;掌握了735049并不让他多知道点关于账号密码的秘密。

乙掌握着388407,他会对真正的密码是什么增多点了解吗?不会。真正的密码当然有可能是123456,如果甲的数字是735049的话;但是真正的密码也有可能是999999,如果甲的数字是611592。甲的数字是随机数产生器产生出来的,每个是0到999999之间的数字都有1/1000000的可能是甲手里的那个;而每个这样的数字,加上乙自己手中的数字,都对应着一个可能的账号密码,不同的数字对应不同的账号密码。最后乙能推断出来的结论还是:最终的密码是000000-999999之间这1000000种可能,每个都有1/1000000的可能是真正的密码。可是关于这点,他没拿到388407以前就知道了。

总结一下:首先我们用一个0到999999之间的随机数把账号密码拆成了让甲和乙分摊的两部分。当他们都决定要知道账号密码时,他们掌握的这两部分秘密可以很方便地推断出账号密码(比吭哧吭哧地拼地图碎片方便多了);其次也更重要的是,甲或乙无法单独地通过自己新掌握的秘密来得到以前不知道的信息。这正是我们希望得到的效果。

而我们刚才又是如何证明,甲或乙在获得分摊给他们的那部分秘密时,没有增加任何他们以前不知道的信息的?是通过说明,对他们来说原本账户密码有1000000种可能,每种的可能性都是1/1000000,而等他们获得分摊的秘密后,他们所知仍是这样。这和被告诉了账号密码的前三位或后三位的情况大不一样。

注意到那个随机数产生器必须是“好的”,产生出0-999999之间每个数字的可能性都要一样。否则的话,比方说它产生735049比产生735048的可能要大,而这点被乙知道了,那么当乙拿到他那部分秘密388407时,就知道真正的账号密码是123456要比是123455的可能要大。于是对于乙来说,1000000种可能中,每种的可能性不再都是1/1000000,而是有多有少,乙就获得了他以前不知道的关于账号密码的信息。所以随机数产生器的质量是非常要紧的。

<(二)
(四)>