第九章公钥密码学.ppt
《第九章公钥密码学.ppt》由会员分享,可在线阅读,更多相关《第九章公钥密码学.ppt(41页珍藏版)》请在三一文库上搜索。
1、第九章 公钥密码学,对称密码体制的缺陷:,9.1公钥密码学思想,定义9.1.1一个公钥密码体制是这样的一个5元组M,C,K,EK,DK,且满足如下的条件: 1.M是可能消息的集合; 2.C是可能的密文的集合; 3. 密钥空间K是一个可能密钥的有限集; 4对每一个K=K1,K2 K,都对应一个加密算法EK1 E, EK1:MC和解密算法DK2 D,DK2:C M,满足对于任意的m M,都有c= EK1(m),m= DK2(c)=DK2(EK1(m))=m; 5对于所有的KK,在已知E的情况下推出D是计算上不可能的; 对每一个K K,函数EK1和DK2都是多项式时间可计算的函数。EK1是一个公开函
2、数,K1 称作公钥;而DK2是一个秘密函数,K2称作私钥,由用户秘密地保存。,public-key/two-key/asymmetric 包括两个密钥: 公开密钥(a public-key), 可以被任何人知道, 用于加密或验证签名 私钥( private-key), 只能被消息的接收者或签名者知道,用于解密或签名 加密或验证签名者不能解密或多或生成签名. 是密码学几千年历史中最有意义的结果,3.公钥加密方案,4.公钥密码理论,由私钥及其他密码信息容易计算出公开密钥 (a polynomial time (P-time) problem) 由公钥及算法描述,计算私钥是难的 (an NP-tim
3、e problem) 因此,公钥可以发布给其他人(wishing to communicate securely with its owner ) 密钥分配问题不是一个容易的问题(the key distribution problem ),5.公钥算法分类,Public-Key Distribution Schemes (PKDS) 用于交换秘密信息(依赖于双方主体) 常用于对称加密算法的密钥 Public Key Encryption (PKE) 用于加密任何消息 任何人可以用公钥加密消息 私钥的拥有者可以解密消息 任何公钥加密方案能够用于密钥分配方案PKDS 许多公钥加密方案也是数字签名
4、方案 Signature Schemes 用于生成对某消息的数字签名 私钥的拥有者生成数字签名 任何人可以用公钥验证签名,6.公钥的安全性,依赖于足够大大的困难性差别 类似与对称算法,穷搜索在理论上是能够破解公钥密码 exhaustive search 但实际上,密钥足够长 (512bits) 一般情况下,有一些已知的困难问题(hard problem” 要求足够大的密钥长度 (512 bits) 导致加密速度比对称算法慢,2. RSA (Rivest, Shamir, Adleman),使用最广泛的公钥加密算法 Rivest, Shamir & Adleman (RSA) in 1977 R
5、 L Rivest, A Shamir, L Adleman, “On Digital Signatures and Public Key Cryptosystems“, Communications of the ACM, vol 21 no 2, pp120-126, Feb 1978,3. RSA Setup,每个用户生成自己的公钥私钥对: 选择两个随机大素数 (100 digit), p, q 计算模数 N=p.q 选择一个随机加密密钥匙 e : eN, gcd(e,(N)=1 解下列同余方程,求解密密钥 d: e.d=1 mod (N) and 0=d=N 公开加密密钥: Kr=er
6、,Nr 保存其解密似钥: K-1r=d,p,q,4。RSA 参数选择,需要选择足够大的素数 p, q 通常选择小的加密指数e,且与(N) 互素 e 对所有用户可以是相同的 最初建议使用e=3 现在3太小 常使用 e=216-1 = 65535 解密指数比较大,5. RSA Usage,要加密消息 M, 发送者要得到接收者的公钥Kr=er,Nr 计算: C=Mer mod Nr, where 0=MN 为解密 C, 接收者使用私钥 K-1r=d,p,q 计算: M=Cd mod Nr,6. RSA理论,RSA 基于Fermats Theorem: if N = pq where p, q are
7、 primes, then: X(N) = 1 mod N for all x not divisible by p or q, ie gcd(x,(N)=1 where (N)=(p-1)(q-1) 但在 RSA 中,e & d 是特殊选择的 ie e.d=1 mod (N) 或e.d=1+R(N) hence have: M = Cd = Me.d = M1+R(N) = M1.(M(N)R = M1.(1)R = M1 mod N,8。RSA举例,例子: 1. 选素数p=47和q71,得n=3337, (n)=46703220; 2. 选择e=79,求得私钥d=e -1 1019(mod
8、 3220)。 3. 公开n=3337和e=79. 4. 现要发送明文688,计算: 68879(mod 3337)=1570 5.收到密文1570后,用私钥d1019进行解密: 15701019(mod 3337)=688,9。RSA 安全性,RSA 安全性基于计算 (N)的困难性 要求分解模N,10. RSA的实现问题,需要计算模 300 digits (or 1024+ bits) 的乘法 计算机不能直接处理这么大的数 (计算速度很慢) 需要考虑其它技术,加速RSA的实现,11. RSA 的快速实现,加密很快,指数小 解密比较慢,指数较大 利用中国剩余定理CRT, CRT 对RSA解密算
9、法生成两个解密方程 (利用M = Cd mod R ) 即: M1 = M mod p = (C mod p)d mod (p-1) M2 = M mod q = (C mod q)d mod (q-1) 解方程 M = M1 mod p M = M2 mod q 具有唯一解(利用CRT ): :M = (M2 +q - M1)u mod q p + M1 其中 p.u mod q = 1,9.2.3概率素性检测,定义9.2.3:如果P是素数,且a小于p,如果至少存在一个x 1,p-1满足x2a(modp),则我们称a是模p的二次剩余(quadratic residue)。 定义9.2.4:设
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第九 章公钥 密码学
链接地址:https://www.31doc.com/p-2581312.html