No Padding, No Problem (90)

RSA chosen-ciphertext attack (CCA)


Oracles can be your best friend, they will decrypt anything, except the flag's ciphertext. How will you break it? Connect with nc 30048.


This is a chosen-ciphertext attack (CCA) against RSA. We are able to choose any ciphertext, except the flag's ciphertext, to decrypt.

TL;DR: we can use cโ€ฒ=cโˆ—2ec'=c * 2^e as the ciphertext, then halve the result.


Note that:

  1. cdโ‰กm(modn)c^d \equiv m \pmod n

  2. dd is chosen such that edโ‰ก1(modฯ•(n))ed \equiv 1 \pmod {\phi(n)}, i.e. ed=1+kฯ•(n),kโˆˆN0ed=1 + k\phi(n), k\in \mathbb{N_0}.

The decryption of cโ€ฒc' would yield:

(cโˆ—2e)dmodโ€‰โ€‰nโ‰กcdโˆ—2edmodโ€‰โ€‰nโ‰ก(cdmodโ€‰โ€‰n)(2edmodโ€‰โ€‰n)modโ€‰โ€‰nโ‰กmโˆ—(21+kฯ•(n)modโ€‰โ€‰n)modโ€‰โ€‰nโ‰กmโˆ—2โˆ—(2kฯ•(n)modโ€‰โ€‰n)modโ€‰โ€‰n\begin{align} (c * 2^e)^d \mod n &\equiv c^d * 2^{ed} \mod n \\ &\equiv (c^d \mod n)(2^{ed} \mod n) \mod n \\ &\equiv m * (2^{1+k\phi(n)} \mod n) \mod n \\ &\equiv m * 2 * (2^{k\phi(n)} \mod n) \mod n \\ \end{align}

From Euler's Theorem, if gcd(a,n)=1gcd(a,n)=1 , then

aฯ•(n)โ‰ก1(modn)a^{\phi(n)} \equiv 1\pmod n

Thus, we have

mโˆ—2โˆ—(2kฯ•(n)modโ€‰โ€‰n)modโ€‰โ€‰nโ‰ก2mmodโ€‰โ€‰nm * 2 * (2^{k\phi(n)} \mod n) \mod n \equiv 2m \mod n

At this point, we can halve the result to get mm .


from Crypto.Util.number import *
from pwn import *
from decimal import *
import re

getcontext().prec = 1000

conn = remote('', 30048)
raw_text = conn.recvuntil('Give me ciphertext to decrypt:').decode()


m ="n: ([0-9]+)\ne: ([0-9]+)\nciphertext: ([0-9]+)", raw_text)
n = int(m[1])
e = int(m[2])
c = int(m[3])

to_decrypt = c * pow(2, e, n) % n

conn.send(str(to_decrypt) + '\r\n')

print("Sent:", to_decrypt)

result = conn.recvline().decode()


m ="([0-9]+)", result)
result = int(Decimal(m[1]) / 2)

print('Result:', long_to_bytes(result))


Last updated