非对称加密算法的研究与设计论文终稿

华北科技学院毕业论文

(1)如果T是+1或-1，那就说明n是一个强伪素数并且要停止检验。我们知道n已经通过了两次检验，Fermat检验和平方根检验。原因是什么呢？因为，如果T是??，T在下一步中就是1，并一直保持是1直到通过Fermat检验。此外，T还通过了平方根检验，因为在接下来的一步中，T总是1，并且1的平方根(在下一步中)是±1(在这一步中)。

(2)如果T是别的值，我们就不能确定n是素数还是复合数，所以我们就要进入下一步运算。

步骤1： 我们把T平方。

(1)如果结果是+1，我们知道肯定会通过Fermat检验，因为在后面的步骤中，T仍然保持是1。不过，这不能通过平方根检验。因为在这一步中T是1，并且在前面的步骤中T是除??之外的别的值(这也正是我们在前面的步骤中没有停下来的原因)，我们宣布n是一个复合数并停止检验。

(2)如果结果是-1，我们知道n最终会通过检验。我们也知道它还会通过平方根检验，因为在这一步中T是-1，并且在下一步中是1。我们就宣布n是强伪素数并停止检验。

(3)如果T是除此以外的其他任意数，我们就不能确定有没有一个素数。这样我们就要进入到下一步。

步骤2到步骤k - 1：

这一步以及直到k??1步的所有步骤与步骤1相同。 步骤k：

这一步是不需要的。如果我们已经到达这一步并且还没有作出决定，这一步对我们就没有什么用。如果这一步的结果是1，通过了Fermat检验，但是，因为前面几步的结果不是±1，没有通过平方根检验。步骤k ???之后，如果我们还没有停止，我们就宣布n是复合数。Miller-Rabin检验需要从步骤0到步骤k ???。 2.4.3推荐的素性检验

今天，最受欢迎的素性检验就是把整除性检验和Miller-Rabin检验结合起来。下面就是推荐的步骤：

(1)选择一个奇数，因为所有的偶数(除2外)肯定都是复合数。

第29页共62页

非对称密码学加密算法的研究与设计――RSA算法的程序设计

(2)对已知素数3、5、7、11、13等等做一些普通的整除性检验，以确保你不是在处理一个明显的复合数。如果数字通过了所有这些检验，就进行下一个步骤。如果数字在通过这些检验的任意一个时失败了，再返回到步骤1并选择另一个奇数。

(3)选择一个基数集合检验。一个大的基数集合更为适合。

(4)对基数中的每一个进行Miller-Rabin检验。如果基数中的某一个检验失败，就要返回到步骤1并选择另一个奇数。如果所基数的检验都通过了，就宣布这个数是一个强伪素数。

2.5因数分解

过去因数分解一直都是我们研究的一个主题，这种研究很可能在将来还要继续下去。因数分解在几种公钥加密系统中起着非常重要的作用。 2.5.1算术基本定理

根据算术基本定理，任意一个大于1的正整数都能分解成唯一的下面的素数因数乘

e2ek?…?pk积形式，其中p1，p2，?????是素数，e1，e2，???ek是正整数。n?p1e1?p2因数

分解有一些直接应用，如最大公约数的计算与最小公倍数的计算。

? 最大公约数

在之前讨论了两个数的最大公约数gcd(a，b)。现在我们可以回忆一下Euclidean算法给出这个值的方法。不过，如果我们已经知道a和b的因数分解结果，也可以不用Euclidean算法，直接用a和b的因数分解结果求出这个值。

? 最小公倍数

最小公倍数lcm(a，b)，就是a和b的所有公倍数中的最小整数。运用因数分解，我们也能求出lcm(a，b)。gcd(a，b)和lcm(a，b)是相互联系的。 2.5.2因数分解方法

对于分解大复合数的有效算法，已经研究了很长时间。遗憾的是，至今人们还没有找到一种有效的算法。虽然有几种算法可以分解一个数成素因数积的形式，但没有一种可以在合理的计算时间内完成对一个很大的数进行因数分解。在后面我们将会了解到，这对于加密来说其实是件好事，因为现代加密术依赖于这个数学事实。在这一部分中，我们给出一些分解复合数的简单算法，目的是解释因数分解的过程其实就是时间消耗的过程。

? 试除法

第30页共62页

华北科技学院毕业论文

