On this page
article
Introduction DRAFT
RSA is a widely-used public-key encryption system that is based on the mathematical properties of large prime numbers. It was one of the first practical public-key cryptosystems and is widely used for secure data transmission.
The RSA encryption process consists of two parts: key generation and encryption/decryption.
Key Generation:
- Select two large prime numbers, p and q.
- Compute n = p*q. n is used as the modulus for both the public and private keys.
- Compute the totient of n, φ(n) = (p-1)*(q-1).
- Select a public exponent e, such that 1 < e < φ(n) and e is coprime to φ(n).
- Compute the private exponent d, such that d*e = 1 mod φ(n).
Encryption/Decryption:
- For encryption, the plaintext message is represented as a number m. The ciphertext c is computed as c = m^e mod n.
- For decryption, the ciphertext c is input and the plaintext message m is computed as m = c^d mod n.
from math import gcd
from random import randrange
def generate_keypair(p, q):
if not (is_prime(p) and is_prime(q)):
raise ValueError('Both numbers must be prime.')
elif p == q:
raise ValueError('p and q cannot be equal')
n = p * q
phi = (p-1) * (q-1)
e = randrange(1, phi)
g = gcd(e, phi)
while g != 1:
e = randrange(1, phi)
g = gcd(e, phi)
d = multiplicative_inverse(e, phi)
return ((e, n), (d, n))
def encrypt(pk, plaintext):
key, n = pk
cipher = [(ord(char) ** key) % n for char in plaintext]
return cipher
def decrypt(pk, ciphertext):
key, n = pk
plain = [chr((char ** key) % n) for char in ciphertext]
return ''.join(plain)