《第6章公钥密码体制》由会员分享，可在线阅读，更多相关《第6章公钥密码体制（123页珍藏版）》请在金锄头文库上搜索。
1、第6章 公钥密码体制,Char 7 pp.2,本章概要,公钥密码的概念、特点和应用范围。 数论基础 RSA算法加、解密过程。 其它公钥算法简介。 教学要求：原理要清楚，数论不深究。,6.1公钥密码的基本思想,Char 7 pp.4,密钥分配:通信密钥太多，管理和分发困难。 传统密钥管理：两两分别用一对密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时，密钥空间急剧增大。如: n=100 时，C(100,2)=4,995 n=5000时，C(5000,2)=12,497,500 数字签名和认证 传统加密算法无法实现抗抵赖的需求,对称密钥面临的困题,Char 7 pp.5,
2、密码体制上的突破,Diffie 若a不能整除b，记为a！b. 性质： （1） 若ba, 则下列各式成立 (b0) (b)a, b(a), (b)(a), ba （2）若cb且ba (c0,b0), 则ca （3）若ba (b0), 则bac （4） 若ba且bc (b0), 则b(ac) （5） 若ab且ba (a0,b0), 则a=b,Char 7 pp.34,定理6.2.1 设a,b是两个整数，b1，则存在唯一确定的整数q、r使满足a=bq+r； 其中0rb。q为a除以b所得的商，r为a除以b所得余数，记：q=a div b, r=a mod b,模运算,Char 7 pp.35,公因子,
3、设d,a1,a2,an(n=2)是任意整数，若有 d|a1,d| a2,d|an，则称d是a1,a2,an的公因子。 若d是a1,a2,an的一个公因子，对a1,a2,an的任一个公因子c，存在cd，则称d是a1,a2,an的最大公因子，记为 gcd （ a1,a2,an ） 若gcd(al,a2,an)=1, 称al,a2,an是互素。 在互素的正整数中, 不一定有素数. 例如(25,36)=1, 但25和36都不是素数而是合数.,Char 7 pp.36,最大公因子的性质,任何不全为0的两个整数的最大公因子存在且唯一 设整数a与b不全为0，则存在整数x和y，使得ax+by=gcd(a,b)
4、。特别地，如果a、b互素，则有ax+by=1 若gcd(a,b)=d, 则gcd (a|d, b|d)=1 若gcd(a,x)=gcd(b,x)=1,那么gcd(ab,x)=1 若c|(ab),gcd(b,c)=1,则c|a,Char 7 pp.37,最小公倍数,设a1,a2,an和m都是正整数, n2. 若ai|m, 1in, 则称m是a1,a2,an的公倍数. 在a1,a2,an所有公倍数中最小的那一个, 称为a1,a2,an的最小公倍数, 记为lcm(a1,a2,an）,Char 7 pp.38,素数定义,一个大于1且只能被1和它本身整除的整数, 称为素数; 否则, 称为合数. 素数有无
5、穷多个； 如果p是一个素数，且p|ab,则p|a或p|b; 记PAI(x)为不大于x的素数个数，则 即对于充分大的x，可以用xlnx近似的表示PAI(x),Char 7 pp.39,算术基本定理,算术基本定理：任意一个正整数n(n1)可以唯一地表示为若干个素数的乘积。这里唯一的意义表示为不考虑素因子的次序。 任意一个整数n(n0,n1)可以唯一地表示为p1 p2 pk ( k=1 )，p1 ,p2, ,pk是素数。 任意一个整数n(n0,n1)可以唯一地表示为 p1r1 p2r2 pkrk，p1 ,p2, ,pk是质数，r1,r2,rk是正整数。,Char 7 pp.40,强素数,n是一个整数
6、，n=pq,且p、q满足以下属性时，称n为强素数： (1)gcd(p-1,q-1)比较小； (2)p-1和q-1都有大素因子(记p*,q*)； (3)p*-1和q*-1都有大的素因子； (4)p+1和q+1都有大的素因子； (5)(p-1)/2和(q-1)/2都是素数 对于强素数，即使采用特殊的因子分解方法，对整数n的因子分解也非常困难。 强素数：439351292910452432574786963588089477522344331,强素数第六章一种强素数因子分解的量子算法.pdf实现,Char 7 pp.41,欧拉函数,欧拉函数(n)：表示区间1,n中与 n 互素的整数的个数；习惯上，
7、欧拉函数的性质： (1)素数 p，有(p)=p1； (2)(n)为积性函数，即，如果gcd(m,n)=1, (mn)=(m)(n) (3)对于n属于Z，n2， (4)对于素数p,q,n=pq,(n)=(pq)=(p-1)(q-1) (5)如果n属于Z，n5，则 积性函数：在数论上，对于正整数n的一个算术函数 f(n)，当中f(1)=1且当a,b互质，f(ab)=f(a)f(b),完全积性函数: 若某算术函数f(n)符合f(1)=1，且就算a,b不互质，f(ab)=f(a)f(b)。,Char 7 pp.42,欧拉函数前30项,Char 7 pp.43,欧拉定理,对于任意互素的a 和 n ，有：
8、 等价形式：,Char 7 pp.44,Euclidean算法(1),根据: (1)：gcd (a, 0) = a; (2)：gcd (a, b) = gcd (b, a mod b) 。 从(1)可以看出，对两个整数，如果第二个整数是0，那么第一个数就是这两个数的最大公约数。 从(2)可以看出，如何去改变a和b的值，直到使b为0的方法，当b变为0时，直接得到最大公约数。 如gcd(36,10)=gcd(10,6)=gcd(6,4) =gcd(4,2)=gcd(2,0)=2,用于计算两个整数的最大公因子,Char 7 pp.45,Euclidean算法(2),Char 7 pp.46,扩展Eu
9、clidean算法(1),给定两个整数a和b，我们还经常需要求得另外两个整数s和t，使得扩展Euclidean算法可以计算gcd(a,b)，也可以同时计算s和t的值。,Char 7 pp.47,扩展Euclidean算法流程(2),Char 7 pp.48,扩展Euclidean算法(3),Char 7 pp.49,同余式,定义:设a、b、m为整数（m0），若a和b被m除得的余数相同，则称a和b对模m同余.记为 或 一切整数n可以按照某个自然数m作为除数的余数进行分类，即n=pm+r（r=0，1，m-1），恰好m个数类.于是同余的概念可理解为,若对n1、n2，有n1=q1m+r，n2=q2m+
10、r，那么n1、n2对模m的同余，即它们用m除所得的余数相等.,Char 7 pp.50,同余式性质,(1) 若 ,则m|(b-a).反之,若m|(b-a),则 ; (2) 如果a=km+b(k为整数),则 ; (3) 每个整数恰与0,1,，m-1，这m个整数中的某一个对模m同余； (4) 同余关系是一种等价关系： 反身性 ； 对称性 ，则 ，反之亦然. 传递性 ， ，则 ； (5)如果 ， ，则 ； 特别地,Char 7 pp.51,中国剩余定理,数学名著孙子算经中： “今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何。” 即“有一批物品，三个三个地数余二个，五个五个地数余三
11、个，七个七个地数余二个，问这批物品最少有多少个。”,Char 7 pp.52,中国剩余定理,明朝数学家程大位： 三人同行七十（70）稀；/除以3的余数用70去乘； 五树梅花廿一（21）枝；/除以5的余数用21去乘； 七子团圆正月半（15）；/除以7的余数用15去乘 除百零五（105）便得知。/上面乘得的三个积相加的和如超过105，就减去105的倍数 7022131521052=23 70是5和7的公倍数，且除以3余1。21是3和7的公倍数，且除以5余1。15是3和5的公倍数，且除以7余1。把70、21、15这三个数分别乘以它们的余数，再把三个积加起来是233，符合题意，但不是最小，而105又是
12、3、5、7的最小公倍数，去掉105的倍数，剩下的差就是最小的一个答案。,Char 7 pp.53,求解如下形式的同余方程组 其中： ， ， ， 。,中国剩余定理,Char 7 pp.54,中国剩余定理,Char 7 pp.55,中国剩余定理,一个数被3除余1，被4除余2，被5除余4，这个数最小是几？ 解：3、4、5三个数两两互质。 则4，5=20；3，5=15；3，4=12；3，4，5=60。 为了使20被3除余1，用202=40； 使15被4除余1，用153=45； 使12被5除余1，用123=36。 然后，401452364=274， 因为，27460，所以，274604=34， ,Cha
13、r 7 pp.56,6.3 RSA算法,Char 7 pp.58,RSA算法 简介,分组密码，安全性依赖于大数的因子分解。 第一个较为完善的公钥算法。 能够同时用于加密和数字签名，且易于理解和操作。 RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，被普遍认为是目前最优秀的公钥算法之一。 目前仍然无法从理论上证明它的保密性能究竟如何 ，因为目前人们并没有从理论上证明破译RSA的难度与大整数分解问题的难度等价。,Char 7 pp.59,RSA算法描述（1）,设分组长度为l bit，每个分组 M 被看作是一个 l bit 的二进制值。 取某一个整数
14、n ，使对所有 M，有 M n 一般， n 的取值满足 2l n 2 l+1。 加密算法 C = Me mod n。 解密算法 M = Cd mod n = (Me)d mod n = Med mod n。 加密密钥（公开密钥）为 KU = e,n。 解密密钥（私有密钥）为 KR = d,n。,Char 7 pp.60,RSA算法描述（2）,要求： e, d, n 使对所有 M n 都有： M = Med mod n 对所有 M n ， Me 和 Cd 的计算相对简单。 给定 e, n ，要推断 d 在计算上不可行。 问题：怎样找到满足 M = Med mod n 的 e, d, n ？ 需要
15、利用数论作为其数学基础。,Char 7 pp.61,欧拉定理与RSA算法,RSA算法要求： M = Med mod n 欧拉定理推论： 有两个素数 p 和 q, 令 n = pq , 对任意整数 k 和 m (0mn), 有下列等式成立： m = mk(n) +1 mod n 其中：(n) = (p-1)(q-1)。,Char 7 pp.62,RSA算法描述,选取足够大的两个素数 p 和 q, 令 n = pq , 则(n) = (p-1)(q-1)。 选取适当的加密密钥 e 和解密密钥 d ，使之满足 。 公开 n 和 e ，保密 p, q 和 d。 加密运算： 解密运算：,Char 7 p
16、p.63,RSA算法实现步骤,密钥的产生 生成两个大素数 p 和 q ，pq； 计算 ， ； 选择随机数 e（即加密密钥）, 使之满足 , ； 计算解密密钥 ； 公布整数 n 和加密密钥 e，公钥KU=e，n。 私钥KR=d，n。,=1,加密 明文 Mn 密文 C=Me(mod n),解密 密文 C 明文 M=Cd(mod n),Char 7 pp.64,RSA算法的特殊要求（）,密码分析者攻击RSA体制的关键点在于如何分解n。若分解成功使n=pq，则可以算出(n)（p-1)(q-1)，然后由公开的e，解出秘密的d。 若使RSA安全，p与q必须是足够大的素数，使分析者没有办法在多项式时间内将n分解出来。建议选择
