使用Curve25519时，私钥似乎总是在$ 2 ^ {254} $位置设置了固定位。为什么？是否有充分的理由在私钥中使用固定位置的最高有效位？

评论

您可以考虑选择其他答案。我认为有更好的答案，然后“阅读本文”。

#1 楼

您看过DjB的论文吗？

为了提高性能，他的设计标准之一是“对密钥中的前1个使用固定位置”。

一组密钥定义为$ \ {\下划线{n}：n \ in 2 ^ {254} + 8 \ {0，1，2，3，\ ldots，2 ^ {251} -1 \} \} $。

评论

$ \ begingroup $
这个答案是重言式的。我阅读了包括这些段落的论文，但为什么领导者保持固定位置1会提高绩效？我没有注意到代码中依赖该位的算法。如果此位错误，代码是否会产生不正确的结果？
$ \ endgroup $
– CodesInChaos
13年20月20日在13:12
$ \ begingroup $
@CodesInChaos我刚刚引用该论文来回答“为什么将它设置为一个”，因为它被列为设计选择。我没有仔细研究算术以找到理由。
$ \ endgroup $
– DrLecter
13年20月20日在13:16
$ \ begingroup $
@CodesInChaos我想答案就足够了。句子“使用Curve25519时，私钥似乎总是在位置2 ^ 254处设置了固定位”。提示有关实施的问题。在论文中暗示这一事实就足够了；为什么本文如此指定它是一个有趣但又不同的问题。
$ \ endgroup $
–马腾·博德威斯♦
2013年11月20日14:22
$ \ begingroup $
该算法旨在用于大多数浮点运算，固定位可能在那里以防止溢出或其他...
$ \ endgroup $
– Richie车架
13年20月20日19:26
$ \ begingroup $
@RichieFrame如何防止溢出？
$ \ endgroup $
–森林
18/12/9在7:56


#2 楼

Curve25519旨在利用Montgomery阶梯的优势，该阶梯与Montgomery曲线相结合，放弃了$ Y $坐标，具有抗旁通道性，并使公钥可以是任何255位字符串。梯形看起来像这样（伪代码）：

Q[0] = P; 
Q[1] = 2*P;
for(int i = log2(exponent) - 2; i >= 0; --i)
{
  Q[ bit(exponent, i)] = 2*Q[ bit(exponent, i)];
  Q[!bit(exponent, i)] = Q[0] + Q[1];
}
return Q[0];


您可能会注意到循环的格式：计数器使用计数器最高有效位的索引进行初始化。指数（即私钥），然后下降到0。

在实践中，阶梯的第一步将是找到指数的最高有效位。当然，这并不难，但是这样做可能会通过计时泄漏有关指数最高有效位的信息：将位254设置为0的指数比将其设置为1的指数运行得更快。问题。

Curve25519始终将最高有效位设置为1，从而完全避免了此问题。这样，循环始终具有相同的迭代次数，并且变量迭代不会意外泄漏任何时序信息。计数。

评论

$ \ begingroup $
感谢您实际解释基本推理，而不是说“因为djb这么说”。
$ \ endgroup $
–orlp
13年11月21日在8:39


$ \ begingroup $
抱歉，我还是不明白。 1）实际代码以$ P $和$ \ infty =（x = 1，z = 0）$开头2）为什么如果代码总是从254位开始梯形图，但是该位恰好是0，代码为什么不起作用？
$ \ endgroup $
– CodesInChaos
13年11月21日在8:55


$ \ begingroup $
确实，参考代码通过以$（P，\ infty）$开头来防止这种情况的发生。但是，每本教科书都显示我描述的版本，因此独立实施者很有可能会犯该错误。将该位设置为1是一种预防措施，几乎不花钱。
$ \ endgroup $
–塞缪尔·内维斯（Samuel Neves）
13年11月21日在14:55
$ \ begingroup $
@AndrewPoelstra您不想在随机数中修复一点点（请参阅：引入偏差），只是为了避免Bleichenbacher式的攻击。
$ \ endgroup $
–塞缪尔·内维斯（Samuel Neves）
17年5月27日在21:35
$ \ begingroup $
@AndrewPoelstra肯定是不一致的，是的，但还要注意，此处的标量乘法是固定基点的，与Diffie-Hellman情况不同。这意味着所使用的算法很可能是梳状的，它（可能）不会像蒙哥马利阶梯那样泄漏MSB。无论如何，我怀疑在ed25519中这样做是对curve25519的向后兼容度量，而不是其他任何事情。
$ \ endgroup $
–塞缪尔·内维斯（Samuel Neves）
17年5月28日在12:19