为什么你不能用公钥反向工作来解密消息?

信息安全 加密 公钥基础设施
2021-08-31 07:42:40

正如标题所暗示的,我很想知道为什么你不能使用消息、公钥和加密消息向后工作来计算如何解密消息!

我不明白如何使用密钥对消息进行加密,然后又如何不能向后“撤消”加密?

4个回答

计算机科学中存在单向函数(未经数学证明,但如果不证明,您将变得富有和出名)。这些函数很容易以一种方式解决,但很难逆转,例如,您很容易569 * 757 * 911 = 392397763在一张纸上在一两分钟内计算出来。另一方面,如果我给你392397763并让你找到主要因素,你会很难过。现在,如果这些数字真的很大,即使是世界上最快的计算机也无法在合理的时间内逆转分解。

在公钥密码学中,这些单向函数以巧妙的方式使用,允许某人使用公钥加密某些东西,但很难解密得到的消息。您应该阅读 Wiki 文章RSA 密码系统

你的问题有点像这样(向汤姆斯托帕德道歉):“为什么我可以把果酱搅拌到我的米布丁里,但不能再搅拌出来?”

一些数学运算倒向和向前一样容易。例如,您可以像减 100 一样轻松地将 100 加到一个数字上。但是,有些更难反转。例如,如果我取x并找到g(x) = a(x^5)+b(x^4)+c(x^3)+d(x^2)+ex+f,我只需要做简单的乘法和加法。g(x)但是要从to回来x是困难的(以代数方式),因为五次方程没有一般代数解. 为什么会这样(与二次方程相反)并不是很明显,但确实如此。举个更合适的例子,如果我告诉你 34129 和 105319 都是质数(它们确实是),你将能够快速计算出它们的乘积是 3594432151。但是,如果我让你找出 3594432151 的两个质因数,您可能会发现这相当困难。

公钥加密采用一对密钥。一般而言,私钥为一个方向上难以反转的算法(例如明文到密文)提供参数,而公钥为另一个方向上难以反转的算法提供参数。

因此,您不能向后工作的原因仅仅是因为该算法旨在使这变得困难。

杂耍很容易:您只需在正确的时间扔球,这样当它们落下时您就可以腾出手来。用一个球或两个球,这是微不足道的。有了三个,就很容易了。随着更多的球,它(令人惊讶地)变得更难。甚至更难

总的来说,使用n位密钥完成的“反转”加密就像玩 2 n 个球一样。使用 2048 位密钥,这就像球。或者。

(当然,由于公钥算法使用了大量的数学结构,聪明的人利用数学将球的数量减少到 162259276829213363391578010288128,这要低得多,但仍然远远超过地球上所有现有计算机的总能力。)

Max,曾经为思考密码学而创造的最佳工具是魔方。如果您认为解决它们是一个未解决的问题,那么 DiffieHellmanKeyExchange、RSA 签名、RSA 加密等有直接的类似物。您可以通过写下动作并在立方体上执行它们并交换它们来玩技巧;群论方程对于密码和魔方是相同的。

但要记住的关键是,我认为必须让你感到困扰的是:你是对的。反转所有这些操作是“可能的”。从技术上讲,我们有 f(x) 和 f_inverse(x),其中 f(x) 在多项式时间内运行(即:您可以快速加密大量数字),而 f_inverse(x, s) 在指数时间内运行(即:甚至中等数字是不可行的) - 除非你有正确的秘密 s 来插入 f_inverse。这样的函数对被称为陷门。常见的陷门是数论问题,例如素数分解和离散对数。