第九章公钥密码学
第九章 公钥密码学
对称密码体制的缺陷: 1)密钥分配问题通信双方要进行加密通信,需要通过秘密 的安全信道协商加密密钥,而这种安全信道可能很难实现; 2)密钥管理问题在有多个用户的网络中,任何两个用户之 间都需要有共享的秘密钥,当网络中的用户n很大时,需 要管理的密钥数目是非常大n(n-1)/2 3)没有签名功能:当主体A收到主体B的电子文挡(电子 数据)时,无法向第三方证明此电子文档确实来源于B
对称密码体制的缺陷： 1） 密钥分配问题 通信双方要进行加密通信，需要通过秘密 的安全信道协商加密密钥，而这种安全信道可能很难实现； 2） 密钥管理问题 在有多个用户的网络中，任何两个用户之 间都需要有共享的秘密钥，当网络中的用户 n 很大时，需 要管理的密钥数目是非常大 n(n −1)/ 2。 3） 没有签名功能：当主体 A 收到主体 B 的电子文挡（电子 数据）时，无法向第三方证明此电子文档确实来源于 B
9.1公钥密码学思想 定义9.11一个公钥密码体制是这样的一个5元组{MCK,E,Dk}, 且满足如下的条件 1.M是可能消息的集合; 2C是可能的密文的集合; 3.密钥空间K是一个可能密钥的有限集 4.对每一个K={K1,K2}∈K,都对应一个加密算法E∈E E:M→C和解密算法Da∈DDk2:C→M满足对于任意的m∈M Ac= Ek1(m), m=Dk2(c)=Dk(Ek1(m))=m 5.对于所有的KK,在已知E的情况下推出D是计算上不可能的 E是一个公开函数风称作公钥:而D是一个秘密函数,总称作
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:M→C和解密算法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是一个公开函数,K1 称作公钥；而DK2是一个秘密函数，K2称作 私钥，由用户秘密地保存
public-key/two-key/asymmetric 3 括两个密钥 公开密钥 a public-key),可以被任何人知 道,用于加密或验证签名 私钥( private-key)只能被消息的接收者 或签名者知道用于解密或签名 加密或验证签名者不能解密或多或生成签 是密码学几千年历史中最有意义的结果
◼ public-key/two-key/asymmetric 包 括两个密钥: ◼ 公开密钥(a public-key), 可以被任何人知 道, 用于加密或验证签名 ◼ 私钥( private-key), 只能被消息的接收者 或签名者知道,用于解密或签名 ◼ 加密或验证签名者不能解密或多或生成签 名. ◼ 是密码学几千年历史中最有意义的结果
3公钥加密方案 Insecure Communications Channel crypt M with ecrypt C with Message source key k key k2 Message Dest C=E K1 M=DA(C) K1 CryptAnalyst K2 K1 Key source Random keys Insecure Key K18K2 Channel Asymmetric (Public-Key ) Encryption System
3.公钥加密方案
4公钥密码理论 口由私钥及其他密码信息容易计算出公开密钥(a polynomial time(p-time) problem) ■由公钥及算法描述计算私钥是难的(anNP time problem) n因此公钥可以发布给其他人( wishing to communicate securely with its owner ■密钥分配问题不是一个容易的问题( the key distribution problem
4.公钥密码理论 ◼ 由私钥及其他密码信息容易计算出公开密钥 (a polynomial time (P-time) problem) ◼ 由公钥及算法描述,计算私钥是难的 (an NPtime problem) ◼ 因此,公钥可以发布给其他人(wishing to communicate securely with its owner ) ◼ 密钥分配问题不是一个容易的问题(the key distribution problem )
5公钥算法分类 Public-Key distribution Schemes(PKDs) 用于交换秘密信息(依赖于双方主体) 常用于对称加密算法的密钥 Public Key Encryption(PKE) 用于加密任何消息 任何人可以用公钥加密消息 私钥的拥有者可以解密消息 ◆任何公钥加密方案能够用于密钥分配方案PKDS 许多公钥加密方案也是数字签名方案 Signature Schemes ◆用于生成对某消息的数字签名 ◆私钥的拥有者生成数字签名 ◆任何人可以用公钥验证签名
5.公钥算法分类 ◼ Public-Key Distribution Schemes (PKDS) 用于交换秘密信息(依赖于双方主体) 常用于对称加密算法的密钥 ◼ Public Key Encryption (PKE) 用于加密任何消息 任何人可以用公钥加密消息 私钥的拥有者可以解密消息 任何公钥加密方案能够用于密钥分配方案PKDS 许多公钥加密方案也是数字签名方案 ◼ Signature Schemes 用于生成对某消息的数字签名 私钥的拥有者生成数字签名 任何人可以用公钥验证签名
6.公钥的安全性 依赖于足够大大的困难性差别 ■类似与对称算法穷搜索在理论上是能够破解公 钥密码 exhaustive search ■但实际上密钥足够长(>512bts) 一般情况下有一些已知的困难问题(hard problen” ■要求足够大的密钥长度(>512bits) ■导致加密速度比对称算法慢
6.公钥的安全性 ◼ 依赖于足够大大的困难性差别 ◼ 类似与对称算法,穷搜索在理论上是能够破解公 钥密码 exhaustive search ◼ 但实际上,密钥足够长 (>512bits) ◼ 一般情况下,有一些已知的困难问题(hard problem” ◼ 要求足够大的密钥长度 (>512 bits) ◼ 导致加密速度比对称算法慢
2. RSA (Rivest, Shamir, Adleman) 使用最厂泛的公钥加密算法 Rivest, Shamir Adleman(rsa)in 1977 rlRivest, a shamir/ adleman on Digita/ Signatures and public Key CryptosystemsCommunications of the ACMW21m2p120126eb1978
2. RSA (Rivest, Shamir, Adleman) ◼ 使用最广泛的公钥加密算法 ◼ Rivest, Shamir & Adleman (RSA) in 1977 ◼ R 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 个用户生成自已的公钥\私钥对: 选择两个随机大素数(100dgjt)p,q 计算模数N=pq ■选择一个随机加密密钥匙e:e<N, gcd(e, o(N)=1 ■解下列同余方程,求解密密钥d: ed=1 od p(N) and o<=d<=N ■公开加密密钥:K={enN} ■保存其解密似钥 K(1={d,p,q}
3. RSA Setup ◼ 每个用户生成自己的公钥\私钥对: ◼ 选择两个随机大素数 (~100 digit), p, q ◼ 计算模数 N=p.q ◼ 选择一个随机加密密钥匙 e : e<N, gcd(e,ø(N))=1 ◼ 解下列同余方程,求解密密钥 d: ◼ e.d=1 mod ø(N) and 0<=d<=N ◼ 公开加密密钥: Kr={er ,Nr } ◼ 保存其解密似钥: ◼ K-1 r={d,p,q}