This is the second in a series of blog posts that will explain challenges from hacking competition held at The Gathering 2017, called TGHack. TGHack is organized by The Gathering, created and held by a number of students at UiO, and sponsored by NSM.

I implore you to read the blog and writeups of Martin Ingesen, another member of the Edward Pwnden CTF team. You should also read the writeup of this challenge by it’s creator here

Close Encounter

Points: 125

Author: PewZ

We intercepted this RSA encrypted message. Can you decrypt it for us?

ciphertext: 3301725813323793523830449827529001764170324266525813942905248339398533386704146778215164605307364778538312368834939155244976282618558606453065237517755562156941816361506386129237655201821569225442531883605299886901781519717 n = 647580559066350764512574139212258654419619377791696792933162647847016182264786947024323483613445156926567953673211035865775396889491136493021394983865794529477091872229948860215774356455333826515720143910504339782998354975787558272036453370109286642626999091302012693562994565167763421804705602666440082138719409120664293876204553614511882382199434919365954997082834057119072868066696185230896273866269308019520562618860020221768639470528300841159704088859374399286986458302241337120121430937058280863472916553328255990461105886678126859657320418919609691089677744300138990131567897731188913573095161012997609872471436323858576012929455006921387033623358406327954425701649820631580290471076284227572599505740170534938538303275799383217459413578897504327360744415747939112249827320135553789275968404788584789483305709222531189435482276931098037440920811828069795012367922134191531348046137386595744872323763751900274523135348273825558806037832123609238684829315071013742451094194097286985647180549444633529585827947422469423955056342229557961062943802754823402381380268562309956425582717559687406317915547051766896665477764999756658000565784673316779579644624160889528487904071313946671365415309957045804828537561845474437630201414013 e = 3

The RSA cryptosystem works in the following manner:

Encryption: $c \equiv m^e \space mod \space n$

Decryption: $m \equiv c^d \space mod \space n$

Where $n = pq$, where $p$ and $q$ are prime, $\phi = (p - 1)(q - 1) \space mod \space n$, and $d$ such that $ed \equiv 1 (mod\space \phi)$ The strength of RSA is the fact that factorization of $n$ into $p$ and $q$ is hard (computationally infeasible).

There are a number of pitfalls, that all result in RSA that can be cracked. They all leverage the fact that poor RSA parameters were chosen.

For one, we see that $n$ isd large, while $c$ seem to be small in relation to them. We also have a small $e$, which in conjunciton with a small plaintext can be an issue. It is not sufficient for $n$ to be large, but it’s prime factors to be relatively far from each other.

If $e$ and $m$ are sufficiently small, and the message is not padded sufficiently, a low public exponent attack can be mounted. But if the prime factors $p$ and $q$ are too close, Fermat factorization be speed up factorization greatly.

Low public exponent

In this case, $e$ is the smallest possible number that can be used. Because we also see a very small cipher $c$, and we expect the plaintext to be short, and it might not be padded sufficiently.

If the following must holds; we can apply a simple low public exponent attack:

If this is true, we can crack the cipher by exploiting:

Leading to:

$m = {(c + \epsilon n)}^{1/3}, \epsilon \in \mathbb{N}$ The cracking can be done by computing:

And stop once a message $m$ is discovered such that:

Which mean that the correct $m$ is discovered, and the RSA encryption is cracked.

This can be solved in the following manner:

import gmpy
import binascii

c = 3301725813323793523830449827529001764170324266525813942905248339398533386704146778215164605307364778538312368834939155244976282618558606453065237517755562156941816361506386129237655201821569225442531883605299886901781519717
n = 647580559066350764512574139212258654419619377791696792933162647847016182264786947024323483613445156926567953673211035865775396889491136493021394983865794529477091872229948860215774356455333826515720143910504339782998354975787558272036453370109286642626999091302012693562994565167763421804705602666440082138719409120664293876204553614511882382199434919365954997082834057119072868066696185230896273866269308019520562618860020221768639470528300841159704088859374399286986458302241337120121430937058280863472916553328255990461105886678126859657320418919609691089677744300138990131567897731188913573095161012997609872471436323858576012929455006921387033623358406327954425701649820631580290471076284227572599505740170534938538303275799383217459413578897504327360744415747939112249827320135553789275968404788584789483305709222531189435482276931098037440920811828069795012367922134191531348046137386595744872323763751900274523135348273825558806037832123609238684829315071013742451094194097286985647180549444633529585827947422469423955056342229557961062943802754823402381380268562309956425582717559687406317915547051766896665477764999756658000565784673316779579644624160889528487904071313946671365415309957045804828537561845474437630201414013

m = gmpy.root(c, 3)[0]

# Stop once we reach the correct message, m
while pow(m, 3, n) != c:
    m = gmpy.root(c + n, 3)[0]

# Print the message in a more convenient format
print(binascii.unhexlify(hex(m)[2:]))

Which will yield the flag: TG17{t00_cl0se_f0r_g00d_crypt0}.

Fermat factorization

Fermat factorization exploit the difference between $p$ and $q$ being small to greatly reduce the amount of time required to factorize $n$, which in turn will be used to compute the secret, $d$.

In particular, it is based on the representation of an odd integer as the difference of two squares:

and in particular, if $n = pq$ we have:

In practice, we can try different values of $x$, hoping that $x^2 - n = y^2$ is a square, meaning $y$ is an integer. This mean that we can start out by trying $x = \sqrt{n}$, and if $x^2 - n = y^2$ is not a square, increment $x$. Continue this until a suitable $x$ is discovered, upon which the factors are $x -y$ and $x + y$.

This can be computed by the following sage function:

def fermat(n):
     a = ceil(sqrt(n))
     b_sq = (a * a) - n
     while int(sqrt(b_sq))**2 != b_sq:
         a += 1
         b_sq = (a * a) - n
     return a - sqrt(b_sq)

This can be used to factor $n$ into $q$ and $p$, which can be used to decrypt the message:

n = 647580559066350764512574139212258654419619377791696792933162647847016182264786947024323483613445156926567953673211035865775396889491136493021394983865794529477091872229948860215774356455333826515720143910504339782998354975787558272036453370109286642626999091302012693562994565167763421804705602666440082138719409120664293876204553614511882382199434919365954997082834057119072868066696185230896273866269308019520562618860020221768639470528300841159704088859374399286986458302241337120121430937058280863472916553328255990461105886678126859657320418919609691089677744300138990131567897731188913573095161012997609872471436323858576012929455006921387033623358406327954425701649820631580290471076284227572599505740170534938538303275799383217459413578897504327360744415747939112249827320135553789275968404788584789483305709222531189435482276931098037440920811828069795012367922134191531348046137386595744872323763751900274523135348273825558806037832123609238684829315071013742451094194097286985647180549444633529585827947422469423955056342229557961062943802754823402381380268562309956425582717559687406317915547051766896665477764999756658000565784673316779579644624160889528487904071313946671365415309957045804828537561845474437630201414013
c = 3301725813323793523830449827529001764170324266525813942905248339398533386704146778215164605307364778538312368834939155244976282618558606453065237517755562156941816361506386129237655201821569225442531883605299886901781519717
e = 3


p = fermat(n)
q = n/p
phi = (p-1)*(q-1)
d = inverse_mod(e, phi)
m = pow(c, d, n)

print binascii.unhexlify(hex(Integer(m))

Yielding the flag: TG17{t00_cl0se_f0r_g00d_crypt0}.

• ← Previous Post