到目前为止，最简单但效率最低的算法就是试除因数分解法。我们用所有正整数试验一下，从2开始进行试除，逐步增加除数的值，去寻找一个可以整除n的数。在Eratosthenes筛法的讨论中，我们知道如果n是一个复合数，那么它就会有一个素数p??。这个算法有两个偱环路径，外部的和内部的。外部循环求唯一因数，内部循环求一个因数的多个复本。例如，24=23×3，外部循环求出因数2和3。内部循环求出2是一个多因数。

? 复杂度

如果n<210，这种情况下试除法通常都是很有效的。但是如果用来分解更大的整数，试除法就变得非常低效甚至不可用了。这种算法的复杂度是随着n的增加呈指数级别增长的。

2.5.3 Fermat方法

Fermat因数分解方法把一个数n分解成两个正整数a和b(不一定是素数)，使得

n=?a?b。Fermat方法基于这样一个事实，即如果我们可以求出x和y，使得n=x2??y2，那么我们就有n=x2 -y2=a??b其中a=(x+y)和b=(x-y)。

这种方法试图求出两个非常接近的整数a和b(a?b)。从大于x=

的最小整数开

始，尝试求出另一个整数y使得关系y2=x2-n成立。在每一次迭代中，我们需要了解x2??n是不是一个完全平方数。如果我们求出这样一个y值，我们就算出a和b并且从运算环路中脱离；否则，我们就要完成另一个迭代。注意，并不是要求必须一步就把一个数分解成素数的积，而是对每一步求出的a和b的每一个值，算法必须要进行递归重复直到求出素因数。现在还有一些更有效的方法，如二次筛选法、数字域方法，这里就不作介绍了

2.6中国剩余定理

中国剩余定理(CRT)用来解决一组带有两两互素数的一个变量和不同模的同余方程。中国剩余定理表明，如果模互素，上述方程具有唯一的解。要注意，即使模不是相关素数但适应另一种条件，方程组也可以只有一个解。不过在密码学中，我们只对运用互素的模解方程有兴趣。

中国剩余定理在密码学中有几种应用。一种应用是解二次同余方程，像在下一部分中讨论的那样；另一种是根据一列小整数，提出一个非常大的整数。

2.7指数与对数

第31页共62页

非对称密码学加密算法的研究与设计――RSA算法的程序设计

指数和对数是互逆的。下面就表示出了它们之间的关系，其中a称为指数或对数的底数。指数y =ax →对数:x=logay 2.7.1 指数

在密码学中，一个普通的模运算是指数的，即我们通常要计算：y?axmodn，我们将在讨论的RSA密码系统，运用指数非常大的求幂运算进行加密和解密。遗憾的是，大多数计算机语言还没有可以有效计算求幂的算符，特别是当指数很大的时候更是如此。为了使这类计算更为有效，我们就需要有更有效的算法。

快速求幂运用平方乘方法是可能的。在传统算法中，只用乘法来模拟求幂，但是，快速求幂算法既运用平方也运用乘法。这种方法的主要想法就是把指数当作nb比特(x?到xnb??1)的二进制数来处理，例如x=22=(10110)2。

注意，y是nb项的乘积。每一项既是1(如果相关的比特是0)也是a2i(如果相关的比特是1)。也就是说，如果比特是1，a2i这一项包含在乘积当中；如果比特是0(乘以1是没有作用的)，就不包含在乘法当中。我们可以对底数连续平方，a，a2，a4??a2nb?1。如果相关的比特是0，这一项就不包括在乘法过程中；如果比特是1，就包括在乘法过程中。

选择性算法，注意算法左到右(最不重要的到最重要的)检验了x中比特的值。运用相反的阶次就可以写出一个算法。因为平方运算是完全独立于乘法运算的，我们就选出了上述算法。它们可以做并行，在提高过程速度的同时就能完成这些运算。 2.7.2对数

在密码学中，我们也需要讨论模对数。如果我们运用指数运算来加密和解密，对手就可以运用对数进行攻击。我们需要知道指数运算的逆运算的难度。

我们可能会想起的第一种解决办法就是解x=logay (mod n)。我们可以写一个算法继续计算y?axmodn，直到求出给定的y的值。详细分析见第三章的3.2加解密过程及算法分析。

2.8分治法基本思想

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。

第32页共62页