symmetric

Category
Cryptography
Tags

We are given a Python script (chal.py):

from Crypto.Util.number import *
from secret import FLAG

p, q, r, s = [getPrime(512) for _ in "1234"]

print(f"h1 = {p + q + r + s}")
print(f"h2 = {p**2 + q**2 + r**2 + s**2}")
print(f"h3 = {p**3 + q**3 + r**3 + s**3}")

N = p*q*r*s
print(f"N = {N}")
pt = bytes_to_long(FLAG)
ct = pow(pt, 65537, N)
print(f"ct = {ct}")

and a output.txt file:

h1 = 44626154099651354925697068610752642661842459492769931945027538340211738148995902544351457443643808803963130274930824732652561687395268828472477422919262224
h2 = 516671113554555861164166966331322883848052630063409185414998284127910160310316421085219788291486248715029393774584960034375836715001130337767354512063372620828300201147366138270597133744747341658011663632381219284289144790858167258162656417236910634201286428763727072739569460623482985066956478781223378673732
h3 = 6147718474663450187001867904227777991349731066494841442199681943204194617136760567222545181562592364728655444222576167723225771866335920325045525027985716792468801076590684892140052786942251780392395274059384743594570343510311801194684613435002073956759521242578078411431891501758484581445964234548107005826532945720412531638919892681259687552977883437895032963223761216846303917338652743754915155934118353066174102436448393348040719582422022713292561416343278608
N = 14184841414933523698606245433393907034474143715949896731683874356940146602876788990832087413915033843120975580859113356518777762025417525571528638829956003882418585702756644491932279294535883798799580861254646149745925137179207140600356428758736111639677698862407787386573263961111978517446397007747429416079059195916290615125084899002162504424765939524455434579218079962808920072946861658695379491917567048202142417165204141307476222251547098848515065051745905180788313450494477967398727631152936238366581978379130450660235139256967936160718128731512409111209840405772933034600016694225294481603355934917366484109057
ct = 720607330561370237459911161481490697044029472780348552630924063963226757984368356580217337982783395620115957442082471977614781910209933696251479615689667675958354681196823652299435457532944189300223816303315625302472302494905575910600277892375951366031061219173465155686586206246661009612156094695841741309002508535764511343569015518587247600796520847856011377777228749182958947015029731456117404560626347774985507275302882865400315045173501559082431672490227728580592379740508214726249635835834752208899970446910850569489282065524329936561486377823093465841715608716032843259935185417766702677708267102415636848129
Observations

This challenge involves recovering four prime numbers from given power sums and their product. The ciphertext is encrypted using RSA, and the goal is to decrypt it to obtain the flag. Given Values:

  • h1 = p + q + r + s
  • h2 = p² + q² + r² + s²
  • h3 = p³ + q³ + r³ + s³
  • N = p * q * r * s
  • ct = pow(FLAG, 65537, N)
Strategy
  1. Compute Elementary Symmetric Sums

Using Newton’s identities, we derive the symmetric sums e1, e2, e3 from h1, h2, h3:

  • e1 = h1
  • e2 = (e1² - h2) // 2
  • e3 = (h3 - e1*h2 + e2*e1) // 3
  1. Construct the Polynomial

The primes p, q, r, s are roots of the polynomial: x⁴ - e1*x³ + e2*x² - e3*x + N

  1. Find the roots

Solve the polynomial to obtain the four primes.

  1. Verify the Primes

Ensure:

  • Their product equals N.
  • Their sum matches h1.
  1. Decrypt the Ciphertext
  • Compute phi(N) = (p-1)(q-1)(r-1)(s-1)
  • Compute the private key d = inverse(65537, phi(N))
  • Decrypt ct to get the flag.
Solver
from Crypto.Util.number import long_to_bytes, inverse
import sympy

# Given values
h1 = 44626154099651354925697068610752642661842459492769931945027538340211738148995902544351457443643808803963130274930824732652561687395268828472477422919262224
h2 = 516671113554555861164166966331322883848052630063409185414998284127910160310316421085219788291486248715029393774584960034375836715001130337767354512063372620828300201147366138270597133744747341658011663632381219284289144790858167258162656417236910634201286428763727072739569460623482985066956478781223378673732
h3 = 6147718474663450187001867904227777991349731066494841442199681943204194617136760567222545181562592364728655444222576167723225771866335920325045525027985716792468801076590684892140052786942251780392395274059384743594570343510311801194684613435002073956759521242578078411431891501758484581445964234548107005826532945720412531638919892681259687552977883437895032963223761216846303917338652743754915155934118353066174102436448393348040719582422022713292561416343278608
N = 14184841414933523698606245433393907034474143715949896731683874356940146602876788990832087413915033843120975580859113356518777762025417525571528638829956003882418585702756644491932279294535883798799580861254646149745925137179207140600356428758736111639677698862407787386573263961111978517446397007747429416079059195916290615125084899002162504424765939524455434579218079962808920072946861658695379491917567048202142417165204141307476222251547098848515065051745905180788313450494477967398727631152936238366581978379130450660235139256967936160718128731512409111209840405772933034600016694225294481603355934917366484109057
ct = 720607330561370237459911161481490697044029472780348552630924063963226757984368356580217337982783395620115957442082471977614781910209933696251479615689667675958354681196823652299435457532944189300223816303315625302472302494905575910600277892375951366031061219173465155686586206246661009612156094695841741309002508535764511343569015518587247600796520847856011377777228749182958947015029731456117404560626347774985507275302882865400315045173501559082431672490227728580592379740508214726249635835834752208899970446910850569489282065524329936561486377823093465841715608716032843259935185417766702677708267102415636848129

# Compute elementary symmetric sums
e1 = h1
e2 = (e1 * e1 - h2) // 2
e3 = (h3 - e1 * h2 + e1 * e2) // 3

# Construct polynomial x⁴ - e1*x³ + e2*x² - e3*x + N
x = sympy.symbols('x')
poly = sympy.Poly(x**4 - e1*x**3 + e2*x**2 - e3*x + N, x)

# Find roots (primes)
roots = sympy.roots(poly, multiple=True)
primes = [int(r) for r in roots if r.is_integer and r > 0]

# Verify solution
assert len(primes) == 4
assert N == primes[0] * primes[1] * primes[2] * primes[3]
assert h1 == sum(primes)

# Compute phi(N) and decrypt
phi = 1
for p in primes:
    phi *= (p - 1)

d = inverse(65537, phi)
pt = pow(ct, d, N)
flag = long_to_bytes(pt)

# Output flag (handle non-UTF-8)
try:
    print(flag.decode())
except UnicodeDecodeError:
    print(flag.hex())
symmetric Flag: uiuctf{5yMmeTRiC_P0lyS_FoRM_A_B4S15}