解的是HNP（Hidden Number Problem），DLP和格扯上关系了.

题目：https://paste.ubuntu.com/p/F38PPcczqj/

题目是一个Diffie Hellman的KE：

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

知道 $A、B、g、p$ ，求 $s$ ；给了一个Oracle（即to_bob），可以实现：

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

即返回低 $64$ 位被mask为 $0$ 的 $m^b \pmod p$ ，在 $k_m$ 比 $m^b \pmod p$ 小的情况下可以写成：

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

这题的解法可以直接照搬[MH20]，但远一点可以追溯到[BV96]；首先进行两次Oracle的查询：

$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$

展开 $p$ （记系数 $k_3$ ）再整理一下：

$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}$

记上式为 $vM=w$ 的话，可以计算（题目的 $p$ 大概 $2^{256}$ ）：

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

于是上个LLL求最短向量就解出 $k_1$ ，进而解出 $s$ ；先给个本地测试的脚本：

# sage
bits = 64
p = 62606792596600834911820789765744078048692259104005438531455193685836606544743
fp = [2, 139, 42798235205263, 181440306484546562787712787, 29001270706552925994696287850627469]
F.<a> = GF(p)
g = F(5)

a = randint(1, p - 1)
A = pow(g, a)
b = randint(1, p - 1)
B = pow(g, b)
s = pow(A, b)

print('a = %s' % a)
print('b = %s' % b)
print('A = %s' % A)
print('B = %s' % B)
print('s = %s' % s)

def leak(msg):
    tmp_s = pow(msg, b)
    leak = tmp_s >> bits
    leak = leak << bits
    return leak

c = randint(1, p - 1)
C = pow(g, c)
t = pow(B, c)
ti = t^(-1)

r1 = leak(A)
r2 = leak(A*C)
K = 2^64

M = matrix(ZZ, [
    [p       , 0, 0],
    [ti      , 1, 0],
    [r2*ti-r1, 0, K]
])
L = M.LLL()

print('')
print(K)
got = int(r1)+L[0][0]
print(got, got==s)

然后改一下就是打远端的Exp：

#sage
from pwn import *

bits = 64
p = 62606792596600834911820789765744078048692259104005438531455193685836606544743
F = GF(p)
g = F(5)

r = remote('39.105.38.192', 30000)

r.recvuntil(b'$')
r.sendline(b'1')
A = F(int(r.recvline()))
print('A  = %d' % A)

r.recvuntil(b'$')
r.sendline(b'2')
B = F(int(r.recvline()))
print('B  = %d' % B)

c = randint(1, p - 1)
C = pow(g, c, p)
t = pow(B, c, p)
ti = t^(-1)

r.recvuntil(b'$')
r.sendline(b'3')
r.recvuntil(b'To Bob: ')
r.sendline(bytes(str(A), encoding='ascii'))
r1 = int(r.recvline())
print('r1 = %d' % r1)

r.recvuntil(b'$')
r.sendline(b'3')
r.recvuntil(b'To Bob: ')
r.sendline(bytes(str(A*C), encoding='ascii'))
r2 = int(r.recvline())
print('r2 = %d' % r2)

K = 2^64

M = matrix(ZZ, [
    [p       , 0, 0],
    [ti      , 1, 0],
    [r2*ti-r1, 0, K]
])
L = M.LLL()
got = int(r1)+L[0][0]
print(L[0][2] == K)
print('got -> %d' % got)


r.recvuntil(b'$')
r.sendline(b'4')
r.recvuntil(b'secret: ')
r.sendline(bytes(str(got), encoding='ascii'))

print(r.recv())
#r.interactive()
r.close()

# b"b'ByteCTF{0fcca5ab-c7dc-4b9a-83f0-b24d4d004c19}'\n"

其实[MH20]中还介绍了很多类似的攻击（即泄露partial information），可以mark一下。

参考·

[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.