Royal Society of Arts [CRYPTO]
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 \(n\), \(e\), and \(c\).
To solve a RSA challenge, the algorithm will be:
\[\begin{aligned} n &= pq\\ \phi(n) &= (p-1)(q-1)\\ d &= e^{-1}\ (mod\ \phi(n))\\ flag &= c^d\ (mod\ n)\\ \end{aligned}\]From the algorithm, we need either \(pq\) or \(\phi(n)\) to get private key \(d\). Obviously, we will not get these values that easily. However, we know the value of \((p-2)(q-1)\) and \((p-1)(q-2)\).
(p-2)*(q-1) = 125152237161980107859596658891851084232065907177682165993300073587653109353529564397637482758441209445085460664497151026134819384539887509146955251284230125943565148141498300205893475242956903188936949934637477735897301870046234768439825644866543391610507164360506843171701976641285249754264159339017466738250
(p-1)*(q-2) = 125152237161980107859596658891851084232065907177682165993300073587653109353529564397637482758441209445085460664497151026134819384539887509146955251284230123577760657520479879758538312798938234126141096433998438004751495264208294710150161381066757910797946636886901614307738041629014360829994204066455759806614
If we multiply both equations, we will get the pattern \((p-1)(q-1)\) which is \(\phi(n)\).
\[\begin{aligned} (p-2)(q-1) \cdot (p-1)(q-2) &= 1251\dots8250 + 1251\dots6614\\ (p-1)(q-1) \cdot (pq-2p-2q+4) &= 1566\dots5500\\ \phi(n) \cdot (pq-2(p+q)+4) &= 1566\dots5500\\ \phi(n) &= {1566\dots5500\over (1251\dots1237-2(p+q)+4)}\\ \end{aligned}\]We can see that we have an unknown value \((p+q)\). This value can be obtained by adding both equations.
\[\begin{aligned} (p-2)(q-1) + (p-1)(q-2) &= 1251\dots8250 \cdot 1251\dots6614\\ pq - p - 2q + 2 + pq - 2p - q + 2 &= 2503\dots4864\\ 2pq + 4 - 3p - 3q &= 2503\dots4684\\ p + q &= {2 \cdot 1251\dots1237 + 4 - 2503\dots4684\over 3}\\ \end{aligned}\]By the end, we can get:
p+q = 22499021746195166693397006566713801096034580830176876576349782670139991145031893943925884176860377452600144311990257304731744774130975813748676075912492538
Insert the value to \({1566\dots5500\over (1251\dots1237-2(p+q)+4)}\) and we get \(\phi(n)\).
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}