非对称加密如何工作？

#1 楼

一般而言，公钥及其对应的私钥通过其内部数学结构链接在一起；这样的密钥不是随机的随机比特的任意序列。加密和解密算法利用了这种结构。

公钥加密系统的一种可能设计是活板门置换。活板门置换是一种数学函数，它是某些空间的置换，因此以一种方式计算该函数很容易，但是反之则很难，除非您知道有关活板门置换如何构建的信息。加密是在邮件上应用该功能，解密是使用陷阱门将功能反转。

对于RSA（一种众所周知的非对称加密算法），请考虑使用较大的密码（例如300位或更多）整数$ n $。 $ n $是复合的：它是两个大质数整数$ p $和$ q $的乘积。这样的复合整数比可观察的宇宙中的粒子多，因此生成这样的整数没有问题。 $ n $之所以称为模数，是因为我们将计算“模$ n $”。事实证明：


以$ n $为模，很容易计算多维数据集（给定$ m $，计算$ m ^ 3 \ mod n $）；
如果$ p $和$ q $的选择是适当的（我略过了细节），加到多维数据集上的是模$ n $的置换（没有两个整数$ n $会具有相同的多维数据集，因此$ 0 $和$ n之间的任何整数-1 $具有唯一的求模$ n $的立方根）;
计算整数模$ n $的立方根非常困难
...除非您知道$ p $和$ q $，在这种情况下，计算变得很容易；
从$ n $中恢复$ p $和$ q $（即因式分解）非常困难。

因此，公钥是$ n $，活板门排列将幂提高到3，反之则是计算立方根； $ p $和$ q $的知识是私钥。即使公用密钥是公用密钥，专用密钥也可以保持“专用”，因为从公用密钥重新计算专用密钥是一个难题。

RSA的内容比上面的描述还多了一些（特别是RSA不一定使用3的幂，但是思想的主旨在那里：一个功能对每个人都是单向的，除了首先选择该功能的人，其内部结构是隐藏的SSL（现在称为TLS）是一种更复杂的野兽，通常在连接的初始阶段使用一些非对称加密，因此客户端和服务器最终会被使用。具有“共享机密”（众所周知的位序列）；然后，共享机密将用于对其余数据进行常规加密和解密（“常规”含义：用于加密和解密的相同密钥）。

#2 楼

许多答案都说“数学结构”是绝对正确的，但是我仍然看到可能存在一个问题：地球上怎么存在？我将尝试在一个更简单的级别上填补这一空白。

所以一个简单的caeser-shift密码可能看起来像这样：$ x + 7 $。在我们真正简单化，危险的示例中，这里的“关键”是$ 7 $。如果我有一些加密的文本，我知道通过减去$ 7 $，我会回到$ x $。因此，这是一个非常简单的对称密码示例，因为我做过的一种方式还允许我撤消它。

您可能已经注意到，密码学中的大多数域都是有限的，例如，字母表中只有26个字母。在某些时候，您需要“环绕”。数学为我们提供了一种进行模运算的技术。本质上，在模数下，您可以认为“如果将其除以模数，则剩下的数”。一些示例：


$ 4 = 4 \ mod 7 $
$ 8 = 1 \ mod 7 $（8/7 = 1余数1）
$ 4 + 7 = 4 \ mod 7 $（11/7 = 1个余数4）
$ -3 = 4 \ mod 7 $（不太难...将7加到-3会发生什么？）

如您所见，算术在模数下成立。本科数学课程严格地建立了这些真理，如果您有兴趣，请阅读数字和小组理论。下一步是了解乘法也成立：


$ 2 * 4 = 1 \ mod 7 $（2 * 4 = 8，如上所述）
$ 5 * 3 = 1 \ mod 7 $（5 * 3 = 15，15/7 = 2余数1）

依此类推。当涉及到逆运算时，数学乘法通常会引发一些问题-例如，如何从1变回5？我可以乘以5。如何从1恢复到2？乘以2。就我想显示的内容而言，这些示例并不完全正确，因此这里有更多示例：


$ 6 * 3 = 4 \ mod 7 $（6 * 3 = 18。18/7 = 2个余数4）
$ 4 * 5 = 6 \ mod 7 $（4 * 5 = 20。20/7 = 2个余数6）。

通过这些示例，我证明了您可以使用乘法从6扩展到4，然后再乘回6，但这可以通过乘以不同的东西来实现。结构体。 RSA的天才在于选择涉及的数字，以便人们可以轻松确定如何获取加密值，而又不会再次获取。我已经在另一个答案中充分解释了；但是，从本质上讲，它只是我们在这里所做的工作的一个更复杂的版本。聪明的部分是理解那些结构，以及数字的哪些选择构成好/坏键，哪些起作用/不起作用。

但是你告诉我乘法很难撤销：除法呢？

首先，这确实取决于环境。在某些情况下，例如上面我提到的琐碎示例，找到一个逆数甚至使用除法都很容易。考虑划分的意义很重要。在一个有理数（可以写为分数的任何数字）字段中，乘法逆以$ p *（1 / p）$的形式存在（以及$ p * q = 1 $）。

但是，在考虑RSA时，请注意，对于某些公钥$ e $，加密是$ t \ timest \ times \ ldots = t ^ e = c \ mod n $。因此，要计算逆，我们需要计算$ c \ times（1 / t）\ times（1 / t）\ times \ ldots = c \ times（1 / t）^ e \ mod n $。原因是$ t $的每个乘法都需要由逆$（1 / t）$撤消，但是应该清楚的是，如果我们只有密文$ c $，我们就不知道$ t $计算$ 1 / t $。

