第八讲 RSA 和 Rabin 算法 ( 下 )

本讲提要  RSA 加密的安全 ( 续 )  RSA 加密实践  Rabin 加密算法  Rabin 加密的执行  Rabin 加密的安全  公钥加密的总结

3.8 循环攻击

3.8 循环攻击 ( 续 )

3.9 消息隐藏问题

3.9 消息隐藏问题 ( 续 )

3.10 前项搜索攻击

3.11 RSA-OAEP

3.11 RSA-OAEP ( 续 )

3.12 定时攻击 对 RSA 算法的攻击，可能不仅仅来自算法本 身，对其的不恰当执行同样可能导致系统的 漏洞。攻击者将可能利用这些执行的弱点来 危及整个 RSA 系统的安全。对密码系统的执 行攻击受到安全工程师和用户的极大关注。 执行攻击包括：定时攻击，电耗分析攻击， 出错攻击，和电磁辐射攻击等。我们常常称 这些攻击为边信道攻击 (side-channel attacks) 。 边信道这个词用来描述从目标设备，例如， 智能卡，无意泄露的信息。

3.12 定时攻击 ( 续 ) 在定时攻击中的边信道是指设备在做秘密 密钥操作时需要的时间。攻击者能够仔细 的测量目标系统的执行时间进而发现存储 于设备中的秘密密钥，最终使整个安全系 统崩溃。不少现实系统潜在受到这一攻击 威胁，包括各种密码令牌，基于网络的密 码系统，以及其它攻击者可以准确测量执 行时间的应用系统。

3.12 定时攻击 ( 续 ) 假定环境. 攻击者可以观察系统对多个密 文消息 g 的解密。他也知道加密算法的执 行细节并能应用这些信息确定可能发生 在算法计算过程中的不同步骤需要的执 行时间。同时，假定计算 g d (mod n) 使用 的是上一讲的算法 4 。

3.12 定时攻击 ( 续 )

4 RSA 加密实践 4.1 模的大小 根据分解整数算法特别是数域筛法的进展， RSA 中的模 n 应该至少为 1024 比特。从长 远的安全考虑，应该使用 2048 比特或更大 的模。

4.2 素数的选择 (1) 素数 p 和 q 的选择原则是使分解整数 n =p  q 在计算上不可能。主要对 p 和 q 的限制 是它们必须有足够的长度并且有差不多 相等的比特长度。例如，如果使用 1024 比特的模 n ，那么， p 和 q 应该都是在 512 比特左右。 (2) 另一个对素数 p 和 q 的限制是 p  q 不能 太小。如果 p 和 q 是随机选择产生，则 p  q 将会以压倒的概率比较大。

4.2 素数的选择 ( 续 ) (3) 许多地方推荐使用强素数 p 和 q 。一个素数 p 是强素数需要满足以下三个条件： * p  1 有大的素数因子，称为 r ； ** p+1 也有大的素数因子； *** r  1 仍然有大的素数因子。

第一个条件的原因是存在 Pollard 的 p  1 分 解算法，这一算法只在模 n 存在一个素数 因子 p 满足 p  1 平滑时有效；第二个条件的 原因是存在 p+1 分解算法，这一算法只在 模 n 存在一个素数因子 p 满足 p  1 平滑时有 效；第三个条件的原因为了保证循环攻击 无效。

如果素数 p 随机选择且足够大，则 p  1 和 p+1 将有非常大的可能有大素数因子。此外，如 果 p 和 q 为随机选择，则循环攻击成功的可能 性可以忽略。因此，强素数并不能比随机选 择素数提供太多的保护。以现有的分解算法 知识，并没有一定需要使用强素数的理由。 另一方面，产生强素数相对随机产生素数仅 增加了微小的计算时间，因此，即使使用强 素数也不会带来多少开销。

4.3 指数 (1) 如果随机选择加密指数 e ，则 RSA 加密 使用算法 4 将需要 k 次模平方和平均 k/2 次 模乘，这里 k 是模 n 的比特长度。加密速 度可以通过选择小的加密指数 e 并 ( 或 ) 选 择加密指数 e 的二进制表示中 1 的个数尽 量少。

4.3 指数 ( 续 ) (2) 在实际中，加密指数通常选择 e=3 。在这 种情况下，要求 p  1 和 q  1 都不可以被 3 整除。 这样做的好处是加密操作速度非常快只需要 1 次模乘和 1 次模平方。另一个在实际中经常使 用的加密指数为 e= =65537 。这个数字的 二进制表示中仅有 2 个 1 ，因此，在使用算法 4 加密时仅需要 16 次模平方和 1 次模乘。加密指 数 e= 常常认为优于 e=3 ，这是由于在应 用中通常不太可能将同一条消息发送给 个接收者。

4.3 指数 ( 续 ) (3) 由于小指数攻击，需要解密指数 d>n 。 Boneh 和 Durfee 认为他们的攻击算法不能算 做理论，这是因为他们也不能证明攻击算 法一定总能成功。但是通过实验已经证实 了攻击算法的确有效，他们并没有发现一 个例子会导致攻击算法失败。

