RSA-Project

RSA key math implemented from scratch in Python: modular exponentiation for encryption and decryption, and the extended Euclidean algorithm to recover the private exponent.

What this demonstrates

RSA security rests on a small set of number-theory operations. This builds them directly instead of calling a crypto library, so the whole chain is visible: derive the modulus and Euler's totient from two large primes, confirm the public exponent is coprime to the totient, invert it modulo the totient to get the private exponent d, then encrypt and decrypt with square-and-multiply modular exponentiation. The primes here are 512-bit values, so the arithmetic runs on Python big integers.

Concepts demonstrated

• Modular exponentiation by square-and-multiply (modPower), the core RSA operation
• The extended Euclidean algorithm (extendedEA) to compute the modular inverse
• Modular inverse of the public exponent to produce the private exponent d
• Euler's totient t = (p-1)(q-1) and the RSA modulus n = p*q
• Euclidean GCD to check that e = 65537 is coprime to the totient
• Miller-Rabin primality testing and trial-division prime generation (getRandomPrime.py) for producing candidate primes p and q

What's implemented

• main.py derives n, t, and d from the project's primes and e = 65537, then encrypts and decrypts the sample messages. The prime-generation and coprimality checks are kept inline as commented reference.
• getRandomPrime.py generates probable primes: a trial-division sieve against small primes followed by a Miller-Rabin test (MRTest) with 20 witnesses.

Stack

• Python 3 (standard library, arbitrary-precision integers)

Usage

python main.py

Prints n, the recovered private exponent d, and the encrypted and decrypted message values. The values are the ones assigned for the project; edit the constants in main.py to run different inputs.