因此，我们的下一个可行途径是将$ c ^ {1 / e} $计算为$ t ^ {e * 1 / e} = t $。这等效于计算$ c $的平方根（例如，$ x ^ {1/2} = \ sqrt {x} $），这在RSA要求的大小模数下很难做到。使用-在某些情况下。在其他情况下，这称为“多维数据集根”攻击：请参阅此演示文稿和本演示文稿。

其他公钥加密系统也使用类似的观察结果-例如，Diffie-Hellman依赖于此属性：
$$ a ^ x = b \ mod n $$
在某些n情况下（例如$（ \ mathbb {Z} _p，\ times）$，即，当n为质数且我们仅对乘法感兴趣时，因此a大于或等于1）这很难逆转。这构成了许多其他公共密码系统的基础。

#3 楼

在基本级别上，客户端（即浏览器）和服务器协商密钥交换算法以得出随机会话密钥，然后它们使用该私钥通过对称算法来加密流量。

有关该过程的很多细节，我在我的博客上广泛地写了此内容：HTTPS连接的最初几毫秒

#4 楼

最简单的解释方法是，两个密钥具有特殊的数学关系，允许一个密钥（私钥或私钥）撤销另一个密钥（公钥）的作用。

所有非对称加密方案除非您有一些秘密知识，否则它们需要一些无法轻易逆转的操作。有了这一知识，就可以逆转操作。

一种常见的加密方案使用以下关系：


给定非常大的m和n，选择一个数p，计算：s = pm模n
现在尝试反转该运算并从s，m和n获得p。
给定p，m和n，计算s很容易，但是给定m，n和s，
计算p非常困难。运算并从k获得m和n。乘法
很简单。在素数附近分解非常大的元素非常困难。

#5 楼

其他人已经很好地解释了“如何”，但是据我所知，没有人写过“非对称加密的作用是什么？”。

，正如许多人认为的那样，它并没有神奇地允许两方合作爱丽丝（Alice）和鲍勃（Bob）可以通过公共频道进行安全通信。

相反，给定了从爱丽丝（Alice）到鲍勃（Bob）的真实频道，公共密钥加密技术随后可以将鲍勃（Bob）到爱丽丝（Alice）的公共频道转换为秘密通道。

相比之下，常规秘密密钥密码术无法利用真实的通道，除非它们也是秘密的。给定从Alice到Bob的秘密（但可能不是真实的）信道，任何时候以后都可以使用秘密密钥加密（MAC）将Bob到Alice的公共信道设为真实，但是只有当从Alice到Bob的信道才是秘密的鲍勃是真实的。 （出于完整性考虑，密钥加密的主要目的是，如果以前有从Alice到Bob的秘密通道，则将从Alice到Bob的公共通道转换为秘密通道。）

#6 楼

非对称（密钥）加密（也称为公钥加密）一次使用两个不同的密钥：私钥和公钥的组合。私钥只有您自己知道，而公钥可以发布给希望与您进行安全通信的任何人查看。

要解码加密的消息，计算机必须使用原始计算机提供的自己的私钥和公钥。即使从一台计算机发送到另一台计算机的消息不安全（因为用于加密的公共密钥已发布并且对任何人都可用），但选择了公共密钥的任何人都不能在没有相关私有密钥的情况下使用它们。 br />
密钥对基于大（长）素数。使公钥加密变得安全的原因在于，实际上有无限数量的质数可用...从理论上讲，这意味着几乎有无限可能使用密钥。

如果您想更深入地研究它，则应查看一些公钥密码学的著名示例，例如Diffie-Hellman密钥交换（作为其中的一个示例）。

#7 楼

我正在从出色的著作《数学密码学概论》中学习现代密码学背后的数学。这是他们对同一事物的解释：

假设爱丽丝想与多人进行秘密交流，其中之一就是鲍勃。 Eve是我们的常规攻击者，始终试图摆脱加密方案并提取明文。公钥密码技术如何帮助Alice和Bob安全通信的抽象如下。
Alice公开地放置一个保险箱。每个人都可以通过在保险箱上的插槽中放几张纸来发送消息。但是，只有Alice才具有打开保险箱和提取消息所需的密钥。
此处，保险箱代表了Alice的公开密钥，所有人都可以看到。消息一旦插入插槽并放在保险柜内，就代表由Alice的公钥和Bob的Bob（以及可能向她发送消息的所有其他人）的私钥对明文进行操作。用钥匙打开保险箱的爱丽丝代表爱丽丝使用她自己的私钥来解密密文。果然，在PKC中，每个人都可以看到接收者的公钥，而发送者和接收者都必须维护其私钥秘密。

我想使用活板门功能和PKC背后的实际数学方法是其他答案已经很好地解释了。但这比喻帮助我理解了公钥和私钥的概念。

#8 楼

在数学上有2个相互关联的键。这些使用所谓的陷门功能=一方面非常容易，另一方面则非常困难。
例如：将两个大数字相乘很容易。找出它们组成的素数非常困难（几乎是不可能的）。在RSA中，它的工作原理是这样的。在ECC中，情况有所不同。加密算法使用此公钥来加密某些内容。只有相关的私钥才能对其解密。 （其背后的数学非常复杂）