> 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/cryptography/rsa/15.-lsb-oracle-attack.md).

# LSB Oracle Attack (Least Significant Bit Oracle)

This is an **interactive attack**. You do not get keys or factors. Instead, you get access to an **oracle** that reveals:

```
The least significant bit (LSB) of the decrypted message
```

Formally:

```
Oracle(C) → (M mod 2)
```

Goal:

```
Recover full plaintext M
```

## 2. Problem Setup

RSA:

```
C = M^e mod n
```

You can query the oracle with any ciphertext `C'` and it returns:

```
LSB( M' ) where M' = (C')^d mod n
```

## 3. Core Idea

RSA is multiplicative:

```
(C · k^e) mod n → (M · k) mod n after decryption
```

So if we send:

```
C' = C · (2^e mod n)
```

Then:

```
Decryption gives: 2M mod n
```

## 4. Key Insight

By querying:

```
C · (2^e)^i mod n
```

we get:

```
2^i · M mod n
```

And the oracle tells:

```
Is this value even or odd?
```

## 5. What This Gives

Each query gives **one bit of information** about `M`.

We use this to **narrow the interval** where `M` lies.

## 6. Interval Reduction Idea

Start with:

```
M ∈ [0, n]
```

Each oracle query:

```
splits the range in half
```

## 7. Attack Logic

At step `i`:

```
Multiply ciphertext by (2^e)^i
Query oracle
```

If result is:

```
Even → M is in lower half
Odd  → M is in upper half
```

## 8. Iterative Process

We maintain:

```
low = 0
high = n
```

Each step:

```
mid = (low + high) / 2
```

Then:

```
If oracle says even → high = mid
If oracle says odd  → low = mid
```

## 9. Python Simulation

```python
def lsb_oracle_attack(n, e, C, oracle):
    low = 0
    high = n

    c = C
    multiplier = pow(2, e, n)

    for _ in range(n.bit_length()):
        c = (c * multiplier) % n
        bit = oracle(c)

        mid = (low + high) // 2

        if bit == 0:
            high = mid
        else:
            low = mid

    return low
```

## 10. Oracle Example (Simulation)

```python
def oracle(C):
    M = pow(C, d, n)
    return M % 2
```

## 11. Why This Works

Because:

```
Multiplying by 2 shifts bits
```

And:

```
LSB tells if value crossed n/2 boundary
```

So each query gives:

```
one bit of M
```

## 12. Complexity

```
O(log n) queries
```

Very efficient.

## 13. When to Recognize

Look for:

```
Oracle access
Server returns:
"even" / "odd"
"0" / "1"
```

Or hints like:

```
"LSB"
"parity oracle"
"bit oracle"
```

## 14. Why Thhs Breaks RSA

Because:

```
RSA is malleable (multiplicative)
```

And:

```
Even tiny leakage (1 bit) → full plaintext recovery
```

## 15. Limitations

```
Requires oracle access
Fails if padding (OAEP) is used
Needs many queries
```

## 16. Summary

```
Multiply ciphertext by powers of 2
→ query LSB
→ shrink interval
→ recover M
```

## 17. Practice Scenario

```
n = large
e = 65537
C = given

Oracle returns:
M mod 2
```

## Task

```
Recover M using oracle queries
```


---

# 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/cryptography/rsa/15.-lsb-oracle-attack.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.