第七讲RSA和Rabin算法上.pptVIP

第七讲 RSA和Rabin算法(上) Diffie和Hellman提出了建立公钥密码系统的可能性。但是，他们并没有提出公钥密码算法。接下来的几年，一些公钥密码算法相继被提出。其中最为成功的依赖大整数分解困难性的公钥密码算法于1977年由Rivest，Shamir，和Adleman提出。这也就是我们熟知的RSA算法。 虽然经过长期的密码分析并不能证明也不能否定RSA的安全，但是这也无疑给算法的安全性一定承诺。Rabin提出了一个基于计算模合数平方根困难的公钥密码算法。Rabin的工作在理论上具有重要价值，这是因为Rabin算法的安全性等价于大整数分解困难问题。 攻击者攻击公钥密码系统的基本目标是针对特定实体可以系统的从密文消息恢复出明文消息。如果能实现这一目标，就说公钥密码系统被破译。一个更具破坏性的目标是恢复出秘密密钥。 可以想到的攻击形式有选择密文攻击，也就是攻击者选择密文消息，之后以某种手段得到其所对应的明文消息。 (1) (冷漠)选择密文攻击。 (2) 适应性选择密文攻击。 注意这里讲到的公钥密码算法都是假定发送消息者已经得到接受者一份真实的公开密钥拷贝。现实中有许多技术保障真实公开密钥分配，包括：在可信信道上交换密钥，使用可信公开文件，使用在线可信服务器或使用离线服务器和证书。 这一讲的公钥密码方案假定明文消息都是以某个固定比特长度被加密。如果消息明文的长度超过规定长度，需要将其按规定长度分组。为了提供对非法控制分组(例如，重新排序)的防护，可以使用密码分组链接(CBC)模式。 本讲提要 RSA加密算法 RSA加密的执行 RSA加密的安全 1 RSA加密算法 1.1 加密 1.1 加密 (续) 1.1 加密 (续) 1.1 加密 (续)  1.1 加密 (续) 1.2 例子 2 RSA 加密的执行 2.1 素性测试 存在一个奇妙的事实，就是分解大整数虽然十分困难但测试整数的素性并不困难。也就是说证明一个数为合数要比分解它容易的多。我们知道很多大整数是合数但却并不能分解它们。 2.1 素性测试 (续) 2.2 模幂 3 RSA加密的安全 3.1 安全参数?，d ? p，q 3.1 安全参数?，d ? p，q (续) 3.2 关于整数分解 3.2.1 指数分解方法 3.2.1 指数分解方法 (续) 3.2.1 指数分解方法 (续) 3.2.1 指数分解方法 (续) 3.2.2 Pollard的p-1算法 3.2.2 Pollard的p-1算法 (续) 3.2.2 Pollard的p-1算法 (续) 3.2.2 Pollard的p-1算法 (续) 3.2.3 二次域筛法 3.2.4 整数分解的进展 3.3 小加密指数 e 3.3 小加密指数 e (续) 3.4 小解密指数d 3.5 乘法特性 3.5 乘法特性 (续) 3.5 乘法特性 (续) 3.6 共模攻击 3.7 部分密钥泄露攻击 3.7 部分密钥泄露攻击 (续) 谢谢 ! * 3.2.3 二次域筛法 (续) *