I recommend you to read my Original writeup intead of this one, as it is much more detailed and it is possible to visualize mathematical expressions much better. The following writeup has been summarized in order to avoid the use of mathematical formulas and python code, because they appear in a very strange way when written in pure Markdown.

The algorithm

The algorithm is based on the well known RSA cryptosystem, but it has two major differences:

• the first one is that instead of using simple integer numbers, it uses Gaussian integers, i.e. complex numbers where both real and imaginary parts are integer values.
• the second is that the modulus N is calculated as P^2.Q^2 instead of simply P.Q . The encryption function was as follows:

As we can see in the encryption routine, the plain text is filled so that its size (in bits) is of the same order of magnitude as the private key. Then the text is divided in half, and each half is converted into a numerical value that is then used to form a complex number where the real part is the rst half and the imaginary part is the second one.

Since complex numbers are used, the code includes a function for multiplication and modular exponentiation of such numbers. Nevertheless, the encryption process occurs in the same way as in RSA: given a private key (e, N) and a plain text message M, the cipher text C is calculated as M e mod N . In this algorithm, the exponent e is fixed as 65537 and both the modulus N and the constants P and Q are present at the end of the file as comments, so all we need to do is implement the decryption function. Based on similarities with RSA, we can assume that the decryption process should also look at least partially similar.

Decryption process

In RSA, decryption would be done as follows:

• Calculate φ(N ) = (P − 1)(Q − 1)
• Calculate d = invmod(e, φ(N ))
• Calculate m = c e mod N

Since N is defined as P^2.Q^2 intead of just P Q , we need to figure out the correct way to calculate φ(N ) (also known as Euler's totient function) for this group of Gaussian integers.

Considering the definition of φ and a generalization of it to Gaussian integers, we find it as being (P^4 − P^2 )(Q^4 − Q^2 ).

THE END

Original writeup (https://github.com/LvMalware/CTF-WriteUps/blob/master/TetCTF/unimplemented.pdf).