<- HACKON CTF

El cifrao del cuñao

4 minutes to read

We are provided with a Python script that encrypts the flag with RSA:

from Crypto.Util.number import getPrime, bytes_to_long
import random


flag='HackOn{testing_flag}'

p = getPrime(1024)
q = getPrime(1024)
r = getPrime(24)

N1 = p * q * r
N = p * q


e1 = 34456075732829756714431696264844933736161425428678777444326530245267175496676105  
e2 = 66213320562378389542956020292848603326457400359492442893037745994906793456536650


c1 = pow(7 * p + random.randint(N,N1) * q, e1, N)
c2 = pow(5 * p + random.randint(2,N) * q, e2, N)

print (f'N1: {N1}\ne1: {e1}\ne2: {e2}\nc1: {c1}\nc2: {c2}')

flag_enc= pow(bytes_to_long(flag.encode()),0x10001,N)
print (f"flag_enc: {flag_enc}")

We also have the output of the script:

N1: 175067650953281050974609338975008206300624155348825595664106085967248998540617589741296346446924688724242605062233417184911333065108859297893274877902045993216986203079495828026354663317386440140270647809550473976974096628129591628284434963946783999869378111149217917648303508065328285929072381617978438470612874589596417613745039005251725210799071272826546175725224168805195456492444749329204834536327769184614475392674754321257754169752988706888110110854886262024581325203950655368202664487427493994718122501091228347564869440655164776355796295767478070623428032139757559412393093121138433999763436450288748369986859103207  
e1: 34456075732829756714431696264844933736161425428678777444326530245267175496676105
e2: 66213320562378389542956020292848603326457400359492442893037745994906793456536650
c1: 6451549454415106937054124906386205073222243394024359630462457026011516075453322110598440273419680741264449270624349464347792470300209994225871051817906071211422868952418491992463196228285205919371173656723348479276338927171156200258373946868108513210341715619135657733694945758701239603020350282490930923223040685524857825378664935954076777009286161163426015863451976127043646518744751008641471118799355737506530194673897401350560878119713588235864131464162613324379365056778461514972632453218452367994231300225730879806827703530704658426099425996148485094190653296415838854275518343410370771236791449822141459828741
c2: 962692207706212570956439147864349279649773113345655426314467693283718484612354279844043839717727068405496826210437866778756030633962827278103786266408189507399825183552809952197915820962569346678627273880805894119629683258989464814629538794918992935736967313768318129713814389945731392361973072114735327121558821584916746528122804041711257237956057904149848804653061211762199626222824628761726392699104681979458399805669073291307091763121332471373822692444415481403270868672559435581015624351087019008601980986815604227475289546705737298842219420062366361168396261671333779917844108475134254136718732987251213358163
flag_enc: 15465286692614275746593514754237742386723861276150927182475649162005944543455951013680150395056664962236242882064880238881068860224733875220632862364701169875117607762861097611036434484377717716522737041218148230761637401384647090841280793847093817991683060457776791068080281552363949410183822084792402759853630877454700951708809147788336138383950624542278364204457482947061715484392305381003183584082954722435919314472678081759451287929983648205030782429815775036186091814941726369980614237971458156295355908243600894532353339370750767776703572265634702300110928757229421759517414772239223719386574540374904804032054

Source code analysis

First, three prime numbers are calculated: $p$, $q$ and $r$. Numbers $p$ and $q$ are 1024-bit numbers, and they are multiplied to get the RSA modulus $N$.

On the other hand, $r$ is a 24-bit number, and it is multiplied times $N$ to get $N_1$, which is the value we have.

In order to find $N$, we can enter $N_1$ in factordb.com, and it will show us the value of $r = 10085597$ and $N$.

Once we have $N$, we are prepared to tackle the RSA challenge. The script performs these encryptions:

$$ \begin{align*} c_1 = (7p + x \cdot q)^{e_1} \mod{N} \\ c_2 = (5p + y \cdot q)^{e_2} \mod{N} \end{align*} $$

Where $x$ and $y$ are two random numbers that are not important.

Among the involved values, we have $N$, $c_1$, $c_2$, $e_1$ and $e_2$.

Solution

The idea is to find a linear combination between $c_1$ and $c_2$ that depends only on $q$ (that is, eliminate $p$). Therefore, we could use the greatest common divisor (GCD) to obtain one of the prime factors pf $N$.

We can take advantage of the fact that Newton’s binomial behaves a bit different when reduced modulo $N$:

$$ \begin{split} c_1 = (7p + xq)^{e_1} & = (7p)^{e_1} + \\ & + (7p)^{e_1 - 1} xq + \\ & + (7p)^{e_1 - 2} (xq)^2 + \\ & + \dots + \\ & + (7p)^{2} (xq)^{e_1 - 2} + \\ & + 7p (xq)^{e_1 - 1} + \\ & + (xq)^{e_1} \end{split} $$

If we apply modulo $N = p \cdot q$, we get:

$$ c_1 = (7p + xq)^{e_1} = (7p)^{e_1} + (xq)^{e_1} \mod{N} $$

Similarly, with the other ciphertext:

