RSA Public Key Algorithm

• Choose two very large primes (simple e.g., P=47, Q=71) and set N = P*Q = 3337 and M = (P-1)*(Q-1) = 3220
• Choose E relatively prime to M, e.g E=79
• Set D = E^-1 (mod M) = 79^-1 (mod 3220) = 1019
• Public key is (N, E) = (3337, 79)
• Private key is (N, D) = (3337, 1019)
• To encrypt n, C = cipher = n^E (mod N) = n^79 mode 3337
• To decrypt C, n = C^D mod N