Problem: [NCTF 2021]dlp
[[toc]]
思路
依然是一个交互题，连接上靶机后首先需要通过proof，然后就进入题目。靶机会生成一个素数p，以及一个100位的素数s0，并以s0按如下方式生成列表s：
s = [getPrime(100)]
for i in range(1023):
s.append(s[i]*s[i]%(p-1))
也就是：
s_i = s_0^{2^i} \quad(mod\;p)
然后题目提供了两种交互：
- 输入1，可以输入一个明文m以及一个索引k，靶机会返回c = m^{s_k} \; (mod\;p)
- 输入2，可以输入一个明文m，如果m满足m^{s_0} = 0xdeadbeef \;(mod\;p)，则可以得到flag
如果能求解DLP的话，那么求出s0过后就很好办，但是分解一下p-1可以发现，p是2q+1型的安全素数，所以求DLP并不可能。那么核心思路就是要利用第一个交互去想办法找到能满足第二个交互要求的m。
那么就要仔细想下怎么利用，首先可以发现s列表其实可以看作是一个比特串，因为他的每个位置都和对应位置的比特一一对应。
这是什么意思呢？比如我们想要利用靶机计算出c = m^{s_0^{11}}的值，我们只需要把11拆成二进制串1011，然后第一次送给靶机(m,0)，得到c_1 = m^{s_0}，第二次送给靶机(c_1,1)，得到c_2 = m^{s_0^{2^0+2^1}}，第三次给靶机(c_2,3)，就得到c_3 = m^{s_0^{2^0+2^1+2^3}}，也就得到我们需要的c = m^{s_0^{11}}的值了。
而回看一下题目任务，我们是想找到一个满足下式的m：
m^{s_0} = 0xdeadbeef \;(mod\;p)
我们不妨取m=0xdeadbeef，那么问题其实可以转化成找出一个满足如下条件的二进制序列k：
(m^{s_0^{\sum{2^k}}})^{s_0} = m \quad(mod\;p)
也就是：
m^{s_0^{\sum{2^k}}} = m^{s_0^{-1}}\quad(mod\;p)
而由于p-1是可以完全分解的，那么令q=(p-1)/2，就可以把指数上的运算单独写出来：
s_0^{\sum{2^k}} = s_0^{-1} \quad(mod\;q)
又因为q也是个素数，所以由费马小定理就有：
\sum{2^k} = -1 \quad(mod\;q-1)
那么我们其实就找到了我们需要的二进制序列k：
\sum{2^k} = q-2
然后就照上面的例子，先利用交互1去得到计算结果：
m = (0xdeadbeef)^{s_0^{-1}} \quad(mod\;p)
然后输入2把这个m发过去就可以了。
EXP
from Pwn4Sage.pwn import *
from Crypto.Util.number import *
from tqdm import *
from hashlib import *
import string
sh = remote("node5.anna.nssctf.cn",28301)
#part1 proof
def proof_of_work():
table = string.digits + string.ascii_letters
temp = sh.recvuntil(b"sha256(XXXX+")
temp = sh.recvline()
suffix = temp[:16].decode()
hex1 = temp[20:].strip().decode()
for i in tqdm(table):
for j in table:
for k in table:
for m in table:
temp1 = i+j+k+m
if(sha256((temp1+suffix).encode()).hexdigest() == hex1):
sh.sendline(temp1.encode())
return
proof_of_work()
#part2
p = 144622268328968993341365710278894755118767129325286994164661347213200068288320713151689155598130690763440455157929587751885813242814750422828312072382119518429040602281694119210475772654999865828418886175678335978908269120940864300610431302161143383386149363868608635140950451657400233892787130315426229955639
q = (p-1) // 2
m = 0xdeadbeef
k = q-2
for i in trange(1024):
if(k % 2):
sh.recvuntil(b'>')
sh.sendline(b'1')
sh.recvuntil(b"Give me m:")
sh.sendline(str(m).encode())
sh.recvuntil(b"Give me k:")
sh.sendline(str(i).encode())
sh.recvuntil(b'c = ')
m = int(sh.recvline().strip().decode())
k = k // 2
sh.recvuntil(b'>')
sh.sendline(b'2')
sh.recvuntil(b"Give me the secret:")
sh.sendline(str(m).encode())
sh.recvline()
print(sh.recvline())
#NSSCTF{58de53dd-16af-4912-8de1-a2f510e6c174}