In this challenge we're given a Rust implementation of RSA.
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:
Final solve script:
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
