This is a simple implimentation of RSA algorithm in python. It also exposes a few rsa vulnerabilities.
-
Choose two large prime numbers p and q.
- p shouldn't equal q
- p and q should be a secret
-
n = p*q
- n is the modulus for both public key and private key
-
using Euler's totient function phi = (p-1)(q-1)
-
choose an interger e such that 2 < e < λ(n) and gcd(e, λ(n)) = 1; that is, e and λ(n) are coprime
- Generally e is 65537
-
Compute d = e (mod λ(n)) using Eucelidean extended algorithm d can be computed efficiently
- d should be a secret
Public key = (e,n)
Private key = (d,n)
let m be the message
ciphertext =
decrypted =
Given the performance of this implementation, bit length shouldn't exceed 1024
from pureRsa import Rsa
bits = 1024
bob = Rsa(bits)
alice = Rsa(bits)
#Bob encrypted message with alice's public key
cipherText = bob.encrypt('Euler is in your closet',alice.getPublicKey())
#Alice decrypts with her private key
decrypted = alice.decrypt(cipherText)
print(decrypted)
In order for the brute force to work in a reasonable amount of time, bit length shouldn't exceed 30
from pureRsa import Rsa,Exploits
bits = 27
bob = Rsa(bits)
alice = Rsa(bits)
cipherText = bob.encrypt('Hello, World!',alice.getPublicKey())
e,n = alice.getPublicKey()
x = Exploits(bits)
print('brute forcing...')
x.bruteForce(e,n)
print('Successfully found private key')
print(f'Brute Forced decryption = {x.decrypt(cipherText)}')