原文链接： http://bristolcrypto.blogspot.com/2014/12/52-things-number-10-what-is-difference.html 

原文就偷懒了，直接贴图片了，希望能看清楚。

[1] - http://people.csail.mit.edu/rivest/RivestKaliski-RSAProblem.pdf 

密码学大量的依赖这样的假设：某些的数学问题在实际可行的时间内难以解决（困难问题，一般指很难找到多项式时间的算法，或着不存在多项式时间算法） 。在本博文讨论公钥（非对称性）密码时，假设单向函数存在（目前还没有人证证明单向函数存在。计算复杂性理论认为：单向函数存在意味着 P ≠ NP）。

因式分解

数论中第一个讨论的困难问题是因式分解。给定一个合整数 N，因式分解问题是找到正整数 p, q，使得 N = pq。虽然表面上看上去是个简单的问题，但实际上研究表明这是一个棘手的问题。通过检查所有的数 p = 2, .. sqrt(N) （根号N），因式分解问题能在指数时间内解决。目前还没有多项式时间算法解决这个问题。显然，有一些 N 的因式分解例子容易解决，例如 N 是偶数时。因此，在密码学构造中使用因式分解时，我们考虑 N 是一个很大的，由两个大素数 p,q 构成。

RSA 问题

在 RSA 公钥加密 [1] 中，Alice 使用 Bob 的公钥 (n, e) 将明文 M 加密成密文 C。 C = M^e (mod n)，n 是两个大素数的乘积，e >= 3 的奇数（群的这些就不翻译了，符号太难打了，不明白的去看看：信息安全数学基础）。Bob 知道私钥 (n, d)，de = 1 (mod (p - 1)(q - 1))，意味着他能计算 M = C^d (mod n)。敌手可以窃听到密文 C，并且知道公钥 (n, e)，然而计算明文 M, 敌手必须找到 n 的因子。这意味着 RSA 问题不会比因式分解问题更困难，但是选择一个合适的 n, RSA 仍然是一个难解决的问题。

Strong RSA 假设

Strong RSA 假设与 RSA 假设不同的地方是：敌手能选择公共指数 e。敌手的任务是从密文 C 计算明文 M, C = M^e (mod n)。这意味着 Strong RSA 假设是一个更强的假设，至少和 RSA 一样简单（这里的简单不是说 RSA 问题简单，Strong RSA 假设 >= RSA 假设，Strong RSA 假设是很多密码学构造的基础）。RSA 问题至少有 25 年以上历史了。

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课