# Analyzing the code

For this challenge we are provided with the server network address and the source code:

Let’s first look at the `main`

function. It first generates some two values `N`

and `token`

. Then it prints us the `N`

and each byte of the `token`

encrypted by function `encryptByte(b, N)`

. After that the program waits for our `input`

and if the value of `input`

is equal to `token`

we get the flag. So we need to decrypt the ciphertext we are given.

Now, let’s go deeper and see what functions `getN()`

and `encryptByte()`

do.

The `genN()`

function generates two 64-bit prime numbers `p, q`

and returns their multiplication.

But note that those prime numbers have specific properties:

Right now it is not clear why primes must have these properties, but obviously they are important for the cryptosystem.

Now let’s look at the `encryptByte()`

This function first creates new variable `z = -1`

and an array of integers of size 8.

Next, in the **for** loop it performs the following steps 8 times:

- Take one bit of the provided byte
- Generate value
`x`

with function`genX(N)`

. - Set
`x = x^2 mod N`

. - If bit is 1 set
`x = x * z mod N`

. - Put
`x`

into the array`enc`

.

After the **for **loop the function returns `enc`

, which is an array of 8 integers.

The function `genX()`

just generates the random value `x`

such that `GCD(x, N) = 1`

.

# Summarizing the cryptosystem

Now we can describe the cryptosystem we need to brake. First of all note that it encrypts each bit of the plain text individually. For every bit `b`

in the plain text we have the number in the ciphertext `c`

such that:

For some random value of `x`

. So this is a basically the Goldwasser-Micali cryptosystem. This cryptosystem is based on the following problem.

## Goldwasser-Micali cryptosystem problem

Suppose that we have `c`

and `N`

, where `N`

is composite. There is no way to determine whether `c`

is a quadratic residue modulo `N`

, i.e., there is no way to determine whether there exists `a`

such that

The thing is that `c`

is a quadratic residue modulo a composite number if and only if it is a quadratic residue modulo every prime factor of `N`

. If we knew prime factors of `N`

we could calculate Legendre symbol for every prime `p`

to determine if `c`

is a quadratic residue modulo `p`

And if Legendre symbol equals to 1 for every prime factor of `N`

than `c`

is a quadratic residue modulo `N`

. Even better, we could calculate Euler’s criterion for each prime, that says that

But we don’t know prime factors of `N`

. (Actually, because primes are of size 64 bit we can easily factor `N`

. That’s actually how I solved the challenge in the first place, but let’s move on to see the actual cryptosystem failure)

There is also a Jacobi symbol modulo `N`

. If Jacobi symbol equals `-1`

then `c`

is definitely not a quadratic residue modulo `N`

. However, if it equals to `1`

, then we still can’t tell for sure if `c`

is a quadratic residue modulo `N`

.

## Cryptosystem failure

Now let’s consider the encryption scheme again to see where the system fails

If the plaintext bit equals to `0`

then we add quadratic residue modulo `N`

to the ciphertext. Jacobi symbol for this value will return `1`

and cryptanalyst will not have a way to tell if this value is a quadratic residue modulo `N`

.

Now, what if the plaintext bit equals to `1`

then we add quadratic residue modulo `N`

multiplied with `(-1)`

to the ciphertext. What will Jacobi symbol be equal to for this value? For original Goldwasser-Micali cryptosystem we should’ve picked multiplier `a`

such that it is a quadratic nonresidue modulo `p`

and `q`

. This would yield Jacobi symbol to be equal to 1, because

But we have the problem with `(-1)`

. Remember that `p`

and `q`

have properties

This yields

but

Thus,

And this is a major failure, because we want it to be `1`

. Using this failure we can easily decrypt ciphertext. All we need to do is to compute Jacobi symbol for every ciphertext number modulo `N`

. If it equals to `1`

then we add `0`

to decrypted text. If it equals to `-1`

then we add `1`

to decrypted text.

The code for the exploit:

Also there is a solution I made in the first place using the factorization and Euler’s criterion: