数论在密码学中的若干应用

刘佳

摘 要：力求用最通俗的语言，以“秘密分享、RSA系统和背包问题”这几个专题为例，介绍说明数论方法在现代密码学中的应用。密码学的研究与分析离不开大量的数学知识，不过应用最多的还是数论知识。所以说数论对以后学习及深入研究密码学相关理论都有非常重要的作用。

关键词：秘密分享；RAS系统；背包问题

密码的历史极其久远，其起源可以追溯到几千年前。人类有记载的通信密码始于公元前400年。有人说，第一次世界大战是化学家的战争，第二次世界大战是物理学家的战争，如果未来发生战争是数学家的战争，其核心是信息战中的军事密码学问题。在我国古代就不乏以藏头诗的形式把真正的信息隐藏于整个诗篇中，从而只让某些掌握了规律的人知道的例子。又如古罗马凯撒大帝通过将拼音字母向后移三位的方法向赛查罗发布命令。更早些时候，古希腊历史学家波里比阿利用删去了J的25字母方阵创造出了通过用表示行和列的两个字母去表示方阵中的一个字母的方法等等。这都可以看作是密码学的雏形。直到20世纪中叶，密码学主要应用于军事或外交方面的消息传送上，随着计算机科学的迅速发展和信息时代的到来，现代密码学的应用范围已经远远超出了军事与外交领域，在金融、财贸和商业等领域也有重要的作用。现代密码学是与计算机紧密联系的，而它所使用的数学工具涉及数论、布尔函Walsh函数、群论、有限域理论、逻辑学乃至代数几何学中的椭圆曲线理论。不过，应用最多的还是数论。此文的目的则是力求用最通俗的语言说明数论方法在现代密码学中的应用，而其对以后学习及深入研究密码学相关理论都有非常重要的作用。

一、一种秘密分享方案

秘密是一种不公开的信息，自然也是语言。从数学角度看一个秘密就是一个字母S，古代曾有过在一个重要的铁门上锁三把锁，钥匙分别由三个人保存，只有三个人都到齐了才能开门的例子。现代密码学中也有类似的情况。早在1979年Shamir就提出了秘密分享的理论。在所谓（t，n）门限秘密分享体制中，秘密被分成了n个份额，至少要掌握t个份额才能获得这个秘密。为了搞清楚什么是秘密分享，我们先看一个我国古代“韩信点兵”中的数学问题。据说韩信在统计士兵的人数时用到了这样一首诗：

三人同行七十稀，五树梅花廿一枝。七子团圆正月半，除百去五便得知。

这里“正月半”表示15，计算人数的方法是：3人一组，分列所剩的人（只能是0，1或2）乘以70；将5人一组，分列所剩的人数乘以21；将7人一组，分列所剩的人数乘以15，然后将以上三个结果相加再减去若干个105，就得到士兵的人数了。比如，若士兵3人一组站立剩一人，5人一组站立剩4人，7人一组站立剩3人，那么，士兵的人数为1×70+4×21+3×15-105=94。再如，若士兵人数被3，5和7除所得余数分别为2，4和5。则士兵人数可以从2×70+4×21+5×15=299中减去1或2个105而求得。究竟是减去105还是210，对统兵的人来说是很容易的，因为他当然对有多少士兵是心中有数的。比如，统兵的人知道士兵的人数是197，那么就应当从299中减去1个105得出194，那么他就会发现有3人缺席。如果士兵总共有90人，那么则要从299中减去2个105得9，表明有1人缺席。容易看出，105是3，5和7的乘积。至于70，21和15是如何得到的，本文不予细说，因为我们的目的是介绍数论的这一方法在秘密分享策略中的应用。首先要注意，由已知某数被3，5和7去除所得的余数去求某数，只可能得出某数的可能值，比如在前面的第二个例子中，士兵的人数可能是194，也可能是89，再者是减去几个105还是加上几个105也是不能完全确定的。比如，在上例中如果给出299加上105所得的数404被3，5和7除的余数分别为2，4和5，再加几个105后分别得509，614，719…等也是满足同样的条件。当然如果已知人数不超过105，那么就只有唯一解89了。现在假设只告诉某数被3除余2，被5除余4，而要求出某数，那么可能的答案就有14，29，44，59，74，89，104，119…。进一步，如果只告诉某数被3除余2，那么可能的答案就更多了：5，8，11，14，…89，92…如果现在设想89是一个秘密，由3个人分享。第一个人只知道那是一个被3整除余2的数，第二个人知道那是一个被5除余4的数，而第三个人则知道那是一个被7除余5的数。那么这三个人中的每一个人都不可以断定这个秘密到底是什么。但如果这三个人现在在一起，就可以在一定的条件下很容易得出来结果是89。一种秘密分享方案正是基于这种思想而得出来的。我们先把以上的数学方法加以推广。

