版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、RSA RSA 算法及平安性分析算法及平安性分析量子密码研讨室量子密码研讨室王滨王滨2019.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,
2、q=5, p=3, q=5, 那么那么 1515= =3-13-1* *5-15-1=8=8 这这8 8个模个模1515的剩余类是:的剩余类是: 1 1,2 2,4 4,7 7,8 8,1111,1313,14 14 Euler定理、定理、Fermat定理定理oEuler定理:设定理:设 x 和和 n 都是正整数,假设都是正整数,假设gcd(x,n)1,那么,那么 x (n)1 (mod n).oFermat定理定理:设设 x 和和 p 都是正整数,假设都是正整数,假设gcd(x,p)1,那么,那么 x p-11 (mod p).RSA算法的实现算法的实现 实现的步骤如下:实现的步骤如下:Bo
3、b为实现者为实现者 (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,解出的,解出的dR
4、SA算法编制算法编制 参数参数T=N;私钥私钥SK=D;公钥公钥PK=E; 设:明文设:明文M,密文,密文C,那么:,那么: 用公钥作业:用公钥作业:ME mod N = C 用私钥作业:用私钥作业:CD mod N = MRSA算法举例算法举例RSA算法的平安性分析算法的平安性分析密码分析者攻击密码分析者攻击RSA体制的关键点在于如何分解体制的关键点在于如何分解n假设分解胜利使假设分解胜利使n=pq,那么可以算出,那么可以算出(n)p-1)(q-1),然后由公开的,然后由公开的e,解出的,解出的d假设使假设使RSA平安,平安,p与与q必为足够大的素数,使分析必为足够大的素数,使分析者没有方法
5、在多项式时间内将者没有方法在多项式时间内将n分解出来分解出来 n取取1024位或取位或取2048位,这样位,这样p、q就应该取就应该取512位和位和1024位。位。RSA算法的平安性分析算法的平安性分析建议选择建议选择p和和q大约是大约是100位的十进制素数位的十进制素数模模n的长度要求至少是的长度要求至少是512比特比特EDI攻击规范运用的攻击规范运用的RSA算法中规定算法中规定n的长度为的长度为512至至1024比特位之间,但必需是比特位之间,但必需是128的倍数的倍数国际数字签名规范国际数字签名规范ISO/IEC 9796中规定中规定n的长度位的长度位512比比特位特位密钥大小 MIPS
6、年 512比特 768比特1024比特2048比特43 1082 10113 10203 10RSA算法的平安性分析算法的平安性分析 为了抵抗现有的整数分解算法,对为了抵抗现有的整数分解算法,对RSA模模n的素因子的素因子p和和q还有如下要求即是强素数:还有如下要求即是强素数: (1) p-1 和和q-1分别含有大素因子分别含有大素因子p1和和q1 (2) P1-1和和q1-1分别含有大素因子分别含有大素因子p2和和q2 (3) p+1和和q+1分别含有大素因子分别含有大素因子p3和和q3RSA算法的平安性分析算法的平安性分析其它参数的选择要求:其它参数的选择要求:(1) |p-q|很大,通常很大,通常 p和和q的长度一样;的长度一样;(2)p-1和和q-1的最大公因子要小;的最大公因子要小;(3)e的选择;的选择;(4)d的选择;的选择;(5)不要许多的用户共用一个不要许多的用户共用一个n。 定义 假设 modemNm 那么称那么称 m m
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 兽医专家2025年度顾问咨询与技术支持合同2篇
- 2025版金融理财产品销售合同履约保证书4篇
- 2025年度出租车租赁与品牌推广合作合同3篇
- 2024礼品购销合同模板购销合同范本
- 2024版济宁房屋租赁合同范本
- 二零二四年专业相机租赁服务合同附带摄影师派遣及培训3篇
- 二零二五版茶叶种植基地土地流转租赁合同3篇
- 2025年养老护理机构PPP项目特许经营合同3篇
- 2025年度城市基础设施建设不定期借款合同3篇
- 二零二四年度2024绵阳租赁保证金合同模板3篇
- 触发点疗法:精准解决身体疼痛的肌筋膜按压疗法
- 化脓性中耳炎
- 探析小学语文教学中融合思政教育的课堂教学
- 医学科研诚信专项教育整治简洁工作总结范文
- 班主任班级管理经验分享PPT
- 小学英语单词汇总大全打印
- 卫生健康系统安全生产隐患全面排查
- GB/T 15114-2023铝合金压铸件
- 2023年考研考博-考博英语-武汉大学考试历年真题摘选含答案解析
- 货物验收单表格模板
- MT/T 323-1993中双链刮板输送机用刮板
评论
0/150
提交评论