区分x25519公钥和随机密钥？

Question

我最近读到了一份协议，该协议避免在透明的情况下发送短暂的x25519密钥，以此来挫败深度数据包检查。

据我所知，x25519公钥实际上是255位，必须将其序列化为256位，而库通常将一个未使用的位修复为0。为了这个问题的目的，我想忽略这一点，集中讨论255个使用过的位。

Alice生成一个随机私钥K和255位公钥K'.她生成R，一个255位的随机字符串。她抛出一枚公平的硬币，如果是头，她就会发出M= K‘的信息。否则，她会发送M= R。

伊芙收到这个信息，不知道K。她必须猜测M= K‘。她能用比她猜的50%的成功率更好的方法做到这一点吗？(换句话说，她能区分x25519公钥的重要位数和随机位数吗？)

编辑:在回答一个问题时，Eve了解曲线参数。

Answer 1

Weierstrass型椭圆曲线的一个有效点满足方程$$ y^2 = x^3 + ax +b，.$$我们可以将其重写为$y = \pm \sqrt{x^3 + ax + b}$，当$x^3 + ax + b$是正方形时有两个解决方案，当$x^3 + ax +b= 0$时有一个解决方案，或者当$x^3 + ax + b$不是平方时有0个解决方案。

在X25519中，我们只看到$x$坐标，但仍然可以利用上面的内容。曲线方程为：$$ y^2 = x^3 +486662 x^2+x 2^{255}-19，$$，其中给定一个有效的公钥$x$，$x^3 + 486662x^2 + x$必须有一个平方根模$2{255}-19$。另一方面，一个随机字符串将是一个正方形，大约是1/2美元的时间。通过检查$n$候选公钥，我们可以将确定性提高到$1 - 1/2^n$。