Primes and cryptography · Definition

RSA cryptosystem

elementary number theoryprimes and cryptography

Before you start you need to know

RSA lets anyone encrypt messages with a public key, while only the holder of the private key can decrypt them. Its security relies on factoring n = pq being computationally hard.

Definition

The RSA cryptosystem is a public-key encryption method based on the difficulty of factoring the product of two large primes. It uses Euler's theorem and modular inverses to encrypt and decrypt messages.

\[c \equiv m^{e} \pmod{n}, \quad m \equiv c^{d} \pmod{n}\]

Let \( p \) and \( q \) be distinct primes, \( n = pq \) and \( \varphi(n) = (p-1)(q-1) \). If we choose \( e \) with \( \gcd(e, \varphi(n)) = 1 \) and compute \( d \) as the modular inverse of \( e \) modulo \( \varphi(n) \), then \( m^{ed} \equiv m \pmod{n} \) for all \( m \), by Euler's theorem and the Chinese remainder theorem.

With \( p = 3 \), \( q = 11 \) we have \( n = 33 \) and \( \varphi(n) = 20 \). Taking \( e = 3 \), the inverse of 3 modulo 20 is \( d = 7 \), so the message \( m = 4 \) encrypts as \( c \equiv 4^3 \equiv 31 \pmod{33} \) and decrypts as \( 31^7 \equiv 4 \pmod{33} \).

A typical error is computing d as the inverse of e modulo n instead of modulo \( \varphi(n) \). With \( n = 33 \) and \( e = 3 \) that inverse does not even exist, since \( \gcd(3, 33) = 3 \), so the exponent must be worked modulo \( \varphi(n) \).

Think about it

Why must d be computed modulo \( \varphi(n) \) and not modulo \( n \)?

Because \( ed \equiv 1 \pmod{\varphi(n)} \) is what makes Euler's theorem work; with \( n = 33 \) and \( e = 3 \) no inverse even exists.

Exercises 10

  1. Which modulus is used to compute the exponent d in RSA?
  2. If p = 5 and q = 7, what is the value of n?
  3. For p = 5 and q = 7, what is the value of φ(n)?
  4. What condition must the public exponent e satisfy in RSA?
  5. Which theorem guarantees that \( m^{ed} \equiv m \pmod{n} \) in RSA?
  6. With p = 3, q = 11 and e = 3, find d such that 3d ≡ 1 (mod 20).
  7. With n = 33 and d = 7, what is the decryption of c = 31?
  8. If e = 5 and φ(n) = 24, what is the modular inverse d of e?
  9. With p = 5 and q = 11, compute φ(n) and the smallest valid exponent e = 3.
  10. With \( p = 3 \), \( q = 11 \) and \( e = 7 \), check whether \( e \) is valid, find \( d \), and verify that \( 4^{ed} \equiv 4 \pmod{33} \).

References

  • David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 10
  • Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 2