$A \equiv g^a \pmod p \\ B \equiv g^B \pmod p \\ s \equiv A^b \equiv g^{ab} \pmod p$

$O(m) = (m^b \pmod p) - k_m\\ k_m=(m^b \pmod p)\ \&\ (2^{64}-1)$

$O(m) = m^b - k_m \pmod p$

$choose\ c\ →\ C \equiv g^c \pmod p \\ r_1 \equiv O(A) \equiv A^b - k_1 \equiv s - k_1 \pmod p \\ r_2 \equiv O(AC) \equiv (AC)^b - k_2 \equiv sB^c - k_2 \pmod p$

$t\equiv B^c \pmod p$，记可简化写为：

$s \equiv r_1 + k_1 \pmod p \\ st \equiv r_2 + k_2 \pmod p$

$r_2t^{-1} + k_2t^{-1} - r_1 - k_1 \equiv s-s \equiv 0 \pmod p$

$k_2t^{-1} + (r_2t^{-1}-r_1) + k_3p = k_1$

$(k_3, k_2, 1) \begin{bmatrix} p & 0 & 0 \\ t^{-1} & 1 & 0 \\ (r_2t^{-1}-r_1) & 0 & K \end{bmatrix} = (k_1, k_2, K) \\ K \approx 2^{64}$

$\sigma(M) \approx \sqrt{3} * 2^{320/3} \approx \sqrt{3} * 2^{106} \\ \|w\| \approx \sqrt{3} * 2^{64} \\ \|w\| < \sigma(M)$

# 参考

[MH20] De Micheli G, Heninger N. Recovering cryptographic keys from partial information, by example[J]. 2020.

[BV96] Boneh D, Venkatesan R. Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes[C]//Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 1996: 129-142.