计算机安全与保密-第3章.ppt_第1页
计算机安全与保密-第3章.ppt_第2页
计算机安全与保密-第3章.ppt_第3页
计算机安全与保密-第3章.ppt_第4页
计算机安全与保密-第3章.ppt_第5页
已阅读5页,还剩32页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

内容 欧拉函数与循环群RSA原理RSA实现的问题大数因式分解问题RABIN公钥密码系统 公钥思想DiffieandHellman1976 公钥算法Rivest Shamir andAdleman1977 欧拉函数自变量为正整数n的函数称为欧拉函数 n n 表示小于n且与n互素的正整数的个数 当n为素数时 n n 1 欧拉函数的计算 欧拉函数与循环群 欧拉 Euler 定理已知a n为整数 如果gcd a n 1 则有a n 1 modn 费马 Fermat 小定理已知a n为整数 如果gcd a n 1 则有an 1 1 modn 封闭a b G 双向运算 结合律a b c a b c幺元a e e a a逆元a a 1 a 1 a e如果仅满足 1 和 2 则称G是一个半群 Semigroup 如果仅满足 1 2 和 3 则称G是一个含么半群 Monoid 阿贝尔群 a b b a 交换律 群 实数加e 0 a 1 a非零实数乘e 1 a 1 a 1 实例 Klein群 无限群 有限群 群的阶设 G 是群 G的元素个数是无限时 G称为无限群G的元素个数是有限时 G称为有限群G的元素个数称为群G的阶 元素的阶满足an e的最小正整数n 称为元素a的阶 记作O a 如果等式永不成立 则称a的阶为无穷大 子群设S是群G的一个非空子集 如果S对G的运算也构成群 则称S是G的子群 Subgroup 记作 S G 循环子群 生成元设G是群 a G 令H ak k Z 则H称为循环子群 CyclicSubgroup a为生成元循环群一个群 G 称为循环群 如果存在一个元素a G 使得G ak k Z Z 是由1生成的循环群 如果p是素数 那么 Zp 是循环群 如果p是素数 那么 Zp 是循环群 生成元为2 p 11时的循环群 RSA 1978年 Rivest Shamir和Adleman AMethodforObtainingDigitalSignaturesandPublic KeyCryptosystems RFC2313与RFC3447RFC2537 RSA MD5KEYsandSIGsintheDomainNameSystem DNS RFC2792 DSAandRSAKeyandSignatureEncodingfortheKeyNoteTrustManagementSystem RFC3110 RSA SHA 1SIGsandRSAKEYsintheDomainNameSystem DNS 实例 p 101q 113b 6597a 3533 n 11413 11200 x 6218y 9324 NP完全问题用非确定性算法可以在多项式时间内求解的问题称为非确定性多项式时间可解类 或简称NP完全问题或NP问题n pq的大数因式分解问题求 n 和大数因式分解是等价的 循环攻击 p 23 q 31 n 23 31 713 a 569 b 29 n 23 1 31 1 660 x 25 y 2529mod713 36 y 0 2529mod713 36 y 1 3629mod713 676y 2 67629mod713 625y 3 62529mod713 583y 4 58329mod713 656y 5 65629mod713 614y 6 61429mod713 501y 7 50129mod713 397y 8 39729mod713 532y 9 53229mod713 25y 10 2529mod713 36 同模攻击 p 89 q 137 n 89 137 12193 a1 10429 b1 661a2 4468 b2 1181 x 2005 y1 2005661mod12193 3429y2 20051181mod12193 11196 c1 661 1mod1181 1047c2 1047 661 1 1181mod12193 586 RSA实现的问题 如何找到足够大的素数 一类是通过数学理论构造出一个大的素数另一类是随机给定一个足够大的数 然后去证明它是素数 如何高效地实现模指数运算 素性检测验证一个数是不是素数叫素性检测Wilson定理 p是素数 22 1124000727777607680000 1mod23 运算量非常大 并不实用 拟素数 设n是一个奇合数 若整数b与n互素 成立 则n称作对于基b的拟素数 随机选取与n互素的整数b 若bn 1 1 modn 成立 则n为拟素数的概率 50 n为素数的概率 50 该性质可以用来构造素性检测算法 算法如下 1 给定奇整数n 3和检测轮数t 令k 1 2 随机选取整数b 2 b n 2 3 计算d b n 4 若d 1 则n是合数 输出 Fail 结束 否则转4 5 计算r b n 1 2 modn 6 若r 1 modn 则n是合数 输出 Fail 结束 否则 表明n通过了一轮素性检测 转到下一步 7 k k 1 若k t 转到 1 否则表明n通过了t轮检测 输出 Success 结束 经过t轮检测并输出 Success 的拟素数确定为素数的概率是 将接受卡密歇尔数的挑战 卡密歇尔 Carmichael 数合数n称为卡密歇尔数 如果对所有与n互素的正整数b 都满足 bn 1 1 modn 561 3 11 17是一个卡密歇尔数 1105 5 13 17也是一个卡密歇尔数 如果卡密歇尔数是有限的 那么前面的概率素性检测算法还是可用的 只需在每次算法运行前先查询 卡密歇尔数表 即可 但遗憾的是存在无穷多个卡密歇尔数 当n足够大时 区间 2 n 内至少有n2 7个卡密歇尔数 欧拉拟素数 已知n是奇素数 如果对任意正整数a 成立 那么称n是对于基a的欧拉拟素数 设n是奇素数 a 0 modn a 0 modb 若方程x2 a modn 有解 则称a是模n的平方剩余 欧拉准则 设n是奇素数 a是整数 那么a是一个模n的二次剩余当且仅当a n 1 2 1 modn 勒让德 Legendre 符号 当n是素数时 雅可比符号与勒让德符号是一样的 雅可比 Jacobi 符号定义为 设m是正奇数 雅可比符号的四个性质 欧拉拟素数是素数的概率 50 反例 Solovay Stassen概率素性检测算法 1 随机选取整数a 2 a n 2 2 计算d gcd a n 3 判断 若d 1 则n是合数 输出 Fail 结束 否则转到 4 4 计算r a n 1 2 modn 5 判断 若r 1 modn 则n是合数 输出 Fail 结束 否则转 6 6 计算勒让德符号s a n 7 判断 若r s 则n是合数 输出 fail 结束 否则转 8 8 n通过一轮素性检测 k k 1 9 若k t 转 1 否则n通过t轮检测 输出 Success 结束 通过t次Solovay Stassen素性检测的整数n为素数的概率 素数定理 从1到N的整数中抽到素数的概率 任选一个512位的随机正整数 它是素数的概率大约为 模指数算法二进制法二进制NAF算法滑动窗口算法 s 1fori lto0do s s smodnif ei 1 thens s gmodn returns 实例 大数因式分解问题 p 1法Dixon算法 a 2fori 2toba aimodnd gcd a1 n if 1 d n thend是n的素因子else寻找n的素因子失败 设n 29389613454601 取b 600 运用p 1算法进行因式分解 在循环结束时 得到 a 22058222139834于是 d gcd 22058222139833 29389613454601

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论