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