文档介绍：第4章 公钥密码体制
主要内容
公钥密码体制的产生
数论基础
公钥密码体制的基本原理
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(p>1)只能被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
除法
设整数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