文档介绍：第四章公钥密码体制?公钥密码又称为双钥密码和非对称密码, 是 1976 年由 Diffie 和 Hellman 在其“密码学新方向”一文中提出的,见划时代的文献: and , New Directrions in Cryptography, IEEE Transaction on Information Theory, -, Nov 1976, -654 ? RSA 公钥算法是由 Rivest,Shamir 和 Adleman 在 1978 年提出来的, munitions of the ACM. . Feb. 1978, -126 数论简介 ?称整数是素数,如果 p的因子只有。?整数的唯一分解定理:任一整数都可以分解成以下的形式: 1,p北 1 2 1 2 tt a p p p a a a =L p其中 1 2 , t p p p > > > L 0, 1,2, , . i i t a 3 = L ?称c是两个整数的最大公因子,如果 。 c的因子。用c= gcd (a,b)表示。若 gcd (a,b)= 1,称 a和b互素。模运算设n是正整数, a是整数,如果用 n除a所得的商位 q,余数位 r,即用 a mod n 表示余数 r,称 a模n的余数为 r,记为 a= r mod n 。如果 a mod n = b mod n ,则称 a和b模n同余。显然,所有整数在模 n同余的意义下划分为 n个等价类, 记为{0,1, …,n-1} 。 a qn r = + nZ= 在该等价类上定义的加法和乘法运算分别称为模加法和模乘法运算。定义如下: [( m od ) ( m od )]m od ( )m od [( m od ) ( m od )]m od ( )m od [( m od ) ( m od )]m od ( )m od a n b n n a b n a n b n n a b n a n b n n a b n + = + - = - ′ = ′ ?如果称a为b的模加法逆元。例如: 2 mod 6 + 4 mod 6 = 0 mod 6 ?如果称a为b的模乘法逆元。例如对于模加法运算,任何元素皆有逆元。而对于模乘法运算,同余类中不是每一个元素皆有逆元。例如: 2 在中无逆元, 但是我们有下面的定理。[( m od ) ( m od )]m od 0m od a n b n n n + = [( m od ) ( m od )]m od 1m od a n b n n n ′ = [(2mod5) (3mod5)]mod5 1mod5 ′ = 8Z 定理:设,,则 a在中有乘法逆元。证明:首先证明。设是中任何两个不相同的数,如果,则存在两个正整数,使得于是,而所以 a是的因子,不访设于是。但为中的元素,所以,得证。由必存在一个整数 b使得。 n a Z ? gcd( , ) 1 a n = nZ | | | | n n aZ Z = , b c nZ m od m od a b n a c n ′ = ′ 1 2 , k k 1 2 , ab k n r ac k n r = + = + 1 2 ( ) ( ) a b c k k n - = - gcd( , ) 1 a n = 3 1 2 ( ) ak k k = - 1 2 ( ) k k - 3 b c k n - = , b c nZ b c = 1m od ab n = Fermat 定理?Fermat 定理: p 素数,a是整数且不能被 p整除,则: a p-1? 1 mod p ?证明: 考虑集合{1,2, …,p-1}, 对每个数乘以 a,得到集合{a mod p,2a mod p, …,(p-1)a mod p}, 对于 p,后者两两不同且都