Project Overview
This project contains a basic implementation of the RSA encryption/decryption scheme. It takes a message of any length from the user, displays the corresponding encrypted string, and asks for a decryption key to recover the message. This key is typically kept secret, of course, but we must know it to verify that encryption/decryption work as expected. The program will attempt to decrypt with any decryption key entered, but only the correct key will recover the true original message.
Upon execution, the program first generates two large prime numbers p, q. The product of p, q is used as the modulus during modular exponentiation of message blocks. The encryption key is a fairly large number relatively prime with Euler's Phi function ϕ(pq), and is also generated at random. The extended Euclidean algorithm is then used to compute the corresponding decryption key, given the encryption key and ϕ(pq) which we can easily find from the two primes p, q. The input string is separated into smaller blocks which are converted into integer value based on their ASCII equivalents, and exponentiated (mod pq) by the encryption key, forming the encrypted string.
For each decryption attempt, blocks in the encrypted string are then exponentiated (mod pq) by the entered decryption key. This process will always produce some result, but whether or not the result is meaningful will depend on whether the key is correct.
The efficient algorithm of modular exponentiation is implemented, making the encryption and decryption steps near instant for any reasonable length message.
As a final note, while the RSA encryption scheme is generally very effective, there are a number of reasons as to why this specific implementation should never actually be put to real use! This project lives only as an exercise putting some number theory concepts to practice.
Source code: https://github.com/CurtisBuckoll/RSA/blob/master/RSA/RSA.cpp