cryptography - 是什么让椭圆曲线密码学中的陷门函数难以逆转？

Question

我一直在阅读这篇关于椭圆曲线加密及其工作原理的文章:
http://arstechnica.com/security/2013/10/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/

在文章中，他们说:

It turns out that if you have two points [on an elliptic curve], an initial point "dotted" with itself n times to arrive at a final point [on the curve], finding out n when you only know the final point and the first point is hard.

它继续指出，找出 n 的唯一方法(如果你只有第一个和最后一个点，并且你知道曲线 eqn)，就是重复点初始点，直到你最终得到匹配的最终点。

我想我明白这一切 - 但让我感到困惑的是 - 如果 n 是私钥，并且最后一点对应于公钥(我认为是这种情况)，那么它不需要完全相同的工作量吗从私钥计算公钥，就像从公钥计算私钥一样(两者都只需要递归地在曲线上点一个点)？我是否误解了文章所说的内容？

Answer 1

编辑:我之前说过 n 不是私钥。在您的示例中， n 是 服务器或客户端私钥。

它的工作原理是有一个任何人都知道的起点。

您选择随机整数 k 并进行“打点操作” k 次。然后将这个新点发送到服务器。 ( k 是你的私钥)

服务器对起点做同样的事情，但是 q -times 并将其发送给您。 ( q 是服务器的私钥)

你把你从服务器得到的点“点”它 k 次。最后一点将是起点“点” k*q 次。

服务器对它从你那里得到的点做同样的事情。再一次，它的最后一点将是起点“点” q*k 次。

这意味着终点(= 起点“点” k*q -times)是共享 secret ，因为任何攻击者都知道起点，起点点点 k 次和起点点缀 q 次。并且仅给出这些数据，实际上不可能找到作为 k*q 乘积的最终点，除非其中任何一个已知。

编辑:不，计算 不需要相同的时间k 从 G = kP 给定 G(发送点)和 P(起点)的已知值。更多在评论部分和:

要上台，见Exponentiation by squaring .

ECC点乘法见point multiplication .