Skip to main content

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!

rsa.py

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))

out.txt

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 nn, ee, and cc.

To solve a RSA challenge, the algorithm will be:

n=pqϕ(n)=(p−1)(q−1)d=e−1 (mod ϕ(n))flag=cd (mod n)\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 pqpq or ϕ(n)\phi(n) to get private key dd. Obviously, we will not get these values that easily. However, we know the value of (p−2)(q−1)(p-2)(q-1) and (p−1)(q−2)(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)(p-1)(q-1) which is ϕ(n)\phi(n).

(p−2)(q−1)⋅(p−1)(q−2)=1251…8250+1251…6614(p−1)(q−1)⋅(pq−2p−2q+4)=1566…5500ϕ(n)⋅(pq−2(p+q)+4)=1566…5500ϕ(n)=1566…5500(1251…1237−2(p+q)+4)\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)(p+q). This value can be obtained by adding both equations.

(p−2)(q−1)+(p−1)(q−2)=1251…8250⋅1251…6614pq−p−2q+2+pq−2p−q+2=2503…48642pq+4−3p−3q=2503…4684p+q=2⋅1251…1237+4−2503…46843\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…5500(1251…1237−2(p+q)+4){1566\dots5500\over (1251\dots1237-2(p+q)+4)} and we get ϕ(n)\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}