有多少有效的X25519私钥？

Question

根据曲线25519网站的说法：

Computing密钥。在程序内部，要生成32字节的Curve25519密钥，首先从密码安全源mysecret[0]、mysecret[1]、.、mysecret[31]生成32个秘密随机字节。然后执行mysecret &= 248；mysecret &= 127；mysecret |= 64；创建一个32字节的Curve25519密钥mysecret[0]、mysecret[1]、.、mysecret[31]。

由于248 = \mathtt{0b11111000}、127 = \mathtt{0b01111111}和64 = \mathtt{0b01000000}，上面的代码强制随机字符串的五位有一个特定的值(四个被清除，一个被设置)。

这意味着存在2^{256-5}=2^{251}\approx 3.619 \times 10^{75}有效的X25519私钥。然而，这个答案指出：

给定一个有效的公钥x，x^3 + 486662x^2 + x必须有一个平方根模2^{255}-19。另一方面，一个随机字符串将是一个正方形，仅围绕1/2的时间。

这个语句似乎意味着有大约\frac{1}{2}(2^{255})=2^{254}有效的X25519公钥，这意味着有关于2^{254}-2^{251} \approx 2.533 \times 10^{76} X25519公钥的，而没有相应的私钥。因此，这些公钥似乎都是无效的。

然而，Curve25519网站指出：

Curve25519函数是精心设计的，允许所有32字节字符串作为Diffie-Hellman公钥。

这似乎与我上面概述的内容相矛盾。因此，从理论上说，if我要计算所有 2^{251} X25519私钥的相应公钥，我将获得多少(唯一的*)公钥？

此外，由于该网站确实说“所有32字节字符串”都是有效的Diffie-Hellman公钥，如果我生成了一个秘密密钥X并执行了该操作，我会得到什么输出？

X = \operatorname{ECDH}(A_S,B_P)

其中B_P是没有相应私钥的2^{254}-2^{251}公钥之一？结果是一些伪随机字符串，还是其他什么？

*据我所知，映射K_S \to K_P对于所有X25519密钥对(K_S,K_P)都是一对一的，但是如果我不正确，请纠正我。

Answer 1

这是一个棘手的话题，因为它取决于在公钥上下文中“有效”的定义。

您对X25519私钥的枚举显然是正确的，因为它遵循X25519私钥的定义，有2^{251}私钥。这是对原来问题的正确答案。

然后，如果您按照X25519的定义从这些私钥生成公钥，您将得到2^{251}-13871158888686176767925968895441824247不同的公钥。值13871158888686176767925968895441824247来自两个私钥，它的随机部分( 251位)加到27742317777372353535851937790883648493中是两个私钥，它们是相反的(模块化大子群的顺序)，并且会产生具有相同x坐标的点。这意味着地图K_S \to K_P不是一对一的.

然而，X25519的实现可以处理这种过程中没有生成的输入公钥。这里的“句柄”意味着它将正确计算，并且不允许私钥恢复攻击。

实际上，它可以处理以32个字节表示的所有值，这些值是属于2^{255-19} (整个曲线，而不仅仅是素数阶子群)或curve25519的二次扭曲的点的x坐标。这将涵盖所有的2^{256}可能值。

如果输入表示扭转上的x坐标，那么结果将在扭转曲线上计算，在这个意义上它仍然是正确的。

Answer 2

Curve25519曲线在素数阶组中有\ell = 2^{252}+27742317777372353535851937790883648493可能点，对应于\ell私钥.

然而，X25519指的是选择私钥和执行Diffie-Hellman交换的一种特殊方法。

您可以使用Curve25519，但完全避免使用X25519。您可以选择任何私钥a，比如0，然后使用常规的变量基标量乘法来计算共享秘密作为aB，其中B=bG，G是众所周知的基点，而b是另一方的私钥，比如0。

使用X25519时，小端点私钥的有效字节最少，因此私钥的倍数为8。这样，如果另一方为您提供了一个位于曲线上但不在素数级组中的公钥点，则无法操作X25519操作的结果。根据具体情况，这会使另一方无法了解有关您的私钥的一些信息。如果您没有夹紧，那么您将不得不采取额外的步骤来验证另一方的公钥是否在质数级组中，方法是将其乘以\ell，并检查结果是否为无穷大的点。

更改最重要的字节，使设置为1的最重要位始终位于相同位置。这意味着原始X25519文件中的实现将在恒定时间内运行，从而避免泄露有关私钥的信息。

这意味着你可以选择任何随机的32字节序列，然后夹紧它来产生私钥。这个私钥可能超过\ell，但这并不重要，因为X25519标量乘法操作的目的是接受超大的私钥。标量乘法操作产生循环组中的点，因此对于(a+n\cdot\ell)B=aB的任何整数值的n。

没有相应私钥的公钥

如果B只是一个随机字节序列，它仍将被X25519视为曲线上的一个有效点。因此，如果字节序列B不是曲线上的有效点，它将被视为曲线上的一个有效点B'。曲线上每8个有效点中就有一个位于素数阶组中，因此其余7个将不具有关联的私钥。将私钥转换为公钥的过程总是会在正确的素数组中产生一个点，因为这涉及到一个肯定在曲线上和正确的素数组中的基点的乘积。因此，不属于素数阶组的有效曲线点不可能由任何私钥生成。

根据我的理解，映射K_S \to K_P对所有X25519密钥对(K_S,K_P)是一对一的，但是如果我不正确，请纠正我。

如果您遵循我前面描述的使用Curve25519的方法，但避免使用X25519，并且整个结果的坐标对被保留下来，那么这将是正确的。对于X25519来说不是这样，因为X25519允许私钥大于\ell，其中多个私钥字节序列将映射到相同的公钥(如前所述)。此外，X25519只输出x坐标，在从x坐标恢复的y坐标符号上留下模糊(Curve25519在x轴上是对称的)。

如果从理论上计算所有2^{251} X25519私钥的相应公钥，我将获得多少(唯一的†)公钥？

这相当于问：

a的可能值有多少，比如a=x\bmod \ell，其中2^{253}\leq x<2^{254}和x是8的倍数。那么，答案必须大致减半，才能解释每个X25519 x坐标输出的y坐标符号的模糊性。也许这里的数学家能解决这个脑筋问题。我预计由于\operatorname{mod} \ell操作会发生碰撞。