HackVent 2023 - [HV23.23] Roll your own RSA
Difficulty: Leet
Category: Cryptography
Author: cryze
Santa wrote his own script to encrypt his secrets with RSA. He got inspired from the windows login where you can specify a hint for your password, so he added a hint for his own software. This won’t break the encryption, will it?
As I had no idea about cryptography, I went to ask ChatGPT. To my surprise it gave me a working solve script:
from sage.all import *
# Provided values
N = 143306145185651132108707...
e = 65537
hint = -36736786172769290028...
encrypted = 7279276277823216...
# The hint is p**3 - q**8 + polynomial_function(x=x).
# Since p and q are primes used in RSA, they are large numbers,
# and their cube and eighth powers, respectively, will be very large.
# The polynomial function adds a relatively small number to p**3 - q**8,
# so we can approximate q by taking the eighth root of the absolute part of hint.
# Once q is approximated, we can use it to approximate p.
# Approximate q by finding the closest integer to the eighth root of the absolute value of the hint
approx_q = Integer(round(abs(hint)**(1/8)))
# Find p using N and approx_q
approx_p = N // approx_q
# Calculate phi and the decryption exponent d
phi = (approx_p - 1) * (approx_q - 1)
d = inverse_mod(e, phi)
# Decrypt the flag
decrypted = power_mod(encrypted, d, N)
flag = int(decrypted).to_bytes((decrypted.nbits() + 7) // 8, byteorder='big').decode()
print(flag)
The flag is:
HV23{1t_w4s_4b0ut_t1m3_f0r_s0me_RSA_4g41n!}