Curve25519规范

Question

Curve25519在素数2^{255}-19上用A = 486662定义，因此曲线方程是：y^2 = x^3 + 486662x^2 + x

我试着去理解，为什么参数是这样的。

首先是首相。我已经从伯恩斯坦纸那里得到了一些想法，为什么他选择这个质数。有人能说，如果其中一个是假的，或者如果我没有提到一个重要的观点？

• 当质数接近2的幂时，外地操作速度更快
• 当键长度接近32 \cdot k时，任何k都不会浪费空间
• 安全级别相当高，因为255位密钥长度(不确定，但它是否等于15000位RSA系统？)

伯恩斯坦很好地描述了质数的选择。但我不明白他为什么选择A= 486662。我读过他选择的理由，但我就是不明白。有人能给我解释一下吗，从一个更基本的层面来说？

编辑：

我试着理解486662的选择，希望有一些问题能帮助我理解它：

• 如何用点来创建子群(因此基点创建了一个具有素数顺序的子群。但是这个顺序也是curve25519的顺序。我对此感到有点困惑)
• 所以子群的阶是素数，但Curve25519的阶也是素数。我不明白当A实际上是一个素数时，A是如何形成一个曲线的，它有{4 \cdot n, 8 \cdot n}的阶
• 什么是攻击，不能使用，当A是这样选择的？(我想:只有小的分组攻击，例如波利格-赫尔曼。但是伯恩斯坦在他的论文中写道，有各种各样的攻击)

Answer 1

从文件中：

我按照蒙哥马利的建议，选择(A /4 2)/4作为一个小整数，以加速(A−2)/4的乘法。

值(A-2)/4越小，该值的乘法速度就越快(这是点加倍公式所需要的)。

因此，曲线基本上是通过增加A值来找到的，限制在(A-2)/4是整数的值上，直到它生成一条具有4n或8n顺序的曲线，其中n是素数(以及本文中描述的其他一些准则:扭转顺序应该是相同格式的；n应该大于2^{252}，这样就可以通过简单地随机填充字节缓冲区来生成私钥，而不必考虑私钥等于曲线顺序的情况)。

Answer 2

如何用点来创建子群(因此基点创建了一个具有素数顺序的子群。但是这个顺序也是curve25519的顺序。我对此感到有点困惑)

在组g中取一个元素G。您可以创建由g生成的子组，方法是接受所有元素1、g、g^2、\ldots、g^{q-1}，以及最终返回完整循环的g^q=1。在这里，l是g的顺序，是G顺序的除数。

椭圆曲线是一个群，所以它的工作原理是一样的。取一个点P，然后子群将是\infty，P，2P，\ldots，(q-1)P，最后，我们得到了值q的qP=\infty。点P有阶q，q是曲线基数的除数。

q不一定是素数，但为了密码学的目的，我们需要一个点P，它生成一个具有q足够大的素数级q的子群。因此，曲线基数必须有一个较大的素数因子。

所以子群的阶是素数，但是Curve25519的阶也是素数。我不明白当A实际上是一个素数时，A是如何形成一个曲线的，它的阶是4\cdot，8\cdot n

您可能会感到困惑，因为Curve25519有order 8\cdot q，其中q是一个大素数。

什么是攻击，不能使用，当A是这样选择的？(我想:只有小的分组攻击，例如波利格-赫尔曼。但是伯恩斯坦在他的论文中写道，有各种各样的攻击)

选择了一份安全标准清单。您可以在SafeCurves上找到一个列表(甚至有一个脚本来验证这些标准)。然后，求解A的算法简单且完全透明:求最小整数A，使曲线满足所有准则。

主要的准则是曲线的基数及其二次扭转是8\cdot q和4\cdot q'，其中q和q'是素数，因为他在他的论文中解释说，这是最好的选择(蒙哥马利曲线总是有一个基数，即4的倍数)。

Answer 3

Meta:我知道这个答案是一个基本的复制和粘贴。这应该是一个评论，以更好地理解这个问题，但它太长，所以我张贴它作为答案。

从曲线25519纸中可以很清楚地看到。

按照蒙哥马利的建议，我选择(A − 2)/4作为一个小整数，以加快(A − 2)/4的乘法速度；这对猜测的安全级别没有影响。为了防止第3节中讨论的各种攻击，我拒绝了A的选择，它的曲线和扭曲顺序不是\{4 · prime, 8 · prime\}；在这里，4, 8是自p \in 1+4\mathbb{Z}以来最小的。对于A，最小的正面选择是358990、464586和486662。我拒绝A = 358990是因为它的素数之一比2^{252}略小，提出了标准和实现应该如何处理用户的秘密密钥匹配质数的理论可能性的问题；讨论这个问题比切换到另一个A要困难得多。出于同样的原因，我拒绝了464586。所以我最后和A = 486662在一起。

如果你能要求一个具体选择的细节，也许会更好。