数论在密码学中若干应用

1、数论在密码学中若干应用摘要：力求用最通俗的语言，以“祕密分享、rsa 系统和背包问题”这几个专题为例，介绍说明数论方法在现 代密码学中的应用。密码学的研究与分析离不开大量的数学 知识，不过应用最多的还是数论知识。所以说数论对以后学 习及深入研究密码学相关理论都有非常重要的作用。关键词：秘密分享；ras系统；背包问题密码的历史极其久远，其起源可以追溯到几千年前。人 类有记载的通信密码始于公元前400年。有人说，第一次世 界大战是化学家的战争，第二次世界大战是物理学家的战 争，如果未来发生战争是数学家的战争，其核心是信息战中 的军事密码学问题。在我国古代就不乏以藏头诗的形式把真 正的信息隐藏于整个

2、诗篇中，从而只让某些掌握了规律的人 知道的例子。又如古罗马凯撒大帝通过将拼音字母向后移三 位的方法向赛查罗发布命令。更早些时候，古希腊历史学家 波里比阿利用删去了 j的25字母方阵创造出了通过用表示 行和列的两个字母去表示方阵中的一个字母的方法等等。这 都可以看作是密码学的雏形。直到20世纪中叶，密码学主 要应用于军事或外交方面的消息传送上，随着计算机科学的 迅速发展和信息时代的到来，现代密码学的应用范围已经远 远超出了军事与外交领域，在金融、财贸和商业等领域也有 重要的作用。现代密码学是与计算机紧密联系的，而它所使 用的数学工具涉及数论、布尔函walsh函数、群论、有限域 理论、逻辑学乃至代

3、数几何学中的椭圆曲线理论。不过，应 用最多的还是数论。此文的目的则是力求用最通俗的语言说 明数论方法在现代密码学中的应用，而其对以后学习及深入 研究密码学相关理论都有非常重要的作用。一、一种秘密分享方案秘密是一种不公开的信息，自然也是语言。从数学角度 看一个秘密就是一个字母s,古代曾有过在一个重要的铁门 上锁三把锁，钥匙分别由三个人保存，只有三个人都到齐了 才能开门的例子。现代密码学中也有类似的情况。早在1979 年shamir就提出了秘密分享的理论。在所谓（t, n）门限 秘密分享体制中，秘密被分成了 n个份额，至少要掌握t个 份额才能获得这个秘密。为了搞清楚什么是祕密分享，我们 先看一个我

4、国古代“韩信点兵”中的数学问题。据说韩信在 统计士兵的人数时用到了这样一首诗：三人同行七十稀，五树梅花廿一枝。七子团圆正月半， 除百去五便得知。这里'正月半”表示15,计算人数的方法是：3人一组, 分列所剩的人（只能是0, 1或2）乘以70；将5人一组， 分列所剩的人数乘以21；将7人一组，分列所剩的人数乘以 15,然后将以上三个结果相加再减去若干个105,就得到士 兵的人数了。比如，若士兵3人一组站立剩一人，5人一组 站立剩4人，7人一组站立剩3人，那么，士兵的人数为 1 x70+4x21 +3x15-105=94o 再如，若士兵人数被 3, 5 和 7 除所得余数分别为2, 4和5

5、o则士兵人数可以从 2x70+4x21+5x15=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去除所得的余数去求某数，只可能得出某数的

6、可能值， 比如在前面的第二个例子中，士兵的人数可能是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,那么可能的答案就更多 t： 5, 8, 11, 14,89

7、, 92如果现在设想89是一个祕 密，由3个人分享。第一个人只知道那是一个被3整除余2 的数，第二个人知道那是一个被5除余4的数，而第三个人 则知道那是一个被7除余5的数。那么这三个人中的每一个 人都不可以断定这个祕密到底是什么。但如果这三个人现在 在一起，就可以在一定的条件下很容易得出来结果是89。一 种秘密分享方案正是基于这种思想而得出来的。我们先把以 上的数学方法加以推广。下面是国际上通称的“中国剩余定理”，也可以称为” 孙子剩余定理”或“孙子定理”，它的证明并不复杂，我们 演示如下：孙子定理内容：设ml,，mk是两两既约的正整数，那么，对于任意 的整数al,，ak 一次同余方程组x三a

8、j(modmj), 1wjwk1 必有解，且解数为1,事实同余方程组的解是 x三m1m1-ial+mkmk-lak (modm)这里m=mlmk, m=mjmj (lwjwk),以及mjt是满足 mjmj-l = l (modmj), lwjwk的一个整数(即是mj对模 mj的逆)证：先证明解的存在性。再证明解的唯一性：若xl, x2是适合于同余式组的任意两个整数：xl=bi (modmi ), x2 = bi(modmi ), i=l, 2,k,所以 xl=x2(modmi ), i=l, 2,k,又(mi, mj) =1, ihj,从而 xl=x2 (modmi), i=l, 2, -k,

9、故解是唯一的，证毕。二、rsa系统一种应用非常广泛的密码系统，由rivest、shamir和 adi eman提出，就是如今被称为rsa的密码系统。rsa公钥 密码体制是基于大整数分解的公开密钥体制的代表算法。大 整数分解问题可以被表述为：已知整数n, n是两个素数p、 q的乘积，即n=pq,求解p和q的值。首先，回忆一下数论中的有关概念：设n是正整数用2 ( n ) =1 0wxaji=2, 3, -n成立时，有多项式解法。这样的序 列称为超递增序列。如1, 3, 6, 13, 27, 52是一个超递增 序列，而1, 3, 4, 9, 15, 25则不是。超递增背包问题的解是容易找到的。将总质量与序列中 最大的数比较，如果总质量小于这个数，则它不在背包中； 如果总质量大于这个数，则它在背包中，用背包质量减去这 个数，转向考察序列下一个最大的数，重复直到结束。如果 总质量变为零，那么有一个解，否则无解。背包公钥密码系统的实现方案就是选取一组正整数al, a2,，an作为公钥予以公布m=mlm2，mn,是n位0, 1 明文符号串。利用公钥加密如下：于是从超递增序列得此序列时，从外表上不再具有超递 增假定已知：参考文献：1 蔡乐才应