weird modulus

Platform: spbctf | Category: Crypto | Type: Challenge | Difficulty: Easy | OS: NA | Author: XESXOR | Date: 2026-03-09 | Status: Solved Techniques: fermat_factorization

Summary

Task: RSA challenge with a weird modulus n where p and q are extremely close. Solution: Fermat factorization works instantly when |p - q| is small.

weird modulus — CryptoKids 2.0

Description

RSA challenge with a "weird" modulus n. Standard RSA parameters are given: n, e, c.

Analysis

Upon analyzing the modulus n, it was found that the prime factors p and q are extremely close to each other. This is a classic RSA vulnerability — when |p - q| is small, Fermat factorization works almost instantly.

Key parameters:

• e = 31337
• n factors in 0 iterations using Fermat's method

Solution

Fermat's factorization method is based on representing n = a² - b², where a = (p+q)/2, b = (p-q)/2. If p and q are close, then b is small, and a ≈ √n. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

 python read-only • copy allowed Copy
#!/usr/bin/env python3
from gmpy2 import isqrt, is_square

def fermat_factor(n):
    """Fermat factorization for close p and q"""
    a = isqrt(n)
    if a * a < n:
        a += 1
    
    iterations = 0
    while True:
        b2 = a * a - n
        if is_square(b2):
            b = isqrt(b2)
            p = a + b
            q = a - b
            print(f"Factored in {iterations} iterations")
            return int(p), int(q)
        a += 1
        iterations += 1

# Challenge parameters
n = ...  # modulus from the challenge
e = 31337
c = ...  # ciphertext from the challenge
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Factorization
p, q = fermat_factor(n)
print(f"p = {p}")
print(f"q = {q}")

# Standard RSA decryption
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)

# Decode the flag
flag = bytes.fromhex(hex(m)[2:]).decode()
print(f"Flag: {flag}")

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