Cryptorium

History

The RSA cipher was introduced in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT. Named after the initials of its inventors, RSA was a groundbreaking development in cryptography, providing a way to securely exchange information without needing a shared secret key. RSA's security relies on the complexity of factoring large composite numbers, which remains a computational challenge.

The RSA algorithm was one of the first practical implementations of public-key cryptography, following the theoretical work of Diffie and Hellman on public-key exchange. Its adoption has had a profound impact on modern secure communication, becoming a cornerstone of internet security protocols.

Working

RSA operates on the principle of public-key cryptography, where two keys are used: a public key for encryption and a private key for decryption. The security of RSA is based on the mathematical challenge of factoring large numbers into their prime components.

Key Concepts

• Prime Numbers: RSA relies on the product of two large prime numbers to create a modulus for encryption and decryption.
• Public and Private Keys: The public key is used for encryption, and the private key is used for decryption. Only the private key can decrypt data encrypted with the corresponding public key.
• Modular Arithmetic: RSA uses modular arithmetic to perform encryption and decryption operations, specifically working modulo the product of the two primes.

Algorithm

Encryption

Key Generation: Generate two large prime numbers, \( p \) and \( q \). Compute \( n = p \times q \), and calculate the totient \( \phi(n) = (p - 1) \times (q - 1) \). Choose a public exponent \( e \) such that \( 1 < e < \phi(n) \) and \( e \) is coprime with \( \phi(n) \). Compute the private exponent \( d \), which is the modular inverse of \( e \) modulo \( \phi(n) \).

Encryption Formula:
C = M^e \mod n
where \( M \) is the plaintext message converted to a number, and \( C \) is the resulting ciphertext.

Example:

• Plaintext: 12
• Public Key: \( (n = 3233, e = 17) \)
• Encryption: C = 12^17 \mod 3233 = 2201

Decryption

Decryption Formula:
M = C^d \mod n
where \( C \) is the ciphertext, \( d \) is the private exponent, and \( M \) is the decrypted plaintext message.

Example:

• Ciphertext: 2201
• Private Key: \( (n = 3233, d = 2753) \)
• Decryption: M = 2201^2753 \mod 3233 = 12