# 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:

1. Take one bit of the provided byte
2. Generate value `x` with function `genX(N)`.
3. Set `x = x^2 mod N`.
4. If bit is 1 set `x = x * z mod N`.
5. 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: