Hack The Box / Challenges / Crypto / Weak RSA

To extract the modulus information from the public key, we can use openssl tool:

openssl rsa -noout -text -modulus -in key.pub -pubin

echo "base16;3303B790FB149DA3406D495AB9B9FB8A9E293445E3BD43B18EF2F0521B726EBE8D838BA7
74BB5240F08F7FBCA0A142A1D4A61EA973294E684A8D1A2CDF18A84F2DB7099B8E977588B0B891292558C
AA05CF5DF2BC6334C5EE5083A234EDFC79A95C478A78E337C723AE8834FB8A9931B74503FFEA9E61BF53D
8716984AC47837B" | bc

3303979099149993406949599999998999293445939943918992905219726999898389977499524090897
9999091429194961999732949684989192999189849299709998997758890989129255899905995992996
3349599508392349999799959478978933797239988349989993197450399999961995398716984994783
79

Found prime in FactorDB:

p=204234381014891586884193035672773438587347585474181580246982884758329525562862413623157
5217906372987360487170945062468605428809604025093949866146482515539
q=280647078974346688506405094715772940902704965380721096222585441676538885813308485821406
66982973481448008792075646342219560082338772652988896389532152684857

Then I’ve used python3 and RSA libs to decrypt the message. The code listing is:

#!/bin/env python

from __future__ import print_function

from Crypto.Util import number
from Crypto.PublicKey.RSA import construct
from Crypto.PublicKey import RSA
import struct
import binascii

def gcd(a, b):
	while a != 0:
		a, b = b % a, a
	return b

def findModInverse(a, m):
	if gcd(a, m) != 1:
		return None
	u1, u2, u3 = 1, 0, a
	v1, v2, v3 = 0, 1, m
   
	while v3 != 0:
		q = u3 // v3
		v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3
	return u1 % m

# Our factored prime numbers p, q
p=20423438101489158688419303567277343858734758547418158024698288475832952556286241362315755217906372987360487170945062468605428809604025093949866146482515539
q=28064707897434668850640509471577294090270496538072109622258544167653888581330848582140666982973481448008792075646342219560082338772652988896389532152684857

# Calculate n = p * q
n = p*q

# Set the exponent
e = 65537
e = 0x6117c60448b139451ab5b60b6257a12bda90c0960fad1e007d16d8fa43aa5aaa3850fc240e5414ad2ba1090e8e12d6495bbc73a0cba562504255c73ea3fbd36a8883f831da8d1b9b8133ac2109e20628e80c7e53baba4ce5a14298811e70b4a2313c914a2a3217c02e951aaee4c9eb39a3f080357b533a6cca9517cb2b95bfcd

# Calculate the d, mod inverse
d = findModInverse(e, (p - 1) * (q - 1))

print("n=",n)
print("e=",e)
print("d=",d)

# Construct RSA private key structure
key = RSA.construct((n,e,d))

# Decrypt the flag
f = open("flag.enc","rb")

# Important, 01 A2 = 0000 0001 1010 0010 = 418
m = int.from_bytes(f.read(),byteorder='big')
print("m=",m)

# Since m will be a list of bytes, we've to convert it to a big integer number
f.close()

# Decrypt message
m = str(hex(key.decrypt(int(m))))
m = m[2:]

# Add leading 0 so that we can convert big hex number to text
if len(m) % 2 > 0: 
	m = "0" + m

m = binascii.unhexlify(m)
print("m=",m)

# Flag will show at the end of the output message.
# HTB{s1mpl3_Wi3n3rs_4tt4ck}

This is a very good exercise for learning how to deal with big numbers and parse them for RSA crypto stuff!