《第4章公钥密码体制》由会员分享，可在线阅读，更多相关《第4章公钥密码体制（74页珍藏版）》请在金锄头文库上搜索。
1、第4章 公钥密码体制,主要内容,公钥密码体制的产生 数论基础 公钥密码体制的基本原理 RSA公钥密码体制 其它公钥密码算法,传统密码体制在应用中的缺陷,密钥管理的麻烦 一个拥有10万用户的民用密码通信网就要拥有近50亿个密钥。 密钥难以传输 不能提供法律证据 信息的证实是指两个方面：一方面是指对发送方的证实，另一方面是指对接收方的证实， 也就是能够确认接收方所收到和保存的信息确实是由发送方发出的。既不是伪造的，也没有经过包括接收方在内的其他人所篡改。 缺乏自动检测密钥泄密的能力,4.1 公钥密码体制的产生,1976年由当时在美国斯坦福大学的迪菲（Diffie）和赫尔曼(Hellman)发表了“
2、New Direction in Cryptography”论文，第一次提出了公钥密码体制的概念。从此开创了密码学的新时代。 自1976年以来，已经提出了多种公钥密码算法，其安全基础是基于一些数学问题， 专家们认为这些问题在短期内不可能得到解决，因为一些问题（如因子分解问题）至今已有数千年的历史。,4.2 数论基础,数论中的许多概念在设计公钥密码算法时是必不可少的。掌握这些基础知识对于理解公钥密码体制的原理和应用十分重要。,整 除,定理：设整数a和b，如果存在整数k，使b=ak，则说b能被a整除，记作：a|b 例：3|15，-15|60 性质： 对所有整数a0， a|0、 a|a成立 对任意整
3、数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,同余,设整
4、数a，b，n(n 0)，如果a-b是n的整数倍，则ab(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 mod n) * (b mod n) (a*b) mod n,设x= a mod n，y= b mod n。 即a=x+k1n，b=y+k2n，k1和k
5、2为整数。 也就是： x=a-k1n，y=b-k2n 那么： (a mod n) (b mod n) =xy= (a-k1n) (b-k2n) =ab+(-ak2-bk1+k1k2n)n。 因为a，b，k1，k2，n皆为整数，所以 (-ak2-bk1+k1k2n)=K也是整数，即： (a mod n) (b mod n)=ab+Kn， 即(a mod n) (b mod n) (ab) mod n。 得证。,性质1,有整数a，b，c，n(n 0)： 如果ab(mod n)， bc(mod n) 那么ac(mod n) 证明： 因为ab(mod n)，bc(mod n)， 即a=b+k1n，b=
6、c+ k2n， 所以a=c+ k2n+k1n=c+(k1+ k2)n， 即a等于c加上n的整数倍，即ac(mod n)。,性质2,有整数a，b，c，n(n 0)： 如果ab(mod n)， cd(mod n) 那么a+cb+d， a-cb-d， acbd (mod n),计算117 mod 13,没有必要先计算117，然后除以13求余数。,如果ab(mod n)， cd(mod n)，则acbd (mod n),计算21234 mod 789,除法,设整数a，b，c，n(n 0)，且gcd(a,n)=1。 如果abac (mod n)，那么bc (mod n) 证明： gcd(a,n)=1，有
7、x和y，使ax+ny=1 两边同乘以(b-c): (b-c)(ax+ny)=b-c 即:(ab-ac)x+n(b-c)y=b-c abac (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 即bc (mod n),4.2.2 欧几里德算法(The Euclidean Algorithm ),用欧几里德算法求最大公约数。欧几里德算法基于以下的定理：对于任意非负整数a和任意正整数b，有： gcd(a,b)=gcd(b,a mod b) 求：gcd(48
8、2,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,4.2.3 乘法逆元,如果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=4*1+0 1=5-1*4=5-1*(1
9、234-246*5)=247*5-1*1234 =247*(11111 - 9*1234) -1*1234 =247*11111 - 2224*1234 =247*11111 - 2224*(12345 -1*11111) =2471*11111 - 2224*12345,中国剩余定理(The Chinese Remainder Theorem),我国古代数学名著孙子算经中，记载这样一个问题： “今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何。” 明朝数学家程大位把这一解法编成四句歌诀：三人同行七十（70）稀，五树梅花廿一（21）枝， 七子团圆正月半（15）， 除百零五（1
10、05）便得知。歌诀中每一句话都是一步解法：第一句指除以3的余数用70去乘；第二句指除以5的余数用21去乘；第三句指除以7的余数用15去乘；第四句指上面乘得的三个积相加的和如超过105，就减去105的倍数，就得到答案了。即： 7022131521052=23,中国剩余定理是指若有一些两两互素的整数m1,m2,.,mn，则对任意的整数：a1,a2,.an，以下联立同余方程组对模m1*m2*.*mn有公解：,4.2.4 费尔马小定理 (Fermats Theorem),如果p是一个素数,a不是p的倍数， 则：ap-11 (mod p) 证明： 设有一整数空间S=1,2,p-1 再设有一函数(x)=a
11、x(mod p) xS (1)对于任何xS，有(x)S (2)对于x和y(xy),有(x)(y) (3)根据乘法定理和除法定理 (p-1)!ap-1(p-1)! mod p,4.2.5 欧拉函数和欧拉定理,(n)：小于n且与n互素的正整数的个数 显然，对于素数p，有(p)=p-1 设有两个素数p和q，p q，那么对于n=pq，有： (n)= (pq)= (p)* (q) =(p-1)*(q-1),欧拉定理(Eulers Theorem),对于任意互素的a和n，有a(n) 1 mod n 证明：对于整数n，与n互素的数有(n)个： 令这些数为：R=x1, x2, ,x (n) 用a与R中的每个元
12、素相乘模n，得到集合S： S =ax1 mod n, ax2 mod n, ,ax (n) mod n 其实S就是R： (ax1 mod n) R S中的元素是唯一的 那么：R中各元素相乘就等于S中各元素相乘：,4.2.6 离散对数(Discrete Logarithms),由Euler定理可知，互素的a和n，有a(n) 1 mod n 也就是说，至少存在一个整数m，使am 1 mod n成立 使得成立am 1 mod n的最小正幂m，称为a的阶、a所属的模n的指数，或a所产生的周期长。 本原根：如果使得am 1 mod n成立的最小正幂m： m=(n)，则称a是n的本原根。,71 mod 1
13、9=7 72 mod 19=11 73 mod 19=1 74 mod 19=(7173) mod 19=71=7 75 mod 19=11,本原根的性质,如果a是n的本原根，且： x1=a1 mod n，x2=a2 mod n，x(n)=a(n) mod n 则： x1x2x(n)，且x(n)=1 特别的：对于素数p，若a是p的本原根，则： (a1 mod p)(a2 mod p)(ap1 mod p)。,指标,某素数p，有本原根a，且： x1=a1 mod p， x2=a2 mod p ， xp-1=ap-1 mod p ， 则：x1x2 xp-1 令：S=x1,x2, xp-1，P=1,
14、2,p-1 则：S=P 对于任意整数b，有br mod p (0rp-1) 所以，对于b和素数p的本原根a，有唯一的幂i，使得： bai mod p ， 0ip-1 指数i称为a模p的b的指标，或称离散对数,记为inda,p(b),指标的性质,inda,p(1)=0 inda,p(a)=1 乘法性质 inda,p(xy)inda,p(x)+ inda,p(y) mod (p) 幂性质 inda,p(yr)r inda,p(y) mod (p),离散对数的计算,对于方程y=gx mod p 给定g,x,p,计算y比较容易。 但给定y,g,p,求x非常困难。X=indg,p(y) 其难度与RSA中
15、因子分解素数之积的难度有相同的数量级。,4.3 公钥密码体制(Public key system) 的基本原理,公钥密码学与其他密码学完全不同： 公钥算法基于数学函数而不是基于替换和置换 使用两个独立的密钥 公钥密码学的提出是为了解决两个问题： 密钥的分配 数字签名 1976年Diffie和Hellman首次公开提出了公钥密码学的概念，被认为是一个惊人的成就。,characteristic of algorithms,It is computationally infeasible to determine the decryption key given only knowledge of
16、the cryptographic algorithm and the encryption key. Either of the two related keys can be used for encryption, with the other used for decryption.,A public-key encryption scheme has five ingredients.,Plaintext: This is the readable message or data that is fed into the algorithm as input. Encryption algorithm: The encryption algorithm performs various transformations on the plaintext. Public and private keys: This is a pair of keys that have
