Oak Land

Catégorie: medium

Points: 122

Résolutions: 122

Énoncé

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}')
# c = 871346503375040565701864845493751233877009611275883500035764036792906970084258238763963152627486758242101207127598485219754255161617890137664012548226251138485059295263306930653899766537171223837761341914356

Analyse

Cherchons des propriétés particuliers de l’entier p

sage: is_prime(p)
True
sage: factor(p-1)
2 * 136327 * 164341 * 169937^4 * 313351^4 * 321427^4 * 323377^4 * 356887^4 * 413783 * 519733^3 * 792413^4 * 860077^4 * 906289 * 976501^2

L’entier p est premier et puisque p-1 est lisse, on sait que le logarithme discret se calcule se manière très rapide modulo p.

Calculons quelques logarithmes discrets:

sage: Zmod(p)(f).log(e)
7389313481223384214994762619823300589978423075857540712007981373887018860174846208000957230283669342186460652521580595183523706412588695116906905718440770776239313669678685198683933547601793742596023475603665
sage: Zmod(p)(g).log(e)
7389313481223384214994762619823300589978423075857540712007981373887018860174846208000957230283669342186460652521580595183523706412588695116906905718440770776239313669678685198683933547601793742596023475603664

On constate que log(f) == log(g)+1 et même que log(f) == p-2. On en déduit que f = 1/e et g = 1/e² modulo p.

Ainsi si on note X = pow(e, x, p) on a l’équation (modulo p) 110 X + 313 / X + 114 / X² = c

Solution

On calcule les racines du polynôme avec SAGE:

sage: f = 110 * x^3 + 313 * x + 114 - c * x^2

sage: f.roots(Zmod(p))
[(6621736714803975486469770941631918297557515256645141403866696899656801529069492623812629032566382224631133756513615225604518504150834965984951182186972792703483282014259169249309903503054330793332575590535531,
  1)]

sage: r = 6621736714803975486469770941631918297557515256645141403866696899656801529069492623812629032566382224631133756513615225604518504150834965984951182186972792703483282014259169249309903503054330793332575590535531

sage: Zmod(p)(r).log(31337)
130669746807581038734209381694055163726297497321549047017439654852953086676029610991997

sage: int(130669746807581038734209381694055163726297497321549047017439654852953086676029610991997).to_bytes(64, "big")
b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00CCTF{V33333rY_eeeeZy_DLP_cH41L3n9E!}'