RSA Basics

RSA is a public key cryptosystem that is widely used for secure data transmission. It is based on the difficulty of factoring large integers. The RSA algorithm involves four steps: key generation, key distribution, encryption, and decryption.

Key Generation

1. Choose two distinct prime numbers \(p\) and \(q\)
2. Compute \(n = p * q\).
3. Compute \(φ(n) = (p - 1) * (q - 1)\).
4. Choose an integer e such that $1 < e < φ(n) $ and $gcd(e, φ(n)) = 1 $.
5. Compute d as the modular multiplicative inverse of e modulo \(φ(n)\).
6. The public key is \((n, e)\) and the private key is \((n, d)\).

Key Distribution

The public key is distributed to anyone who wants to send an encrypted message to the owner of the private key.

Encryption

Given a message m, the sender encrypts it using the recipient's public key (n, e) as follows:

\(c = m^e \mod n\)

Decryption

The recipient decrypts the ciphertext c using their private key (n, d) as follows:

\(m = c^d \mod n\)

Python Implementation

Here is a simple Python implementation of the RSA algorithm:

from Crypto.Util.number import getPrime, inverse

def generate_keypair(bits):
    p = getPrime(bits)
    q = getPrime(bits)
    n = p * q
    phi = (p - 1) * (q - 1)
    e = 65537
    d = inverse(e, phi)
    return (n, e), (n, d)

def encrypt(m, public_key):
    n, e = public_key
    return pow(m, e, n)

def decrypt(c, private_key):
    n, d = private_key
    return pow(c, d, n)

public_key, private_key = generate_keypair(1024)
message = "Hello, RSA!"
m = int.from_bytes(message.encode(), "big")

c = encrypt(m, public_key)
print("Encrypted:", c)

m = decrypt(c, private_key)

print("Decrypted:", m.to_bytes((m.bit_length() + 7) // 8, "big").decode())