第4单元 公钥密码体制.pptVIP

主要内容 公钥密码体制的产生 数论基础 公钥密码体制的基本原理 RSA公钥密码体制 其它公钥密码算法 传统密码体制在应用中的缺陷 密钥管理的麻烦 密钥难以传输 不能提供法律证据 缺乏自动检测密钥泄密的能力 整 除 定理：设整数a和b，如果存在整数k，使b=ak，则说b能被a整除，记作：a|b 例：3|15，-15|60 性质： 对所有整数a≠0， a|0、 a|a成立 对任意整数b， 1|b成立 素数(prime number) 定义：如果整数p(p1)只能被1或者它本身整除，而不能被其他整数整除，则其为素数，否则为合数。 素数定理： 在各种应用中，我们需要大的素数,如100位的素数 素数是构成整数的因子，每一个整数都是由一个或几个素数的不同次幂相乘得来的。 最大公约数 a和b的最大公约数是能够同时整除a和b的最大正整数，记为gcd(a,b)。 如果gcd(a,b)=1，则说a和b是互素的。 定理： 设a和b是两个整数(至少一个非0)， d=gcd(a,b)，则存在整数x和y，使得ax+by=d 特殊地，如果a和b互素，则有整数x和y，使得ax+by=1 同余 设整数a，b，n(n ≠0)，如果a-b是n的整数倍，则a≡b(mod n)，即a同余于b模n。也可理解为a/n的余数等于b/n的余数。 (mod n)运算将所有的整数(无论小于n还是大于n)，都映射到{0,1,…,n-1}组成的集合。 模算术的性质： (a mod n) + (b mod n)= (a+b) mod n (a mod n) - (b mod n)= (a-b) mod n (a mod n) * (b mod n)= (a*b) mod n 性质 有整数a，b，c，n(n ≠0)： 如果a≡b(mod n)， b≡c(mod n) 那么a≡c(mod n) 如果a≡b(mod n)， c≡d(mod n) 那么a+c≡b+d， a-c≡b-d， ac≡bd (mod n) 计算117 mod 13 计算21234 mod 789 指数运算的优化 启示：如求x16，直接计算的话需做15次乘法。然而如果重复对每个部分结果做平方运算即求x，x2，x4，x8，x16则只需4次乘法。 求am可如下进行，其中a，m是正整数： 将m表示为二进制形式bk bk-1…b0，即 m=bk2k+bk-12k-1+…+b12+b0 因此 例如：23=1×24+0×23+1×22+1×21+1×20 a23 = ? 快速指数算法：(给定a,m) d=1； For i=k Downto 0 DO { d=(d×d) mod n; if bi=1 then { d=(d×a) mod n } } return d. 算法验证：例如 求7560 mod 561。 将560表示为1 0 0 0 1 1 0 0 0 0 迭代指数中间值(1 2 4 8 17 35 70 140 280 560） 算法的中间结果 ( 7 49 157 526…… 67 1) 所以7560 mod 561=1。 除法 设整数a，b，c，n(n ≠0)，且gcd(a,n)=1。 如果ab≡ac (mod n)，那么b≡c (mod n) 证明：∵ gcd(a,n)=1，∴有x和y，使ax+ny=1 两边同乘以(b-c): (b-c)(ax+ny)=b-c 即:(ab-ac)x+n(b-c)y=b-c ……① ∵ ab≡ac (mod n), 即ab=ac+k1n,∴ab-ac 是n的倍数 同时，n(b-c)y显然也是n的倍数 所以，:(ab-ac)x+n(b-c)y也是n的倍数，假设是k2倍 则①式变为：b-c= k2n 即b≡c (mod n) 欧几里德算法(Euclid) 用欧几里德算法求最大公约数。 求：gcd(482,1180) 1180=2*482+216 482=2*216+50 216=4*50+16 50=3*16+2 16=8*2+0 所以gcd(482,1180)=2 乘法逆元 如果gcd(a,b)=1，那么： 存在a-1，使a* a-1 ≡1 mod b 存在b-1，使b* b-1 ≡1 mod a 这里，把a-1称为a模b的乘法逆元， b-1称为b模a的乘法逆元 用扩展的欧几里德算法求乘法逆元 gcd(11111,12345) 12345=1*11111+1234 11111=9*1234+5 1234=246*5+4 5=1*4+1 4