> 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/13.-known-prefix-attack.md).

# Known Prefix Attack (Structured Message Attack)

This attack applies when part of the plaintext is **known and fixed**, and only a **small unknown portion** remains.

```
M = known_prefix || unknown_suffix
```

Example:

```
M = "flag{" + x
```

Encryption:

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

Goal:

```
Recover unknown part x
```

## 2. Core Idea

We rewrite the message as a number:

```
M = A + x
```

Where:

```
A = known prefix (converted to integer and shifted)
x = unknown part (small)
```

Then:

```
C = (A + x)^e mod n
```

## 3. Key Insight

```
x is small
```

So we solve:

```
(A + x)^e ≡ C mod n
```

This becomes a **small root problem**, solvable using:

```
Coppersmith method
```

## 4. Mathematical Form

Define:

```
f(x) = (A + x)^e − C mod n
```

We want:

```
f(x) ≡ 0 mod n
```

with:

```
x small
```

## 5. When It Works

```
Small unknown part (few bytes)
Small exponent (e = 3 or 5)
Large known prefix
No padding
```

## 6. Attack Strategy

1. Convert prefix to integer:

```
A = prefix << (unknown_bits)
```

2. Define polynomial:

```
f(x) = (A + x)^e − C
```

3. Solve:

```
Find small root x
```

4. Recover:

```
M = A + x
```

## 7. SageMath Implementation

```python
# SageMath required

n = ...
e = 3
C = ...

prefix = b"flag{"
unknown_bits = 32  # size of unknown part

A = int.from_bytes(prefix, 'big') << unknown_bits

PR.<x> = PolynomialRing(Zmod(n))
f = (A + x)^e - C

roots = f.small_roots(X=2^unknown_bits, beta=0.4)

if roots:
    x_val = roots[0]
    M = A + x_val
    print("Recovered M:", M)
```

## 8. Explanation of Parameters

```
X = search bound for x
beta = controls success (0.3–0.5 typical)
```

## 9. Example (Concept)

```
prefix = "flag{"
x = "abc"
```

```
M = "flag{abc}"
```

Convert to integer:

```
M = A + x
```

Then solve for `x`.

## 10. When to Recognize

Look for:

```
Known format (flag, message header)
"flag{...}"
"msg=HELLO_????"
"prefix is known"
```

## 11. Why This Breaks RSA

Because:

```
RSA is deterministic
Structure is preserved
Small unknown → recoverable
```

## 12. Limitations

```
Fails if unknown part is large
Fails with proper padding (OAEP)
Requires lattice methods
```

## 13. Pure Python Option (Bruteforce)

If unknown is very small:

```python
n = ...
e = 3
C = ...

prefix = b"flag{"
A = int.from_bytes(prefix, 'big') << 16  # small unknown

for x in range(2**16):
    M = A + x
    if pow(M, e, n) == C:
        print("Found:", M)
        break
```

## 14. Summary

```
Known prefix + small unknown
→ M = A + x
→ build polynomial
→ solve small root
→ recover message
```

## 15. Practice Problem

```
n = 3233
e = 3

Message starts with "hi"
Unknown part is 2 bytes

C = 855
```

## Task

```
Recover full message
```

Next options:

```
Boneh–Durfee attack
generalized Hastad
LSB oracle attack
padding oracle (Bleichenbacher)
```

Pick next.


---

# 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/13.-known-prefix-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.