Down the Rabinhole
6 minutes to read
We are given a Python code to encrypt the flag, and the corresponding out.txt file:
from Crypto.Util.number import getPrime, isPrime, bytes_to_long
from Crypto.Util.Padding import pad
import os
FLAG = b"HTB{--REDACTED--}"
def getPrimes(coefficient):
while True:
a = getPrime(512)
p = 3 * coefficient * a + 2
if isPrime(p):
break
while True:
b = getPrime(512)
q = 3 * coefficient * b + 2
if isPrime(q):
break
return p, q
def encrypt(message, coefficient):
p, q = getPrimes(coefficient)
n = p * q
padded_message = bytes_to_long(pad(message, 256))
message = bytes_to_long(message)
c1 = (message * (message + coefficient)) % n
c2 = (padded_message * (padded_message + coefficient)) % n
return (n, c1, c2)
def main():
coefficient = getPrime(128)
out = ""
message = FLAG[0:len(FLAG)//2]
n1, c1, c2 = encrypt(message, coefficient)
out += f"{n1}\n{c1}\n{c2}\n"
message = FLAG[len(FLAG)//2:]
n2, c3, c4 = encrypt(message, coefficient)
out += f"{n2}\n{c3}\n{c4}\n"
out += f"{len(FLAG)}"
with open("out.txt", "w") as f:
f.write(out)
if __name__ == '__main__':
main()
19776862259930835769533075141648724317136726865325219582974628641663028757626265811083579217562652521882819442186121072998911507994180202653223643709290080839913395525826127153190928840827396123760992080649033993986933259414523207699646834981906819263319717393978144309193843291629147724979917210633945695963741292906203710063193032172565935616940163881309010593278779797311032854042143
18940449739373929782738747330951086701639920358124022449285915914681280430796481828627299763135820762855030234173393995786612606880441619894387463477558992819159868677736220547584576162287130594708254787956440732197673909613467337841562238900614238638819659960733399020443364866675611439229048487547611412841048501574753238490324081535533435151621545695715920828646120795059085207687562
8139131820890905559667838555211733555742225714065473904284826530490173193882559461890851501765452084252909412188575022633596512451349296562551141247433279875212083704533696867645657058965269748533381751261887853181791035505421692256731545740535452608088572835061213186774986415770477686449034066741760771862922788827235376073691257160953903839272893965131226612277505938410382901008254
26981290975895303933094134784682647576666219028610175215312705398803184876873073206073503314367717924247311343215620922642215797499997039996235807898656819655954778538207489354154710796202412578870511364360408739855039573753404337104901925571890067221867326539447741757218265017060345184819121122211405292705642802582423249795098475142694876497945367191724577275836649641722277321440333
11417442976137891276889457530453693512824297007151561589652706330477531354073557298919952168938641673547415923544612769937040826488039629275033613885416852757446100888628373584968290007182319967658770715301605453943639269415203462531753249668211460008832837924575003999865632991329309338991536326471187269457640505585240846158952935988441171094886116683100214189858525596159931001818615
18355127503780127719693553150263322113757549849264731376621241697648137569897555203319854095104524520716185245672659763235856966677160994023952943459682923666302498240656511471051133821432105321005228730688019003306690750456433049212247022010356640992865785005342800448602013572898416040572578635571772069565860571397553306232025854213437948953083273924864099046923310816080854899416432
186
First of all, we see that the program takes a 128-bit prime number called coefficient to generate other prime numbers $p$ and $q$. Let $C$ be the value of coefficient, then the prime numbers $p$ and $q$ are computed as:
$$ p = 3 a C + 2 $$
$$ q = 3 b C + 2 $$
Where $a$ and $b$ are 512-bit prime numbers. Using this strange method, we have two modulus: $n_1$ and $n_2$. Hence, we might be able to find the coefficient $C$ because it is common in the two modulus. Let $p_i = 3 a_i C + 2$ and $q_i = 3 b_i C + 2$, then:
$$ \begin{equation} \begin{split} n_i &= p_i \cdot q_i \\ &= (3 a_i C + 2) \cdot (3 b_i C + 2) \\ &= 9 a_i b_i C^2 + 6 a_i C + 6 b_i C + 4 \end{split} \end{equation} $$
Notice that:
$$ \begin{equation} \begin{split} n_i - 4 &= 9 a_i b_i C^2 + 6 a_i C + 6 b_i C \\ &= 3 C \cdot (3 a_i b_i C + 2 a_i + 2 b_i) \end{split} \end{equation} $$
Since we have $n_1$ and $n_2$, then $3 C = \gcd{(n_1 - 4, n_2 - 4)}$, so
$$ C = \frac{\gcd{(n_1 - 4, n_2 - 4)}}{3} $$
Alright, now let’s see how the ciphertexts $c_1$ and $c_2$ are computed (the procedure will be the same for $c_3$ and $c_4$). Let $m_1$ be the first half of the flag:
$$ \begin{equation} \begin{split} c_1 &= m_1 \cdot (m_1 + C) \mod{n_1} \\ &= m_1^2 + m_1 C \mod{n_1} \end{split} \end{equation} $$
$$ \begin{equation} \begin{split} c_2 &= \mathrm{pad}\, (m_1, 256) \cdot \left(\mathrm{pad}\, (m_1, 256) \cdot C\right) \mod{n_1} \\ &= \mathrm{pad}\, (m_1, 256)^2 + \mathrm{pad}\, (m_1, 256) \cdot C \mod{n_1} \end{split} \end{equation} $$
The pad function adds more bytes to the message in a predictable way. For example, if a message of 12 bytes long is padded up to 16 bytes, the padding will be 4 bytes \x04. These are some examples:
$ python3 -q
>>> from Crypto.Util.Padding import pad
>>> pad(b'A' * 12, 16)
b'AAAAAAAAAAAA\x04\x04\x04\x04'
>>> pad(b'A' * 10, 16)
b'AAAAAAAAAA\x06\x06\x06\x06\x06\x06'
>>> pad(b'A' * 1, 16)
b'A\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f'
We can express the pad operation in mathematical terms like this, being $L$ the length of the message:
$$ \mathrm{pad}\,(m_i, 256) = m_i \cdot 256 ^ {256 - L} + P $$
And $P$ (the actual padding) is the following expression. For simplification purposes, let $K = 256 - L$:
$$ P = K \cdot (1 + 256 + 256^2 + \dots + 256^{K - 1}) $$
Which is the sum of a geometric progression, which equals
$$ P = K \cdot \frac{256^K - 1}{256 - 1} $$
Therefore, we can express $c_2$ as follows
$$ \begin{equation} \begin{split} c_2 &= \mathrm{pad}\, (m_1, 256)^2 + \mathrm{pad}\, (m_1, 256) \cdot C \mod{n_1} \\ &= \left(m_1 \cdot 256 ^ K + P\right)^2 + \left(m_1 \cdot 256^K + P\right) \cdot C \mod{n_1} \\ &= m_1^2 \cdot 256 ^{2 K} + 2 m_1 P \cdot 256^K + P^2 + m_1 C \cdot 256^K + P C \mod{n_1} \end{split} \end{equation} $$
Now we can move some things around:
$$ c_2 - P^2 - P C = m_1^2 \cdot 256 ^{2 K} + 2 m_1 P \cdot 256^K + m_1 C \cdot 256^K \mod{n_1} $$
$$ c_2 - P^2 - P C = 256^K \cdot (m_1^2 \cdot 256^K + 2 m_1 P + m_1 C) \mod{n_1} $$
$$ (c_2 - P^2 - P C) \cdot \left(256^K\right)^{-1} = m_1^2 \cdot 256^K + 2 m_1 P + m_1 C \mod{n_1} $$
Let’s define $X$ as
$$ \begin{equation} \begin{split} X &:= (c_2 - P^2 - P C) \cdot \left(256^K\right)^{-1} \mod{n_1} \\ &= m_1^2 \cdot 256^K + 2 m_1 P + m_1 C \mod{n_1} \end{split} \end{equation} $$
We can get rid of $m_1^2 \cdot 256^K$ if we substract $c_1 \cdot 256^K$:
$$ \begin{equation} \begin{split} X &- c_1 \cdot 256^K = \\ &= (m_1^2 \cdot 256^K + 2 m_1 P + m_1 C) - c_1 \cdot 256^K \mod{n_1} \\ &= (m_1^2 \cdot 256^K + 2 m_1 P + m_1 C) - (m_1^2 + m_1 C) \cdot 256^K \mod{n_1} \\ &= 2 m_1 P + m_1 C - m_1 C \cdot 256^K \mod{n_1} \\ &= m_1 \cdot (2 P + C - C \cdot 256^K) \mod{n_1} \end{split} \end{equation} $$
At this point, we can isolate $m_1$:
$$ m_1 = (X - c_1 \cdot 256^K) \cdot (2 P + C - C \cdot 256^K)^{-1} \mod{n_1} $$
So we have everything, we only need to script it. This is a Python script that solves the challenge:
#!/usr/bin/env python3
import math
def main():
with open('out.txt') as f:
n1, c1, c2, n2, c3, c4, L = map(int, f.read().splitlines())
C = math.gcd(n1 - 4, n2 - 4) // 3
K = 256 - math.floor(L / 2)
P = int(hex(K)[2:] * K, 16)
X = (c2 - P ** 2 - P * C) * pow(256 ** K, -1, n1) % n1
m1 = (X - 256 ** K * c1) * pow(2 * P + C - C * 256 ** K, -1, n1) % n1
K = 256 - math.ceil(L / 2)
P = int(hex(K)[2:] * K, 16)
Y = (c4 - P ** 2 - P * C) * pow(256 ** K, -1, n2) % n2
m2 = (Y - 256 ** K * c3) * pow(2 * P + C - C * 256 ** K, -1, n2) % n2
print(bytes.fromhex(hex(m1)[2:] + hex(m2)[2:]))
if __name__ == '__main__':
main()
$ python3 solve.py
b'HTB{You_were_supposed_to_find_the_gcd_trick_then_search_and_find_the_ACSC_writeup_learn_some_interesting_stuff_and_solve_the_challege_but_I_forgot_about_the_most_basic_thing_I_m_sorry:(}'
The full script can be found in here: solve.py.