RSA Encryption
Public-key cryptosystem invented by Rivest, Shamir, Adleman in 1977. Foundation of modern internet security. Based on difficulty of factoring large primes.
Visualization
Interactive visualization for RSA Encryption
Interactive visualization with step-by-step execution
Implementation
1// Simplified RSA (educational only, not secure)
2function generateRSAKeys(p: number, q: number): {
3 publicKey: [number, number];
4 privateKey: [number, number];
5} {
6 const n = p * q;
7 const phi = (p - 1) * (q - 1);
8
9 // Choose e
10 let e = 65537; // Common choice
11 if (e >= phi || gcd(e, phi) !== 1) {
12 e = 3;
13 while (gcd(e, phi) !== 1) e += 2;
14 }
15
16 // Compute d using Extended Euclidean
17 const [_, d] = extendedGCD(e, phi);
18 const dPositive = ((d % phi) + phi) % phi;
19
20 return {
21 publicKey: [e, n],
22 privateKey: [dPositive, n]
23 };
24}
25
26function rsaEncrypt(message: number, publicKey: [number, number]): number {
27 const [e, n] = publicKey;
28 return modPow(message, e, n);
29}
30
31function rsaDecrypt(ciphertext: number, privateKey: [number, number]): number {
32 const [d, n] = privateKey;
33 return modPow(ciphertext, d, n);
34}
35
36function modPow(base: number, exp: number, mod: number): number {
37 let result = 1;
38 base %= mod;
39 while (exp > 0) {
40 if (exp % 2 === 1) result = (result * base) % mod;
41 base = (base * base) % mod;
42 exp = Math.floor(exp / 2);
43 }
44 return result;
45}
46
47function gcd(a: number, b: number): number {
48 while (b) [a, b] = [b, a % b];
49 return a;
50}
51
52function extendedGCD(a: number, b: number): [number, number] {
53 if (b === 0) return [a, 1];
54 const [g, x1] = extendedGCD(b, a % b);
55 return [g, x1 - Math.floor(a / b) * x1];
56}Deep Dive
Theoretical Foundation
Choose two large primes p, q. Compute n=pq, φ=(p-1)(q-1). Choose e coprime to φ. Compute d: e×d ≡ 1 (mod φ). Public key (n,e), private key (n,d). Encrypt: c = m^e mod n. Decrypt: m = c^d mod n. Security relies on difficulty of factoring n.
Complexity
Time
O(log³ n)
O(log³ n)
O(log³ n)
Space
O(1)
Applications
Industry Use
HTTPS/TLS for secure web browsing
Email encryption (PGP/GPG)
Digital signatures for software/documents
Cryptocurrency transactions
VPN and secure communications
Code signing certificates
Banking and financial systems
Government and military communications
Use Cases
Related Algorithms
A* Search Algorithm
Informed search algorithm combining best-first search with Dijkstra's algorithm using heuristics. Widely used in pathfinding and graph traversal, A* is optimal and complete when using admissible heuristic. Used in games, GPS navigation, and robotics. Invented by Peter Hart, Nils Nilsson, and Bertram Raphael in 1968.
Convex Hull (Graham Scan)
Find smallest convex polygon containing all points. Graham Scan invented by Ronald Graham in 1972, runs in O(n log n). Essential in computational geometry, computer graphics, and pattern recognition.
Line Segment Intersection
Determine if two line segments intersect. Fundamental geometric primitive used in graphics, CAD, GIS. Uses orientation and collinearity tests.
Caesar Cipher
The Caesar Cipher is one of the oldest and simplest encryption techniques, named after Julius Caesar who used it to protect military messages around 100 BC. It works by shifting each letter in the plaintext by a fixed number of positions down the alphabet. For example, with a shift of 3, A becomes D, B becomes E, and so on. Despite being used for over 2000 years, it's extremely weak by modern standards with only 25 possible keys, making it trivially breakable by brute force or frequency analysis.