The Riddler's Cipher Delight
Challenge#
Category: Cryptography
Difficulty: Easy
Given this python code:
# enc.py
# N = 17520886769422446781402845171452766678392945055507226042115591127790949038926405961588057901152880775198538951363849458511296788407527886190154759113620716962246342938913740398465525503895457929394994569820769711534794538522137993456194572001467194513826600891537022249206765745867423270603572791751504625621683522248065102814089587644651305112722919320696919194544558237008950904152753314856531469392976852299194227815343105809059455186267184706498969875531092067425496067267400027976328334687257293407409892934030446988318349271430705178690957392508571214791220858911022252486038830213798547638612103672306741523579
# e = 3
# c = 5959848254333830910624523071067197529743942832931749422613446095759596470869632698744448445022974243192082623200541274049999046045462632699888118125553180389758240097512080800465269924123706310996597928101365256237876736940573969864179631586328876422479408805381027940806738410297399027560825960052951200511768291312433697743253773594534719688371211151318607767527029263892621127356788516738086153844247429662752321125
from Crypto.Util.number import *
e = 3
while True:
p = getPrime(1024)
q = getPrime(1024)
N = p*q
phi = (p-1)*(q-1)
if GCD(phi, e) == 1:
break
d = inverse(e, phi)
with open("flag.txt", "rb") as f:
m = bytes_to_long(f.read())
assert m < N
c = pow(m, e, N)
print("N = ", N)
print("e = ", e)
print("c = ", c)The Vulnerability: Low Public Exponent Attack#
In this script, standard RSA encryption is used: .
However, two conditions create a classic vulnerability:
- Small Exponent: The public exponent is very small ().
- Small Message / No Padding: The message is just the byte-representation of the text in
flag.txt. A typical CTF flag is around 40-50 bytes, meaning .
When we cube , .
Because is generated from two 1024-bit primes, is a 2048-bit number (). Since , the modulo operation never actually “wraps around” or triggers.
This means that the ciphertext is literally just the normal integer cube of the message: .
The Solution#
To retrieve the flag, we just need to calculate the standard integer cube root of the ciphertext , and then convert that integer back to bytes.
Here is a Python solver script. You don’t even need the value to solve it. I’ve included a simple binary search algorithm for the cube root so you don’t need to install any external math libraries like gmpy2.
from Crypto.Util.number import long_to_bytes
# The given ciphertext
c = 5959848254333830910624523071067197529743942832931749422613446095759596470869632698744448445022974243192082623200541274049999046045462632699888118125553180389758240097512080800465269924123706310996597928101365256237876736940573969864179631586328876422479408805381027940806738410297399027560825960052951200511768291312433697743253773594534719688371211151318607767527029263892621127356788516738086153844247429662752321125
def integer_cbrt(n):
"""Finds the integer cube root of n using binary search."""
low = 1
high = n
while low <= high:
mid = (low + high) // 2
cubed = mid ** 3
if cubed < n:
low = mid + 1
elif cubed > n:
high = mid - 1
else:
return mid
return None
# 1. Calculate the cube root of c
m = integer_cbrt(c)
# 2. Convert the integer message back to bytes
if m is not None:
flag = long_to_bytes(m)
print("Flag found:")
print(flag.decode('utf-8'))
else:
print("Could not find an exact integer cube root. Are you sure m^3 < N?")Running the code , we get the flag : apoorvctf{3ncrypt1ng_w1th_RSA_c4n_b3_4_d4ng3r0us_cl1ff_83}