Skip to main content

Royal Society of Arts 2 [CRYPTO]

April 27, 2023

RSA challenge with the combination of flag regex checker.

Challenge Description​

70 points, 256 solves

RSA strikes strikes strikes strikes strikes again again again again again!

rsa2.py

from Crypto.Util.number import getStrongPrime, bytes_to_long, long_to_bytes
f = open("flag.txt").read()
m = bytes_to_long(f.encode())
p = getStrongPrime(512)
q = getStrongPrime(512)
n = p*q
e = 65537
c = pow(m,e,n)
print("n =",n)
print("e =",e)
print("c =",c)

d = pow(e, -1, (p-1)*(q-1))

c = int(input("Text to decrypt: "))

if c == m or b"actf{" in long_to_bytes(pow(c, d, n)):
print("No flag for you!")
exit(1)

print("m =", pow(c, d, n))

Analysis​

In this challenge, we need to bypass the conditional statement from preventing us to access the flag.

if c == m or b"actf{" in long_to_bytes(pow(c, d, n)):
print("No flag for you!")
exit(1)

By observing both conditions, we can conclude that:

  1. c == m: This condition preventing the player from brute-forcing the flag. Therefore, even we get the long integer m (flagflag), we did not know the value is literally the flag.
  2. b"actf{" in long_to_bytes(pow(c, d, n)): This condition is checking the flag format actf{. Therefore, we cannot simply insert the c into the input field.
  3. The if statement accepts any integer inputs outside of Condition 1 and Condition 2.

We need to submit an integer that is closely related to mm and cc. Hence, we can encapsulate cc that is generated every single execution by submitting c2c^2. This is because c2c^2 will not produce the flag format actf{ after decryption and it will not tampered the original flagflag value.

c=flage (mod n)c2=(flage)2 (mod n)flag2=(c2)d (mod n)flag=(c2)d\begin{aligned} c &= flag^e\ (mod\ n)\\ c^2 &= (flag^e)^2\ (mod\ n)\\ flag^2 &= (c^2)^d\ (mod\ n)\\ flag &= \sqrt(c^2)^d\\ \end{aligned}

NOTE: This method only works if n, p, and q are larger than bytes_to_long(flag). We can indirectly verify that flag is smaller than both p and q.

From here, we have our solution.

Solution​

#!/usr/bin/env python3
from pwn import *
from Crypto.Util.number import long_to_bytes
from sage.all import *

context.log_level = 'critical'

io = remote("challs.actf.co", 32400)
io.recvline() # n value
io.recvline() # e value
c = io.recvline().split(b'=')[1].decode() # c value
io.recvuntil(b':') # Type to decrypt:
io.sendline(str(int(c)**2).encode())
m_square = io.recvline().split(b'=')[1].decode()
io.close()

FLAG = int(sqrt(m_square))
print(long_to_bytes(FLAG))

FLAG: actf{rs4_is_sorta_homom0rphic_50c8d344df58322b}