1
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Shaliath
    Commented Oct 24, 2022 at 8:58
  • $\begingroup$ 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. $\endgroup$
    – ConMan
    Commented Oct 24, 2022 at 22:23
  • $\begingroup$ 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? $\endgroup$
    – Shaliath
    Commented Oct 25, 2022 at 10:31
  • $\begingroup$ 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. $\endgroup$
    – ConMan
    Commented Oct 25, 2022 at 22:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .