<- CRYPTO

Rookie Mistake

8 minutes to read

We are given the Python source code that encrypts the flag:

import os
from Crypto.Util.number import bytes_to_long, getPrime
from sympy import *
from secret import flag

flag1 = bytes_to_long(flag[:len(flag)//2] + os.urandom(69))
flag2 = bytes_to_long(flag[len(flag)//2:] + os.urandom(200))  

def genprime():
    p = 2
    while p.bit_length() < 1020:
        p *= getPrime(30)
    while True:
        x = getPrime(16)
        if isprime((p * x) + 1):
            return (p * x) + 1
            break
      
p,q = [genprime() for _ in range(2)]

print("-" * 10 + "RSA PART" + "-" * 10)

e = 0x69420
ct1 = pow(flag1,e,p)

print(f'p: {hex(p)}')
print(f'e: {hex(e)}')
print(f'ct: {hex(ct1)}')

print("-" * 10 + "DH PART" + "-" * 10)

n = p * q
g = 0x69420
ct2 = pow(g, flag2, n)

print(f'n: {hex(n)}')
print(f'g: {hex(g)}')
print(f'ct: {hex(ct2)}')

We also have the output of the script:

----------RSA PART----------
p: 0x16498bf7cc48a7465416e0f9ec8034f4030991e73aff9524ef74cc574228e36e6e1944c7686f69f0d1186a69b7aa77d7e954edc8a6932f006786f4648ecc8d4f4d3f6c03d9a1ee9fe61b28b6dd2791a63be581b8811a8ac90a387241ea68b7d36b4a274f64c7a721ad55cfcef23cd14c72542f576e4b507c11c4fa198e80021d484691b
e: 0x69420
ct: 0xa82b37d57b6476fa98f6ee7c278d934bd96c49aa1c5399552d25211230d76cb16ade049572bf631e3849903638d41c884957b9592d0aa072b2bdc3105fe0e3253284f85286ec613966f9cde77ae06e2053dc2254e44ca673b4c76879eff84e5fc32af976c1bfafe147a277d72aad674db749ed8f34d2ebe8189cf12afc9baa17764e4b
----------DH PART----------
n: 0xbe30ccaf896c16f53515e298df25df9158d0a95295c119f0444398b94fae26c0b4cf3a43b120cf0fb657069e0621eb1d2dd832eef3065e80ddbc35854dd4585cc41fd6a5b36339c0d9fcc066272be6818be6a624f75482bbb9c408010ac8c27b20397d870bfcb14e6318097b1601f99e391c9b68c5c586f8da561ff8507be9212713b910b748370ce692c11afa09b74ce80c5f5dd72046415aeed85e1ecedca14abe17ed19ab97729b859120699d9f80dd13f8483773df15b938b8399702a6e846b8728a70f1940d4c6e5835a06a89925eb1ec91a796f270e2d9be1a2c4bee5517109c161f04333d9c0d4034fbbd2dcf69fe734b759a89937f4d8ea0ee6b8385aae14a2cce361
g: 0x69420
ct: 0x65d57a564b8a8667a956705442063392b9b975b8ef869a6dbed04d6e585351f559fe6f5d96823f60b7306740fe2cf5aa81e4a12736d4f0a4826cbc8b4312643af19c75432b4ab222837031851f312df5d707b39bdf2d272f25c1947f3e2943f3592cb0519fee8f4b458021b6b8ee4eabeeae5127d412df4f6a88f66d7cc34c6bb77e0a1440737d0e167f9489f0c7fbfd7f6a5870b4b2865d29b91f6c2b375951e85b1b9f03887d4d3c4a6218111a95021ed1d554c57269e7830c3e7b8e17d13e1fb75ee9f305833d0cb6bfab738572cdbbc8b33b878ad25f78d47d7f449a6c348f5f9f1df3e09f924534a3669b4e69bd0411d154ec756b210691e2efc4a55aa664d938a868f4d

The code splits the flag in two parts and encrypts the first part with RSA and the second part is used for a kind of Diffie-Hellman algorithm.

RSA part

Here, the program generates two primes numbers $p$ and $q$ with the following function:

def genprime():
    p = 2
    while p.bit_length() < 1020:
        p *= getPrime(30)
    while True:
        x = getPrime(16)
        if isprime((p * x) + 1):
            return (p * x) + 1
            break
      
p,q = [genprime() for _ in range(2)]

This function does generate prime numbers $p$ and $q$, but we can see that $p - 1$ and $q - 1$ are smooth, which means that they are a product of small factors, so they can be easily factored:

$ sage -q
sage: p = 0x16498bf7cc48a7465416e0f9ec8034f4030991e73aff9524ef74cc574228e36e6e1944c7686f69f0d1186a69b7aa77d7e954edc8a6932f006786f4648ecc8d4f4d3f6c03d9a1ee9fe6
....: 1b28b6dd2791a63be581b8811a8ac90a387241ea68b7d36b4a274f64c7a721ad55cfcef23cd14c72542f576e4b507c11c4fa198e80021d484691b
sage: factor(p - 1)
2 * 36209 * 547798523 * 585495871 * 603764827 * 620106793 * 620486891 * 622959187 * 624928979 * 642300709 * 643598621 * 644170013 * 670656013 * 675669877 * 676128059 * 679467623 * 685343431 * 715193489 * 721280123 * 721341683 * 733843933 * 738509881 * 803591153 * 845584237 * 855999569 * 864585809 * 864781919 * 875862569 * 879413083 * 895364923 * 902987851 * 919851767 * 951702877 * 995048801 * 1025446181 * 1030369169 * 1047227333

Nevertheless, the RSA encryption is wrong, because it uses only $n = p$, and not $n = p \cdot q$:

e = 0x69420
ct1 = pow(flag1,e,p)

print(f'p: {hex(p)}')
print(f'e: {hex(e)}')
print(f'ct: {hex(ct1)}')

Modular inverse

So, to decrypt RSA we need to find $d = e^{-1} \mod{\phi(n)}$, but this time $n = p$, so $\phi(p) = p - 1$.

Notice that $e$ is an even number, like $p - 1$:

sage: factor(e)  
2^5 * 3^3 * 499

This means that $e$ has no inverse modulo $p - 1$, because they share a common factor of $2$:

sage: gcd(e, p - 1)  
2

However, we can do a simple trick. We know that this is the ciphertext:

$$ \mathrm{ct}_1 = (F_1)^e \mod{p} $$

But we have the factorization of $e$, let’s say $e = 2^5 \cdot e’ = 32 \cdot e’$, so

$$ \mathrm{ct}_1 = (F_1)^{32 \cdot e'} \mod{p} = \Big((F_1)^{32}\Big)^{e'} \mod{p} $$

We know that $e’$ has an inverse modulo $p - 1$ because there are no common factors. With this, we can compute $d’ = (e’)^{-1} \mod{p - 1}$, so we can partially decrypt RSA to find

$$ (F_1)^{32} = (\mathrm{ct}_1)^{d'} \mod{p} $$

sage: e_prime = e // 32
sage: d_prime = pow(e_prime, -1, p - 1)  
sage: F1_32 = pow(ct1, d_prime, p)

Modular square root

At this point, we need to compute five modular square roots to get $F_1$. We are lucky because $p \equiv 3 \pmod{4}$:

sage: p % 4  
3

As a result, the modular square root is very easy to compute (no need to use Tonelly-Shanks or Cipolla’s algorithm). Actually we simply need to do the following operation:

$$ \sqrt{a} \mod{p} = a^{\frac{p + 1}{4}} \mod{p} $$

This happens because $p \equiv 3 \pmod{4}$, so $p + 1$ is divisible by $4$. As a result, we can see that for a quadratic residue $a$, we have

$$ \Big(a^{\frac{p + 1}{4}}\Big)^2 \equiv a^{\frac{p + 1}{2}} \equiv a^{\frac{p - 1}{2} + 1} \equiv a^{\frac{p - 1}{2}} \cdot a \pmod{p} $$

But $a$ is a quadratic residue, so $a^{\frac{p - 1}{2}} \equiv 1 \pmod{p}$ because of the Legendre symbol. Therefore:

$$ a \equiv \Big(a^{\frac{p + 1}{4}}\Big)^2 \pmod{p} \iff \sqrt{a} \mod{p} = a^{\frac{p + 1}{4}} \mod{p} $$

In the challenge, we need to compute a total of 5 modular square roots, which means that

$$ \begin{align} \sqrt{\sqrt{\sqrt{\sqrt{\sqrt{a}}}}} \mod{p} & = \left(\left(\left(\left(a^{\frac{p + 1}{4}}\right)^{\frac{p + 1}{4}}\right)^{\frac{p + 1}{4}}\right)^{\frac{p + 1}{4}}\right)^{\frac{p + 1}{4}} \mod{p} \\ \\ & = a^{\left(\frac{p + 1}{4}\right)^5} \mod{p} \end{align} $$

Also, notice that we can have two values (“positive” and “negative”):

sage: F1_pos = pow(F1_32, ((p + 1) // 4) ** 5, p)
sage: F1_neg = - pow(F1_32, ((p + 1) // 4) ** 5, p) % p  
sage: pow(F1_pos, 32, p) == F1_32
True
sage: pow(F1_neg, 32, p) == F1_32
True

Both results are correct, now we can transform the integers to bytes and find the first part of the flag:

sage: from Crypto.Util.number import long_to_bytes
sage: 
sage: long_to_bytes(F1_pos)
b"\x01d\x98\xbf|\xc4\x8ateAm\xc7J\x85\x87\xd7\xd7\xb79\xbaBK\x99\xd9\x1e\x81\xedX@\xaf\x1a\xd7\xb3k`\xd9\xfd\x12\x8em\x9e\xaa'1+\x1bv\t\x0b5\xe0\xac\x16\t\xbe\x87\xd2\x04\x0f\xde\x14zd.y\x08Z\x93\xda\xfd\xd0\x98\xb4\x8fA\x0e\x07N\x8c;\\$\xfe\x1d\xb5\xe1,!\xf0b\xd1U9\xa8:\xe3\xef\xf1X\x16\x07\xb4_\xad\x8a\xf6\x82\x99\xea\x99\x8b\x85L\xe3\xb2l\xe3\xa1E\xb2\xb2j\xca\xad3W\xdcy\xa2\xb7\xda\xdc"  
sage: long_to_bytes(F1_neg)
b'HTB{why_d1d_y0u_m3ss_3v3ryth1ng_up_1ts_n0t_th4t_h4rd\xa6{\xcb\x9c,b\x9cNQI\xd2q}f\x83\xec\xdf\x07\x99Y\xfd\xd20|\x8a\xa0@\xb5\xce\xe4\xfeP\x99F\xc3J^\xee\x98\x1a\xc4\x8f\xde\xdac\x04\x8aA\x8fzA\x90\x88\x93CoU\x0e\xb1\x84\xf4e\x90#\xa81\xcc\x8e?'
sage: 
sage: flag_1 = long_to_bytes(F1_neg)[:-69]
sage: flag_1
b'HTB{why_d1d_y0u_m3ss_3v3ryth1ng_up_1ts_n0t_th4t_h4rd'

It is worth mentioning that SageMath has already a built-in function to compute modular square roots. Obviously, the result is the same:

sage: F1_pos
4201194382473724823946245664476268770218779530267745631798277601475967345630248107533462798803204288137779509787564780504966343462663924226975569401791847021826701859300016252917662627194197632101762089232321707672259836580168886302616280071328841634356403810182532413499230647098791128541962463909881376626892593884
sage: F1_neg
704870176009839943295001005721824489658707968101575547302884245480223451122699901534421255763466589831492608647316303534144245099881861784549081734244119834897278951901021794139800755949365192687382593739705762118319271568111895419695283389845409501392586562162954626526287954893771121659455
sage: Mod(F1_32, p).nth_root(32, all=True)
[4201194382473724823946245664476268770218779530267745631798277601475967345630248107533462798803204288137779509787564780504966343462663924226975569401791847021826701859300016252917662627194197632101762089232321707672259836580168886302616280071328841634356403810182532413499230647098791128541962463909881376626892593884,  
 704870176009839943295001005721824489658707968101575547302884245480223451122699901534421255763466589831492608647316303534144245099881861784549081734244119834897278951901021794139800755949365192687382593739705762118319271568111895419695283389845409501392586562162954626526287954893771121659455]

Diffie-Hellman part

Here, the script takes $n = p \cdot q$ and computes $\mathrm{ct}_2 = g^{F_2} \mod{n}$:

n = p * q
g = 0x69420
ct2 = pow(g, flag2, n)

print(f'n: {hex(n)}')
print(f'g: {hex(g)}')
print(f'ct: {hex(ct2)}')

Discrete logarithm problem

So, we need to solve a discrete logarithm problem (DLP). Notice that we have $n$ and $p$, so it is trivial to find $q$. Moreover, we can factor $q - 1$ because it is smooth:

sage: n = 0xbe30ccaf896c16f53515e298df25df9158d0a95295c119f0444398b94fae26c0b4cf3a43b120cf0fb657069e0621eb1d2dd832eef3065e80ddbc35854dd4585cc41fd6a5b36339c0d9
....: fcc066272be6818be6a624f75482bbb9c408010ac8c27b20397d870bfcb14e6318097b1601f99e391c9b68c5c586f8da561ff8507be9212713b910b748370ce692c11afa09b74ce80c5f5dd7
....: 2046415aeed85e1ecedca14abe17ed19ab97729b859120699d9f80dd13f8483773df15b938b8399702a6e846b8728a70f1940d4c6e5835a06a89925eb1ec91a796f270e2d9be1a2c4bee5517
....: 109c161f04333d9c0d4034fbbd2dcf69fe734b759a89937f4d8ea0ee6b8385aae14a2cce361
sage: g = 0x69420
ct2 = 0x65d57a564b8a8667a956705442063392b9b975b8ef869a6dbed04d6e585351f559fe6f5d96823f60b7306740fe2cf5aa81e4a12736d4f0a4826cbc8b4312643af19c75432b4ab222
....: 837031851f312df5d707b39bdf2d272f25c1947f3e2943f3592cb0519fee8f4b458021b6b8ee4eabeeae5127d412df4f6a88f66d7cc34c6bb77e0a1440737d0e167f9489f0c7fbfd7f6a5870
....: b4b2865d29b91f6c2b375951e85b1b9f03887d4d3c4a6218111a95021ed1d554c57269e7830c3e7b8e17d13e1fb75ee9f305833d0cb6bfab738572cdbbc8b33b878ad25f78d47d7f449a6c34
....: 8f5f9f1df3e09f924534a3669b4e69bd0411d154ec756b210691e2efc4a55aa664d938a868f4d
sage: 
sage: n % p
0
sage: q = n // p
sage: factor(q - 1)
2 * 40063 * 551582609 * 555256837 * 567856451 * 573405799 * 583336199 * 592968841 * 604811437 * 607714537 * 631781797 * 642077581 * 658176689 * 693045383 * 696054091 * 783195877 * 803763223 * 816799999 * 831612053 * 831917677 * 854559229 * 859490563 * 878834741 * 888267077 * 898662421 * 914208679 * 926926393 * 973394783 * 982425319 * 995929153 * 1014167779 * 1021103537 * 1026380813 * 1030635341 * 1059922679 * 1067331847 * 1072990939

The DLP itself is hard to solve. However, this time it is not! At this context, we are working on the group $\mathbb{Z}_n$, where $n = p \cdot q$. As a result, the order of the group is $\phi(n) = \phi(p) \cdot \phi(q) = (p - 1) \cdot (q - 1)$. And this order $\phi(n)$ is smooth.

The order of a group means that for any $a \in \mathbb{Z}_n$, we have that $a^{\phi(n)} \equiv 1 \mod{n}$. Similarly, the order of an element is the smallest positive integer $k$ such that $a^k \equiv 1 \mod{n}$. Related to this, Lagrange’s theorem states that $k \;|\; \phi(n)$.

Having said this, the approach we will follow is Pohlig-Hellman algorithm, which solves a discrete logarithm on a group with smooth order by solving smaller discrete logarithms and then joining all the result using the Chinese Remainder Theorem (CRT).

Pohlig-Hellman algorithm

The idea is the following:

  • We take a prime factor $k$ from $\phi(n)$
  • We compute $(\mathrm{ct}_2)^{\frac{\phi(n)}{k}} \mod{p}$ and $g^{\frac{\phi(n)}{k}} \mod{p}$
  • We know that the order of the previous results is $k$
  • Therefore, since $\mathrm{ct}_2 = g^{F_2} \mod{p}$, we also have that

$$ (\mathrm{ct}_2)^{\frac{\phi(n)}{k}} = (g^{F_2})^{\frac{\phi(n)}{k}} \mod{p} = (g^{\frac{\phi(n)}{k}})^{F_2} \mod{p} $$

  • $F_2$ can be rewritten as $F_2 = \alpha \cdot k + r$ for some integers $\alpha, r$ such that $0 \leqslant r < k$. As a result

$$ \begin{align} (\mathrm{ct}_2)^{\frac{\phi(n)}{k}} & = (g^{\frac{\phi(n)}{k}})^{F_2} \mod{p} \\ & = (g^{\frac{\phi(n)}{k}})^{\alpha \cdot k + r} \mod{p} \\ & = (g^{\frac{\phi(n)}{k}})^{\alpha \cdot k} \cdot (g^{\frac{\phi(n)}{k}})^r \mod{p} \\ & = (g^{\phi(n)})^\alpha \cdot (g^{\frac{\phi(n)}{k}})^r \mod{p} \\ & = 1^\alpha \cdot (g^{\frac{\phi(n)}{k}})^r \mod{p} \\ & = (g^{\frac{\phi(n)}{k}})^r \mod{p} \\ \end{align} $$

  • The takeaway is that we can easily find $r$ and solve this smaller DLP because the prime factor $k$ is assumed to be small too

  • In other words, we are finding $r = F_2 \mod{k}$

We can perform the above procedure for all prime factors of $\phi(n)$ to get a system of congruences:

$$ \begin{cases} F_2 \equiv r_1 \pmod{k_1} \\ F_2 \equiv r_2 \pmod{k_2} \\ \dots \\ F_2 \equiv r_m \pmod{k_m} \\ \end{cases} $$

And as all $k_i$ are pairwise coprime factors, we can use the CRT to find $F_2 \mod{\prod_i k_i}$, which must be equal to $F_2$.

We can use SageMath to implement it:

sage: order = (p - 1) * (q - 1)
sage: factors = factor(order)
sage:
sage: Zn = Zmod(n)
sage: g = Zn(g)
sage: ct2 = Zn(ct2)
sage:
sage: dlogs = []
sage: crt_moduli = []
sage:
sage: for prime, exponent in factors:
....:     if int(g) % prime == 0:
....:         continue
....:     k = prime ** exponent
....:     dlog = discrete_log(ct2 ** (order // k), g ** (order // k), ord=k, algorithm='bsgs')  
....:     crt_moduli.append(k)
....:     dlogs.append(dlog)
....:
sage: F2 = crt(dlogs, crt_moduli)

Notice that we need to skip prime factors of $\phi(n)$ that are not coprime with the base $g$. Also, we are specifying the order $k$ of the elements in discrete_log, to let it go faster. Moreover, we use Baby-step Giant-step, which is fast enough for groups of small order.

It’s worth mentioning that SageMath’s built-in discrete_log function already uses Pohlig-Hellman algorithm when possible:

sage: discrete_log(ct2, g, order)
2804476603085107565027707255749331066295103785426224861629602201861680712499854130377652576076102338557402972269310646835886484491716329948655731491481860234974607399319663254766286986177485599417063421968583069450861571804348897620247729058365086491428960261457881020586798485365714478651540371063176262146817288318452782818035727600844973213824528482080917545525357109160391608446961425726431705862033416482182497028540360742130961638707993186618482030415914893938295007102503532179843459346182484919123109958806129275887177866427746552590289190952679504543771881453032958846129549284558335743189694513183  
sage: discrete_log(ct2, g, order) == F2
True

With this, we have found the second part of the flag:

sage: long_to_bytes(F2)
b'_ju5t_us3_pr0p3r_p4r4m3t3rs_f0r_4ny_crypt0syst3m...}\xed\xe3\xe5\x10\xb3\xa0f\x95E\xb8\xc6!\xf4\x881\xb1\xd1\xc9\xef\x12\'\x9a,\x9ba\x18i\x8a\xc9\xcd\t#\x92\xf4%\x8d\xe2\xd4g-1\xf4\x0bM$\x13\xe0\x1cO>y\xb0Y\x07\x12\xa1\xb0\x85\x7f\x9e\xb8\xeav\xf7C\x8ff\xb6\xe9\xf7\xe8R\xa9\xc6o^\xd9\x16\x03\xb4\x93\xf5\xecr}\x9f\xd4*\xf5\\\xa3?F\xa4d\x08\x8d\xe6>\xa8\xe1\x8bJ\x9a\xa4oN\xed3\xe2\xffe\xd6\x14\xcd\xb0\x89;+f\xacf\xa0"\'\xc6\xd0d!\x1f\x16U@(\x84\xb0\xab<s\x98Oimb\xe53,l\x1a\x11\x1c\x8b\xb9\x9c\xf1\x07;|\x94O\x13\x9b\r\x99R\xd7\xfb\xb3\xe1\xff\x99\x03\xb2i\xbb\xdc\xb8\xc1U\xf7\xf8\x03\xe4\xbf1O\x9en\x94\xe3\x92\xc0z\x05J\x17w\xf7\x80\x1f'  
sage: 
sage: flag_2 = long_to_bytes(F2)[:-200]
sage: flag_2
b'_ju5t_us3_pr0p3r_p4r4m3t3rs_f0r_4ny_crypt0syst3m...}'

Flag

Finally, we can join the two parts and read the flag:

sage: flag_1 + flag_2
b'HTB{why_d1d_y0u_m3ss_3v3ryth1ng_up_1ts_n0t_th4t_h4rd_ju5t_us3_pr0p3r_p4r4m3t3rs_f0r_4ny_crypt0syst3m...}'