我了解x25519公钥实际上是255位，必须将其序列化为256位，剩下一个通常被库修复为0的未使用位。出于这个问题的目的，我想将其忽略，只关注255个使用过的位。
Alice生成一个随机私有密钥K和255位公共密钥K'。她生成R（255位随机字符串）。她掷出一枚公平硬币，如果正面朝上，她会发送一条消息M = K'。否则，她发送M =R。
夏娃收到此消息，但不知道K。她必须猜测是否M = K'。她能否做到比通过猜测获得的成功率高50％？ （换句话说，她能区分x25519公钥的有效位与随机位吗？）
编辑：在回答一个问题时，伊芙了解曲线参数。
#1 楼
Weierstrass形式的椭圆曲线的有效点满足方程$$
$$
我们可以重写这是$ y = \ pm \ sqrt {x ^ 3 + ax + b} $，当$ x ^ 3 + ax + b $是一个正方形时，它有2个解；当$ x ^ 3 + ax + b + b时，有1个解= 0 $，或者$ x ^ 3 + ax + b $不是正方形时的0个解。
在X25519中，我们只看到$ x $坐标，但是我们仍然可以使用以上。曲线方程为
$$
y ^ 2 = x ^ 3 + 486662x ^ 2 + x \ bmod 2 ^ {255} -19 \ ,
$$
from给定有效的公钥$ x $，则$ x ^ 3 + 486662x ^ 2 + x $必须具有平方根模$ 2 ^ {255} -19 $。另一方面，随机字符串只有大约$ 1/2 $的时间是一个正方形。通过检查$ n $个候选公钥，我们可以将确定性提高到$ 1-1/2 ^ n $。
评论
$ \ begingroup $
如果使用curve25519的标准实现，则素数次子组的投影每次尝试应再赋予3位。
$ \ endgroup $
– CodesInChaos
18年8月27日在19:35
评论
您可以使用elligator2编码来避免这种情况