RSA¶

Overview¶

The RSA encryption algorithm is an asymmetric encryption algorithm widely used in public-key cryptography and electronic commerce. RSA was proposed in 1977 at the Massachusetts Institute of Technology (MIT) by Ron Rivest, Adi Shamir, and Leonard Adleman. RSA is the combination of the first letters of their surnames.

The security of the RSA algorithm is based on the mathematical difficulty of large integer factorization: multiplying two large prime numbers together is easy, but factoring their product back into the original primes is computationally extremely difficult. This one-way trapdoor function property makes RSA one of the earliest practical public-key encryption systems and the most widely used asymmetric encryption algorithm to date.

Core Principles¶

Large Integer Factorization Difficulty

The difficulty of factoring extremely large integers determines the reliability of the RSA algorithm. In other words, the harder it is to factor an extremely large integer, the more reliable RSA is. Factoring large integers is an extremely difficult task. Currently, aside from brute force, no other effective method has been discovered.

Mathematical Foundation

The RSA algorithm is based on the following mathematical facts: 1. Choosing two large prime numbers p and q is easy 2. Computing their product N = p x q is easy 3. But factoring N back into p and q is extremely difficult 4. Euler's totient function phi(N) = (p-1)(q-1) is key to key generation

Key Generation¶

Generation Steps:

Choose primes: Prepare two coprime numbers p and q. These two numbers cannot be too small, as that would make them easy to break
Compute modulus: Multiply p by q to get N. If the coprimes p and q are sufficiently large, then given current computing technology and other tools, it remains infeasible to factor N back into p and q
Compute Euler's totient function: phi(N) = (p-1)(q-1)
Choose public key exponent: Select an integer e that is less than phi(N) and coprime to phi(N); 65537 (0x10001) is commonly chosen
Compute private key exponent: Compute d, the modular multiplicative inverse of e, such that (e x d) mod phi(N) = 1
Key pair:
Public key: (N, e)
Private key: (N, d)

Security Consideration: The primes p and q must be destroyed after key generation; their exposure would allow the private key to be computed.

Encryption and Decryption¶

Encryption Process

RSA encryption raises the plaintext to the power e and takes the remainder modulo N:

Ciphertext C = M^e mod N

where M is the plaintext, and e and N are the public key

Decryption Process

Raising the ciphertext to the power d and taking the remainder modulo N yields the plaintext:

Plaintext M = C^d mod N

where C is the ciphertext, and d and N are the private key

Mathematical Correctness

According to Euler's theorem and Fermat's little theorem, it can be proven that:

(M^e)^d mod N = M^(ed) mod N = M

Ciphertext Length: The length of the generated ciphertext equals the key length. The larger the key, the longer the ciphertext, the slower the encryption, and the harder it is to break.

Digital Signatures¶

RSA can be used not only for encryption but also for digital signatures.

Signing Process (Private Key Signing)

Compute the hash value H = Hash(M) for message M
Sign the hash value with the private key: S = H^d mod N
Send the signature S along with the message M

Verification Process (Public Key Verification)

The receiver computes the hash value H' = Hash(M)
Decrypts the signature using the public key: H'' = S^e mod N
Verifies H' = H''; if equal, the signature is valid

Use Cases: - Software release verification (ensuring software has not been tampered with) - SSL/TLS certificates - Code signing - Electronic document signing

Padding Schemes¶

For security, RSA encryption and signing must use appropriate padding schemes; raw data should not be processed directly.

PKCS#1 v1.5

The earliest padding scheme, simple but with security vulnerabilities: - Bleichenbacher attack discovered in 1998 - Only used for legacy protocol support - Not recommended for new systems

OAEP (Optimal Asymmetric Encryption Padding)

The recommended modern encryption padding scheme: - Proposed by Bellare and Rogaway - Standardized in PKCS#1 v2 and RFC 3447 - Provides probabilistic encryption - Has security proofs and can resist various attacks - Uses MGF1 (Mask Generation Function) and hash algorithms (such as SHA-256) - Recommended for new protocols and applications

PSS (Probabilistic Signature Scheme)

The recommended signature padding scheme: - Defined in RFC 3447 - More complex than PKCS#1 v1.5 but with security proofs - Recommended for RSA signatures in new protocols - Note: OAEP cannot be used for signing; it is only for encryption

Recommended Key Lengths¶

Historical and Current Recommendations:

512 bits: Broken (1999)
768 bits: Broken (2009); this is the longest RSA key broken to date
1024 bits: Basically secure, but no longer recommended
2048 bits: NIST-recommended minimum length, extremely secure, current standard
3072 bits: Higher security level, recommended for long-term protection
4096 bits: Highest commonly used level, suitable for extremely high security requirements

Security Level Comparison:

