原文链接： 4a2K9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8X3u0J5K9i4y4@1L8$3I4U0M7Y4W2H3N6r3!0Q4x3X3g2T1L8r3!0Y4M7%4m8G2N6q4)9J5k6h3y4G2L8g2)9J5c8U0t1H3x3e0c8Q4x3V1j5I4x3W2)9J5c8U0f1J5i4K6u0V1N6r3S2A6L8X3N6K6i4K6u0V1L8Y4g2E0j5X3g2J5i4K6u0V1x3e0m8Q4x3X3c8%4K9r3q4@1i4K6u0V1K9i4y4Q4x3X3c8V1K9h3k6X3k6i4u0W2L8X3y4W2i4K6u0W2K9s2c8E0L8q4)9J5y4X3&6T1M7%4m8Q4x3@1t1`.

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

[1] - 89eK9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8Y4m8W2L8%4m8D9k6g2)9J5k6h3y4K6j5h3W2D9i4K6u0W2L8h3W2@1i4K6u0W2k6h3c8#2i4K6u0r3M7X3W2$3k6i4y4@1i4K6u0r3f1X3W2$3k6i4y4@1d9$3q4D9K9i4y4C8K9g2)9J5k6q4u0e0b7g2m8J5L8$3u0D9k6h3#2Q4x3X3g2H3k6r3k6Q4x3U0k6F1j5Y4y4H3i4K6y4n7

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

[培训]科锐软件逆向54期预科班、正式班开始火爆招生报名啦！！！