RSA

What is RSA (Rivest-Shamir-Adleman)?

RSA is a public-key cryptographic algorithm used for data encryption, digital signatures, and key exchange.
It is based on the mathematical difficulty of factoring large prime numbers.

1. How RSA Works

✔ Asymmetric encryption: Uses a public key for encryption and a private key for decryption.
✔ Digital signatures: Uses a private key to sign messages and a public key to verify signatures.

2. RSA Key Generation

RSA security is based on the difficulty of the integer factorization problem.

Select two large prime numbers pp and qq
- These primes must be very large (e.g., 1024-bit, 2048-bit, or 4096-bit).
Compute their product → N=p×q
- N becomes part of the public key.
- The larger N, the more secure RSA is.
Compute Euler’s Totient Function → ϕ(N)=(p−1)×(q−1)
Select a public exponent ee
- Typically 65537 (2¹⁶ + 1) is used.
- ee must satisfy 1<e<ϕ(N)1 < e < \phi(N) and be coprime to ϕ(N)\phi(N).
Compute the private key d
- dd is the modular inverse of e under ϕ(N)

✔ Final Public Key: (N,e)
✔ Final Private Key: (N,d)

3. RSA Encryption & Decryption

Encryption:
- The sender encrypts the message MM using the recipient’s public key (N,e):
Decryption:
- The recipient decrypts the ciphertext CC using their private key (N,d)(N, d):

✔ Public keys are widely available, but decryption is impossible without the private key.

4. RSA Digital Signatures

RSA is also used for message authentication and integrity verification through digital signatures.

Signing (Using Private Key)
- The sender signs a message MM using their private key dd:
- This ensures that only the sender could have generated this signature.
Verification (Using Public Key)
- The recipient verifies the signature using the sender’s public key ee:
- If M′=M, the signature is valid.

✔ Digital signatures are widely used in SSL/TLS certificates, blockchain, and secure communications.

5. RSA Vulnerabilities & Attacks

While RSA is secure, it is vulnerable to certain attacks:

Attack Type	Description	Countermeasure
Factorization Attack	If N=p×q is factored, the private key d can be recovered	Use 2048-bit or larger keys
Weak Key Attack	Poor choice of e or weak primes can weaken security	Use secure primes and e=65537
Side-Channel Attack	Power analysis, timing attacks, or electromagnetic leaks can expose keys	Use constant-time algorithms and hardware security
MITM Key Exchange Attack	An attacker can replace the public key with their own	Use certificates (PKI) to authenticate public keys

✔ To maintain security, RSA should use strong key sizes and secure implementation practices.

6. RSA vs. Other Cryptographic Algorithms

Algorithm	Key Size	Security Level	Speed
RSA	2048-bit+	Secure but requires large keys	Slow
ECC (Elliptic Curve Cryptography)	256-bit (RSA-3072 equivalent)	Stronger than RSA at smaller sizes	Faster
AES (Symmetric Encryption)	256-bit	Secure but requires key exchange	Very Fast

✔ RSA is strong but slow, and ECC is becoming the preferred alternative for modern cryptography.
✔ AES is much faster but requires a separate key exchange method.

7. Real-World Applications of RSA

✔ TLS/SSL (HTTPS security) → Website encryption
✔ PGP (Pretty Good Privacy) → Secure email encryption
✔ Digital Signatures → Document authentication, blockchain security
✔ SSH (Secure Shell) → Secure remote access authentication

However, as quantum computing advances, RSA security may weaken, leading to research in Post-Quantum Cryptography (PQC).

ATTACK

RSA attacks can be categorized into two areas: discrete logarithm attacks and factorization attacks.
Most attacks focus on factoring N.

PGP

PGP (Pretty Good Privacy) is implemented based on RSA and is likely the most widely used encryption software.
PGP is a protocol, not an algorithm.

It uses an asymmetric encryption algorithm for key exchange and a symmetric encryption algorithm to encrypt the message.

Public Key Cryptography - RSA

Table of contents

RSA