Rem, Shinobu, Asuna

#!/usr/bin/env python3
from Crypto.Util.number import *

FLAG = open('flag.txt', 'rb').read()

bits = 512
e = 65537
p = getPrime(bits)
q = getPrime(bits)
n = p*q
phi = (p-1)*(q-1)
d = inverse(e, phi)
hint = 2*d*(p-1337)

m = bytes_to_long(FLAG)
c = pow(m, e, n)

print(f"n = {hex(n)}")
print(f"e = {hex(e)}")
print(f"c = {hex(c)}")
print(f"hint = {hex(hint)}")

Typical RSA challenge and YOU DON'T NEED TO FACTORIZE N every time you see an RSA challenge!

We have,

p≈512 bitsq≈512 bitsn=p∗q≈1024 bitshint+=2∗d∗(p−1337) + where d is the private exponentp \approx 512 \text{ bits} \\ q \approx 512 \text{ bits} \\ n = p*q\approx 1024 \text{ bits}\\ hint^{+} = 2*d*(p-1337) \\~\\ \text{+ where d is the private exponent}

Actually, it's very hard to factor a 1024 bit RSA public modulus but If we have some of the leaked data about private keys or the modulus then we can use some tricks to factor the 1024-bit modulus.

Let's start with Fermat's little theorem which states that,

ap−1≡1(modp)ap−1−1≡0(modp) i.e. (ap−1−1) is an integer multiple of pa^{p-1} \equiv 1 \pmod p \\ a^{p-1}-1 \equiv 0 \pmod p \\~\\ \text{i.e. $(a^{p-1}-1)$ is an integer multiple of $p$}

Let a≡2e(modn)a \equiv 2^{e} \pmod n. Now we can apply this here,

ahint=a2∗d∗(p−1337)(modn)=(2e)2∗d∗(p−1337)(modn)=(22)e∗d∗(p−1337)(modn)=4(p−1337)(modn)=4(p−1)−1336(modn)=4(p−1)∗4−1336(modn)ahint∗41336=4p−1(modn)Therefore,p=GCD(ahint∗41336−1,n)\begin{aligned} a^{hint} &= a^{2*d*(p-1337)} \pmod n\\ &= (2^{e})^{2*d*(p-1337)} \pmod n\\ &= (2^{2})^{e*d*(p-1337)} \pmod n\\ &= 4^{(p-1337)} \pmod n\\ &= 4^{(p-1) - 1336} \pmod n\\ &= 4^{(p-1)}*4^{-1336} \pmod n\\ a^{hint} * 4^{1336} &= 4^{p-1} \pmod n\\ \text{Therefore,}\\ p &= GCD(a^{hint} * 4^{1336} -1, n) \end{aligned}

With this trick, we can get one of the factors of the public modulus (n) and then simply decrypt the ciphertext!

Solve Script: solve.py

Flag: wormcon{RSA_And_Fermat's_Little_Theorem!?}

PreviousFake EncryptionNextExclusive

Last updated