孙子神奇妙算与现代密码门限方案

★ 提示：如果文中数字/公式显示较大, 请点击右上角中“刷新”即可恢复正常。

编者按：2019年7月，中国高等教育学会学术年会在扬州大学召开，本次年会的主题是《大学数学与中学数学的衔接与贯通》。会上，中科院数据与通信保护研究教育中心的翟起滨教授作了题为《谈谈余数定理在中学代数课程中的地位》，这次带来的是翟起滨教授在《信息安全研究》杂志发表的有关余数定理在密码学中的应用的文章，原文题为《由孙子神奇妙算诱导出的密码门限方案》。

摘要：1979 年 11 月以色列密码学家 Adi Shamir 正式发表论文，提出著名的密码门限方案。事实上，1978 年 8 月，我国著名数学家华罗庚为了招收研究生，给出的考试中的一道题目就是这个问题。本文的目的是讲出这件事，并且给出当时的解答方法；这个方法来自孙子的神奇妙算。

关键词：密码学；门限方案；孙子的神奇妙算；多项式插值

华罗庚在 1978 年 8 月给相关研究生考生的复试问题之一，按题意归结为：由 10 位科学家在同一个实验室参与一个保密研究项目，他们将相关文件锁在一个保密柜中，要对保密柜的锁进行一个精妙的设计：当且仅当不少于 3 个科学家到这个实验室时，才能打开保密柜，将文件取出来。你能设计出一个数学解决方案吗？

为了解答这个问题，先简谈一下孙子的神奇妙算：

(孙子算经) 今有物不知其数。三三数之余二，五五数之余三，七七数之余二。问物几何？具体的故事为：韩信带 1 500 名兵士打仗，战死 400 人左右。战后点兵：站 3 人一排，多出 2 人；站 5 人一 排，多出 3 人；站 7 人一排，多岀 2 人韩信马上说岀人数 1073。

对应的同余方程为

请大家最好读一下华罗庚的这本小册子。

图 1《从孙子的“神机妙算”谈起》封面图

解决上述问题的一个口诀是 (出自明朝数学家程大位，将解法编成易于上口的《孙子歌诀》): 

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

上述物不知其数问题被抽象为孙子定理，传到西方后被推广为中国剩余定理。这些问题的实质是：建立不同模数的、具有局部特征的“正交坐标系”。在这个具体例子中，就是要建立类似 3 维欧氏空间的直角坐标系，这个坐标系的 3 个单位 (向量) 分别为 70,21,15, 如图 2 所示：

图2 坐标系

物不知其数的一般例子：今有物不知其数。三三数之余 ；五五数之余 ；七七数之余 ，问物几何？

答曰：物的个数为 ，。

可以想像 为这 3 维空间的坐标；70,21,15 分别为坐标系中 轴、 轴、 轴上的单位向量。

问题是，70,21,15 如何求得的？求解方法来自中国古代数学家秦九韶 (公元 1202-1261). 我们知道 17 世纪，法国人笛卡尔发明了直角坐标系。然而，13 世纪中国人秦九韶十分清晰地给出“孙子”坐标系。

我们对第 1 个同余方程组的解法为：令 , 第 1 个同余方程组等价于同余方程 , 通过带余除法，容易解出 , 综合上述第 1 个方程组，即得 ，。表达形象一些就是坐标向量：

同理可以算出：

于是我们有结论:

也就是回答了上面提及的物品个数为 的原因，。

我们进一步有整数环上的中国剩余定理 (孙子定理): 设自然数 两两互素，并记 ，同余方程组

在模 同余的意义下有唯一解。

下面给出华罗庚先生在 1978 年 8 月给研究生考生的那个复试问题的解答：

