6计算机安全ciper-5.ppt

  1. 1、本文档共53页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
对文摘函数的生日攻击 目标:找到两个产生相同文摘的信息 对MD5生日攻击的代价是264,而不是2128。 公钥密码学的历史 76年Diffie和Hellman发表了“密码学的新方向”,奠定了公钥密码学的基础 公钥技术是二十世纪密码学最重要的思想 改变了密钥分发的方式 可以广泛用于数字签名和身份认证服务 78年,RSA算法 PKI 公钥密码 公钥密码 RSA 1977年由Ron Rivest、Adi Shamir和Len Adleman发明,1978年公布,2002图灵奖 块加密算法。 明文和密文在0~n-1之间,n是一个正整数 应用最广泛的公钥密码算法 只在美国申请专利,且已于2000年9月到期 On Digital Signatures and Public Key Cryptosystems, Communications of the ACM, vol 21 no 2, pp120-126, Feb 1978 加解密 加密 得到A的公钥(e,n) 消息表示成[0,n-1]内的整数m 计算 C = me mod n 解密 用私钥d Cd mod n = m 满足以下条件: med mod n = m, 对所有Mn 计算me和Cd相对容易 从e和n得到d是在计算上不可行的 密钥生成 密钥生成: 2个长度接近的大质数p、q 计算 n = pq, Φ(n) = (q-1)(p-1) 选择随机整数 e, 1 e Φ(n), 满足 gcd(e, Φ(n)) = 1 计算d, 1 d Φ(n)满足. ed=1 mod Φ(n) 公开密钥Public key: (e, n) 私有密钥Secret key: (d,p,q, Φ(n) ) 基础 Euler数?(n)定义为小于n且与n互素的正整数个数 p是素数,?(p)=p-1 若n的因子分解为n=?Piai, ai0,Pi互不相同,则 ?(n)= ?Piai?(1-1/Pi) 若gcd(m,n)=1,则?(mn)=?(m)?(n),特别地,若p?q且都是素数, ?(pq)=(p-1)(q-1) 费马(小)定理 ap=a mod p, p质数,a、p互质 欧拉定理 a、n互质, aΦ(n)=1 mod n 推论:任意a,aΦ(n)+1=a mod n 中国余数定理(CRT) 某一范围的整数可通过它对两两互质的整数取模来重构 n=pq ,则任意0x n,可通过(x mod p, x mod q)来重构 x与二元组一一对应 用CRT证明x(p-1)(q-1)=1 mod pq xy mod n,对应(xy mod p, xy mod q) p、q长度短,使得乘法次数少 xe mod p = x e mod p-1 mod p 高精度整数取模乘法 O(n2) 快速傅里叶变换(FFT) FFT:点表示--多项式表示O(nlogn) O(nlogn) 蒙哥马利算法 模幂的实现 农民算法 乘法 乘方 小指数e=3, 5, 17, 65537 为什么不是7,11,13,…? 俄国农民算法 从左到右的农民算法: 输入: 正整数m,整数g(g m)及正整数e e=en-1...e0 输出: ge mod m 。 (1) s ← 1 ; (2) 对 i从 n-1 依次到 0,执行: 1) s ← s2 mod m ; 2) 如果 ei = 1, 则 s ← s*g mod m ;//(s ← s*gei mod m ) (3) 返回 s。 原理: M = ((((((ek2+bk-1)2+ek-2)2+ek-3)2+…)2+e0 从右到左的农民算法: 输入: 正整数m、g(gm)及正整数e, ei为e的二进制表示中进位第i高的bit 输出: ge mod m 。 (1) s ← 1 ; (2) 对 i从 0 依次到 n - 1,执行: 1) 如果 ei = 1 , 则 s ← s*g mod m ; 2) g ← g*g mod m 。 (3) 返回 s。 对两种算法的分析 两种算法都需要平均3/ 2?(n ?1) 次乘法。 L-R 是用固定的g值作乘法,R-L 的g值是变化的,因此在硬件实现时,需要增加一个寄存器。 R-L 算法中,平方和模乘是独立的,可以并行运算。但在L-R 算法中不能。 素数生成算法 判定一个数是素数比较难,但判定一个数不是素数却很容易。 快速筛选法的特点是执行速度快而成功率低, 精确筛选法的特点正好相反,它的执行速度慢但成功率高 一个256-bit的合数通过二阶费马测试的概率仅有10-22 ,512-bit的合数通过二阶费马测试的概率仅有10-44 。 素数生成算法 质数分布: π(N)=N/ln N 1~N之间的数是素数的概率为 1/ln N 1024bit的

文档评论(0)

junjun37473 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档