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

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

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

• Thanks for the answer! Finding $y$ is clear to me now. I have a few questions though. When finding $s^{-1}$, which values are plugged into the EEA as $r_0$ and $r_1$? $757$ and $582$ ($p$ and $s$)? And how do we get the final message from $m = 670 \bmod 757$? Is it $186 \times 85$, and then converting that number to bytes? Commented Oct 24, 2022 at 8:58
• If you're trying to find the inverse of $x$ mod $m$, then you're trying to solve $ax + bm = 1$ so you set $r_0 = m$ and $r_1 = x$ - so in both cases we put $r_0 = p$, and then we put $g$ in the first time and $s$ the second. Technically in this framework $m = 670$ is the message, but in computer terms you'd then read that as binary. Commented Oct 24, 2022 at 22:23
• I see, but $m = 670$ isn't the entire message. The given flag FLAG{PLACEHOLDER_VALUE} converted to long int has a value of $6733198372838931630179430884192353758790689152518407549$, converted with Python's Crypto.Util.number.bytes_to_long() function. I now understand how to find all the variables (thanks!), but not how to get the multiplier for $m$. Indeed, $6733...\equiv 670 \pmod {757}$. My question now is, is there a quick way to get the multiplier to go from $670$ to $6733...$, considering the long number is unknown? Commented Oct 25, 2022 at 10:31
• With the information you've provided, you can only reconstruct $m \mod p$. Typically you would break $m$ up into shorter pieces and encrypt each of them individually. Commented Oct 25, 2022 at 22:50