[TWCTF-2016: Crypto] Twin Primes Writeup


Challenge description:
Decrypt it.

We have 4 files in the archive:

  • encrypt.py – A Python script uses RSA algorithm to encrypt the flag
  • encryped – The encrypted message
  • key 1 – n, and e of one of the keys used in the encryption process
  • key 2 – n, and e of the other key used in the encryption process

Are you ready for your math lesson? Here we go.
After reading encrypt.py we know that:

  • n1 = p*q
  • n2 (p+2)(q+2)
  • p and q are twin primesi.e p is prime and p+is also prime; similar for q.

Now let’s turn the equation into an equation with one unknown and then solve it for the unknown.We can Isolate q to be twin-primes_1  and substitute q in the other equation. Now we have an equation in one unknown:twin-primes_2

Solve the equation and you’ll get: twin-primes_3

We need to solve this quadratic equation in order to find p and q. After that it will not be a problem to find the d’s and build the keys.
The rest is in the script:



Leave a Reply

Your email address will not be published. Required fields are marked *