解：10 位科学家分别为 , 他们有序对应“锁”中的秘密的相异的 10 个素数 作为模数。设打开保密柜的密码口令为正整数 ；“锁”通过秘密计算得到 将 作为秘密口令交给科学家 保存。另外，从已选的 10 个素数中，每次抽选 3 个相异素数计算出一个孙子 3 维坐标系的 3 个坐标轴的 3 个单位基向量；共有 120 个这样的组合。当不少于 个科学家到这个实验室时，只要分别输入 3 个科学家的秘密口令，“锁”就可以利用对应的 3 维坐标系的 3 个单位基向量。用前面“物不知其数的解法”和秘密口令 的数值 10 进位位数就可以将打开锁的密码算出，从而使保密柜打开。

Adi Shamir 在 1979 年 11 月公开发表了 1 篇论文“How to Share a Secret”, 论述所谓密码门限方案。文章给出 —门限方案的定义。

定义 1. 设 是取自有限集 的某一秘密数据。又设 个参与者 各自拥有关于 的部分信息 , 将集合 称为一个 —门限方案是指它满足如下 2 个条件：

• 1) 利用任意  个不同的部分信息 ，均可容易求得 ；

• 2) 利用任意 个不同的部分信息 ，都无法有效地求得 。

有趣的是将华罗庚先生的那个考题稍微一推广就是 Adi Shamir 的 —门限方案的现行说法：由 位科学家在同一个实验室参与一个保密研究项目，他们将相关文件锁在一个保密柜中，要对保密柜的锁进行一个精妙的设计：当且仅当不少于 个科学家到这个实验室时，他们相互配合才能打开保密柜，将文件取出来，你能设计出一个数学模型方案吗？请写出来。

1979 年 Shamir 给出的密码门限解决方案是利用了拉格朗日插值公式[2-8]，它的实质还是中国孙子的神奇妙算！

对某个多项式函数，已知有给定的 个取值点：

其中 对应着自变量的位置，而 对应着函数在这个位置 (每一个 值都不等于 0) 的取值。

假设任意 2 个不同的 都互不相同，那么应用拉格朗日插值公式所得到的拉格朗日插值多项式为

其中每个 为拉格朗日基本多项式 (或称插值基函数)，其表达式为

拉格朗日基本多项式 的特点是在 上取值为 1, 在其他的点 上取值为 0.

我们将这个一般的拉格朗日插值公式退缩到 3 次插值的 2 次多项式情形：

对于 来说， 是打开保密柜的密码，若有 3 个插值，即 ，，，它们只要被 3 个人分别输入“锁”, 那么利用插值公式就可求解  ，从而得到那个常数 。

这种方法本质上就是孙子定理的应用，首先注意中学代数中的余数定理：对于 , 如果有 , 则有 , 也就是 。

对于上面的 来说，若 ，有同余方程组：

类比整数情形时的秦九韶方法计算：

计算出：

同理可以求得：

说穿了，华罗庚先生非常推崇的“孙子的神奇妙算”在密码门限方案中扮演了最核心的角色。

向上滑动阅览 参考文献

1. 华罗庚。从孙子的神奇妙算谈起［М］. 北京：人民教育出版社，1964

2. Rivest M, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems [OL]. 1978 E2017-10-09].

3. Liu C L. Introduction to Combinatorial Mathematics [M]. New York：McGraw-Hill, 1968

4. Knuth D. The Art of Computer Programming, Vol. 2 [M] 11Seminumerical Algorithms. Reading, MA：Addison-Wesley, 1969

5. Aho A, Hopcroft J, Ullman J. The Design and Analysis of Computer Algorithms [NQ. Reading, MA：Addison-Wesley, 1974

6. Diffie W, Hellman M. New directions in cryptography [Jl IEEE Trans on Information Theory, 1976, IT-22: 644-654

7. Blakley G R Safeguarding cryptographic keys [C/OL] // Proc of AFIPS 1979 NCC. 1979 [2017-10-09].

8. Shamir A. How to share a secret [OL]. 1979 [2017-10-09].

延伸阅读：

本文转自：《信息安全研究》 第3 卷 第 10 期
温馨提示：快速看到我们的最新文章马上把「和乐数学」公众号设为星标吧。打开公众号，点击“设为星标”即可！