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

《数论在密码学中的若干应用.docx》由会员分享，可在线阅读，更多相关《数论在密码学中的若干应用.docx（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、应用最多的还是数论。此文的目的则是力求用最通俗的语言说明数论方法在现代密码学中的应用，而其对以后学习及深化探讨密码学相关理论都有特别重要的作用。 一、一种隐私共享方案 隐私是一种不公开的信息，自然也是语言。从数学角度看一个隐私就是一个字母S，古代曾有过在一个重要的铁门上锁三把锁，钥匙分别由三个人保存，只有三个人都到齐了才能开门的例子。现代密码学中也有类似的状况。早在11019年Shamir就提出了隐私共享的理论。在所谓门限隐私共享体制中，隐私被分成了n个份额，至少要驾驭t个份额才能获得这个隐私。为了搞清晰什么是隐私共享，我们先看一个我国古代“韩信点兵”中的数学问题。据说韩信在统计士兵的人数时用

4、到了这样一首诗： 三人同行七十三稀，五树梅花廿一枝。七子团聚正月半，除一百零一去五便得知。 这里“正月半”表示15，计算人数的方法是：3人一组，分列所剩的人乘以73；将5人一组，分列所剩的人数乘以21；将7人一组，分列所剩的人数乘以15，然后将以上三个结果相加再减去若干个105，就得到士兵的人数了。比如，若士兵3人一组站立剩一人，5人一组站立剩4人，7人一组站立剩3人，那么，士兵的人数为173+421+315-105=94。再如，若士兵人数被3，5和7除所得余数分别为2，4和5。则士兵人数可以从273+421+515=2101中减去1或2个105而求得。原委是减去105还是210，对统兵的人来

5、说是很简单的，因为他当然对有多少士兵是心中有数的。比如，统兵的人知道士兵的人数是1101，那么就应当从2101中减去1个105得出194，那么他就会发觉有3人缺席。假如士兵总共有90人，那么则要从2101中减去2个105得9，表明有1人缺席。简单看出，105是3，5和7的乘积。至于73，21和15是如何得到的，本文不予细说，因为我们的目的是介绍数论的这一方法在隐私共享策略中的应用。首先要留意，由已知某数被3，5和7去除所得的余数去求某数，只可能得出某数的可能值，比如在前面的其次个例子中，士兵的人数可能是194，也可能是89，再者是减去几个105还是加上几个105也是不能完全确定的。比如，在上例

6、中假如给出2101加上105所得的数404被3，5和7除的余数分别为2，4和5，再加几个105后分别得509，614，739等也是满意同样的条件。当然假如已知人数不超过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的数。那么这三个人中的每一个人都不

7、行以断定这个隐私究竟是什么。但假如这三个人现在在一起，就可以在肯定的条件下很简单得出来结果是89。一种隐私共享方案正是基于这种思想而得出来的。我们先把以上的数学方法加以推广。 下面是国际上通称的“中国剩余定理”，也可以称为“孙子剩余定理”或“孙子定理”，它的证明并不困难，我们演示如下： 孙子定理内容： 设m1，mk是两两既约的正整数，那么，对于随意的整数a1，ak一次同余方程组xaj，1jk必有解，且解数为1，事实同余方程组的解是xM1M1-1a1+MkMk-1ak 这里m=m1mk，m=mjMj，以及Mj-1是满意MjMj-11，1jk的一个整数 证：先证明解的存在性。 再证明解的唯一性：

8、若x1，x2是适合于同余式组的随意两个整数：x1bi，x2bi，i=1，2，k，所以x1x2，i=1，2，k，又=1，ij，从而x1x2，i=1，2，k，故解是唯一的，证毕。 二、RSA系统 一种应用特别广泛的密码系统，由Rivest、Shamir和Adleman提出，就是如今被称为RSA的密码系统。RSA公钥密码体制是基于大整数分解的公开密钥体制的代表算法。大整数分解问题可以被表述为：已知整数n，n是两个素数p、q的乘积，即n=pq，求解p和q的值。 首先，回忆一下数论中的有关概念：设n是正整数用=10xaji=2，3，n成立时，有多项式解法。这样的序列称为超递增序列。如1，3，6，13，2

9、7，52是一个超递增序列，而1，3，4，9，15，25则不是。 超递增背包问题的解是简单找到的。将总质量与序列中最大的数比较，假如总质量小于这个数，则它不在背包中；假如总质量大于这个数，则它在背包中，用背包质量减去这个数，转向考察序列下一个最大的数，重复直到结束。假如总质量变为零，那么有一个解，否则无解。 背包公钥密码系统的实现方案就是选取一组正整数a1，a2，an作为公钥予以公布m=m1m2，mn，是n位0，1明文符号串。利用公钥加密如下： 于是从超递增序列得此序列时，从外表上不再具有超递增假定已知： 参考文献： 1蔡乐才.应用密码学.北京：中国电力出版社，2022. 2章照止.现代密码学基础.北京邮电高校出版社，2004. 3刘木兰，龚奇敏.密码学进展.北京：科学出版社，19101. 4杨义先.现代密码新理论.北京：科学出版社，2002. 5潘承洞，潘永彪.初等数论.北京高校出版社，2003. 第6页 共6页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页