《公钥密码》由会员分享，可在线阅读，更多相关《公钥密码（79页珍藏版）》请在金锄头文库上搜索。
1、第四章 公钥密码体制l公钥密码又称为双钥密码和非对称密码 ，是1976年由Diffie和Hellman在其“密 码学新方向”一文中提出的，见划时代 的文献：W.Diffie and M.E.Hellman, New Directrions in Cryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654lRSA公钥算法是由Rivest,Shamir和 Adleman在1978年提出来的, 见Communitions of the ACM. Vol.21.No.2. Feb. 1
2、978, PP.120-126数论简介n素数n模运算n费尔玛定理和欧拉定理n素性检验n欧几里得算法n中国剩余定理n离散对数n平方剩余素数和互素数n称整数 是素数，如果p的因子只有 。n整数的唯一分解定理：任一整数都可以分解成以下 的形式：其中l 称c是两个整数的最大公因子，如果1. c是a和b的公因子。2. a和b的任一公因子也是c的因子。用cgcd（a，b）表示。若gcd（a，b）1，称a和b互素。模运算设n是正整数，a是整数，如果用n除a所得的商位q， 余数位r，即用a mod n表示余数r，称a模n的余数为r，记为ar mod n。如果a mod n b mod n，则称a和b模n同余。
3、显然，所有整数在模n同余的意义下划分为n个等价 类,记为 0,1,n-1。在该等价类上定义的加法和乘法运算分别称为模加法和模乘法运 算。定义如下： 如果称a为b的模加法逆元。例如：2 mod 64 mod 60 mod 6 如果称a为b的模乘法逆元。例如对于模加法运算，任何元素皆有逆元。而对于模乘法运算，同余类中不是每一个元素皆有逆元。例如：2 在 中无逆元,但是我们有下面的定理。定理：设 ， ，则a在 中 有乘法逆元。 证明：首先证明 。 设 是 中任何两个不相同的数，如果，则存在两个正整数 ，使得 于是 ，而 所以a是 的因子，不访设 于是 。但 为 中的元素，所以 ，得证。 由必存在一个
4、整数b使得 。Fermat定理Fermat定理: p素数,a是整数且不能被p整除,则: ap-1 1 mod p证明: 考虑集合1,2,p-1,对每个数乘以a,得到集合 a mod p,2a mod p,(p-1)a mod p,对于p,后者两两 不同且都在1与p-1之间,因此两个集合相同,于是:(p-1)! = 12(p-1) (a mod p)(2a mod p)(p-1)a mod p) mod p a2a(p-1)a mod p ap-1(p-1)! mod p 注意到(p-1)!与p互素,因此定理成立.推论: p素数,a是任意整数,则: ap a mod pEuler数Euler数(
5、n)定义为小于n且与n互素 的正整数个数.p是素数,(p)=p-1若n的因子分解为n=Piai, ai0,Pi 互不相同,则(n)= Piai(1-1/Pi)Euler定理若gcd(m,n)=1,则 (mn)=(m)(n),特别地,若pq且 都是素数, (pq)=(p-1)(q-1)Euler定理: 若a与n为互素的正整数 ,则: a(n) 1 mod nEuler数和Euler定理欧拉定理：a (n) 1 (mod n)其中： a和n必须是互素的； (n) =n(1-1/p1)(1-1/p2)(1-1/pn) p1,p2,pn是n的素数因子(n) 是n的欧拉函数，它确定1,2,n中有多少个是
6、与n互 素的。例如：20=225，有两个素数2和5，这样，(20) =20(1-1/2)(1-1/5)=8 即20中有8个整数与20是互素的，即它们没有2或5为因子： 1, 3, 7, 9, 11, 13, 17, 19Euler定理证明a(n) 1 mod n证明: R=x1,x2,x(n)为所有小于n且与n互素的正整 数,考虑集合 S=(ax1mod n), (ax2mod n), (ax(n) mod n) (aximod n)与n互素 (aximod n)两两不等: (aximod n) = (axjmod n) ximod n = xjmod nS有(n)个元素n故S也是所有小于n且
7、与n互素的正整数 ,因此S=R,从而 xi=(a ximod n) (a xi) mod n (a(n) xi) mod nn注意到xi 与n互素,从而得到结论.Euler定理推论推论: 若n=pq, pq都是素数, k是任意整数,则 mk(p-1)(q-1)+1 m mod n, 对任意0mn 证明:若m与n互素,注意到(n)=(p-1)(q-1),由Euler定理 可得到结论;否则m必定是p或者q的倍数,不妨设m=sp, 则0sq为正整数,m与q互素,由Euler定理得到:m(q) 1 mod q (m(q)k(p) 1 mod q mk(p-1)(q-1) = tq+1 t是整数 等式两
8、边乘以m=sp,得到:mk(p-1)(q-1)+1 = (tq+1)sp = tspq+sp m mod n检测素数直接判断一个整数是否为素数是困难的命题: 如果p是素数,则方程 x2 1 mod p 只有平凡解x 1 mod p.证明: x2 1 mod p p|(x2-1) p|(x+1)(x-1) p|(x+1),或者p|(x-1) x+1=kp,或者x-1=jp, k,j是整数 x=kp-1,或者x=jp+1 x 1 mod p, 或者x -1 mod p若方程x2 1 mod p存在的解不是x 1 ，则P不是 素数。(2)目前还没有一个高效的办法，实际中应用最多 Miller and
9、 Rabin, WITNESS算法 WITNESS(a,n) 判定n 是否为素数，a是某些小于n的整数1. 令bkbk-1b0 为(n-1)的二进制表示， 2. d 1 3. for i k downto 0 4.do x d 5.d (d d) mod n 6.if d = 1 and x 1 and x n-1 7. then return FALSE 8.if bi = 1 9. then d (d a) mod n 10. if d 1 11. then return FALSE 12. return TRUE 返回值： TRUE: n可能是素数 FALSE: n一定不是素数应用： 随
10、机选择a n, 计算s次， 如果每次都返回true， 则这时n是素数的概率为(1 - 1/2s)(3)通常的办法是随机选取一个大的奇数，然后进行素性检验1. 随机选一个奇数n (如: 可使用伪随机数发生器) 2. 随机选择一个整数a n 3. 执行概率素数判定测试(如:用WITNESS(a,n),如果n 未测试 通过,则拒绝数值n, 转向步骤1 4. 如果n已通过足够的测试, 则接受n, 否则转向步骤2;说明： 随机选取大约用 ln(N)/2的次数，如 ln(2200)/2=70 好在生成密钥对时才用到，慢一点还可忍受。 确定素数p和q以后，只需选取e, 满足gcd(e,(n)=1, 计算 d
11、 = e-1 mod (n) （sieve扩展的欧拉算法）欧几里得算法欧几里得算法是数论中的一个基本 技术，是求两个正整数的最大公因子的 简化过程。推广的欧几里得算法不仅可 求两个正整数的最大公因子，而且当两 个正整数的互素时，还可求出其中一个 数关于另一个数的乘法逆元。 1.求最大公因子 Euclid算法基于下面一个基本结论： 对任意的非负整数a和正整数b，有gcd(a,b)= gcd(b, a mod b)重复使用这个结论，可求得两个数的最大公 因子。由于 ，因此可假定算法 的输入为两个正整数 并设 。Euclid算法：如果gcd(a,b)=1，b在mod a（不 妨设 ）下有乘法逆元，即
12、 存在一个 使得用推广的Euclid算法可求b的逆元 。2. 求乘法逆元为公因子。中国剩余定理中国剩余定理：设自然数m1,m2,mr两两互素， 并记N=m1m2mr，则同余方程组在模N同余的意义下有唯一解。证明：考虑方程组，(1=i=r)由于诸mi(1=i=r)两两互素，这个方程组作变量替换， 令x=(N/mi) y，方程组等价于解同余方程：(N/mi)y1(mod mi)n若要得到特解yi,只要令 xi=(N/mi)yi 则方程组的解为 x0=b1x1+ b2x2+ + brxr (mod N) 模N意义下唯一。原根(primitive root) Euler定理表明,对两个互素的整数a,n
13、, a(n) 1 mod n 定义： 素数p的原根定义：如果a是素数p的原根，则数 a mod p, a2 mod p, , ap-1 mod p 是不同的并且包含1到p-1的整数的某种排列。对任意的与p互素的整数b，我们可以找到唯一的 幂i满足 b=ai mod p 0=i=(p-1)离散对数若a是素数p的一个原根,则对任意整数b, b0 mod p,存在唯一的整数i, 1i(p-1),使得:bai mod pi称为b以a为基模p的指数(离散对数),记作inda,p(b).容易知 道:inda,p(xy)= inda,p(x)+inda,p(y) mod (p)inda,p(xr)= rin
14、da,p(x) mod (p)离散对数的计算: ygx mod p 已知g,x,p,计算y是容易的 已知y,g,p,计算x是困难的平方剩余设p是一素数，a小于p，称a是p的平方剩 余，如果方程 有解。否则 称为平方非剩余。例如： 有解1和6，所以1是模7 的平方剩余。而 无解，所以3 是模7的平方非剩余。 容易证明模p的平方剩余的个数与模p的非 平方剩余的个数相同，都为 。模p的元素为0，1，2，p1/2,(p1)/2，,2，1定义1：设p是素数，a是一整数，符号 的定义如下：称符号 为Legendre符号。一般有 例如：定义2：设n是正整数，且 ，定义 Jacobi符号为其中右端的符号是Legendre符号。设n是两个大素数p和q的乘积。由上
