# d-phi-enc

**Author**. EggRoll (idek)

## Overview

from Crypto.Util.number import bytes_to_long, getStrongPrime

from secret import flag

assert len(flag) == 255
e = 3
p = getStrongPrime(1024, e=e)
q = getStrongPrime(1024, e=e)
n = p * q
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
enc_d = pow(d, e, n)
enc_phi = pow(phi, e, n)
enc_flag = pow(bytes_to_long(flag), e, n)
print(f"{n = }")
print(f"{enc_d = }")
print(f"{enc_phi = }")
print(f"{enc_flag = }")

So basically, we are given a standard RSA with the following additional hints:
1. $d^e \pmod{n}$
2. $\phi(n)^e \pmod{n}$

## Exploit

First of all, there is a relationship between $d$ and $\phi(n)$. Precisely, we have $$ed \equiv 1 \pmod{\phi(n)}$$ Or equivalent, $$ed = 1 + k\phi(n)$$ for some $k$. Once $k$ is known, related message attack can be applied and we will find the value of $d$, which is enough to retrieve the flag.

Now, notice that in the code, there is a weird parameter setting, say $e=3$. Therefore, only few possible values for $k$. We could simply try all possibilities.

from output import *

def gcd(f1, f2):

	if f1 % f2 == 0:
		return f2
	else:
		return gcd(f2, f1 % f2)

P.<x> = PolynomialRing(Zmod(n))

k = 2
f = x^3 - enc_d
g = (inverse_mod(k, n) * (3*x-1))^3 - enc_phi
d = n - int(gcd(f, g).monic().list()[0])

from Crypto.Util.number import long_to_bytes
print(long_to_bytes(int(pow(enc_flag, d, n))))

:::success
HackTM{Have you warmed up? If not, I suggest you consider the case where e=65537, although I don't know if it's solvable. Why did I say that? Because I have to make this flag much longer to avoid solving it just by calculating the cubic root of enc_flag.}
:::