RSA

Description

Level: 3 Score 40 Category crypto

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: SecurityValley/PublicCTFChallenges/crypto/rsa

Analysis

Challenge gives us simple RSA encryption and to decrypt it we have to do following:

1. Obtain the private exponent d and the modulus n from the decryption key.

   • The private exponent d can be calculated using the modular multiplicative inverse of e modulo φ(n), where φ(n) represents Euler's totient function applied to n.

2. Iterate through each element c in the encrypted message.

3. Calculate the decrypted value m using the formula: m = (c ** d) % n.

4. Convert the decrypted value m back to the original character using the chr() function.

5. Concatenate the characters obtained to form the original message.

Solution

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 decrypt_msg(msg):
    e, n, phi = get_keys()
    d = mod_inverse(e, phi) # Private Exponent
    
    # 1. Calculate decrypted value 
    # 2. Value into character
    # 3. Concatenate
    #            3        2    1
    enc_msg = ''.join(map(chr, [pow(c, d, n) for c in msg]))

    return enc_msg


msg = [5129, 10327, 42284, 57695, 5730, 64016, 31008, 40005,
       63768, 46371, 7692, 48194, 9075, 32422, 35191, 63230]
print(decrypt_msg(msg))

Note: If you dont want to install `sympy` library, you can always use online [SymPy Live Shell](https://live.sympy.org)