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

# rsa\_oracle — picoCTF 2024 Solution (Simple Writeup)

## 1. Problem Idea

You are given:

* `password.enc` → RSA encrypted password
* `secret.enc` → AES encrypted file
* RSA oracle at `nc titan.picoctf.net 62026`

The oracle can:

* Encrypt anything (E)
* Decrypt anything (D)

BUT it has a restriction:

> It will NOT decrypt the exact password ciphertext

## 2. Key Concept (Very Important)

This challenge is based on:

> RSA homomorphic property

That means:

\[ (c\_1 \cdot c\_2)^d = m\_1 \cdot m\_2 ]

So multiplication in ciphertext space becomes multiplication in plaintext space after decryption.

## 3. Attack Idea (Blinding Trick)

We “trick” the oracle into decrypting something slightly different.

## Step 1: Encrypt a small number

We choose:

```
2
```

Send to oracle:

```
E → 2
```

Oracle returns:

```
c_a = encrypt(2)
```

## Step 2: Multiply ciphertexts

We already have:

```
c = password.enc
```

Now compute:

```
c' = c * c_a
```

## Step 3: Decrypt modified ciphertext

Send:

```
D → c'
```

Oracle returns:

```
2 * password
```

Because:

* encryption of 2 was multiplied in
* oracle decrypts product due to RSA property

## Step 4: Remove blinding factor

Now divide:

```
password = (2 * password) / 2
```

So you recover original password.

## 4. Why this works

Because RSA is:

* multiplicative
* deterministic (no padding here)
* vulnerable when oracle exists

So:

```
D(c * E(2)) = 2 * m
```

Then:

```
(2 * m) / 2 = m
```

## 5. Final Step — Decrypt secret file

Now use recovered password:

```bash
openssl enc -aes-256-cbc -d -in secret.enc -k <password>
```

This reveals the flag.

## 6. Why oracle restriction fails

The oracle blocks only:

* exact `password.enc`

But we send:

* `password.enc * encrypt(2)`

So it looks different, but still contains same information.

## 7. Key Insight

This is NOT breaking RSA mathematically.

It is:

> abusing RSA’s algebraic structure through an oracle

## 8. Summary Flow

```
password.enc
   ↓
multiply with encrypt(2)
   ↓
send to oracle
   ↓
get 2 × password
   ↓
divide by 2
   ↓
recover password
   ↓
decrypt secret.enc
```

## 9. Final Understanding

This challenge teaches:

* RSA is malleable without padding
* oracles leak information indirectly
* encryption must include padding (OAEP) to be secure


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://alham-rizvi.gitbook.io/alhamrizvi/picoctf-writeups/picoctf/cryptography/rsa_oracle.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.