公钥加密与消息认证.ppt

3.3 公钥加密原理 网友小榕打算用E-mail将自己写的小说加密发送给网友老狼，但是小榕与老狼之间从未有过密码通信的约定。如何使老狼能够读懂加密的文件呢？ 假设小榕与老狼之间的任何E-mail都可能被第三方监测到。显然，如果小榕在E-mail中告诉老狼解密方法，那么读到E-mail的其他人也能解密读懂小榕的小说。 如何设计一个方案，使得小榕与老狼之间通过若干次E-mail的来往就能够建立起密码通信，并且使得监听了他们所有E-mail的人无法破译小榕的加密文件。 Alice委托Bob按照他的指示股票交易 假设Alice指示Bob以10美元的价格卖出了1万股股票，不久，该股票升为20美元。Alice起了贪心，一口咬定从未发过卖出股票的指示，Bob如何辨白？ 假设Bob私自以10美元的价格卖出了1万股股票，不久，该股票升为20美元。Alice此时发现，但Bob一口咬定是遵照Alice的指示卖出股票的，Alice如何证明？ 素数： 素数p是大于1且因子仅为 1和p 的整数。为简单起见，下面仅涉及非负整数 设a、b为整数，且不全为0， gcd(a,b)表示a和b的最大公因子 如果gcd(a,b)=1，称a和b互为素数（互素）。即a和b仅有一个公因子1 模运算 给定任一正整数n 和任一整数a，如果用a 除以n，得到商q和余数r，则以下关系成立：a = qn + r 0≤r n 如果a是一个整数，而n 是一个正整数，则定义 a mod n 为a 除以n 的余数。 例如，30 mod 7 = 2 注意：如果a mod n = 0，则n是a的一个因子 模运算的一些性质 [(a mod n) + (b mod n)] mod n = (a + b) mod n [(a mod n) - (b mod n)] mod n = (a - b) mod n [(a mod n) X (b mod n)] mod n = (a X b) mod n 若(a X b) mod n = (a X c) mod n，则b mod n = c mod n 如果（a mod n）＝（b mod n），则称整数a 和b 模n 同余，记为a ≡ b (mod n) 模运算的同余性质 如果n 能够整除(a – b)，即n|(a – b) ，则a ≡ b mod n 反之，如果a ≡ b mod n，则n 能够整除(a – b)，即n|(a – b) 例如：23 – 8 = 15，而15能够被5整除， 因此23 ≡ 8 mod 5， 23和8是模5同余的。 公开密钥加密算法是整个密码学发展历史中最伟大的一次革命，也许可以说是唯一的一次革命 公开密钥加密算法依赖于数学函数而不依赖于替代和置换 公开密钥加密算法是非对称的，使用两个独立的密钥，因此又称非对称加密算法 公开密钥加密在防范密码攻击上比常规加密更安全 实际上，两者都依赖于密钥长度和解密的计算工作量，从抗密码分析的角度抗，互相之间都不比对方优越 公开密钥加密使得常规加密过时 实际上，公开密钥加密在计算上相对的巨大开销，使得公开密钥加密更多地用于密钥管理和数字签名应用 相对于传统加密使用密钥分发中心的握手协议，感觉使用公钥密码时密钥分发是微不足道的 实际上，公钥密码除需要协议外，还需要中心代理，因此公钥加密的操作并不简单或者高效 公钥密码使得发送端和接收端在不共享任何秘密消息（密钥）的前提下即可交换大量秘密信息（实现保密通信）成为可能！ 解决密钥的分配和共享问题 解决密钥组合爆炸的问题 公钥密码也使得发送端和接收端在实现保密通信的同时各自依然可以保有秘密（私钥）成为可能！－－解决数字签名问题 公钥加密原理 一个公开密钥模型由六要素组成： 明文（Plaintext） 公钥（Public key） 私钥（Private key） 加密算法（Encryption Algorithm） 密文（Ciphertext） 解密算法（Decryption Algorithm） 公开密钥加密的核心在于基于一个单向函数（one-way function，函数计算很容易，但逆运算不可行）设计算法 公钥加密模型 加密/解密：发送方用接收方的公钥加密报文，接收方用自己的私钥解密 数字签名：发送方用自己的私钥签署报文 密钥交换：双方合作以便交换会话密钥 参与方B容易通过计算产生出一对密钥（公开密钥PUb ，私有密钥PRb ），公布PUb 发送方A很容易计算产生密文 接收方B容易计算解密密文 攻击方即使知道公开密钥PUb，要确定私有密钥PRb 在计算上是不可行的 攻击方即使知道公开密钥PUb和密文C，要确定明文M在计算上是不可行的 密码对互相之间可以交换使用 1976年Diffie He