在有限循环群中有效地进行比较或模块化的能力将如何打破椭圆曲线密码？

Question

这是维塔利克·布特林的帖子报道。

在这里他说

请注意，不支持模(%)和比较运算符(<，>，≤，≥)，因为在有限循环群算法中没有直接进行模或比较的有效方法(感谢这一点；如果有任何一种方法，则椭圆曲线密码将被破坏得比您可以说的“二进制搜索”和“中国余数定理”更快)。

• 我不知道在椭圆曲线组中比较意味着什么。就点数而言，究竟什么才是小于或更大的意义？考虑到这一点，为什么会有比较破坏ECC？
• 再说一次，我不明白他在椭圆曲线群中指的是什么模块？如果可能的话，什么模块能够有效地破坏ECC &怎样才能破坏ECC？
• 其次，一般地考虑有限循环群，而不是椭圆曲线群。例如，如果你取一个数字循环群，那么它们的运算本身就是基于模(即加法模某个数或乘法模某个数)，那么为什么他说它不受支持呢？

Answer 1

椭圆曲线群的比较

如果我们专门研究椭圆曲线组(\mathbb G,+)的生成器D3，我们可以定义一个函数f_G:[0,n)\to\mathbb G，其中n是组顺序，如( \infty为组中性/无穷远点)f_G(a)=\begin{cases}\infty&\text{if }a=0\\f_G(a-1)+P&\text{otherwise}\end{cases}。

换句话说，我们定义了f_G，使得f_G(a)=a\cdot G，其中\cdot是“标量乘法”。这个f_G是一个双射，它的逆函数f_G^{-1}定义得很好，即使对于随机给定的P，f_G^{-1}(P)很难计算。因此，[0,n)中的自然比较为椭圆曲线组的元素(定义为P\;<_GQ\iff f_G^{-1}(P) )产生了一个比较\mathbb G (依赖于G)。

考虑到这一点，为什么会有比较破坏ECC？

具有可计算的比较中断ECC。给定G和给定P和Q的甲骨文，可以计算离散对数到基G (它打破了\log_2 n查询)，方法是通过二进制搜索找到x，这样就可以找到x=f_G^{-1}(P)。

椭圆曲线群中的模

对于任何生成器G，它都保存P+Q=f_G(f_G^{-1}(P)+f_G^{-1}(Q)\bmod n)。我们也可以将P\ *_G Q定义为f_G(f_G^{-1}(P)*f_G^{-1}(Q)\bmod n)。现在(\mathbb G,+,*_G)与有限环\mathbb Z/n\mathbb Z#qcStackCode#整数模n#qcStackCode#同构。通过想像力，我们可以在\mathbb Z/n\mathbb Z中定义的任何(少数)模块操作符都会为\mathbb G生成一个模块(依赖于G)。

什么模块如果(可计算的)有效地破坏ECC &如何？

用[0,n)定义模块通常的方式是u\bmod v=w\iff0\le w

对于一个固定的生成器G，它在\mathbb G中定义了一个模块\bmod_G，如下所示。对于Q\ne\infty和任何P\in\mathbb G，它都包含(P\,\bmod_G Q)=P\,\iff\,P\;<_GQ。因此，计算\bmod_G的能力意味着评估<_G的能力，从而破坏了前面看到的组中的ECC。实际上，有更好的方法(对\bmod_G oracle的查询要少得多)，可以使用\bmod_G来计算最大的公共除数。

有限循环群的推广

顾名思义，他们有一个发电机。它可以用来构造环\mathbb Z/n\mathbb Z的同构，同样的推理成立。