$$ c_2 = (5p + yq)^{e_2} = (5p)^{e_2} + (yq)^{e_2} \mod{N} $$

Hence, we can multiply $c_1$ times $5^{e_1}$ and $c_2$ times $7^{e_2}$ to get the same factor multiplying $p$:

$$ \begin{align*} 5^{e_1} c_1 = 5^{e_1} (7p)^{e_1} + 5^{e_1} (xq)^{e_1} \mod{N} \\ 7^{e_2} c_2 = 7^{e_2} (5p)^{e_2} + 7^{e_2} (yq)^{e_2} \mod{N} \end{align*} $$

As a result, we have:

$$ \begin{align*} 5^{e_1} c_1 = (35p)^{e_1} + (5xq)^{e_1} \mod{N} \\ 7^{e_2} c_2 = (35p)^{e_2} + (7yq)^{e_2} \mod{N} \end{align*} $$

Nor, we can raise the first equation to the power of $e_2$ and the second equation to the power of $e_1$, and because of Newton’s binomial modulo $N$, we have the following:

$$ \begin{align*} (5^{e_1} c_1)^{e_2} = \left((35p)^{e_1} + (5xq)^{e_1}\right)^{e_2} = (35p)^{e_1 e_2} + (5xq)^{e_1 e_2} \mod{N} \\ (7^{e_2} c_2)^{e_1} = \left((35p)^{e_2} + (7yq)^{e_2}\right)^{e_1} = (35p)^{e_1 e_2} + (7yq)^{e_1 e_2} \mod{N} \end{align*} $$

So, we can substract both equations and get something that has a common factor with $q$:

$$ \begin{split} (5^{e_1} c_1)^{e_2} - (7^{e_2} c_2)^{e_1} & = (5xq)^{e_1 e_2} - (7yq)^{e_1 e_2} \mod{N} \\ & = q^{e_1 e_2} \cdot \left((5x)^{e_1 e_2} - (7y)^{e_1 e_2}\right) \mod{N} \end{split} $$

With this, we can find $q$ using the GCD with $N$. Once we have a prime factor of $N$, it’s trivial to decrypt RSA.

Flag

The above computations can be quickly done in a Python REPL:

$ python3 -q
>>> N1 = 175067650953281050974609338975008206300624155348825595664106085967248998540617589741296346446924688724242605062233417184911333065108859297893274877902045993216986203079495828026354663317386440140270647809550473976974096628129591628284434963946783999869378111149217917648303508065328285929072381617978438470612874589596417613745039005251725210799071272826546175725224168805195456492444749329204834536327769184614475392674754321257754169752988706888110110854886262024581325203950655368202664487427493994718122501091228347564869440655164776355796295767478070623428032139757559412393093121138433999763436450288748369986859103207  
>>> e1 = 34456075732829756714431696264844933736161425428678777444326530245267175496676105
>>> e2 = 66213320562378389542956020292848603326457400359492442893037745994906793456536650
>>> c1 = 6451549454415106937054124906386205073222243394024359630462457026011516075453322110598440273419680741264449270624349464347792470300209994225871051817906071211422868952418491992463196228285205919371173656723348479276338927171156200258373946868108513210341715619135657733694945758701239603020350282490930923223040685524857825378664935954076777009286161163426015863451976127043646518744751008641471118799355737506530194673897401350560878119713588235864131464162613324379365056778461514972632453218452367994231300225730879806827703530704658426099425996148485094190653296415838854275518343410370771236791449822141459828741
>>> c2 = 962692207706212570956439147864349279649773113345655426314467693283718484612354279844043839717727068405496826210437866778756030633962827278103786266408189507399825183552809952197915820962569346678627273880805894119629683258989464814629538794918992935736967313768318129713814389945731392361973072114735327121558821584916746528122804041711257237956057904149848804653061211762199626222824628761726392699104681979458399805669073291307091763121332471373822692444415481403270868672559435581015624351087019008601980986815604227475289546705737298842219420062366361168396261671333779917844108475134254136718732987251213358163
>>> flag_enc = 15465286692614275746593514754237742386723861276150927182475649162005944543455951013680150395056664962236242882064880238881068860224733875220632862364701169875117607762861097611036434484377717716522737041218148230761637401384647090841280793847093817991683060457776791068080281552363949410183822084792402759853630877454700951708809147788336138383950624542278364204457482947061715484392305381003183584082954722435919314472678081759451287929983648205030782429815775036186091814941726369980614237971458156295355908243600894532353339370750767776703572265634702300110928757229421759517414772239223719386574540374904804032054
>>>
>>> r = 10085597
>>> assert N % r == 0
>>>
>>> from math import gcd
>>> N = N1 // r
>>> q = gcd(pow(pow(5, e1, N) * c1, e2, N) - pow(pow(7, e2, N) * c2, e1, N), N)
>>> assert N % q == 0 and 1 < q < N
>>>
>>> p = N // q
>>> d = pow(0x10001, -1, (p - 1) * (q - 1))
>>> m = pow(flag_enc, d, N)
>>>
>>> bytes.fromhex(hex(m)[2:])
b'HackOn{c4m4r3r0_7r4ig4_l4_mUlt4_a7b93daf}'