5 Rabin 加密算法 5.1 算法描述

5.1 算法描述 ( 续 )

6 Rabin 加密的执行 6.1 计算平方根

6.2 关于效率 Rabin 加密过程的效率非常高，这是因为仅 需要 1 次模平方计算。比较而言， RSA 加密 使用加密指 e=3 需要 1 次模乘和模平方计算。 Rabin 解密速度要比加密慢，但是与 RSA 解 密在一个数量级上。

6.3 冗余问题 Rabin 公钥加密方案的一个缺点是接收者需要 从 4 种可能情况中选择一个正确的解密明文消 息。这一解密中的不确定问题在实践中可以 通过预先增加定义原始明文消息冗余来解决。 ( 例如，明文消息的最后 64 比特需要被复制。 ) 这样，将有非常高的概率解密出来的 4 个可能 明文消息中仅有一个符合冗余的规则。如果 4 个平方根中没有一个符合冗余规则，则接收 者就认为出错而拒绝密文消息。

(1) Rabin 公钥加密方案存在类似 RSA 加密中 的小指数加密和前项搜索问题。前项搜索问 题可以通过明文消息加盐来解决。 (2) 作为被动攻击者的任务是从密文消息 c 恢 复出明文消息 m 。这就是平方根 SQROOT 问 题。分解 n 和计算模 n 的平方根问题在计算上 是等价的。因此，假定分解 n 在计算上不可 能， Rabin 公钥加密方案就可以证明能够抵 抗被动攻击者的攻击。 7 Rabin 加密的安全

理由. 假定有一个多项式时间的算法 R 可以解 决 SQROOT 问题。这个算法就可以用来解决 合数 n 的分解问题。随机选择一个整数 x 满足 (x ， n)=1 ，并计算 a  x 2 (mod n) 。接下来，算 法 R 在输入为 a 和 n 的情况下运行，返回模 n 平方根 y 。如果 y  x(mod n) ，分解尝试失败， 随机选择另一个整数 x 重复上述过程。否则， (x  y ， n) 就可以得到 n 的一个非平凡因子， p 或 q 。由于 a 有 4 个模 n 的平方根，每次尝试成 功的可能性为 1/2 。

(3) 对于主动攻击者， Rabin 公钥加密存在选 择密文攻击问题。这样的攻击可以按如下步 骤进行。攻击者选择一个随机整数 m 并计算 c  m 2 (mod n) 。攻击者提交 c 给 A 的解密机， 它将解密 c 并返回某个明文消息 y 。由于 A 不 知道明文消息 m ，并且 m 为随机选择，明文 消息 y 未必就是同一个消息 m 。如果随机返回， 将有 1/2 可能性， y 不等于  m(mod n) ，在这种 情况下， (m  y ， n) 就是 n 的一个素数因子。 否则，攻击可以换新的 m 重复以上过程。

(4) 如果将冗余规则用于以上情况，则 Rabin 公钥加密方案将不在存在选择密文攻击问题。 如果攻击者选择一条消息 m 并具有规定的冗 余并将 c  m 2 (mod n) 提交给 A 的加密机，加密 机将以非常高的概率返回消息 m 本身给攻击 者 ( 由于其它 3 个 c 的模平方根有非常大的概 率不包含规定的冗余 ) ，则将不会提供给攻 击者任何信息。另一方面，如果攻击者选择 不包含冗余的消息 m ，则有非常高的可能性 4 个模平方根都不具有需要的冗余形式。在这 种情况下，解密机将认为对 c 的解密失败并 对攻击者不做答复。因此， Rabin 公钥加密 通过增加适当的冗余规则将提高其实用价值。

8 公钥加密的总结 8.1 公钥加密的要求 在一个公钥系统中，消息集合 M ，密钥集 合 K ，和加 / 解密函数 E/D ，必须满足如下 要求： (1) 对于任何消息 m  M ，满足 D k (E k (m))=m 。 (2) 对于每一个消息 m  M 和密钥 k  K ，值 E k (m) 和 D k (m) 容易计算。

8.1 公钥加密的要求 ( 续 ) (3) 给定密钥 k  K ，很容易找到函数 E k 和 D k 。 (4) 对于几乎所有密钥 k  K ，如果仅仅知 道函数 E k ，不可能发现一个算法有效计算 函数 D k 。

8.1 公钥加密的要求 ( 续 )

8.2 关于认证和不可否认 (1) 在对称密码系统中，认证是容易的， 但不存在不可否认问题。 (2) 在公钥密码系统中，认证和不可否认 都不能自然成立。但是，这些目标容易实 现。例如，在 RSA 系统中计算并发送消息 E kb (S ka (m))=E kb (D ka (m)) 。

8.3 陷门单向函数

8.3 陷门单向函数 ( 续 )

谢谢！