Introduction

  1. What is RSA?

    1. RSA (named after its inventors Rivest, Shamir, and Adleman) is an asymmetric cryptographic algorithm that uses a pair of keys:
      1. Public Key: Used for encrypting messages.
      2. Private Key: Used for decrypting messages.
    2. Its security is based on the difficulty of factoring the product of two large prime numbers.

  2. Key Concepts and Terminology

    1. Public key cryptography: Involves two keys, public and private.
    2. Prime numbers: Numbers only divisible by 1 and themselves.
    3. Modular arithmetic: Arithmetic done with a modulus (remainder).
    4. Euler’s Totient function (φ(n)): Number of integers less than n that are coprime to n.

  3. RSA Algorithm Steps

    1. Key Generation

      1. The most important part. You create the public and private keys here.

      2. Choose two large prime numbers: $p$ and $q$

        These should be large (hundreds of digits) and randomly chosen.

      3. Calculate $n = p \times q$

        $n$ will be used as part of both the public and private keys. It is the modulus for encryption and decryption.

      4. Calculate Euler’s Totient $\varphi(n) = (p - 1)(q - 1)$

        This value is used to determine the public and private exponents.

      5. Choose public exponent $e$ such that:

        1. $1 < e < \varphi(n)$
        2. $e$ and $\varphi(n)$ are coprime (i.e., $gcd(\varphi(n) = 1$)

        Common choice: $e = 65537$, because it’s a prime and efficient for computation.

      6. Calculate private exponent dd as the modular inverse of $e$ modulo $\varphi(n)$:

        $$ d \equiv e^{-1} \mod \varphi(n) $$

        This means:

        $$ (d \times e) \mod \varphi(n) = 1 $$

      7. Public key = $(n, e)$

      8. Private key = $(n, d)$

    2. Encryption
      1. To encrypt a message $M$ (where $M < n$) using the public key $(n, e)$:
      2. $C = M^e \mod n$
      3. Where:
      4. $M$ is the plaintext message represented as an integer.
      5. $C$ is the ciphertext (encrypted message).
    3. Decryption
      1. To decrypt ciphertext $C$ using the private key $(n, d)$:
      2. $M = C^d \mod n$
      3. This recovers the original message $M$.

  4. Why Does RSA Work?

    1. This relies on the mathematical property of modular exponentiation and Euler's theorem:

      $$ M^{\varphi(n)} \equiv 1 \mod n \quad \text{for } M \text{ coprime with } n $$

    2. Because dd is chosen such that $d \times e \equiv 1 \mod \varphi(n)$, raising M to the power of e and then dd modulo nn gets back the original M.

  5. Security of RSA

    1. RSA’s security depends on the difficulty of factoring the large number nn back into pp and qq.
    2. If an attacker can factor nn, they can compute φ(n)\varphi(n) and then dd, breaking the encryption.
    3. Hence, the primes pp and qq must be large (e.g., 2048 bits combined) to ensure security.

Examples

  1. RSA algorithm step-by-step with the primes:

    1. $p = 13$
    2. $q = 11$

  2. Step 1: Calculate $n = p \times q$

    $$ n = 13 \times 11 = 143 $$

    1. This $n$ will be part of the public and private keys.

  3. Step 2: Calculate Euler's Totient $\varphi(n)$

    $$ \varphi(n) = (p-1)(q-1) = (13-1)(11-1) = 12 \times 10 = 120 $$

  4. Step 3: Choose the public exponent $e$

    1. $e$ must satisfy:

      1. $1 < e < \varphi(n)$ → $1 < e < 120$
      2. $gcd$($e, 120$) = 1 (i.e., $e$ and 120 are coprime)

    2. Explanation:

      • Step-by-Step Guide

    3. Commonly used $e$ is 17, but let's check if 17 works:

    4. gcd(17, 120) = 1 → valid.

    5. So,

      $$ e = 17 $$

  5. Step 4: Calculate the private exponent $d$