# Crypto - RustSA

## Description

<figure><img src="/files/6PuXeufEKN2CLQzocI0k" alt=""><figcaption></figcaption></figure>

## Downloads

{% file src="/files/fSWkFgNt2LOwnasnzUsj" %}

## Solution

In this challenge we're given a Rust implementation of RSA.

```rust
use std::io;
use std::convert::TryInto;

const PUBLIC_EXP: u128 = 65537;

// computes x^y mod n
fn mod_exp(x: u128, y: u128) -> u128 {
    let mut bit_length:u128 = 0;
    let mut y0:u128 = y;
    while y0 > 0 {
        y0 >>= 1;
        bit_length += 1;
    }
    let mut result:u128 = 1;
    for i in (0..bit_length).rev() {
        result = result * result;
        if (y >> i) & 1 == 1 {
            result = result * x;
        }
    }
    return result;
}

fn main() {
    let stdin = io::stdin();
    let plaintext = &mut String::new();
    println!("RustSA encryption service! Type your message below (exactly 16 characters):");
    let _ = stdin.read_line(plaintext);
    let plaintext_bytes_untrimmed = plaintext.as_bytes();
    let plaintext_bytes = &plaintext_bytes_untrimmed[0..plaintext_bytes_untrimmed.len()-1];
    if plaintext_bytes.len() != 16 {
        println!("Message not 16 characters.");
        return;
    }
    let plaintext_int = u128::from_be_bytes(plaintext_bytes.try_into().expect("Conversion Error"));
    let result = mod_exp(plaintext_int, PUBLIC_EXP);
    println!("Your ciphertext is below:");
    println!("{}", result);
}
```

If you throw the code into any LLM, you'll immediately know that there is a flaw in the implementation of the **mod\_exp** function. It only does **x^y** and does not do the modulo part.

If we take a look at the given ciphertext:

```
RustSA encryption service! Type your message below (exactly 16 characters):
Your ciphertext is below:
187943791592623141370643984438525124469
```

I thought it was unusual. With **x^65537**, there is no way the resulting ciphertext is so small. If we take a closer look at the given **mod\_exp** implementation again, we'll notice that the result is of u128 type (and actually the challenge text already hinted towards that.)

The next step is to figure out how Rust handles the overflow and apparently, it is via a simple wrapping arithmetic. From Deepseek:

<figure><img src="/files/5ilGgkS24CC3H5j64xYz" alt=""><figcaption><p>Deepseek</p></figcaption></figure>

Final solve script:

```python
import gmpy2

def reverse_mod_exp_2pow128(result, y):
    # Compute phi(2^128) = 2^127
    phi = gmpy2.mpz(1) << 127
    
    # Check if y is invertible mod phi (must be odd)
    if y % 2 == 0:
        raise ValueError("y must be odd for a unique solution")
    
    # Compute d = y^{-1} mod phi
    d = gmpy2.invert(y, phi)
    
    # Compute x = result^d mod 2^128
    x = gmpy2.powmod(result, d, gmpy2.mpz(1) << 128)
    return x

# Example: Find x such that x^3 ≡ 12345 mod 2^128
result = 187943791592623141370643984438525124469
y = 65537
x = reverse_mod_exp_2pow128(result, y)

plaintext_bytes = int(x).to_bytes(16, byteorder='big')
print("Recovered plaintext:", plaintext_bytes.decode('utf-8'))    # eUl3r5_70713n7_u
```


---

# 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://arne-ctf.gitbook.io/ctf/2025/san-diego-ctf/crypto-rustsa.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.