RSA (Rivest–Shamir–Adleman)RSA is a widely used public-key cryptographic system that allows for secure data transmission and digital signatures. It is an asymmetric algorithm, meaning it uses a pair of keys: a public key, which can be shared with anyone, and a private key, which must be kept secret by its owner. RSA's security relies on the practical difficulty of factoring the product of two large prime numbers, a problem known as the integer factorization problem.
How RSA Works:
1. Key Generation: The core of RSA involves generating a public/private key pair. This process typically involves:
* Choosing two distinct large prime numbers, `p` and `q`.
* Calculating `n = p * q` (the modulus) and `φ(n) = (p-1)(q-1)` (Euler's totient function).
* Choosing an integer `e` (the public exponent) such that `1 < e < φ(n)` and `e` is coprime to `φ(n)`.
* Calculating `d` (the private exponent) such that `d * e ≡ 1 (mod φ(n))`. This `d` is the modular multiplicative inverse of `e` modulo `φ(n)`.
* The public key consists of `(n, e)`. The private key consists of `(n, d)` (or often `p`, `q`, `d`, and other derived values for optimization).
2. Encryption: To encrypt a message `M` for a recipient with public key `(n, e)`:
* The sender computes the ciphertext `C = M^e mod n`. `M` must be an integer less than `n`.
3. Decryption: To decrypt the ciphertext `C` with the private key `(n, d)`:
* The recipient computes `M = C^d mod n`.
4. Digital Signatures: RSA can also be used for digital signatures, ensuring data integrity and sender authenticity:
* To sign a message `M`, the sender computes a hash `H(M)` of the message and then "encrypts" the hash with their private key: `S = H(M)^d mod n`. `S` is the signature.
* To verify the signature `S`, the receiver computes `H(M)` themselves, and then "decrypts" the signature with the sender's public key: `H'(M) = S^e mod n`. If `H'(M)` matches `H(M)`, the signature is valid.
Use Cases:
* Secure Communications: Often used to encrypt a symmetric key (e.g., AES key), which then encrypts the actual bulk data due to RSA's slower performance compared to symmetric algorithms.
* Digital Signatures: Verifying the authenticity and integrity of messages, software, and documents.
* Key Exchange: Facilitating the secure exchange of cryptographic keys over an insecure channel.
Security Considerations:
* Key Length: RSA's security relies on the difficulty of factoring large numbers. Common key lengths today are 2048 bits or 3072 bits. Longer keys provide more security but are computationally more intensive.
* Padding Schemes: Raw RSA is vulnerable to various attacks. Practical implementations always use padding schemes like PKCS#1 v1.5 or OAEP (Optimal Asymmetric Encryption Padding) to add randomness and structure to the message before encryption, preventing attacks like chosen-ciphertext attacks.
* Randomness: Proper generation of prime numbers and random data for padding is crucial.
In Rust, RSA functionality is typically provided by cryptographic libraries, which handle the complex mathematics and security best practices, allowing developers to use RSA without implementing it from scratch.
Example Code
```rust
// Cargo.toml dependencies:
// [dependencies]
// rsa = { version = "0.9", features = ["sha2"] } // Or the latest stable version
// rand_core = { version = "0.6", features = ["std"] }
// rand = "0.8" // For OsRng in older versions, newer rsa crate might bundle it
// sha2 = "0.10"
use rsa::{pkcs1::{v1_5::*, traits::PublicKeyParts}, RsaPrivateKey, RsaPublicKey};
use rand::rngs::OsRng; // Secure random number generator
use sha2::{Sha256, Digest};
fn main() -> Result<(), Box<dyn std::error::Error>> {
// 1. Key Generation
let mut rng = OsRng;
let bits = 2048; // Key size in bits (e.g., 2048 or 3072 for good security)
println!("Generating {}-bit RSA key pair...", bits);
let private_key = RsaPrivateKey::new(&mut rng, bits)
.expect("Failed to generate private key");
let public_key = RsaPublicKey::from(&private_key);
println!("Key pair generated successfully.");
// 2. Encryption
let message_to_encrypt = b"This is a secret message to be encrypted with RSA.";
println!("\nOriginal message: {:?}", std::str::from_utf8(message_to_encrypt)?);
// Encrypt the message using PKCS#1 v1.5 padding with the public key
let encrypted_data = public_key.encrypt(
&mut rng, // Random number generator for padding
Pkcs1v15Encrypt,
message_to_encrypt,
).expect("Failed to encrypt message");
println!("Encrypted data (base64 for display): {}", base64::encode(&encrypted_data));
// 3. Decryption
// Decrypt the message using PKCS#1 v1.5 padding with the private key
let decrypted_data = private_key.decrypt(
&mut rng, // Random number generator for blinding (side-channel protection)
Pkcs1v15Encrypt,
&encrypted_data,
).expect("Failed to decrypt message");
println!("Decrypted message: {:?}", std::str::from_utf8(&decrypted_data)?);
assert_eq!(message_to_encrypt, decrypted_data.as_slice());
println!("Encryption and decryption successful!");
// 4. Digital Signing
let message_to_sign = b"This message demonstrates RSA digital signatures.";
println!("\nMessage to sign: {:?}", std::str::from_utf8(message_to_sign)?);
// Hash the message (e.g., using SHA256)
let mut hasher = Sha256::new();
hasher.update(message_to_sign);
let hashed_message = hasher.finalize();
// Sign the hash with the private key using PKCS#1 v1.5 padding
let signature = private_key.sign(
&mut rng, // Random number generator for blinding
Pkcs1v15Sign::new::<Sha256>(),
&hashed_message,
).expect("Failed to sign message");
println!("Digital Signature (base64 for display): {}", base64::encode(&signature));
// 5. Signature Verification
// To verify, the verifier would re-hash the original message
let mut verifier_hasher = Sha256::new();
verifier_hasher.update(message_to_sign);
let verifier_hashed_message = verifier_hasher.finalize();
// Verify the signature with the public key
match public_key.verify(
Pkcs1v15Sign::new::<Sha256>(),
&verifier_hashed_message,
&signature,
) {
Ok(_) => println!("Signature verified successfully!"),
Err(e) => eprintln!("Signature verification failed: {}", e),
}
Ok(())
}
```