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
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
$ 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
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
Notice that
sage: factor(e)
2^5 * 3^3 * 499
This means that
sage: gcd(e, p - 1)
2
However, we can do a simple trick. We know that this is the ciphertext:
But we have the factorization of
We know that
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
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:
This happens because
But
In the challenge, we need to compute a total of 5 modular square roots, which means that
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 * 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
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
The order of a group means that for any
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
from - We compute
and - We know that the order of the previous results is
- Therefore, since
, we also have that
can be rewritten as for some integers such that . As a result
The takeaway is that we can easily find
and solve this smaller DLP because the prime factor is assumed to be small tooIn other words, we are finding
We can perform the above procedure for all prime factors of
And as all
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 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...}'