Complex RSA

by goulov and ice

Points: 197 (Dynamic, 12 solves)

Description:

Things in this world sometimes are different than they appear!

nc 167.71.62.250 14559

Solution:

TLDR

  1. We are given the KeyGen function, notice that one prime is much larger than the other, so factoring n is possible.

  2. Recover n by asking for the encryption of -1. Assume e is small and recover it by solving the dlog by enumeration. Factor n.

  3. Compute d (as usual) and decrypt using Square and Multiply adapted for the Complex numbers.

Description

We are given a server to connect to, there we are greeted by:

|-------------------------------------|
| Options:                         |
|    [E]ncrypted message           |
|    [K]ey generation function     |
|    [S]end the decrypted message  |
|    [T]ry encryption              |
|    [Q]uit                        |
|-------------------------------------|
  • From here we can get the KeyGen function: 
    def gen_key(e, nbit):
  p = getPrime(nbit << 2)
  q = getPrime(nbit >> 2)
  print 'p =', p
  print 'q =', q
  n = p * q
  return (e, n)
  • We are also given an oracle that encrypts chosen messages: 
    Send your input as a pair (a, b):
$ (a, b)
((a + b √-1) ** e) (mod n) = (x, y)
  • And get a challenge Encrypted message that we must decrypt, and submit the answer to the challenge.

If it wasn’t clear from the name of the challenge, it is easy to see now that this challenge implements RSA using complex numbers (actually Gaussian integers since the real and imaginary parts are integers).

Our solution took the following steps:

Finding the public key (n,e)

Since we are not give the public key (n,e), we need to get it first.

Recovering n turns out to be an easy job. Since the encryption oracle accepts requests to encrypt negative numbers, we can ask for the encryption of (-1, 0), which is -1^e = -1 (e is odd) and -1 mod n = n - 1.

For e, the work is a bit more cumbersome. However, if we assume e is small, we can solve the discrete logarithm (e.g. for the encryption of (2, 0) which is 2^e mod n) by enumerating e. This turns out to be good enough to recover the public exponent.

Recovering the secret key d

Looking at the given KeyGen function, we notice that one of the primes is substantially smaller than the other. We also deduce from the code that n is an integer. Trying to factor n results in success!

Given the prime factorization of n we just compute ord = (p*p-1)*(q*q-1) (equivalent to phi(n) but for this group of Gaussian integers (nevertheless it is actually a multiple of phi(n))) and finally d = e^-1 mod ord. Now we own the secret key as well!

Decrypting

This challenge still requires one more trick even after recovering the secret key. Unfortunately, Python’s pow() function does not work well with complex numbers, so decrypting by pow(c, d, n) for a complex c does not seem to work. For this we just implement ourselves the square and multiply algorithm for complex modular exponentiation. Then everything that remains is to decrypt the given challenge and submit it, then we are saluted with the flag !

Congratz!!, you got the flag :) CCTF{_____e^(i*PI)=-1_____}

Resources:

The solution code can be found in sol.py. An example of the interaction with the server can be found in dump.txt.