椭圆曲线加密原理

这篇文章旨在解释运用椭圆曲线的数学知识加密的原理，抽离了数学细节，尽量用简单的图形解释椭圆曲线加密算法。内容从基础到密钥交换，加密和解密。为了绘制椭圆曲线，并了解事物的工作方式，可以使用Python进行曲线绘制和计算。绘图库是matplotlib。

椭圆曲线是由y^2= x^3+ a x + b

例如，让a=−3并且b=5，然后绘制曲线时，它看起来像这样：

现在，让我们玩一个游戏。选取曲线上x值不同的两个不同的随机点，并用一条直线连接这两个点，假设A和B。然后您会注意到直线在第三点触及曲线。找到第三个点并将其y值翻转到x轴的另一侧后，我们将其称为A+B。

A和B线接触曲线上的第三个点，并且其相反点位于x轴的另一侧

点A+B是A的总和和B。您可以认为此过程是某种太空旅行。想象有敌人跟随您的飞船。要失去敌人，您可以直接从路线上走近一条捷径，到达路线上的另一点，一旦到达第三点，就会迅速反弹到路线的另一侧。

好吧，敌人仍然跟随，让我们再做一次。这次我们从最后一点A+B开始到另一点C。

A + B和C线接触曲线上的第三个点，其相反点在x轴的另一侧

如您所见，只要新线不是垂直的，我们就可以通过添加新的点来反弹来重复相同的技巧。

随着时间的流逝，您意识到找到一个新的起点很繁琐。为了使技巧更直观，更容易重复，现在让我们沿当前位置P的切线使用快捷方式，它看起来像这样：

P的切线触及曲线上的第三个点，其相反点位于x轴的另一侧

考虑前面两点式的跳跃技巧，就像看到A点一样B点在P处彼此无限接近，实际上是相同的把戏。这样我们就可以应用前面的规则，调用P的结果总和和P，即P+ P，即2P。

同样地，我们可以重复同一步骤以输掉敌人，这一次，我们从2P开始回到原点P：

2P的切线接触曲线上的第三个点，其相反点位于x轴的另一侧

为了得到结果，我们称它为P+2 P或3P。显然，我们可以多次这样做以达到NP。现在，给定点N的坐标，问题就来了P，你能找出什么是N值？换句话说，我们从P跳了多少次至NP，如下图所示：

定起点P和终点NP，您能找到N值是多少？

我可以告诉你答案N所述的ÑP上图的点是13。我说起来真的很容易，因为我选择了这个号码。您将很难找到答案，因为没有已知的简单有效的方法来计算N 值。

就是这样，您刚刚学习了椭圆曲线密码学的基础！曲线和原点P是每个人都知道并同意使用的共享价值，最后一点NP是您的公开密钥，可以安全地共享给任何人。您跳了多少步，值N是您的私钥。正如我们所说，只知道N的人P和P，对于他们来说很难找出您的私钥，因为众所周知这是一个很难解决的问题。

没那么快！

要获得NP点，并不意味着您需要进行N次。如果您可以在合理的时间内完成操作，那么我是否可以做同样的事情，一步一步向前走，直到遇到相同的点NP才能确切地知道需要执行多少步骤？

问题是，对于求和运算，或者我们在椭圆曲线上做的技巧有一个有趣的特征。曲线上的点和求和运算遵循群律。这个想法是，您可以对组中的元素进行某种操作，在这里我们称其为“添加”，它们仍将保留在组中。并且该操作具有特定的属性。一种特定的属性关联性是这样的：

（A + B ）+ C

是相同的

A + （B + C）

这个概念背后的数学证明实际上是不容易的，你可以看到它在这里或在这里如果你有兴趣。虽然很难证明，但是如果绘制曲线和直线，则很容易自己查看。让我们来看一个例子。如您所见，我们有一个点（A+B）+C上面，根据关联性，我们应该能够做B+C首先是A+（B+C），并且它应该到达相同的最终位置。现在是B+C。

B和C线接触曲线上的第三点，并且其相反点位于x轴的另一侧

接下来，让我们做A+（B+C）。

A和（B + C）线接触曲线上的第三个点，其相反点位于x轴的另一侧

看最终位置，它与（A+B）+C完全相同。不相信我吗？这是我编写的程序中打印出的值：

ab_c = ab + c

a_bc = a + bc

(ab_c, a_bc)

(Point(0.9531851331698311,1.733918191357413),

 Point(0.9531851331698316, 1.7339181913574133))

如您所见，ab_c并且a_bc几乎是相同的。差异是由于浮点计算舍入误差。这实际上是一个大问题，我们将在后面讨论。

类似地，对于单点情况，群律允许我们以不同的顺序求和到相同的位置。这是关键一点，请记住我们如何达到3P通过P+ 2 P？现在我想告诉你

P+ 3 P= 4 P

是相同的

2 P+ 2 P= 4 P

首先，让我们看一下以愚蠢的方式进行计算，只是继续添加P。这是最后的步骤P+ 3 P：