下面是国际上通称的“中国剩余定理”，也可以称为“孙子剩余定理”或“孙子定理”，它的证明并不复杂，我们演示如下：

孙子定理内容：

设m1，…，mk是两两既约的正整数，那么，对于任意的整数a1，…，ak一次同余方程组x≡aj（modmj），1≤j≤k①必有解，且解数为1，事实同余方程组①的解是x≡M1M1-1a1+…+MkMk-1ak（modm）②

这里m=m1…mk，m=mjMj（1≤j≤k），以及Mj-1是满足MjMj-1≡1（modmj），1≤j≤k③的一个整数（即是Mj对模mj的逆）

证：先证明解的存在性。

再证明解的唯一性：

若x1，x2是适合于同余式组的任意两个整数：x1≡bi（modmi），x2≡bi（modmi），i=1，2，…k，所以x1≡x2（modmi），i=1，2，…k，又（mi，mj）=1，i≠j，从而x1≡x2（modmi），i=1，2，…k，故解是唯一的，证毕。

二、RSA系统

一种应用非常广泛的密码系统，由Rivest、Shamir和Adleman提出，就是如今被称为RSA的密码系统。RSA公钥密码体制是基于大整数分解的公开密钥体制的代表算法。大整数分解问题可以被表述为：已知整数n，n是两个素数p、q的乘积，即n=pq，求解p和q的值。

首先，回忆一下数论中的有关概念：设n是正整数用ψ（n）=1{0≤x

1.加密方法

2.还原定理

设n，e，d如下所述，则ω=[（ωe，modn）d，modn]

3.解密方法

所谓解密就是要从c=ωe密文恢复出来，由还原定理知共需将密文c再d次方，然后再模n进行约简即得ω如密文c=1281，由d=157知由c157模去若干个n即得明文（1281157，mod2773）=1901。

注：在上例中曾涉及（190117，mod2773）与（1281157，mod2773）的计算，看起来似乎计算量大得惊人，其实不然，以第一个计算为例：19012≡582（mod2773）也容易算出来。因此，不容易得出19014≡252≡1625（mod2773）最后得出190117625×1901≡1281（mod2773）

三、背包问题

在最初提出公钥密码思想的时候，还没有一个这样的实例。两年后首先由Merkle和Hellman提出一个基于组合数学中背包问题的公钥密码系统。这个背包系统称为MH背包问题。

背包问题是这样的：已知有n个物品，它们重量分别为a1，a2…an，现在其中装有某些物品，重量为b的背包，问装的是哪些物品？

需要注意的是，并非所有的背包问题都没有有效算法求解。如序列a1，a2，…，an满足条件：ai>■aji=2，3，…n成立时，有多项式解法。这样的序列称为超递增序列。如1，3，6，13，27，52是一个超递增序列，而1，3，4，9，15，25则不是。

超递增背包问题的解是容易找到的。将总质量与序列中最大的数比较，如果总质量小于这个数，则它不在背包中；如果总质量大于这个数，则它在背包中，用背包质量减去这个数，转向考察序列下一个最大的数，重复直到结束。如果总质量变为零，那么有一个解，否则无解。

背包公钥密码系统的实现方案就是选取一组正整数a1，a2，…，an作为公钥予以公布m=m1m2…，mn，是n位0，1明文符号串。利用公钥加密如下：

于是从超递增序列得此序列时，从外表上不再具有超递增假定已知：

参考文献：

[1]蔡乐才.应用密码学.北京：中国电力出版社，2005.

[2]章照止.现代密码学基础.北京邮电大学出版社，2004.

[3]刘木兰，龚奇敏.密码学进展.北京：科学出版社，1998.

[4]杨义先.现代密码新理论.北京：科学出版社，2002.

[5]潘承洞，潘永彪.初等数论.北京大学出版社，2003.

（作者单位 上海市民办交大——飞达中学）