[CryptoCTF 2022]Oak land wp

Problem: [CryptoCTF 2022]Oak land

#!/usr/bin/env python3

from Crypto.Util.number import *
from flag import flag

p = 7389313481223384214994762619823300589978423075857540712007981373887018860174846208000957230283669342186460652521580595183523706412588695116906905718440770776239313669678685198683933547601793742596023475603667
e = 31337
f = 7236042467316654159796543399639966340258093274047941788600980451877044636122969830708918356119442228154447395855689559447196348683125675305629837437591088260218138895919514078948650757100432223219969122629790
g = 1878626136321051642174045874618248475160620873585704351202865003185878331837410979441756843820270907300810543618813757245154196050399357659526631164136221434463496532263979506870318259276669412698827040743576

x = bytes_to_long(flag.encode('utf-8'))
assert x < p
c = (110 * pow(e, x, p) + 313 * pow(f, x, p) + 114 * pow(g, x, p)) % p
print(f'c = {c}')
​

测试显然p是平滑的，所以很容易求dlp,关键c是多个dlp的和，不能直接求，但测试可以发现：e^{-1}\equiv f ;e^{-2}\equiv g,我们设h=e^x,则有:

求解出这个h再做discrete_log就行了：

#!/bin/env sage
#[CryptoCTF 2022]Oak land
p = 7389313481223384214994762619823300589978423075857540712007981373887018860174846208000957230283669342186460652521580595183523706412588695116906905718440770776239313669678685198683933547601793742596023475603667
e = 31337
f = 7236042467316654159796543399639966340258093274047941788600980451877044636122969830708918356119442228154447395855689559447196348683125675305629837437591088260218138895919514078948650757100432223219969122629790
g = 1878626136321051642174045874618248475160620873585704351202865003185878331837410979441756843820270907300810543618813757245154196050399357659526631164136221434463496532263979506870318259276669412698827040743576
c = 871346503375040565701864845493751233877009611275883500035764036792906970084258238763963152627486758242101207127598485219754255161617890137664012548226251138485059295263306930653899766537171223837761341914356

P.<x>=Zmod(p)[]
f=110*x+313*x**-1+114*x**-2-c
h=f.numerator().roots()[0][0]
m=discrete_log(h,mod(e,p))
flag=bytes(ZZ(m).digits(256))[::-1]
print(flag.decode())
​