第4章公钥密码体制

第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或者它本身整除，而 不能被其他整数整除，则其为素数，否则为合数。 素数定理：

设 ( x)是小于x的素数的个数,则 x ( x) ( x) , 且当x , 1 x ln x ln x

在各种应用中，我们需要大的素数,如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

同余≠0),如果a-b是n的整数倍， 则a≡b(mod n),即a同余于b模n。也可理解为 a/n的余数等于b/n的余数。 (mod n)运算将所有的整数(无论小于n还是大 于n),都映射到{0,1, ,n-1}组成的集合。 模算术的性质： 设整数a,b,n(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

性质

有整数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

乘法逆元 如果gcd(a,b)=1,那么：

≡1 mod b 存在b-1,使b* b-1 ≡1 mod a 这里，把a-1称为a模b的乘法逆元， b-1称为b 模a的乘法逆元 存在a-1,使a* a-1

用扩展的欧几里德算法求乘法逆元

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*(1234-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

费尔马小定理 (Fermat) 如果p是一个素数,a不是p的倍数，

则：ap-1≡1 (mod p) 证明：设有一整数空间S={1,2,…,p-1} 再设有一函数Ψ (x)=ax(mod p) x∈S (1)对于任何x∈S,有Ψ (x)∈S (2)对于x和y(x≠y),有Ψ (x)≠Ψ (y) (3)根据乘法定理和除法定理 (p-1)!ap-1≡(p-1)! mod p

欧拉函数 Ф(n):小于n且与n互素的正整数的个数 显然，对于素数p,有Ф(p)=p-1 设有两个素数p和q,p

≠q,那么对于n=pq, 有： Ф(n)= Ф(pq)= Ф(p)* Ф(q) =(p-1)*(q-1)

欧拉定理(Euler)对于任意互素的a和n,有aФ(n) ≡1 mod n 证明：对于整数n,与n互素的数有Ф(n)个：

令这些数为：R={x1, x2, …,x Ф(n) } 用a与R中的每个元素相乘模n,得到集合S:

S ={ax1 mod n, x2 mod n, …,x Ф(n) mod n } 其实S就是R: (ax1 mod n) ∈ R

S中的元素是唯一的

那么：R中各元素相乘就等于S中各元素相乘：

x ax mod ni 1 i i 1 i

( n)

( n)

离散对数≡1 mod n 也就是说，至少存在一个整数m,使am ≡1 mod n成立 m 使得成立a ≡1 mod n的最小正幂m,称为a的阶、a

由Euler定理可知，互素的a和n,有aФ(n)

所属的模n的指数，或a所产生的周期长。

本原根：如果使得am

≡1 mod n成立的最小正幂m:

m=Ф(n),则称a是n的本原根。