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}