RACTF 2020 Crypto - Really Simple Algorithm


Really Simple Algorithm

This is a typical RSA challenge. On netcatting the server, we get

p: 692978822802216497910263439691526372004023822242590405470708610553024726
q: 818545152008458581431308715472370387421587511434432009344550954468777476
e: 65537
ct: 32339597696112020672456048174497066278381984032062108835179880038510430

Now, following wikipedia article, one could understand, in order to solve the challenge, one need to follow the following steps :-

  • calculate n = p*q
  • calculate phi of n which is euler’s totient which denotes the number of positive integers, which are relatively prime (GCD=1) with n.
    In our case, it is calculated as phi = (p - 1) * (q - 1)
  • calculate the decryption key d which is modular inverse of encryption key e over phi
    It is calculated using extended gcd. For our case, we can find the implementation in gmpy2
  • d = gmpy2.invert(e, phi)
  • Once you have d, one can easily calculate plaintext as ciphertext raised to the power d modulo n
  • pt = pow(ct, d, n)
  • converting pt from integer representation to a string or byte-string prepresentation
  • plaintext = bytes.fromhex(hex(pt)[2:]) or equivalently plaintext = int.to_bytes(pt,(pt.bit_length()+7)//8,'big')
  • print the plaintext, print(plaintext.decode())

Now, this process can be automated too, but since time is not concerned with this task as with the next Really Speedy Algorithm, I like to do it anyways

from pwn import remote
from gmpy2 import invert

HOST, PORT = "", 20391

REM = remote(HOST, PORT)

p = int(REM.recvline().decode().strip()[3:])
q = int(REM.recvline().decode().strip()[3:])
e = int(REM.recvline().decode().strip()[3:])
ct = int(REM.recvline().decode().strip()[4:])

PHI = (p - 1) * (q - 1)
D = invert(e, PHI)
MESSAGE = pow(ct, D, p * q)

And we get our flag