How to find unknown (pseudo-random) number in crypto algorithm equation, similar to RSA

Question

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)$

Answer 1

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):

index $i$	quotient $q_{i-1}$	remainder $r_i$	$s_i$	$t_i$
0		757	1	0
1		623	0	1
2	1	134	1	-1
3	4	87	-4	5
4	1	47	5	-6
5	1	40	-9	11
6	1	7	14	-17
7	5	5	-79	96
8	1	2	93	-113
9	2	1	-265	322
10	2	0	623	-757

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$.