【安全课件】第20讲rsa算法及安全性分析.pptx

RSA 算法及安全性分析量子密码研究室王滨2005.4.13Euler 函数 所有模m和r同余的整数组成剩余类[r] 剩余类[r]中的每一个数和m互素的充要条件是r和m互素 和m互素的同余类数目用φ(m)表示，称m的Euler函数 当m是素数时，小于m的所有整数均与m互素，因此φ(m)=m-1对n=pq, p和q 是素数，φ(n)=φ(p)φ(q)=(p-1)(q-1)Euler 函数举例 设p=3, q=5, 那么 φ（15）=（3-1）*（5-1）=8 这8个模15的剩余类是： {1，2，4，7，8，11，13，14} Euler定理、Fermat定理Euler定理：设 x 和 n 都是正整数，如果gcd(x，n)＝1，则 x φ(n)≡1 (mod n).Fermat定理:设 x 和 p 都是正整数，如果gcd(x，p)＝1，则 x p-1≡1 (mod p).RSA算法的实现 实现的步骤如下：Bob为实现者 (1) Bob寻找出两个大素数p和q (2) Bob计算出n=pq 和φ(n)=(p-1)(q-1) (3) Bob选择一个随机数e (0e φ(n))，满足(e,φ(n))=1 (4) Bob使用辗转相除法计算d=e-1(modφ(n)) (5) Bob在目录中公开n和e作为公钥密码分析者攻击RSA体制的关键点在于如何分解n。若分解成功使n=pq，则可以算出φ(n)＝（p-1)(q-1)，然后由公开的e，解出秘密的dRSA算法编制 参数T={N}；私钥SK=D；公钥PK=E； 设：明文M，密文C，那么： 用公钥作业：ME mod N = C 用私钥作业：CD mod N = MRSA算法举例设 p=7, q=17, n=7*17=119; 参数T={n=119};φ(n)=(7-1)(17-1)=96;选择e=5, gcd(5,96)=1;公钥pk=5;计算d, ( d*e) mod 96=1; d=77;私钥sk=77;设:明文m=19 加密：（19）5 mod 119 = 66 脱密：（66）77 mod 119 = 199、要学生做的事，教职员躬亲共做；要学生学的知识，教职员躬亲共学；要学生守的规则，教职员躬亲共守。10、阅读一切好书如同和过去最杰出的人谈话。11、一个好的教师，是一个懂得心理学和教育学的人。12、要记住，你不仅是教课的教师，也是学生的教育者，生活的导师和道德的引路人。13、He who seize the right moment, is the right man.谁把握机遇，谁就心想事成。14、谁要是自己还没有发展培养和教育好，他就不能发展培养和教育别人。15、一年之计，莫如树谷；十年之计，莫如树木；终身之计，莫如树人。16、提出一个问题往往比解决一个更重要。因为解决问题也许仅是一个数学上或实验上的技能而已，而提出新的问题，却需要有创造性的想像力，而且标志着科学的真正进步。17、儿童是中心，教育的措施便围绕他们而组织起来。2、Our destiny offers not only the cup of despair, but the chalice of opportunity. (Richard Nixon, American President )命运给予我们的不是失望之酒，而是机会之杯。二〇二一年六月十七日2021年6月17日星期四3、Patience is bitter, but its fruit is sweet. (Jean Jacques Rousseau , French thinker)忍耐是痛苦的，但它的果实是甜蜜的。10:516.17.202110:516.17.202110:5110:51:196.17.202110:516.17.20214、All that you do, do with your might; things done by halves are never done right.----R.H. Stoddard, American poet做一切事都应尽力而为，半途而废永远不行6.17.20216.17.202110:5110:5110:51:1910:51:195、You have to believe in yourself. Thats the secret of success. ----Charles Chaplin人必须相信自己，这是成功的秘诀。-Thursday, June 17, 2021June 21Thursday, June 17, 20216/17/2021?RSA算法的安全性分析密码分析者攻击RSA体制的关键点在于如何分解n若分解成功使n=pq，则可以算出φ(n)＝（p-1)(q-1)，然后由