gen-define-the-rsa-algorithm-and-give-one-short-worked-example-55e1

Define the RSA algorithm and give one short worked example.

# RSA Algorithm ## Definition RSA (Rivest-Shamir-Adleman) is a public-key cryptographic algorithm that uses the mathematical difficulty of factoring large prime numbers for secure communication. ## Key Steps 1. **Key Generation:** - Choose two distinct prime numbers *p* and *q* - Compute *n = p × q* (modulus) - Compute φ(*n*) = (*p*-1)(*q*-1) (Euler's totient) - Choose *e* such that 1 < *e* < φ(*n*) and gcd(*e*, φ(*n*)) = 1 (public exponent) - Compute *d* ≡ *e*⁻¹ (mod φ(*n*)) (private exponent) - **Public key:** (*n*, *e*) - **Private key:** (*n*, *d*) 2. **Encryption:** C = M^*e* mod *n* 3. **Decryption:** M = C^*d* mod *n* ## Worked Example **Setup:** - *p* = 3, *q* = 11 - *n* = 3 × 11 = 33 - φ(33) = 2 × 10 = 20 - *e* = 3 (since gcd(3,20) = 1) - *d* = 7 (since 3 × 7 = 21 ≡ 1 mod 20) **Encrypt** message M = 4: - C = 4³ mod 33 = 64 mod 33 = **31** **Decrypt** ciphertext C = 31: - M = 31⁷ mod 33 = 4 ✓ The message is successfully recovered!