■密钥的产生涉及求剩余类环的乘法逆 对任意的正整数n,Zn是交换环(剩余类环) 对Zn中任意一个元素,存在关于模n逆 元的条件是该数与n互质 ■用 Euclidean算法。 23:31:48
23:31:48 密钥的产生涉及求剩余类环的乘法逆 对任意的正整数n,Zn是交换环(剩余类环) 对Zn中任意一个元素，存在关于模n逆 元的条件是该数与n互质。 用Euclidean算法
2快速加密解密方法 然后先做预计算 C-=a·a =a-·a x-次乘法 ab=a+2b++2b-=a(a2)1…(a2)b 1b2=0 然后根据b=1取出相应的与其他项相乘,最多需r-次 乘法。故整个幂运算最多需要2r-2次模乘法运算,即 2logn1次模乘法运算。 23:31:48
23:31:48 2)快速加密解密方法 在RSA实现时，还要计算幂模ab mod n(0<b<n)，这就需要能够快速求幂模。 将 b 表示成二进制 b=br-12r-1+…b12+ b0(r=logn)，则有 1 1 1 0 1 1 0 1 ( ) ( ) 2 2 2 2 r r r r b b b b b b b a a a a a 1 1 0 ( ) 2 2 i b i a bb a i i i 然后先做预计算 1次乘法 1 2 2 2 2 2 4 2 2 2 r a a a a a a a a a r r r 然后根据bi=1取出相应的与其他项相乘，最多需r-1次 乘法。故整个幂运算最多需要2r-2次模乘法运算，即 2logn-2次模乘法运算
为了提高RSA算法的解密速度,解密时 可以按下面方法进行计算 ■■ 设密文c= me mod n,n=pq 设c1≡ c mod p,C2= c mod q, d=d mod(p-1), d2=d mod(q-1), m1≡C1modp, m2≡C2 mod go 、c2、d1和d2是容易计算的,由此可以 求得有m1和m2 ■由中国剩余定理解同余方程组m=m;mod p,m=m2modq,就可求出m ■该方法可提高解密速度4-8倍。 23:31:48
23:31:48 为了提高RSA算法的解密速度，解密时 可以按下面方法进行计算： 设密文c=m e mod n,n=pq 。 设 c 1 c mod p, c 2 c mod q, d 1 d mod (p-1), d 2 d mod (q-1), m 1 c 1 d1 mod p, m 2 c 2 d2 mod q 。 c 1 、 c 2 、 d 1 和 d 2是容易计算的，由此可以 求得有 m 1 和 m 2 。 由中国剩余定理解同余方程组 m m 1 mod p, m m 2 mod q,就可求出 m 。 该方法可提高解密速度4-8倍
3)中国剩余定理 称x= b,mod m为同余式方程,满足该式 的每个x都是该方程的解。 如对于同余式方程x=4mod7,对任意的 整数k,4+7k都是此方程的解。 ■需要求n个同余式方程x= b, mod m1,x≡ b2modm2,= bmod m的共同解,这 就是所谓的联立同余式问题。 ■该问题有共同解的充要条件是 (m,m)(b,b),这里词,i=1,2,…n 23:31:48
23:31:48 3)中国剩余定理 称xb1mod m1为同余式方程，满足该式 的每个x都是该方程的解。 如对于同余式方程x4mod 7，对任意的 整数k，4+7k都是此方程的解。 需要求n个同余式方程xb1mod m1,x b2mod m2,…,xbnmod mn 的共同解，这 就是所谓的联立同余式问题。 该问题有共同解的充要条件是 (mi,mj)|(bi,bj)，这里ij，i,j=1,2,…n
。定理A:若存在a,满足n个同余式为程、b modm(i=1,2,,n),即a= b mod m(i=1,2,…,n 则有a= b mod lcm(m1,m2,…,m) ■定理B(中国剩余定理):设m1,m2…,mn是两两 互素的正整数,则x=b; mod m(i=1,2,…,n)在模 mum m下有唯一解 ■证明:令M=mm2…mn,M=M/m,求y满足 My=1 mod m, Gi=1,2…n) ■因为(Mm)=1,故解y是存在的。 令x=b1M1y1+b2M2y2+…+ b,Myn modM。 证明该表达式就是x=b;modm(i=1,2,…m)在模 m1m2,mn下的解。 23:31:48
23:31:48 定理A：若存在a，满足n个同余式方程xb mod mi(i=1,2,…n)，即ab mod mi(i=1,2,…n)， 则有ab mod lcm(m1,m2,…,mn)。 定理B(中国剩余定理)：设m1,m2,…,mn是两两 互素的正整数，则xbimod mi(i=1,2,…n)在模 m1m2…mn下有唯一解。 证明：令M=m1m2…mn, Mj=M/mj,求yj满足 Mjyj1mod mj(j=1,2,…n)。 因为(Mj,mj)=1，故解yj是存在的。 令x=b1M1y1+b2M2y2+…+bnMnyn modM。 证明该表达式就是xbimod mi(i=1,2,…n)在模 m1m2…mn下的解