密码学基础课件：第十三讲 RSA.ppt

大整数的除法和模运算 0=a-q_{k-1}br^{k-1}br^{k-1} q_{k-1}=[a/br^{k-1}]（用减法处理） 为了求得其它q_{k-2},…,q_0，我们需要设R_0=a; R_i=r_{i-1}-bq_{k-i}r^{k-i};q_{k-i}=[R_i/br^{k-i}] 即R_1=a-bq_{k-1}r^{k-1}。。。 模运算 模运算就是取余例如 a=bq+R 那么a = R mod b 因此，模运算最简单的就是 [a/b]=q; a-b*q=R 大整数的欧几里得算法 设整数a,b，其中ab, d=gcd(a,b)表示a,b最大公约数则 d|a, d|b，而a=bq+R，即R=a-bq，所以d|R d|b,d|R，而b=Rq_1+R_1…….. AbRR_1…..，最终R_n=0. R_{n-2}=qR_{n-1},R_{n-1}即最小公倍数 在程序中使用a, b, R来递归计算 在b！=0时，计算a%b=R,然后a=b;b=R; 当b==0时，表明R_n为0，a的保存值为最小公倍数 大整数的欧几里得算法 对应到大整数，模运算用大整数的一般算法，赋值用大整数的赋值。 大整数的扩展欧几里得算法 gcd(a,b)=ax_n+by_n(可以通过反向递归验证) 然后： gcd(b,a mod b)=bx_{n-1}+(a mod b)y_{n-1} (即反向递归到最终结果的前一步) 那么，已知gcd(a,b)=gcd(b,a mod b)，可得 ax_n+by_n=bx_{n-1}+(a mod b)y_{n-1} =bx_{n-1}+(a-[a/b]*b)y_{n-1} =ay_{n-1}+b(x_{n-1}-q_ny_{n-1}) ?x_n=y_{n-1};y_n=x_{n-1}-q_ny_{n-1} 大整数的扩展欧几里得算法 所以我们看到： x_n=y_{n-1} y_n=x_{n-1}-q_ny_{n-1} 那么初值是多少？ 考虑GCD算法最后第二步步R_{n-2}=qR_{n-1}， Gcd(R_{n-2},R_{n-1})=0*R_{n-2}+1*R_{n-1} Gcd(R_{n-1},R_{n-1}})=1*R_{n-1}+0*R_{n-1} 所以初值x_0=1;y_0=0; 大整数的扩展欧几里得算法* 欧几里得： a=bq_1+r_1 b=r_1q_2+r_2 r_1=r_2q_3+r_3 … r_{n-3}=r_{n-2}q_{n-1}+r_{n-1} r_{n-2}=r_{n-1}q_{n} 扩展算法： r_1=a-bq_1 r_2=b-(a-bq_1)q_2 r_3=(a-bq_1)-(b-(a-bq_1)q_2)q_3 …. r_{n-1}=x_na+y_nb 大整数的扩展欧几里得算法* 假设存在x_n，y_n序列，那么第k-2,k-1，k步成立： r_{k-2}=x_{k-1}a+y_{k-1}b; r_{k-1}=x_ka+y_kb r_k=x_{k+1}a+y_{k+1}b 由欧几里得算法，又有 r_k=r_{k-2}-r_{k-1}q_k ?r_k= x_{k-1}a+y_{k-1}b-(x_ka+y_kb)q_k =(x_{k-1}-q_kx_k})a+(y_{k-1}-y_kq_k)b ?x_{k+1}=x_{k-1}-q_kx_k; y_{k+1}=y_{k-1}-y_kq_k 大整数的扩展欧几里得算法* 已知，如果有x_n,y_n序列，满足 x_{k+1}=x_{k-1}-q_kx_k; y_{k+1}=y_{k-1}-y_kq_k 由r_1=a-bq_1 可知x_2=1,y_2=-q_1； x_2=x_0-q_1x_1; y_2=y_0-y_1q_1 ?y_0=0;y_1=1; ?x_0=1,x_1=0 这两组初值对应平凡等式(a=a,b=b) a=x_0*a+0*b; b=x_1*a+y_1*b 大整数的扩展欧几里得算法* 结论： x_{k+1}=x_{k-1}-q_kx_k; y_{k+1}=y_{k-1}-y_kq_k y_0=0;y_1=1; x_0=1,x_1=0 正确性： 可以通过第二数学归纳法归纳证明 32*9=288;319-288=31 * 0=a-bxx 除法的本质就是把a那么多橘子按照x个橘子一堆来分，可以分几堆，余几个？例如12个橘子3个3个分，可以分12/3=4堆，4就是商数。 经过测试，0到2^32遍历时间是1.5秒左右，不执行任何操作。所以大整数运算中的基过大应该不利于除法的计算。 * 注意q_{n-1} 这里是网上的一个算法，结果并不是很好，因为需要完全的商序列才能计算，所以看着玩。 * 这个