RSA-Challenge in CTFlearn
RSA Theory
The RSA algorithm is a method used to securely encrypt messages or create digital signatures. It relies on the difficulty of factoring large numbers into their prime components. RSA is an asymmetric encryption method that uses two keys: a private key and a public key.
Using the public key, which consists of a large composite number, messages can be encrypted. The private key, however, remains secret and is required to decrypt these encrypted messages. Only the owner of the private key can decrypt and read the message.
RSA guarantees security due to the difficulty of calculating the two prime factors p and q from the large number n (the modulus). Even if the public key e and n are known, the encrypted message cannot be reversed without the private key dd. The process can be summarized as follows:
Key Generation
Two prime numbers are multiplied to compute n = p x q. The value of n, with the exponent e, forms the public key, which is availabe for everybody. To compute the private key, the modulare inverse of e to (p - 1)(q - 1) must be determined. The equation e x d ≡ 1 (mod(p - 1)(q - 1)) must hold, ensuring that d is the modular inverse of e, and d remains secret.
Encryption
The message m, that needs to be smaller than n, us encrypted by raising it to the power od the public key e and then taking the result modulo n:
c = m^e mod n
The result c is the ciphertext, which is the encrypted form of the message m.
Decryption
To translate the original message m from the ciphertext c, the private key d is used. The ciphertext c is raised to the power of d, and the result is taken modulo n:
m' = c^d mod n
This proves that m' = m, which indicates that the original message is correctly stored withhin the process.
RSA-Challenge in CTFlearn
With a RSA-challenge - Challenge RSA Noob - from the platform CTFlearn, the RSA method is explained more in a practical way.
The challenge provides the following information.
Getting the values
It indicates, that the searched values are provided in the link.
e: 1
c: 9327565722767258308650643213344542404592011161659991421
n: 245841236512478852752909734912575581815967630033049838269083
RSA-Equation
Due to e = 1, the decryption follows a different pattern. In a typical case, a RSA message m in encrypted by raising m to the power of the exponent e and then taking the result modulo n:
c = m^e mod n
In this challenge the exponent e = 1, which means the message m remains unchanged because any number raised to the power of 1 remains the same. This means:
c = m^1 mod n = m mod n
The ciphertext c is therefore m modulo n. If the message m is smaller than n, then c is equal to m, because m mod n = m as long as m < n.
Conversion of m
The ciphertext c - or in this case the message m - can be converted with a Python code.
The constructor is called when an instance of the class is created. It stores the passed values of e, c, and n in the instance of the class.
The method checks whether the value of e=1. If yes, it returns the ciphertext c since no encryption has taken place. If e is not equal to 1, an error is triggered because only the case e=1 is implemented.
The values for e, c, and n are set, which will later be used in the instance.
An instance of the "RSASolver" class is created with the given values for e, c, and n.
The "decrypt()" method is called to decrypt the ciphertext c. Since e = 1 ,c is returned unchanged.
The result is converted to hexadecimal, then to bytes, and finally decoded into readable text. If the conversion to a readable string fails, an error message is displayed.
We obtain the flag, which is necessary for successfully completing the challenge.
These steps can be performed using various platforms that convert the value m from a decimal number to a hexadecimal number and then translate it into plaintext.
The flag is used on the CTFlearn platform as confirmation that the challenge has been successfully completed.
The challenge is successfully completed.
References
converter: https://www.rapidtables.com/convert/number/hex-to-ascii.html
- Linnemann, Torsten. "Grundlagen der RSA-Verschlüsselung". Link, n.d. Zugriff am 15. Dezember 2024.
CTFlearn. "CTFlearn: Learn cybersecurity through challenges". Link, 2023. Accessed on September 22, 2024.