和3P线接触曲线上的第三点，并且其相反点位于x轴的另一侧

然后，让我们尝试添加点2P 本身，这正是我们之前做过的切线切线技巧：

2P切线接触曲线上的第三个点，其相反点位于x轴的另一侧

看到？两种方式都导致相同的结果。就是这样，因为我们可以轻松地将一个点加倍，并且添加顺序无关紧要。我们可以通过不断加倍一个点并选择需要快速合成所需值的点的幂来“作弊”，而无需将其一一加起来。

让我们尝试增加一个更大的数字，例如227P，让我们首先将其分解为二进制，以便获得其两个成分的幂。其二进制表示为

11100011

换句话说，将两个值的所有幂加起来就是

27P+ 26P+ 25P+ 21个P+ 20P

和即

128 P+ 64 P+ 32 P+ 2 P+ P

所以我们需要的操作是

加P并加倍P

加2P和双2P

双4P

双8P

双16P

加32P和双32P

加64P和加倍64P

加128P和双128P

仅需8步，而227步则更快。此方法称为double和add。它使我们可以快速地在椭圆曲线上达到所需的多次点跳变。数227在此示例中，假设我们可以使用O（logn ），甚至与宇宙中原子的数量一样多，例如1082，大约是2275，此方法仍可以通过275个重复步骤来完成计算。

现在我们知道了如何以经线速度在椭圆曲线上向前跳跃，因此，我们可以轻松地向前跳跃达数十亿次。虽然对我们来说很容易，但是对于攻击者而言，要确切地知道我们跳了多少次是非常困难的，即找出什么是NN的价值P和P如果N，则给出点够大的 这称为椭圆曲线离散对数问题，如果您想了解更多有关此主题的信息，可以进行搜索。

让我们首先介绍密钥交换。

想想看，爱丽丝和鲍勃正在太空旅行，他们将交换叛乱新总部的位置。突然，他们意识到帝国的无人机正在拖尾它们并拦截其航天器之间的通信。为了安全地交换信息，他们同意在只有他们两个都知道的秘密坐标下会面。但是，如果敌人正在窃听，他们如何交换这个秘密坐标呢？现在，椭圆曲线密码术在这里进行救援。这是爱丽丝和鲍勃要做的事情：

爱丽丝：

嘿鲍勃，让我们以P为起点，这是我的公钥NP

鲍勃：

以P为起点对我来说听起来不错，而我的公钥是MP

在这里，按照我们的定义，NP是P的点N之后求和运算次数。同样，MP是P的点M之后 求和运算次数。

接下来，爱丽丝以鲍勃的MP，开始将此点添加到自身N 时间：

鲍勃将改用爱丽丝的公钥NP并将此点添加到自身M 时间：

恩，M和N很大，因为我们不希望敌人轻易发现它。显然，他们并没有真正做到一对一的添加，他们只是在使用我们刚刚介绍的“加法加法”作弊。最终，他们将在一个秘密的协调满足小号ķ 只有他们知道

小号ķ= （N× M）P= （M× N）P

想想看，对于爱丽丝，每一跳都是M点P的价值倍，她为N做次。对于鲍勃来说，每次跳跃都是N点P的价值倍，他为M做时间。假设爱丽丝一次跳跃4光年，而她跳跃3次。鲍勃一次跳跃3光年，他跳跃4次，即4×3或3×4他们都将在12点结束：

跳4点3倍或跳3点4倍相同

对于窃听者，他们需要找出N或M以获得相同的坐标。迈出一步，最后一点将完全消失。但是，正如我们之前提到的，鉴于数量足够大，没有简单的方法可以做到这一点，因此我们可以确定只有爱丽丝和鲍勃才能知道这个秘密坐标。这种密钥交换协议称为椭圆曲线Diffie-Hellman。

加密

现在让我们谈谈加密。对于爱丽丝，要将信息安全地发送给鲍勃，他们需要首先执行椭圆曲线Diffie-Hellman密钥交换，正如我们上面刚刚提到的：

爱丽丝和鲍勃执行ECDH进行密钥交换并获得共享密钥SK

请注意此处，爱丽丝需要能够验证公钥MP真的属于鲍勃。否则，冒名顶替者可以向爱丽丝提供自己的公钥，并声称自己是鲍勃。然后，爱丽丝将与攻击者交换共享密钥。然后，攻击者可以进行中间人攻击。为了解决该问题，还有另一个概念称为“公钥基础结构”，因为它不在主题范围内，如果您感兴趣，可以对其进行搜索。

由于今天我们只想关注椭圆曲线密码学，所以假设爱丽丝已经知道MP并真诚地知道它来自鲍勃，鲍勃也知道爱丽丝的公钥。现在，在交换密钥之后，他们最终得到了相同的共享秘密坐标，我们可以将x值作为密钥。一旦我们有了一个共享的秘密，现在就很容易了。然后，我们可以使用任何安全的对称加密方法使用共享密钥S对我们的机密数据进行加密。ķ。假设我们在这里使用AES256。接收者Bob可以使用相同的共享密钥S解密加密的消息。ķ。

