如何区分X25519输出和随机输出？

Question

假设Alice有一个X25519密钥对\{S_A,P_A\} (分别是秘密密钥和公钥)。使用随机选择的X25519公钥\{P_*\} (例如P_A\notin \{P_*\})，Alice计算几个值X_* = \operatorname{X25519}(S_*,P_*)。

然后，她反复抛出一枚硬币。每次，如果结果是头，她会向Bob发送一个(真正的)随机256位字符串。如果结果是尾部，她会在\{X_*\}中向Bob发送一些值。鲍勃不知道掷硬币的结果。

我知道ECDH函数的输出不是一致随机的，所以Bob如何以超过50%的准确度确定Alice是向他发送了一个随机字符串，还是从集合\{X_*\}**?**发送了一个值。

鲍勃知道P_A和曲线参数，但他不知道set \{X_*\}的元素。

这个问题不同于区分x 25519公钥和随机密钥？，后者要求区分X25519公钥和随机密钥。这个问题要求区分X25519函数的输出(即用ECDH函数计算的共享秘密)和随机输出。给定两个秘密的公钥对\{S_A,P_A\}和\{S_B,P_B\}，即这个问题询问如何区分\operatorname{X25519}(S_A,P_B) (或等价地说是\operatorname{X25519}(S_B,P_A))和随机，而另一个问题是如何区分P_A和P_B。

编辑:变量的固定名称。S_*的目的是成为X_*。

Answer 1

Alice生成几个X_* = \operatorname{X25519}(S_*,P_*)。

如果Alice使用X25519函数，输出将属于\mathbb{F_{2^{255}-19}}，并将表示curve25519的大素数级子群中一个点的X-coordinate。此信息可供Alice用于区分随机256位字符串。

1. Bob可以查看最重要的位MSB(X_*)，由于X25519的小端点表示，这将是从右到右的8位。对于使用\operatorname{X25519}函数生成的所有公钥，这是零。如果MSB(X_*) = 1知道这是随机字符串。
2. 给定X_*和MSB(X_*)=0，Bob可以计算\mathbb{F_{2^{255}-19}}中X_*^3 + 486662X_*^2 + X_*值的平方根。如果X_*在字段中没有平方根，那么Bob就知道这是随机字符串。平均而言，大约一半的值将没有一个有效的平方根。

这两种组合信息使Bob能够明确地区分关于随机字符串的\frac{3}{4}确实是随机字符串。这可以用来有一个75%的整体猜测的准确性。

请注意，在不给Bob任何好处的情况下，执行用户要求的正确方法是使用短吻鳄方案对公钥进行编码，但是对可用的公钥有限制。

Answer 2

标量乘法中的248‘位(大端位)总是被设置为零.