InfoSec Notes
HubCybersecurity vs Information SecurityHistory of Information SecurityImportance of Information SecuritySecurity Principles and the CIA TriadWhat is Information Security?Accountability in Information SecurityAuthentication in Information SecurityAuthorization in Information SecurityAvailability in Information SecurityConfidentiality in Information SecurityIntegrity in Information SecurityNon-Repudiation in Information SecurityAES - Advanced Encryption StandardAsymmetric Key CryptographyDES - Data Encryption StandardDigital SignaturesEncryption vs DecryptionCryptographic Hash FunctionsIntroduction to CryptographyPublic Key Infrastructure (PKI)RSA AlgorithmSymmetric Key CryptographyIntroduction to Access ControlAttribute-Based Access Control (ABAC)Discretionary Access Control (DAC)Mandatory Access Control (MAC)Role-Based Access Control (RBAC) — Information SecurityZero Trust Security ArchitectureFirewalls in Network SecurityIntrusion Detection Systems (IDS)Intrusion Prevention Systems (IPS)Network Monitoring and AnalysisNetwork Security BasicsSecure Network DesignVirtual Private Networks (VPN)Wireless Network SecurityAPI SecurityIntroduction to Application SecuritySecurity Code ReviewDependency and Supply Chain SecurityDynamic Application Security Testing (DAST)Secure Software Development LifecycleStatic Application Security Testing (SAST)Web Authentication MechanismsCross-Site Scripting (XSS)Cross-Site Request Forgery (CSRF)File Upload SecurityHTTPS and SSL/TLSSecure Coding Practices — Information SecuritySession Management SecuritySQL Injection Attacks and PreventionIntroduction to Web SecurityOS Access Control ModelsEndpoint SecurityFile System Permissions and SecurityLinux SecurityIntroduction to OS SecurityUser Account ManagementWindows SecurityCloud Security FundamentalsCloud Security Best PracticesContainer Security — Information SecurityData Security in the CloudCloud Identity and Access ManagementKubernetes SecurityShared Responsibility Model — Information SecurityIntroduction to Digital ForensicsDisk ForensicsDigital Evidence CollectionDigital Forensic ToolsIncident Investigation ProceduresMemory ForensicsNetwork ForensicsContainment StrategiesDetection and Analysis PhaseEradication and RecoveryIntroduction to Incident ResponseIncident Response LifecycleIncident Response PlaybooksPost-Incident Review and Lessons LearnedBusiness Continuity PlanningDisaster Recovery PlanningRisk Assessment MethodologyIntroduction to Risk ManagementSecurity ControlsThreat ModelingVulnerability AssessmentCompliance ManagementGDPR Data Protection OverviewISO 27001 Information Security ManagementNIST Cybersecurity FrameworkSecurity Audits and AssessmentsSecurity GovernanceSecurity Policies and StandardsCloud Security Interview QuestionsCryptography Interview QuestionsInformation Security CheatsheetInformation Security Interview QuestionsNetwork Security Interview QuestionsGlossary of Information Security TermsImportant Security Concepts ReferenceRecommended Books and Learning ResourcesSecurity Tools OverviewIncident Response LabLog Analysis ProjectNetwork Monitoring ProjectPassword Manager ProjectSecure Login System ProjectVulnerability Scanner ProjectInsider ThreatsMalware Types and AnalysisPhishing Attacks and PreventionRansomware AttacksSecurity Threats OverviewSocial Engineering AttacksSpyware and Surveillance SoftwareTrojan Horse MalwareComputer VirusesNetwork Worms
Complete guide to the RSA public-key cryptosystem covering mathematical foundations, key generation, encryption/decryption steps, digital signatures, and security considerations.
Overview
RSA (Rivest-Shamir-Adleman) is the most widely deployed public-key cryptosystem, invented in 1977. Its security is based on the mathematical difficulty of factoring the product of two large prime numbers. RSA is used for encryption, digital signatures, and key exchange.
Mathematical Foundation
RSA relies on these mathematical principles:
- Prime factorization is hard: Given n = p × q (where p, q are large primes), finding p and q from n alone is computationally infeasible for large numbers.
- Euler's theorem: a^φ(n) ≡ 1 (mod n) for gcd(a,n) = 1
- Modular exponentiation: Computing a^b mod n is efficient even for very large numbers.
RSA Key Generation Step-by-Step
| Step 1 | Choose two large distinct primes p and q |
| Step 2 | Compute n = p × q |
| Step 3 | Compute Euler's totient: φ(n) = (p-1)(q-1) |
| Step 4 | Choose public exponent e such that: |
| Step 5 | Compute private exponent d such that: |
| Public Key | (e, n) — share freely |
| Private Key | (d, n) — keep secret |
| Discard | p, q, φ(n) — must be destroyed |
Complete RSA Example (Small Numbers)
Example
def rsa_complete_example():
"""Complete RSA demonstration with small numbers."""
print("=" * 60)
print("RSA ALGORITHM - Complete Step-by-Step Example")
print("=" * 60)
# Step 1: Choose primes
p = 61
q = 53
print(f"\n[Step 1] Choose primes: p = {p}, q = {q}")
# Step 2: Compute modulus
n = p * q # 3233
print(f"[Step 2] Compute n = p × q = {p} × {q} = {n}")
# Step 3: Euler's totient
phi_n = (p - 1) * (q - 1) # 3120
print(f"[Step 3] Compute φ(n) = (p-1)(q-1) = {p-1} × {q-1} = {phi_n}")
# Step 4: Choose public exponent
e = 17 # Must be coprime to phi_n
from math import gcd
assert gcd(e, phi_n) == 1
print(f"[Step 4] Choose e = {e} (gcd({e}, {phi_n}) = {gcd(e, phi_n)} ✓)")
# Step 5: Compute private exponent
d = pow(e, -1, phi_n) # Modular inverse: d = 2753
print(f"[Step 5] Compute d = e^(-1) mod φ(n) = {d}")
print(f" Verify: d × e mod φ(n) = {d} × {e} mod {phi_n} = {(d * e) % phi_n}")
print(f"\n{'='*60}")
print(f"PUBLIC KEY: (e={e}, n={n})")
print(f"PRIVATE KEY: (d={d}, n={n})")
print(f"{'='*60}")
# Encryption
print(f"\n--- ENCRYPTION ---")
M = 65 # Message (ASCII 'A')
print(f"Message M = {M} (character: '{chr(M)}')")
C = pow(M, e, n) # C = M^e mod n
print(f"Ciphertext C = M^e mod n = {M}^{e} mod {n} = {C}")
# Decryption
print(f"\n--- DECRYPTION ---")
D = pow(C, d, n) # D = C^d mod n
print(f"Decrypted M = C^d mod n = {C}^{d} mod {n} = {D}")
print(f"Recovered character: '{chr(D)}'")
print(f"Correct: {D == M} ✓")
# Digital Signature
print(f"\n--- DIGITAL SIGNATURE ---")
message = 42
print(f"Message to sign: {message}")
signature = pow(message, d, n) # Sign with private key
print(f"Signature S = M^d mod n = {message}^{d} mod {n} = {signature}")
verified = pow(signature, e, n) # Verify with public key
print(f"Verify: S^e mod n = {signature}^{e} mod {n} = {verified}")
print(f"Signature valid: {verified == message} ✓")
rsa_complete_example()
Production RSA with Python
Example
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives import hashes, serialization
def rsa_production_demo():
"""Production-grade RSA operations."""
# Generate RSA-2048 key pair
private_key = rsa.generate_private_key(
public_exponent=65537,
key_size=2048,
)
public_key = private_key.public_key()
# Display key info
numbers = private_key.private_numbers()
print(f"RSA-2048 Key Generated:")
print(f" Public exponent (e): {numbers.public_numbers.e}")
print(f" Modulus (n): {str(numbers.public_numbers.n)[:40]}... ({numbers.public_numbers.n.bit_length()} bits)")
# ENCRYPTION with OAEP padding
message = b"RSA encrypted message - sensitive data"
ciphertext = public_key.encrypt(
message,
padding.OAEP(
mgf=padding.MGF1(algorithm=hashes.SHA256()),
algorithm=hashes.SHA256(),
label=None
)
)
print(f"\nEncryption (OAEP):")
print(f" Plaintext: {message.decode()}")
print(f" Ciphertext: {ciphertext.hex()[:48]}... ({len(ciphertext)} bytes)")
# DECRYPTION
decrypted = private_key.decrypt(
ciphertext,
padding.OAEP(
mgf=padding.MGF1(algorithm=hashes.SHA256()),
algorithm=hashes.SHA256(),
label=None
)
)
print(f" Decrypted: {decrypted.decode()}")
# DIGITAL SIGNATURE
message_to_sign = b"I authorize payment of $10,000"
signature = private_key.sign(
message_to_sign,
padding.PSS(
mgf=padding.MGF1(hashes.SHA256()),
salt_length=padding.PSS.MAX_LENGTH
),
hashes.SHA256()
)
print(f"\nDigital Signature (PSS):")
print(f" Message: {message_to_sign.decode()}")
print(f" Signature: {signature.hex()[:48]}...")
# Verify signature
try:
public_key.verify(
signature, message_to_sign,
padding.PSS(mgf=padding.MGF1(hashes.SHA256()),
salt_length=padding.PSS.MAX_LENGTH),
hashes.SHA256()
)
print(f" Verification: VALID ✓")
except Exception:
print(f" Verification: INVALID ✗")
rsa_production_demo()
RSA Key Sizes and Security
| Key Size | Security Level | Status | Recommended Until |
|---|---|---|---|
| 512 bits | ~30 bits | BROKEN (1999) | Never |
| 1024 bits | ~80 bits | DEPRECATED | Already expired |
| 2048 bits | ~112 bits | Minimum acceptable | ~2030 |
| 3072 bits | ~128 bits | Recommended | ~2040 |
| 4096 bits | ~140 bits | High security | Long-term |
Common RSA Attacks
| Attack | Description | Prevention |
|---|---|---|
| Brute force factoring | Factor n to find p, q | Use ≥2048-bit keys |
| Small exponent attack | e too small, cube root attack | Always use e=65537 |
| Common modulus attack | Same n with different e values | Unique n per key pair |
| Timing attack | Measure decryption time | Constant-time implementation |
| Textbook RSA | No padding, deterministic | Always use OAEP or PSS |
| Bleichenbacher attack | PKCS#1 v1.5 padding oracle | Use OAEP padding |
Interview Questions
- Why can't RSA encrypt messages larger than the key size?
- RSA operates on numbers less than the modulus n. For RSA-2048, you can only encrypt up to 2048 bits (~256 bytes), minus padding overhead. For larger data, use hybrid encryption: RSA encrypts a symmetric key, which encrypts the actual data.
- Why is e=65537 commonly used as the public exponent?
- 65537 (2^16 + 1) is a Fermat prime that balances security and performance. It's large enough to resist small-exponent attacks but has only two bits set (making modular exponentiation fast). It's coprime to most φ(n) values.
- What makes RSA vulnerable to quantum computers?
- Shor's algorithm can factor large integers in polynomial time on a quantum computer, breaking RSA completely. A sufficiently powerful quantum computer (~4000 logical qubits for RSA-2048) could break RSA in hours. Post-quantum alternatives (lattice-based, hash-based) are being standardized.
- Why is padding critical for RSA security?
- Without padding (textbook RSA), encryption is deterministic — the same message always produces the same ciphertext. This leaks information and enables chosen-ciphertext attacks. OAEP adds randomness and structure that prevents these attacks.
- Explain the relationship between RSA key generation parameters p, q, n, e, and d.
- p and q are large primes (kept secret). n = p×q is the public modulus. e is the public exponent (chosen, typically 65537). d is the private exponent (computed as modular inverse of e mod φ(n)). The security relies on the difficulty of finding d without knowing p and q.
Summary
RSA remains fundamental to internet security, used in TLS certificates, SSH keys, and code signing. While being gradually replaced by ECC for performance reasons, RSA's mathematical elegance and proven security (with proper key sizes and padding) make it a cornerstone of modern cryptography. Always use at least RSA-2048, OAEP padding for encryption, PSS for signatures, and plan migration to post-quantum algorithms.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for RSA Algorithm.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Information Security topic.
Search Terms
information-security, information security, information, security, cryptography, rsa, algorithm, rsa algorithm
Related Information Security Topics
Continue learning this concept
CryptographyAES - Advanced Encryption StandardComplete guide to the AES algorithm covering its structure, rounds, key expansion, modes of operation, implementation in Python, and why AES replaced DES as the global encryption standard.CryptographyAsymmetric Key CryptographyDeep dive into public key cryptography covering RSA, ECC, Diffie-Hellman key exchange, digital signatures, and how asymmetric algorithms solve the key distribution problem.CryptographyDES - Data Encryption StandardUnderstanding the Data Encryption Standard (DES), its Feistel structure, historical significance, vulnerabilities, evolution to 3DES, and why it was replaced by AES.CryptographyDigital SignaturesComplete guide to digital signatures covering RSA and ECDSA signing, verification process, certificate chains, applications in code signing and documents, with Python implementations.CryptographyEncryption vs DecryptionUnderstanding the fundamental processes of encryption and decryption, their differences, step-by-step operations, and practical applications in modern information security.CryptographyCryptographic Hash FunctionsComprehensive guide to hash functions including MD5, SHA family, properties, applications in password storage, integrity verification, and digital signatures with Python implementations.