N1CTF 2019: BabyRSA

The CTF problem “BabyRSA” provides an encryped flag and the encryption code. We do some group computations and realize that the plaintext space is as small as it gets.

Problem

N1CTF problem from September 2019.

The plaintext space in TokyoWesterns CTF real-baby-rsa challenge is too small, so I decide to add some random padding to the plaintext to prevent bruteforce attack.

Hope this padding can prevent the hackers. XD

The encryption code was provided, along with the ciphertext.

#!/usr/bin/env python2
# -*- coding: utf-8 -*-
from Crypto.Util import number
import random
from secret import flag
N = 23981306327188221819291352455300124608114670714977979223022816906368788909398653961976023086718129607035805397846230124785550919468973090809881210560931396002918119995710297723411794214888622784232065592366390586879306041418300835178522354945438521139847806375923379136235993890801176301812907708937658277646761892297209069757559519399120988948212988924583632878840216559421398253025960456164998680766732013248599742397199862820924441357624187811402515396393385081892966284318521068948266144251848088067639941653475035145362236917008153460707675427945577597137822575880268720238301307972813226576071488632898694390629
e = 0x10001
m = number.bytes_to_long(flag)
with open('flag.enc', 'w') as f:
    while m:
        padding = random.randint(0, 2**1000) ** 2
        message = padding << 1 + m % 2
        cipher = pow(message, e, N)
        f.write(hex(cipher)+'\n')
        m /= 2

Analysis

Here’s how the encryption is being performed:

# for each bit m of the message
padding = random.randint(0, 2**1000) ** 2   # generate quadratic residue in Z*N
message = padding << 1 + m % 2              # multiply by 2 if the message bit is 0
cipher = pow(message, e, N)                 # encrypt message using RSA
f.write(hex(cipher)+'\n')                   # write chunk of ciphertext

The ciphertext is a list $c[i]$ of elements corresponding to the message bits.

# q := a random quadratic residue in Z*N
# m[i] := the ith bit of the plaintext
if m[i] == 1:
    c[i] = q^e
if m[i] == 0:
    c[i] = (2*q)^e

So, decrypting the ciphertext can be reduced to distinguishing between $q^e$ and $(2q)^e$.

Since $q$ is a quadratic residue, it has Jacobi symbol $(\frac{q}{N}) = 1$.

And, the Jacobi symbol $(\frac{2}{N}) = -1$ in this case.

> from sympy.ntheory import jacobi_symbol
> jacobi_symbol(2, N)
-1

It follows that $q^e$ and $(2q)^e$ have Jacobi symbols $1$ and $-1$, respectively, which leaks the plaintext.

Code

from Crypto.Util import number
from sympy.ntheory import jacobi_symbol

N = # 239813...

raw = open('flag.enc', 'r').read()
ciphertext = [int(c, 0) for c in raw.split('\n')[:-1]]
jacobi_symbols = [jacobi_symbol(c, N) for c in ciphertext]

m = 0
for js in reversed(jacobi_symbols): # reverse to correct bit ordering
    m <<= 1
    if js == 1: m |= 1

plaintext = number.long_to_bytes(m)
print plaintext

We try this on the encrypted flag and we’re done.

N1CTF{You_can_leak_the_jacobi_symbol_from_RSA}

Resources

Download source for the encryption/decryption.