第5章节RSA公钥密码体制课件(1020KB).pptVIP

5.10 RSA在有限域Fp上多项式上的推广 1.最高公因式的概念 2.同余 3.完全剩余系 4.缩系 5.欧拉函数 * 定理5.32 设f(x)是Fp上的n次多项式,其标准分解为 为不可约多项式,且 的次数为 则有 * 5.10.2 RSA在Fp上的多项式上的推广 * * Fp上的多项式相乘，就是求Fp上的序列的卷积，它也可用快速数论变换来计算．然而，Berlekamp曾经给出Fp[x]上n次多项式分解的算法,其计算量为 ,这样对给定的p而言,这一算法确实给出了Fp[x]多项式分解的多项式算法,因此,这个密码体制是不安全的.但当p很大时,实际分解Fp[x]上的多项式依然十分困难,因此,仍可以构作安全的密码体制.这个例子告诉我们,理论上,可以认为具有多项式时间的算法是有效的,但在实际问题中往往不是这样. * 有两组B-数可以用于Fermat因数分解法,即 5.7.2连分数因数分解法 1.连分数递推公式 首先介绍任一实数,构造它的连分数表示式的步骤,即x表示为 连分数的有关性质 连分数因数分解法 (4)用数-1和满足以下条件的素数p组成因数基:p能整除两个以上的 ,或者,某个 的标准分解式中含有p的偶数次幂; (5)从 中选出所有的B-数,象Fermat因数分解法一样,试图求出n的真因数. 上述用连分数寻求B-数,并且将n分解因数的方法,称为连分数因数分解法. * 二次筛法 1983年,Pomerance提出了分解整数的二次筛法.它是连分数方法的改进.二次筛法的第一步仍然是选定一组因子基,然后通过在因子基上分解二次多项式 来寻找s,t,满足 从而分解n,当p是奇素数时,存在整数x使 当且仅当 * 二次筛法的计算过程为: 1)对每个因子基中的素数p,用p去除 对能被p整除的那些值,求出 (因子基中所选的素数p必须使得p至少整除其中一个Q(x)). 2)如果有x使 ,则 ,所以其后第kp个值自动地被p整除,k=1,2,3,… 3)用1)和2)对Q(x)进行”筛选”,直到这些值最后完全被分解,其所有素因子在因子基中 * 4)筛法不仅可以对 进行,也可以对更一般的二次多项式(ax+b)^2-n进行,这样就可以把计算工作分散到不同的计算机上去做. 5)最后,给出相应的F2上的指数向量,得到一个F2上的 矩阵,求出其线性相关部分. 例:用二次筛法分解n=4033. 对于 的奇素数中,除开5,11外,均有Lengdre符号为1,取因子基为2,3,7,13,17,19. * * 最后4033=37*139. 二次筛法比连分数方法的分解速度更快一些,1994年众多的计算数论专家,利用Internet网共同分解了在1977年提出的一个有关RSA的129位数,它是一个64位的素数和一个65位素数的乘积,其分解算法就是用的二次筛法,其因子基有524339个素数,最后经过处理的F2上的矩阵仍然相当大,有188346行和188146列,但最终分解成功. 5.7.4 p-1方法 我们下面将介绍1974年提出的Pollard的p-1方法. 算法如下:输入n和B. (1)a=2; (2)对j=2到B做 (3)d=gcd{a-1,n}; (4)若1dn,那么d是n的因子,否则失败. 它有两个输入,待分解的奇整数n,界B.下面就是在p-1算法中将出现的情况:假设p是n的素因子,且对每个满足 的素数幂q,有 那么它必有 . 在第2)步for循环结束时 ,而 所以 所以p=gcd{a-1,n}. 例5.21设n如果使用B=180的p-1算法,那么发现在第3)步中a=11620221425,计算出的d为135979,n的完全分解为135979*115979. 因为135978仅有小的素因子135978=2*3*131*173,因此只要B=173,将会给出分解. RSA存在以下两种攻击，并不是因为算法本身存在缺陷，而是由于参数选择不当造成的。 1. 共模攻击 在实现RSA时，为方便起见，可能给每一用户相同的模数n，虽然加解密密钥不同，然而这样做是不行的。 5.8对RSA中小指数的攻击 设两个用户的公开钥分别为e1和e2，且e1和e2互素（一般情况