Skip to content

README.md

Latest commit

 

History

History
43 lines (28 loc) · 1.91 KB

README.md

File metadata and controls

43 lines (28 loc) · 1.91 KB

RSA Decryption Project

This project is an educational tool designed to decrypt a message encrypted with RSA encryption. Given a public key and an encrypted message, the program demonstrates how to break RSA encryption to retrieve the original message by calculating the private key. This project is built for a scenario where only the public key is known.

Problem Statement

In this project, we assume:

  • The public key ((e, n)) is known.
  • The private key is unknown.
  • An encrypted message ( C ) was intecepted.

The task is to "break" the RSA encryption and decrypt the intecepted message without the private key. The solution involves factoring ( n ), computing Euler’s totient function, and finding the decryption exponent using the extended Euclidean algorithm.

How It Works

The program follows these steps to decrypt the message:

  1. Factorize ( n ): Determine the two prime factors of ( n ) to calculate Euler's totient function.
  2. Calculate Euler's Totient Function: Using the factors of ( n ), compute ( \phi(n) ).
  3. Determine Decryption Exponent ( d ): Using the extended Euclidean GCD function, find ( d ) such that ( e \cdot d \equiv 1 \ (\text{mod} \ \phi(n)) ).
  4. Decrypt the Message: Use the decryption exponent to compute the plaintext message from ( C ).
  5. Translate the Message: Convert the decrypted numerical message into readable text.

Inputs

  • Public Key (e, n): The encryption exponent ( e ) and modulus ( n ) are provided by the user.
  • Message Size and Encrypted Message ( C ): The program accepts the encrypted message size and the message itself as input.

Output

The program prints:

  1. The decoded numerical message.
  2. The translated plaintext message.

Requirements

  • C++

Author

Marlon L

Acknowledgments

Thanks to Professor Strzheletska and Mr. Euclid who made this project possible.