Joseph Surin
Computing & Software Systems @ The University of Melbourne

CTF Writeups/Projects/Random Stuff
⬅ BACK
SharkyCTF 2020 Writeups

I played SharkyCTF this weekend on team misc and we came 5th.


Noisy RSA

crypto (398pts)

Something about this randomly generated noise doesn't seem right...

generate.py:

from Crypto.Util.number import bytes_to_long, getStrongPrime
from fractions import gcd
from secret import flag
from Crypto.Random import get_random_bytes

def encrypt(number):
	return pow(number,e,N)

def noisy_encrypt(a,m):
	return encrypt(pow(a,3,N)+(m << 24))

e = 3
p = getStrongPrime(512)
q = getStrongPrime(512)

while (gcd(e,(p-1)*(q-1)) != 1):
	p = getStrongPrime(512)
	q = getStrongPrime(512)

N = p * q

print("N : " + str(N) + "\n")
print("e : " + str(e) + "\n")

rand = bytes_to_long(get_random_bytes(64))

ct = []
ct.append(encrypt(rand << 24))

for car in flag:
	ct.append(noisy_encrypt(car,rand))

print(ct)

Solution

We have a bunch of ciphertexts which are the encryptions of single plaintext characters. The encryption uses low public exponent RSA with linear padding, and we are given the encryption of the padding used as well as some known plaintext/ciphertext pairs (from the flag format). We can use the Franklin-Reiter related message attack to recover the random padding and therefore generate a mapping from possible plaintext characters to their encryption.

Recovering rr

Let rr denote the random padding used (the rand variable in the handout code) and let M2=r×224M_2 = r \times 2^{24}. Let bb denote the first plaintext character in its integer representation (we know b=ord("s")=115b = \mathrm{ord}("s") = 115). Let C2C_2 denote the encryption of M2M_2, that is C2M2e(modN)C_2 \equiv M_2^e \pmod N.

Define the function f(x)=x+bf(x) = x + b and let M1=f(M2)M_1 = f(M_2). Let C1C_1 denote the encryption of M1M_1, that is C1f(M2)e(modN)C_1 \equiv f(M_2)^e \pmod N. It is clear that we have the values of C1C_1 and C2C_2 as they are the second and first values in the ct array respectively. Hence, we can define the new functions: g1f(x)eC1(modN)g2xeC2(modN)\begin{aligned} g_1 &\equiv f(x)^e - C_1 \pmod N \\ g_2 &\equiv x^e - C_2 \pmod N \end{aligned}

We see that g1g_1 and g2g_2 share a root. Namely, x=M2x = M_2. Thus, g1g_1 and g2g_2 share the common factor (xM2)(x - M_2). We can use the Euclidean algorithm to efficiently compute the gcd of the two polynomials and therefore recover the padding.

Solving the challenge

Now that we have rr, we can generate a mapping from plaintext characters to their ciphertexts and use this to map the ciphertexts in ct to their plaintext.

from string import printable
from values import ct, N, e

C1 = ct[1]
C2 = ct[0]

b = pow(ord('s'), e, N)

Z = Zmod(N)
P.<x> = PolynomialRing(Z)
def pgcd(g1,g2):
    return g1.monic() if not g2 else pgcd(g2, g1%g2)
g1 = (x + b)^e - C1
g2 = x^e - C2
M2 = -pgcd(g1, g2).coefficients()[0]

r = M2 >> 24
# yes we could just use M2 instead of computing r << 24, but this is easier to understand
mapping = { pow(pow(ord(c), 3, N) + (r << 24), e, N):c for c in printable }
flag = ''
for c in ct[1:]:
    flag += mapping[c]
print(flag)

Flag: shkCTF{L0NG_LIV3_N0ISY_RS4_b86040a760e25740477a498855be3c33}