# magic dlog

A server asks you to input a modulus $p$ (here required to be prime, but relaxed to any number in magic rsa), an exponent $e$, and then a number $x$ such that $x_{e}=sha384(x)(modp)$.

So the obvious approach is to make $p−1$ smooth such that we can construct $e$ after fixing $x$ (and consequently $sha384(x)$).

There’s one more caveat, in that the upper bits of $p$ has to match some given
(random) ~136-bit pattern $m$. I’m not sure of any direct construction of smooth
numbers on a form like $2_{248}m+k$, but since $m$ is “small” we can hope
that it itself^{1} is smooth-ish and just multiply it with smooth numbers that is
“almost” $2_{248}$. I chose to find the acceptably smooth numbers on the form
$2_{k}−1$ (which was easy as these “Mersenne numbers” tend to be rich in
divisors, especially for composite exponents) and then just pick numbers from
this list with exponents that summed to 248. The $m$-factor will need to be
adjusted upward to make the upper bits match. In the end we have a lot of
candidates $p=1+(m+ϵ)(2_{k_{0}}−1)(2_{k_{1}}−1)⋯$ and once
we find such a prime we’re all set.

Pick some primitive root $x$, compute $sha384(x)$ and do a discrete log using all the factors of $p−1$.

A pretty good Euler hack problem overall, I thought.

Or really the adjusted $m+ϵ$ that we’ll end up actually using.↩