Rocket Ship Academy
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≑1(mod(pβˆ’1)(qβˆ’1))ed\equiv1\pmod{(p-1)(q-1)}
Therefore, suppose we supply a ciphertext
cβ€²=rec(modn)c'=r^ec\pmod{n}
then decrypting this gives
mβ€²=redcd(modn)mβ€²=rm(modn)m'=r^{ed}c^d\pmod{n}\newline m'=rm\pmod{n}
Let
r=2r=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
received = conn.recv().decode()
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
received = conn.recv().decode()
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}.
Last modified 5mo ago
Copy link