爱丽丝使用共享密钥SK加密该秘密消息，并将其发送给鲍勃，然后鲍勃使用共享密钥SK对其解密。

太好了，现在即使帝国的无人机窃听了所有通信，爱丽丝仍可以安全地与鲍勃共享叛乱新总部的位置。同样，鲍勃可以使用相同的共享密钥Sķ 加密安全消息并将其发送回爱丽丝。

当爱丽丝（Alice）和鲍勃（Bob）彼此认识时，我们知道可以使用椭圆曲线密码术安全地发送消息。但是，如果在某些情况下我们想安全地向某人发送消息，但他们不知道并且可能不在乎您是谁，该怎么办？很简单，在我们的示例中，我们假设鲍勃已经知道爱丽丝的公钥，假设只有爱丽丝知道鲍勃的公钥MP，她可以使用自己的私钥N，生成相同的共享密钥Sķ，加密数据并发送她的公共密钥NP以纯文本格式以及加密数据。鲍勃收到消息后，就可以使用NP和他的私钥M创建相同的密钥Sķ并解密加密的数据。但是，鲍勃将无法知道消息是来自谁的，因为附加的公共密钥NP可以属于任何人。如果Bob不在乎发件人是谁，Alice也可以选择为同一操作创建一个临时的新密钥对。

浮点问题

到目前为止，我们一直在讨论具有实数计算的椭圆曲线密码学。我们在这里使用实数的原因是它更容易解释和理解。在现实世界中，这实际上并不是我们进行加密的方式。使用实数会带来很多问题，我们之前显示的一个大问题是会出现计算错误。另一个问题是，在某些极端情况下，该数字可能会非常庞大，并且浮点数可能无法容纳它。

您可能会问，我们应该使用什么代替，答案是在有限域或更精确地在对p取模为p的整数的有限域上执行它，其中p是质数。同样，我们不想挖兔子洞太深，所以如果你有兴趣，你可以阅读椭圆曲线密码：有限域离散对数，或观看从Trustica这一系列的视频和它们的相应条款。

要在数学中解释整数模p的有限域上的椭圆曲线：

ÿ2≡ X3+ a x + b（国防部p ）

我们选择p=19令a=−3并且b=5，然后将其可视化：

整数模p = 19的有限域上的椭圆曲线

这看起来似乎不太像“曲线”，但确实是在有限域上的椭圆曲线。基本上，y2（国防部p ）将等于x3+ a x + b（国防部p ）仅在特定的整数点上。取点（11，7）例如，对于y：

ÿ2≡ 72≡ 49 ≡ 11（国防部19 ）

对于x：

X3+ 一个X + b ≡ 113- 3 × 11 + 5 ≡ 1303 ≡ 11（国防部19 ）

由于双方有相同的余数11除以19，所以的确是曲线上的一点。

虽然它看起来不像曲线，但它确实遵循与实数相同的群定律。让我们来看一个例子，设定点甲=（3，2）和乙=（5，18），然后计算A+B 用相同的总和运算：

取p = 19的整数的有限域上的椭圆曲线，求和点A + B

是的，关于有限区域上的该曲线有些特殊，当一条线到达边界时，实际上可以弯曲到另一端，因为模块化操作是在绕来绕去的。这条线会碰到第三点，就像实数上的曲线一样。

鉴于我们的例子中，（18，8）是我们要达到的目标。我们翻转y价值8是-8和mod 19将让你（18，11）。所以A的总和和B是（18，11）。

为了更容易理解，我个人非常喜欢在3D空间中将其呈现为甜甜圈形状，就像Trustica视频系列中有关ECC的视频那样：

来自Trustica系列视频的 3D空间有限域上的椭圆曲线呈甜甜圈形状

但是考虑到我正在写一篇文章，将其以简单的2D图像呈现会更容易。

现在，让我们添加一个新点C=（10 ，14 ）到A+B：

整数有限域以p = 19为模的椭圆曲线，总和（A + B）+ C

接下来，让我们看看组法的结合性是否仍然与有限域保持一致，这一次我们添加B+C 第一：

整数有限域的椭圆曲线，模p= 19，总和B + C

然后，我们添加一个到B+C：

整数模p = 19的有限域上的椭圆曲线，总和A +（B + C）

是的，它们在相同的点两端向上（14，16）：

a_b = a + b

b_c = b + c

(a_b + c), (a + b_c)

(Point(p=19, x=14, y=16), Point(p=19, x=14,y=16))

现在您可能会问，如何在自身上添加点？是的，加点本身具有相同的规则，即使用有限域上的切线连接第三个。正如我们已经展示了它如何处理实数一样，我们不想在这里重复自己，或者实际上是因为我很懒。

最后，由于有限字段仅对整数进行运算，因此我们不会损失任何精度。它更适合于加密目的。