FastRsa

Author: 0xIDA
Platform: FlagYard · Category: crypto · Difficulty: Easy

Solvers

• solve.py

Summary

Interactive RSA challenge: 14 timed rounds print n, m^3 mod n, and (m+1)^3 mod n. Recover m each round with Franklin-Reiter (related messages, e=3, difference 1). After all rounds the server prints the flag.

Solution

Step 1: Analyze chall.py

Server generates RSA modulus from two primes near 2^b, encrypts random m with e=3, and also encrypts m+1. Five-second timeout per answer.

Step 2: Franklin-Reiter for m and m+1

Polynomial GCD of x^3 - c1 and (x+1)^3 - c2 over Z/nZ yields linear factor x - m.

#!/usr/bin/env python3
from pwn import *

def egcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = egcd(b, a % b)
    return g, y, x - (a // b) * y

def modinv(a, n):
    g, x, y = egcd(a % n, n)
    if g != 1:
        raise ValueError("no inv")
    return x % n

def franklin_reiter_m_m1(n, c1, c2):
    A, B = 3 % n, 3 % n
    C = (1 - c2 + c1) % n
    invA = modinv(A, n)
    b = (B * invA) % n
    c = (C * invA) % n
    p = (b * b - c) % n
    q = (b * c - c1) % n
    return (-q * modinv(p, n)) % n

r = remote("tcp.flagyard.com", PORT)  # from start_instance
for i in range(1, 15):
    n = int(r.recvline())
    c1 = int(r.recvline())
    c2 = int(r.recvline())
    m = franklin_reiter_m_m1(n, c1, c2)
    r.recvuntil(b"Enter Number : ")
    r.sendline(str(m).encode())
    r.recvuntil(b"============================\n")
    r.recvuntil(b"============================\n")
print(r.recvall(timeout=5))

Instance address obtained via Flagyard MCP start_instance → tcp.flagyard.com:<port>.

Flag

FlagY{559bf2a4d502fad715f6949b6aca6f96}

Live submitted: success (2026-07-12).

Tools

• Flagyard MCP (start_instance, submit_flag)
• pwntools remote
• Franklin-Reiter pure Python