I am trying to solve a past CTF (Capture the Flag) event crypto question. The algorithm is similar to RSA: it generates a public and private key, then encrypts the flag with the public key. It looks similar to RSA, except the encryption is done with a pseudo-random, huge e, the public key has 3 values, and the private key one value. Unfortunately the exercise doesn't have a writeup, so I can't see how others solved it.
The key generation is done with a prime number, up to $2^{1024}$, called $p$. 2 pseudo-random numbers are picked, $g$ and $x$, used to generate $h = g^x \bmod p$. $(p, g, h)$ are the public key, and $x$ is the private key.
To encrypt a message $m$, another pseudo-random number $y$ is picked, used to calculate $s = h ^ y \bmod p$. The result of the encryption are 2 numbers, $c1$ and $c2$: $c1 = g \times y \bmod p$ and $c2 = m \times s \bmod p$.
All the pseudo-random numbers values are between $2$ and $2^{1024} – 2$.
For the exercise, the values of $(p, g, h)$ (the public key) are given, along with the values of $c1$ and $c2$.
To solve it, I figure the value of $y$ has to be found. If it was such that $g \times y \bmod p = 1$, it would be easy to find, but it's not. I have tested a brute forcing algorithm and it works fine with values up to $2^{10}$, as I am able to find the flag. With the real values brute forcing $y$ would take forever, as it can go up to $2^{1024} – 2$, so I assume there must be a mathematical relation between them that makes the algorithm weak, but I can't seem to find it.
Edit: in case it might make the question clearer, here are some test values, for a flag of FLAG{PLACEHOLDER_VALUE}
$p = 757$
$g = 623$
$h = 414$
$(c1, c2) = (306, 85)$
Best Answer
The whole thing hinges on being able to efficiently calculate multiplicative inverses modulo $p$, which we can do via the Extended Euclidean algorithm.
We first find $g^{-1}$, which gives us $c_1 \times g^{-1} = y$. From that we can calculate $s = h^y$, and then by finding $s^{-1}$ we take $c_2 \times s^{-1} = m$ to retrieve the message, all without ever knowing what $x$ was.
Using the example values, it looks something like this (following the notation from the Wikipedia article):
So $322 \times 623 - 265 \times 757 = 1$, and hence $623^{-1} \equiv 322 \mod 757$. Then $y \equiv g^{-1} c_1 = 322 \times 306 \equiv 122 \mod 757$, and with a bit of careful manipulation I think we get $s \equiv 414^{122} \equiv 582 \mod 757$, then repeating the EEA gives $s^{-1} = 186$, finally leading to $m \equiv 186 \times 85 \equiv 670 \mod 757$.