The creators of a certain system have taken care of the security of storing users data and encrypted users passwords. To register a new user the administrator should enter encrypted password into the database. You were able to get a users passwords database and a script, that administrator used for passwords encryption. The answer for this task is the password the encrypted version of which: hnd/goJ/e4h1foWDhYOFiIZ+f3l1e4R5iI+Gin+FhA==

When we look at the main function, we see that the script starts with randomly assigning two numbers from unknown lists to the variables p and q. However, even though it uses some random numbers, the encrypted output must always be the same for a specific plaintext. Therefore, we don’t need to worry about random variables. Let’s find where the real encryption takes place.

Here, the script iterates over the bytes of the input. It does some operations on each byte, then finally encode the byte array with base64 and print it. The thing is it calculates each byte independently which allows us to brute force the plaintext’s bytes. We also know the paintext only contains printable characters, so we don’t even need to try all 256 ascii characters. Let’s modify this loop such that it brute forces the given encrypted text.

First, we base64 decode the text. Then, for each byte of the decoded text, we try to find a printable character such that if we apply the same operations with the encryption loop, the result is the decoded byte.

We have just one problem. The encryption code is itself really slow, as a result our decryption code will be slow as well. It takes too much time to calculate the variables. Let’s try to modify it such that it becomes faster and still gives the same output.

If we look carefully, we notice that dwfregrgre function returns a list which contains prime numbers in range [x, z]. In the main function, script starts with randomly assigning a prime number in range [100, 1000] to p, then it randomly assigns a prime number in range [200, 1000] to q. It really doesn’t matter which prime is assigned, it just need to be within the range. In order to make our decryption script execute faster, I assigned 101 to p and assigned 211 to q.

Here is the whole decryption script.

Let’s execute the script.

Our flag is KLCTF{paillier_homomorphic_encryption}.