Royal Society of Arts [CRYPTO]
April 27, 2023
A basic RSA challenge with the combination of algebraic equations.
Challenge Description
70 points, 445 solves
RSA strikes strikes strikes strikes again again again again!
from Crypto.Util.number import getStrongPrime, bytes_to_long
f = open("flag.txt").read()
m = bytes_to_long(f.encode())
p = getStrongPrime(512)
q = getStrongPrime(512)
n = p*q
e = 65537
c = pow(m,e,n)
print("n =",n)
print("e =",e)
print("c =",c)
print("(p-2)*(q-1) =", (p-2)*(q-1))
print("(p-1)*(q-2) =", (p-1)*(q-2))
n = 125152237161980107859596658891851084232065907177682165993300073587653109353529564397637482758441209445085460664497151026134819384539887509146955251284230158509195522123739130077725744091649212709410268449632822394998403777113982287135909401792915941770405800840172214125677106752311001755849804716850482011237
e = 65537
c = 40544832072726879770661606103417010618988078158535064967318135325645800905492733782556836821807067038917156891878646364780739241157067824416245546374568847937204678288252116089080688173934638564031950544806463980467254757125934359394683198190255474629179266277601987023393543376811412693043039558487983367289
(p-2)*(q-1) = 125152237161980107859596658891851084232065907177682165993300073587653109353529564397637482758441209445085460664497151026134819384539887509146955251284230125943565148141498300205893475242956903188936949934637477735897301870046234768439825644866543391610507164360506843171701976641285249754264159339017466738250
(p-1)*(q-2) = 125152237161980107859596658891851084232065907177682165993300073587653109353529564397637482758441209445085460664497151026134819384539887509146955251284230123577760657520479879758538312798938234126141096433998438004751495264208294710150161381066757910797946636886901614307738041629014360829994204066455759806614
Analysis
From the output, we know the value of , , and .
To solve a RSA challenge, the algorithm will be:
From the algorithm, we need either or to get private key . Obviously, we will not get these values that easily. However, we know the value of and .
(p-2)*(q-1) = 125152237161980107859596658891851084232065907177682165993300073587653109353529564397637482758441209445085460664497151026134819384539887509146955251284230125943565148141498300205893475242956903188936949934637477735897301870046234768439825644866543391610507164360506843171701976641285249754264159339017466738250
(p-1)*(q-2) = 125152237161980107859596658891851084232065907177682165993300073587653109353529564397637482758441209445085460664497151026134819384539887509146955251284230123577760657520479879758538312798938234126141096433998438004751495264208294710150161381066757910797946636886901614307738041629014360829994204066455759806614
If we multiply both equations, we will get the pattern which is .
We can see that we have an unknown value . This value can be obtained by adding both equations.
By the end, we can get:
p+q = 22499021746195166693397006566713801096034580830176876576349782670139991145031893943925884176860377452600144311990257304731744774130975813748676075912492538
Insert the value to and we get .
phi = 125152237161980107859596658891851084232065907177682165993300073587653109353529564397637482758441209445085460664497151026134819384539887509146955251284230136010173775928572436680719177377848116674829438272756246045215733637122837255241965475908739081392953200695860223868372375007536870780036056040774569518700
Solution
#!/usr/bin/env python3
from Crypto.Util.number import long_to_bytes
n = 125152237161980107859596658891851084232065907177682165993300073587653109353529564397637482758441209445085460664497151026134819384539887509146955251284230158509195522123739130077725744091649212709410268449632822394998403777113982287135909401792915941770405800840172214125677106752311001755849804716850482011237
e = 65537
c = 40544832072726879770661606103417010618988078158535064967318135325645800905492733782556836821807067038917156891878646364780739241157067824416245546374568847937204678288252116089080688173934638564031950544806463980467254757125934359394683198190255474629179266277601987023393543376811412693043039558487983367289
# (p-2)*(q-1) = 125152237161980107859596658891851084232065907177682165993300073587653109353529564397637482758441209445085460664497151026134819384539887509146955251284230125943565148141498300205893475242956903188936949934637477735897301870046234768439825644866543391610507164360506843171701976641285249754264159339017466738250
# (p-1)*(q-2) = 125152237161980107859596658891851084232065907177682165993300073587653109353529564397637482758441209445085460664497151026134819384539887509146955251284230123577760657520479879758538312798938234126141096433998438004751495264208294710150161381066757910797946636886901614307738041629014360829994204066455759806614
# p + q = 22499021746195166693397006566713801096034580830176876576349782670139991145031893943925884176860377452600144311990257304731744774130975813748676075912492538
phi = 125152237161980107859596658891851084232065907177682165993300073587653109353529564397637482758441209445085460664497151026134819384539887509146955251284230136010173775928572436680719177377848116674829438272756246045215733637122837255241965475908739081392953200695860223868372375007536870780036056040774569518700
d = pow(e, -1, phi)
flag = pow(c, d, n)
print(long_to_bytes(flag))
FLAG: actf{tw0_equ4ti0ns_in_tw0_unkn0wns_d62507431b7e7087}