Tags: prime crypto rsa
Rating:
Prompt:
I’m using four primes to encrypt my flag, so I’m only giving you three hints — can you decrypt the flag?
We are given two files:
chal.py: encryption script
output.txt: outputs from the encryption phase
? 1. Challenge Analysis
Let’s first understand what the challenge is doing based on the chal.py script:
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}")
The script uses four 512-bit primes to construct a modulus:
N = p * q * r * s
This is similar to RSA, but with four primes instead of two.
We are given:
h1 = p + q + r + s (sum of primes)
h2 = p² + q² + r² + s² (sum of squares)
h3 = p³ + q³ + r³ + s³ (sum of cubes)
N = p * q * r * s (product of primes)
ct = ciphertext = pt^e mod N, with e = 65537
from Crypto.Util.number import long_to_bytes, inverse
from sympy import symbols, solve
from sympy.polys.polytools import Poly
from math import prod
h1 = 44626154099651354925697068610752642661842459492769931945027538340211738148995902544351457443643808803963130274930824732652561687395268828472477422919262224
h2 = 516671113554555861164166966331322883848052630063409185414998284127910160310316421085219788291486248715029393774584960034375836715001130337767354512063372620828300201147366138270597133744747341658011663632381219284289144790858167258162656417236910634201286428763727072739569460623482985066956478781223378673732
h3 = 6147718474663450187001867904227777991349731066494841442199681943204194617136760567222545181562592364728655444222576167723225771866335920325045525027985716792468801076590684892140052786942251780392395274059384743594570343510311801194684613435002073956759521242578078411431891501758484581445964234548107005826532945720412531638919892681259687552977883437895032963223761216846303917338652743754915155934118353066174102436448393348040719582422022713292561416343278608
N = 14184841414933523698606245433393907034474143715949896731683874356940146602876788990832087413915033843120975580859113356518777762025417525571528638829956003882418585702756644491932279294535883798799580861254646149745925137179207140600356428758736111639677698862407787386573263961111978517446397007747429416079059195916290615125084899002162504424765939524455434579218079962808920072946861658695379491917567048202142417165204141307476222251547098848515065051745905180788313450494477967398727631152936238366581978379130450660235139256967936160718128731512409111209840405772933034600016694225294481603355934917366484109057
ct = 720607330561370237459911161481490697044029472780348552630924063963226757984368356580217337982783395620115957442082471977614781910209933696251479615689667675958354681196823652299435457532944189300223816303315625302472302494905575910600277892375951366031061219173465155686586206246661009612156094695841741309002508535764511343569015518587247600796520847856011377777228749182958947015029731456117404560626347774985507275302882865400315045173501559082431672490227728580592379740508214726249635835834752208899970446910850569489282065524329936561486377823093465841715608716032843259935185417766702677708267102415636848129
S1, S2, S3 = h1, h2, h3
e1 = S1
e2 = (S1**2 - S2) // 2
e3 = (S1**3 - 3*S1*S2 + 2*S3) // 6
e4 = N
x = symbols('x')
poly = Poly(x**4 - e1*x**3 + e2*x**2 - e3*x + e4)
roots = solve(poly)
primes = sorted([int(root) for root in roots])
phi = prod([p - 1 for p in primes])
d = inverse(65537, phi)
pt = pow(ct, d, N)
flag = long_to_bytes(pt)
print("✅ Flag:", flag.decode())
