# Mini RSA

## Problem

> What happens if you have a small exponent? There is a twist though, we padded the plaintext so that (M \*\* e) is just barely larger than N. Let's decrypt this: ciphertext

* [ciphertext](https://github.com/HHousen/PicoCTF-2021/blob/master/Cryptography/Mini%20RSA/ciphertext/README.md)

## Solution

1. I spent a while (2 hours) searching for resources to solve this. However, [this Cryptography StackExchange comment](https://crypto.stackexchange.com/a/6771) is where I found the solution. Other helpful resources include: [RSA Padding Schemes - Wikipedia](https://en.wikipedia.org/wiki/RSA_\(cryptosystem\)#Padding_schemes), [Cryptography StackExchange 1](https://crypto.stackexchange.com/a/64304), [Cryptography StackExchange 2](https://crypto.stackexchange.com/a/80346), and [Cryptography StackExchange 3](https://crypto.stackexchange.com/a/111)
2. Without padding, encryption of `m` is `m^e mod n`: the message `m` is interpreted as an integer, then raised to exponent `e`, and the result is reduced modulo `n`. If `e = 3` and `m` is short, then `m^3` could be an integer which is smaller than `n`, in which case the modulo operation is a no-operation. In that case, you can just compute the cube root of the value you have. However, we cannot simply compute `c^(1/3)` (where `c` is the ciphertext) because there is a slight amount of padding to the message to make `m^e` larger than `n`, which makes the modulo operation take effect.
3. With a short `m` slightly wider than `n^(1/e)`, which is what we have, we are given `c = m^e mod n` and can find by enumeration `k` such that `k * n + c` is an `e`th power: then `m = (k * n + c)^(1/e)`.
4. We can use python and write a [solution script](https://github.com/HHousen/PicoCTF-2021/blob/master/Cryptography/Mini%20RSA/script.py) to search though thousnads of values for `k` until we find one that contains the start of the flag. When we find the padding amount, we can increase the precision and rerun the calculation to get the entire flag. Keeping the precision high enough just to see the beginning of the flag speeds up the enumeration of `k`.

### Flag

`picoCTF{e_sh0u1d_b3_lArg3r_a166c1e3}`


---

# Agent Instructions: 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:

```
GET https://picoctf2021.haydenhousen.com/cryptography/mini-rsa.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
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.