Rsa

This is a writeup of the crypto challenge RSA from the Security Valley CTF

Premise

We have again capture a bunch of numbers in a list. That makes no sense at all. But a whisteblower has leak that it can be a RSA encrypted block and has published a piece of code.

Link: https://github.com/SecurityValley/PublicCTFChallenges/tree/master/crypto/rsa

Challenge code:

peace_of_code.py

#/usr/bin/python3
from argparse import ArgumentParser
from sympy import mod_inverse, prime

def get_keys():
    p, q = prime(50), prime(60)
    n = p *q 
    phi = (p-1)*(q-1)
    e = 47

    return e, n, phi

def encrypt_msg(msg):
    e, n, _ = get_keys()
    enc_msg = [(ord(i) ** e) % n for i in msg]

    return enc_msg

def main(args):
    
    if args.mod == "enc":
        print(encrypt_msg(args.text))
        
    elif args.mod == "dec":
        pass

    else:
        print("unkown mode...")

if __name__ == "__main__":

    parser = ArgumentParser()
    parser.add_argument("-t","--text", dest="text", type=str)
    parser.add_argument("-m", "--mode", dest="mod", required=True)

    args = parser.parse_args()

    main(args)

Challenge ciphertext:

[5129, 10327, 42284, 57695, 5730, 64016, 31008, 40005, 63768, 46371, 7692, 48194, 9075, 32422, 35191, 63230]

Solution

We start off by analyzing the encoder function. If we look at how RSA decryption works, we can find that we need. To perform a decryption, we need to find the lowest common multiple of p and q reduced by 1, this being: lcm(p - 1, q - 1). To find p and q, we can simply import sympy and check the numbers generated by the prime(50) and prime(60) function. Running this gives us: p = 229 and q = 281. This now allows us to calculate lcm(p - 1, q - 1) which gives us 63840. We now have what we need to find the d variable, since this is the modular multiplicative inverse of: e mod lcm(p - 1, q - 1), or more accurately, since we have e from the key generation function: 47 mod 63840, we can find the modular multiplicative inverse with something like an online calculator such as the one provided by planetcalc, which gives us 13583. Furthermore, we’re going to need the n variable, which is simply p*q which is 229 * 281 = 64349. The actual decryption to get back plaintext from ciphertext is: m(c) = c^d mod n or in numbers: m(c) = c^13583 mod 64349.

With this, we can create a decryption algorithm to the existing code which might look something like:

d = 13583
n = 64349

ciphertext = [5129, 10327, 42284, 57695, 5730, 64016, 31008, 40005, 63768, 46371, 7692, 48194, 9075, 32422, 35191, 63230]

dec_msg_lst = [chr((i ** d) % n) for i in ciphertext]

dec_msg = ''.join(dec_msg_lst)

print(dec_msg)

Which when run with the ciphertext prints out the flag: SecVal{[REDACTED]}