binary basis
4 minutes to read
We are given the Python source code to encrypt the flag:
from Crypto.Util.number import getPrime, bytes_to_long
from math import prod
FLAG = open('flag.txt', 'rb').read()
primes = [getPrime(128) for _ in range(16)]
n = prod(primes)
e = 0x10001
m = bytes_to_long(FLAG)
c = pow(m, e, n)
treat = sum([primes[i]*2**(0x1337-158*(2*i+1)) for i in range(16)])
with open('output.txt', 'w') as f:
f.write(f'{n = }\n')
f.write(f'{e = }\n')
f.write(f'{c = }\n')
f.write(f'{treat = }\n')
And this is the output of the script:
n = 119493145368134756606524581488517378672235496744508597127639648421685629462649680337305664581985725401892086474314689141024498358715132868441978738105268336335778301627806695859205063825847290995872425532374614756539044160447358903375166525543471922868488499105664355206800751381027260462074705122647672994384365333260862845803962495145681040264675164695690862737006515315087470040757606517140071798300326022127659497206583492859643180260756285101547522674696613261207152550090000611298331939402585491230470733454735317291288404096144773097239721697692471487615973994925335486666529576878075473132154318910180009691
e = 65537
c = 78434014553061170529838401917720357645901208101352296269884472900978844319305951884764695717375322363272928093737865793113104432023794235229497701142692681415679549147532592802702053823324082733182072770779006523720442490771120987890027997070704393610765382574187921750560918055356164458340750383236011537901475045013520557031618820264221766743094536121925226791850895255993453048670745607742469934947653147879259892501050933253400391984499229656112961295969492487005786860006961292676090836472527246673699345029628224872195546099448661501561676622720260514226385260271583307493991971640825413235694692735476316469
treat = 41064122210117590309893920850940851964448573197364702312218652847563074658468550776049623436077059647900426409109763901345955202703985682630778316836716410976908994802298857481157910324003086887604087560484126319093760348302784031959884608690718739939531289130555241671099503557713216197592401241234208735819631180320413760718656876867323406561829316166491696103527500078153837145772310740455509956660694823144830260095551391236403182836214728060291251693690579998717099897785954779748569649102911569556210804834065634957865690729391572538723259866564481741517395331813459603466263827141279911919706281328288050460721861661990446597425850271364217052936489186818846863874578006688813944143685727931104321810713830759839918256937075645849871941798921033683465399959646136621559049887273682054277330663458615787744906360121329675910070999119357809181250170609599790023712764414191551844874675524795782430239120555096062003800058693423405350206617745916914116965357631650740005441388405061692790006508760971107741027556312990780727724371467017609554695371798159449361071175599514947307436760940029734313697931199508407965056916479246854944553994533969739046153764629534835323207379057477612661669942078609127146916601554609679997006901572586628537881511818938391905350113674432833361660748486019032622987316746412638187233454037252369980080224744837380800996358881451638758024280972061536248320550269641404509205922332930938158599125930491114698209185841465863646506532208640
Source code analysis
The source code is really simple. It basically creates a multiprime RSA private key and uses the associated public key to encrypt the flag.
Moreover, it defines a treat variable that depends on the primes list from the private key:
primes = [getPrime(128) for _ in range(16)]
n = prod(primes)
e = 0x10001
m = bytes_to_long(FLAG)
c = pow(m, e, n)
treat = sum([primes[i]*2**(0x1337-158*(2*i+1)) for i in range(16)])
RSA background
In RSA, the private key is mainly composed of two prime numbers $p$ and $q$. These numbers are supposed to be large (normally, they have 1024 bits). On the other hand, the public key holds the exponent $e = 65537$ and the modulus $n = p \cdot q$.
The security of this cryptosystem relies on the fact that integer factorization is a computationally hard problem even for powerful computers. Therefore, given the public modulus $n$, we can say that it is impossible to factor it into $p$ and $q$ if no more information is given.
RSA works so that, given a message $m$ in decimal format, we can encrypt it as follows:
$$ c = m^e \mod{n} $$
On the other hand, the decryption needs two more values: $\phi(n) = (p - 1) (q - 1)$ and $d = e^{-1} \mod{\phi(n)}$, so that:
$$ m = c^d \mod{n} $$
Therefore, the best way to decrypt RSA is to somewhat find the factorization of $n$ (that is, finding $p$ and $q$).
For the case of multiprime RSA, $n$ is the product of more than two prime numbers. However, the rest is still the same. We need to find $\phi{(n)}$ in order to compute the private exponent $d$. Assuming that all primes $p_i$ that form $n$ are different, the formula for $\phi{(n)}$ is
$$ \phi{(n)} = \phi{\left(\prod_{i = 0}^{15} p_i \right)} = \prod_{i = 0}^{15} \phi{(p_i)} = \prod_{i = 0}^{15} (p_i - 1) $$
Solution
Let’s take a closer look at treat:
treat = sum([primes[i]*2**(0x1337-158*(2*i+1)) for i in range(16)])
In math terms, we can rewrite the above code to
$$ \begin{align*} \mathtt{treat} & = \sum_{i = 0}^{15} p_i \cdot 2^{\mathtt{0x1337} - 158 \cdot (2i + 1)} \\ & = \sum_{i = 0}^{15} p_i \cdot 2^{4761 - 316 i} \\ & = 2^{4761} p_0 + 2^{4445} p_1 + 2^{4129} p_2 + \dots + 2^{21} p_{15} \\ & = 2^{21} \left(2^{4740} p_0 + 2^{4424} p_1 + 2^{4108} p_2 + \dots + p_{15}\right) \\ & = 2^{21} \sum_{i = 0}^{15} p_i \cdot 2^{4740 - 316i} \\ & = 2^{21} \sum_{i = 0}^{15} p_i \cdot 2^{316 \cdot (15 - i)} \\ \end{align*} $$
Notice that prime numbers are generated as 128-bit integers. This means that if we express treat in 316-bit chunks (separated at bit number 128 to highlight prime numbers versus padding bits), the prime numbers won’t overlap:
$ python3 -q
>>> n = 119493145368134756606524581488517378672235496744508597127639648421685629462649680337305664581985725401892086474314689141024498358715132868441978738105268336335778301627806695859205063825847290995872425532374614756539044160447358903375166525543471922868488499105664355206800751381027260462074705122647672994384365333260862845803962495145681040264675164695690862737006515315087470040757606517140071798300326022127659497206583492859643180260756285101547522674696613261207152550090000611298331939402585491230470733454735317291288404096144773097239721697692471487615973994925335486666529576878075473132154318910180009691
>>> e = 65537
>>> c = 78434014553061170529838401917720357645901208101352296269884472900978844319305951884764695717375322363272928093737865793113104432023794235229497701142692681415679549147532592802702053823324082733182072770779006523720442490771120987890027997070704393610765382574187921750560918055356164458340750383236011537901475045013520557031618820264221766743094536121925226791850895255993453048670745607742469934947653147879259892501050933253400391984499229656112961295969492487005786860006961292676090836472527246673699345029628224872195546099448661501561676622720260514226385260271583307493991971640825413235694692735476316469
>>> treat = 41064122210117590309893920850940851964448573197364702312218652847563074658468550776049623436077059647900426409109763901345955202703985682630778316836716410976908994802298857481157910324003086887604087560484126319093760348302784031959884608690718739939531289130555241671099503557713216197592401241234208735819631180320413760718656876867323406561829316166491696103527500078153837145772310740455509956660694823144830260095551391236403182836214728060291251693690579998717099897785954779748569649102911569556210804834065634957865690729391572538723259866564481741517395331813459603466263827141279911919706281328288050460721861661990446597425850271364217052936489186818846863874578006688813944143685727931104321810713830759839918256937075645849871941798921033683465399959646136621559049887273682054277330663458615787744906360121329675910070999119357809181250170609599790023712764414191551844874675524795782430239120555096062003800058693423405350206617745916914116965357631650740005441388405061692790006508760971107741027556312990780727724371467017609554695371798159449361071175599514947307436760940029734313697931199508407965056916479246854944553994533969739046153764629534835323207379057477612661669942078609127146916601554609679997006901572586628537881511818938391905350113674432833361660748486019032622987316746412638187233454037252369980080224744837380800996358881451638758024280972061536248320550269641404509205922332930938158599125930491114698209185841465863646506532208640
>>>
>>> binary = bin(treat)[2:]
>>> print('\n'.join(binary[i : i + 128] + '\n' + binary[i + 128: i + 316] for i in range(0, len(binary), 316)))
11000001001110001000000101110010111100001000001000110000000101110011101010001101000010101100100000001001011110010010110011001101
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
11101000101101110110100011001110011001111110011010000110000001111101010111100000101111010101010000010100100011010111011110010101
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
11110011101010010111000011001111001011010000000001101011000111010101110110110111000001100001001010100001010000000110011111011001
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
10010111010101111100101101111110000100101001100100100100001111110001001100000101100101010100100100110111111010110000110101100111
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
11110100011001010100100000001000010100100000101101100000001010001101110110111111101110101101001100000011001100011011000100001011
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
10101000111110001101000011000011111110001010101110111111011000100110001001011011000101111000111100000001011101111011110101011101
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
11011001001000110010110000110000010101011100111100011001010100101111111110100111000000000011101100111000000010001010110110111011
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
11011011100011111110010111101011011001111111110000101010011010010111011100111010110010001000010101100111111111011010010111011001
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
10011011010110100100101111110011110110100001001100001100100111110111110110011101101110011001011010010111011000000101001010010001
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
10010010010001111010011011011101001100100001111110001110100100110001100110111001010010010111100010011001100110101000010110010101
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
10010000110010111100011111101111000011011000101110000111100100101001100011000110111000101110100111011001010010001111100101110111
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
10010000001100001010101100110011111100011101111000001001110111111011111001101000000111101110001001100101010100000011010101010101
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
10011010101001100100011000011011000000011010001110000001011100101101100111110010110111011111111010111100101110101111100111001001
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
10000101011110010010100111110110001001101011011111001010001001000011100110001000000010111101000001111101001101111011001010001011
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
11111011110011010010100011010100110111110011110101110111001111010011100001001011110011101000100111111101111101010101000010011001
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
10011100010010011001010110110001001100001110111111010001010100111101000010000111100111001100110001111000011101001000010101010101
000000000000000000000
As a result, the treat variable contains the prime numbers! Therefore, we will be able to decrypt RSA using this information:
>>> primes = [int(binary[i : i + 128], 2) for i in range(0, len(binary), 316)]
>>> prod(primes) == n
True
Another way of getting the primes is to use a similar expression of treat, changing the product by an integer division and adding the 128-bit constraint:
>>> primes == [(treat // 2 ** (0x1337 - 158 * (2 * i + 1))) % 2 ** 128 for i in range(16)]
True
Flag
At this point, we only need to decrypt the ciphertext, computing $\phi{(n)}$ and $d$, and then applying the decryption method:
>>> phi_n = prod(p - 1 for p in primes)
>>> d = pow(e, -1, phi_n)
>>>
>>> m = pow(c, d, n)
>>> bytes.fromhex(hex(m)[2:])
b'HTB{any_leak_related_to_the_primes_can_lead_to_full_factorization}'