> For the complete documentation index, see [llms.txt](https://simon-6.gitbook.io/simoncyber/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://simon-6.gitbook.io/simoncyber/ctf-writeups/picoctf-2024/cryptography/rsa_oracle-medium.md).

# rsa\_oracle (medium)

<figure><img src="/files/4aUH5GjDuKFT0CI3q9DP" alt=""><figcaption></figcaption></figure>

***

One of the hints states that this CTF focuses on a Chosen Ciphertext Attack.

### Chosen Ciphertext Attacks on RSA

{% embed url="<https://www.geeksforgeeks.org/computer-networks/chosen-ciphertext-attacks-on-rsa/>" %}

A Chosen Ciphertext attack is when a hacker decrypts known ciphertexts in a way to figure out the encryption of a target message (ciphertext). &#x20;

{% hint style="info" %}
There's a lot more attacks than just this. "According to RSA, cryptanalytic attacks are categorized based on the information available to the cryptanalyst. These include ciphertext-only attacks, known-plaintext attacks, and chosen-plaintext attacks. Chosen-plaintext attacks are particularly relevant to public-key cryptography, where encryption keys are public."
{% endhint %}

Specifically, there's a property called "homomorphism". Essentially, if you multiply two ciphertexts together, you get the encryption of the product of their plaintext.&#x20;

In RSA:

* Encrypting message m gives you: c = m^e mod N
* Encrypting message m₁ gives you: c₁ = m₁^e mod N
* Encrypting message m₂ gives you: c₂ = m₂^e mod N

Now if you multiply them:

* c₁ · c₂ = (m₁^e) · (m₂^e) = (m₁ · m₂)^e mod N

Now let's call C1 and C2 as C3. If you now decrypt C3, you get the product of C1 and C2 as plaintext. For example, if C1 was 3 and C2 was 5, we would've gotten 15.&#x20;

***

To solve it, I'll need to write a python script. However, since I can't really write code I'll just be using a write-up to hopefully explain.

```python
from pwn import *

context.log_level='critical'
p = remote("titan.picoctf.net", 61923)

p.recvuntil(b"decrypt.")

with open("password.enc") as file:
    c = int(file.read())

p.sendline(b"E")
p.recvuntil(b"keysize): ")
p.sendline(b"\x02")
p.recvuntil(b"mod n) ")

c_a = int(p.recvline())

p.sendline(b"D")
p.recvuntil(b"decrypt: ")
p.sendline(str(c_a*c).encode())
p.recvuntil(b"mod n): ")

password = int(p.recvline(), 16) // 2
password = password.to_bytes(len(str(password))-7, "big").decode("utf-8")

print("Password:", password)
```

Let's take this script line by line.&#x20;

```python
from pwn import *
context.log_level='critical'
p = remote("titan.picoctf.net", 61923)
```

This is the default way to import the pwntools library. The "context.log\_level" sets it to a specific level, such as critical, info, warn, or debug. We set it to critical so we can bypass the notifications. Then we call a tube object as p. We then send and receive variables to p.

```
p.recvuntil(b"decrypt.")
```

"recvuntil" is a process from the pwnlib specifically for tubes like p. The command says to read data until we see a specific text. Here, it would read until it sees the bytes of the word "decrypt". (b is for bytes).

{% hint style="info" %}
The reason why we need "b" is because we're connecting to a remote connection.&#x20;
{% endhint %}

```
with open("password.enc") as file:
    c = int(file.read())
```

Opens the file, and stored it into the variable called c.&#x20;

```
p.sendline(b"E")
p.recvuntil(b"keysize): ")
p.sendline(b"\x02")
p.recvuntil(b"mod n) ")
```

It sends the line since we put recvuntill decrypt. We choose the encrypt option. Then we read the keysize (which is the server prompt put out). Then we send the byte of the number 2. It reads untill mod n.

```
c_a = int(p.recvline())
```

This stores the ciphertext number.

```
p.sendline(b"D")
p.recvuntil(b"decrypt: ")
p.sendline(str(c_a*c).encode())
p.recvuntil(b"mod n): ")
```

This repeats the process, except we're decrypting. However, we're decrypting the string of (c\_a\*c). What does this mean? So we know that c\_a is the ciphertext of 2 we passed in the algorithm, and c as the password. This is the root of the problem!&#x20;

{% hint style="info" %}
in ""p.sendline(str(c\_a\*c).encode())", we need the str() and encode() function. Since we are mutiplying integers and the server a string/byte, we then convert it to a string. Then we use the encode() to convert each character into its byte. We CAN NOT use b since b doesn't work on calculated values or variables, only on literal text.&#x20;
{% endhint %}

```
password = int(p.recvline(), 16) // 2
password = password.to_bytes(len(str(password))-7, "big").decode("utf-8")

print("Password:", password)
```

This takes the new cipher text and stores it in to password. It converts to decimal first using base 16 (since decimal is base 10) and divides it by 2. It then converts it to bytes to process it as text. However, to convert to bytes, we need a byte length for the "to\_bytes". We could either do -7 or +7 ("(bit\_length + 7) // 8") is more accepted. It then decodes it to text.

<figure><img src="/files/czLbaRHguaun8ayyhieu" alt=""><figcaption></figcaption></figure>

After running the python script, we get our flag.&#x20;