# CTF-writeups

Some CTF writeups

Project maintained by Qyn-CTF

## First looks

We’re given $$dp = d \bmod p-1$$, $$d$$ and $$e = 65537$$. We’re also given the ciphertext. Our goal is to recover the modulus $$N = p \times q$$

## Solving

We know that $$d \times e = 1 \bmod \varphi(N)$$. Which means that $$d \times e - 1 = \it{n} \times \varphi(N)$$ for any $$\it{n} \in \mathbb{N}$$ and since $$\it{n} < \varphi(N)$$ is $$\it{n} < e = 65537$$. This allows us to bruteforce $$\varphi(N)$$.
We also know that $$dp - d = \it{k} \times (p-1)$$, and since $$\varphi(N) = (p-1) \times (q-1)$$ they both contain a factor of $$p-1$$. So we can set $$nP = GCD(dp - d, \varphi(N))$$. Now, since $$nP$$ is a factor of $$p - 1$$, we can simply try out simple factors $$< 100$$.
When the result ($$nP + 1$$) is prime and bit length of 1024, it’s probably our value of $$p - 1$$, however, we can verify this by using Euler’s theorm: $$n^{\varphi(N)} = 1 \bmod N$$ for any $$\it{n} \in \mathbb{N}$$, and $$N$$ is a multiple of $$p$$ the following holds true: $$n^{\varphi(N)} = 1 \bmod (nP + 1)$$. So $$nP == GCD(n^{\varphi(N)} - 1, nP)$$.

We can then do the same for $$q$$ and retrieve $$N$$

#### Side node

It’s also possible to use Euler’s theorm to retrieve $$p$$ by: $$p = GCD(n^{\varphi(N)} - 1, nP)$$ and checking whether $$p$$ is not $$1$$ and is prime

### Code

from Crypto.Util.number import inverse, long_to_bytes, isPrime
import math

e = 65537
d = 0xbdf70cdd2e1a1044beb1d4d01cb7053cc1178b27d3d2eba2639894a396e1fe2e35a34e869b4dd1d474346c80bfe290d588673322c32eb3f7e722761f2cb6f0d98085efe0c9f39f430dc11cff01df514826b4de2026ab589238a90f4e3e63ec34b0e67a53eafb383bb3cac9a4ca27ac2049ce02de431142a88fb1a981a7b109141a77ef7ec8223b2228c1cebc667259fda28fa37ad7741536102ceb79d49fd55165af732395de55953826bc3e46f96886aad59ee8530d01692706c07f5cab6edac031cfee7f5adeca38b7b658232148e04e56494cbd3db4cda24c553e7fbc5087f3919994919847ccf28e352f09685ebfb6ada898d60295b674abf909d8944001
dp = 0x5bbcca611e9d82ad17fe3430571a2e571f5fbffe8491ed3b4ac6f056cf86746da7770bbba469b4e648a2b4c03645c9d21c3fc9d1fe52aebacb0cc97b2ae7bf4287dd3ed3219f081725fc34595b7d8bdccb4a2baff5461b42329f4e07ea132a24e9f52e3161813f93098164f56f2af3dc3099a0e779f12d74dbe61abe04827001
c = 0xae5ff79b741ed77e531c1a8ef87084abda154321685c46e5b00ed351c5ebfa4c3adac5e6b4adbb009a57bee28e3fcfd6df24fb6c5aad77073b836d2f6d3042f81bb3381466763dd2a0459c2096718bcdba3000823aa1cc807c71e56f43a5e62a70066ab7dafca015ee8b62aa21aa6353cb18bb4d26317a0f623ab5b01de50da1146f920b69434c0b62c1878e4b312d298afa70ebc5b52170abd06d8aadbd5abc0686ef84f234617ae7f3e3de428ce6c53c553be235a49e42ce80b7ae0ba051c00f8cd9d15c5c84f1eae18f129832409fa52fb9227d7a48184ec9fcfb20805878e0f233390604415df34306ee4c47f8486501a1b741b310bff98c41e9c9dbad30

kphiN = e * d - 1
nDP = d - dp

checkRange = 100
for k in range(3, e + 1):
if kphiN % k == 0:
phiN = kphiN // k
p = math.gcd(phiN, nDP)
nP = p
n = 2
while not isPrime(nP + 1) and n < checkRange:
nP = p // n
n += 1

p = nP + 1
if p.bit_length() == 1024 and isPrime(p) and p == math.gcd(p, pow(5, phiN, p) - 1):
print(p)
print("Found p")
break

for k in range(3, 65537 + 1):
if kphiN % k == 0:
phiN = kphiN // k
if phiN % (p - 1) != 0:
continue
q = (phiN // (p - 1))
nQ = q
n = 2
#while not isPrime(q) and q != 1:
#    q = math.gcd(q, pow(n, phiN, q) - 1)
#    n += 1
while not isPrime(nQ + 1) and n < checkRange:
nQ = q // n
n += 1

q = nQ + 1
if q.bit_length() == 1024 and isPrime(q) and q == math.gcd(q, pow(5, phiN, q) - 1):
print(q)
print("Found q")
break

assert q != 1 or p != -1, "Was unable to recover p and/or q"

N = p * q
m = pow(c, d, N)
print(long_to_bytes(m).decode())


Which prints the flag: HackTM{0ac4d80522000109a3e010feee5dc627ee37413754489996dde528724ea2189dabfb722f2877d8a3f8f3c8f994fee230c24fb54a77dafbedfc30b7ccdb0b9851}

Home