AlexCTF 2017 : crypto150-what_is_this_encryption

Fady assumed this time that you will be so n00b to tell what encryption he is using
he send the following note to his friend in plain sight:


He is underestimating our crypto skills!


The encryption is RSA, and was given to us

  • p = first prime number
  • q = second prime number
  • e = public/encryption exponent
  • ct = ciphertext (encrypted text)

Quoted from wikipedia..

A user of RSA creates and then publishes a public key based on two large prime numbers, along with an auxiliary value. The prime numbers must be kept secret. Anyone can use the public key to encrypt a message, but with currently published methods, if the public key is large enough, only someone with knowledge of the prime numbers can feasibly decode the message.

Well, in this case we have the primes.. to decrypt we still need to find

  • n = product of two primes (p and q)
  • d = decryption key

Extended Euclidean Algorithm

Ok, we have the two primes, n is easy to find, but how to recover decryption key?

We need to compute a polynomial greatest common divisor. To do this we used the Extended Euclidean algorithm, take a look at the articles if you like a lot of boring math stuff.

## Extended Euclidean Algorithm
def egcd(a, b):  
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
        gcd = b
    return gcd, x, y

n = p*q #product of primes  
phi = (p-1)*(q-1) #modular multiplicative inverse  
gcd, a, b = egcd(e, phi) #calling extended euclidean algorithm  
d = a #a is decryption key  

Now pow ciphered_text d and n and we have the decrypted text.


Full script