RSA Key Length	Symmetric Equivalent	Elliptic Curve Equivalent	Use Case
1024 bits	80 bits	160 bits	Deprecated
2048 bits	112 bits	224 bits	Current standard
3072 bits	128 bits	256 bits	Recommended
7680 bits	192 bits	384 bits	High security
15360 bits	256 bits	521 bits	Ultra-high security

Future Trend: RSA 2048-bit security is expected to last only until 2030.

RSA vs ECC Comparison¶

Key Length

At the same security level, ECC key lengths are much smaller than RSA: - For 112-bit symmetric key equivalent strength, RSA requires a 2048-bit key, while ECC requires only 224 bits - 128-bit security requires 3072-bit RSA, but only 256-bit ECC - 256-bit security requires 15360-bit RSA, but only 512-bit ECC

Performance Comparison

ECC is considered the successor to RSA because it uses smaller keys and signatures at the same security level, with very fast key generation, fast key agreement, and fast signatures.

RSA's main drawback is speed: approximately 1000 times slower than symmetric encryption algorithms
With ECC on Apache and IIS servers, web server response times are more than ten times faster than RSA
Shorter key lengths mean devices need less processing power to encrypt and decrypt data
ECC is well-suited for mobile devices, IoT, and other use cases with more limited computing capability

Quantum Computing Threat

Both RSA and ECC are quantum-insecure: - Shor's quantum algorithm can factor large integers and solve discrete logarithm problems in polynomial time - Both need to transition to post-quantum cryptographic algorithms - ECC based on supersingular elliptic curve isogeny cryptography is harder to break and relatively less susceptible to quantum computing - Symmetric encryption such as AES-256 is quantum-safe

Use Cases¶

SSL/TLS Certificates

HTTPS websites use RSA certificates for authentication and key exchange: - The server uses an RSA private key to prove its identity - Typically RSA is used for authentication, symmetric encryption for actual data transmission - Modern TLS 1.3 tends to use ECC

SSH Keys

Secure Shell protocol supports RSA key authentication: - ssh-keygen -t rsa -b 4096 generates an RSA key pair - The public key is deployed to the server, private key kept on the client - Modern practice recommends Ed25519 over RSA

PGP/GPG Encryption

Email and file encryption: - Uses RSA to encrypt symmetric keys - Symmetric keys encrypt the actual content - Hybrid encryption scheme combines both advantages

Code Signing

Software developers sign applications and updates: - Apple, Microsoft, Android all use RSA signatures - Prevents malware and tampering - Establishes trustworthiness of software origin

Digital Certificates

PKI (Public Key Infrastructure) system: - X.509 certificates use RSA public keys - CAs (Certificate Authorities) use RSA to sign certificates - Browsers verify website certificate chains

Security Analysis¶

Known Attacks

Small exponent attack: If the public key exponent e is too small (e.g., 3), there may be risk
Timing attack: Inferring private key information by measuring decryption time
Padding attack: Such as Bleichenbacher attack against PKCS#1 v1.5
Side-channel attack: Obtaining information through power analysis, electromagnetic leakage, etc.

Countermeasures

Use recommended key lengths (at least 2048 bits)
Use secure padding schemes (OAEP, PSS)
Properly implement constant-time algorithms
Use Hardware Security Modules (HSMs) to protect private keys
Rotate keys regularly

Difficulty of Breaking

The longest RSA key broken to date is 768 bits, which demonstrates the security of longer keys. Breaking RSA-2048 requires computational resources that are infeasible with current technology, but the emergence of quantum computing may change this.

Implementations and Standards¶

Standard Specifications

PKCS#1: Published by RSA Laboratories, defines RSA key formats and operations
RFC 8017: Latest standard for PKCS #1 v2.2
FIPS 186-4: U.S. federal standard defining RSA signatures
X.509: Digital certificate standard

Common Libraries

OpenSSL: C language, most widely used cryptographic library
Bouncy Castle: Java/C# implementation
PyCrypto / Cryptography: Python implementation
Crypto++: C++ implementation
WebCrypto API: Browser built-in cryptographic API

Advantages and Limitations¶

Advantages: - Mature and reliable, verified over 40+ years - Widely supported, supported by virtually all systems - Simple to implement, mathematical principles are easy to understand - Supports both encryption and signing

Limitations: - Slow, approximately 1000x slower than symmetric encryption - Large key lengths, requiring more storage and bandwidth - Quantum-insecure, migration to PQC needed - Gradually being replaced by ECC

Future Outlook¶

Migration to ECC

Experts predict RSA will be replaced by ECC as the current standard, as ECC offers better performance and shorter keys.

Post-Quantum Cryptography

The emergence of quantum computing will pose enormous challenges to existing encryption algorithms. Many current encryption algorithms, such as RSA and ECC, may not withstand quantum computing attacks. Transition to lattice-based cryptography, hash-based signatures, and other post-quantum algorithms is needed.

Hybrid Schemes

During the transition period, hybrid schemes combining RSA/ECC with post-quantum algorithms ensure that the system remains secure as long as at least one algorithm is safe.