RSA Chosen Ciphertext Attack

# Description

Oracle: a person or thing regarded as an infallible authority on something.
Do we have one of those here?
nc 20.198.209.142 55002
The flag is in the flag format: STC{...}
Author: zeyu2001

# Solution

We are given an RSA decryption oracle. We can supply any ciphertext to be decrypted, except the original, given ciphertext.
Textbook RSA is vulnerable to Chosen Ciphertext Attack (CCA), where a user is able to supply an arbitrary ciphertext to be decrypted.
Recall that
$ed\equiv1\pmod{(p-1)(q-1)}$
Therefore, suppose we supply a ciphertext
$c'=r^ec\pmod{n}$
then decrypting this gives
$m'=r^{ed}c^d\pmod{n}\newline m'=rm\pmod{n}$
Let
$r=2$
. The solve script is as follows:
1
from Crypto.Util.number import long_to_bytes
2
from pwn import *
3
from decimal import *
4
import re
5
β
6
getcontext().prec = 100000000
7
β
8
pattern = "n = (\d+)\ne = (\d+)\nc = (\d+)"
9
β
10
conn = remote('localhost', '12345')
11
12
β
13
matches = re.search(pattern, received)
14
n, e, c = int(matches[1]), int(matches[2]), int(matches[3])
15
β
16
print('n =', n)
17
print('e =', e)
18
print('c =', c)
19
print()
20
β
21
ciphertext = Decimal(c) * ((2 ** Decimal(e)) % Decimal(n)) % Decimal(n)
22
print('Ciphertext:', ciphertext)
23
β
24
conn.send(str(ciphertext) + '\r\n')
25
β
26
27
matches = re.search("Decrypted: (\d+)\n", received)
28
β
29
decrypted = int(matches[1])
30
print()
31
β
32
print(long_to_bytes(Decimal(decrypted) / 2))
Copied!
The flag is STC{ch0s3n_c1ph3rt3xt_d7b593cd54baba9e2ffa49215d33e4c657cf230a}.