-
-
[转帖]知识点 10:RSA 问题和 Strong-RSA 问题的区别是什么
-
2019-10-22 16:46
9286
-
[转帖]知识点 10:RSA 问题和 Strong-RSA 问题的区别是什么
52 Things: Number 10: What is the difference between the RSA and strong-RSA problem?
原文链接:
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 年以上历史了。
[培训]二进制漏洞攻防(第3期);满10人开班;模糊测试与工具使用二次开发;网络协议漏洞挖掘;Linux内核漏洞挖掘与利用;AOSP漏洞挖掘与利用;代码审计。
最后于 2019-10-23 09:57
被tilamisu编辑
,原因: