Jacek Cichoń

Katedra Podstaw Informatyki ● WIT ● PWr
Main page For students

Proof of correctness of RSA protocol

Description of the protocol

  1. We fix two different prime numbers $p$, $q$.
  2. We count $n = p\cdot q$.
  3. We count $m = \phi(n) = (p-1)(q-1)$ ($\phi$ is the Euler "totient" function)
  4. We find a number $d\in\{2,\ldots,m-1\}$ such that $\gcd(d,m)=1$
  5. We find the number $e\in\{2,\ldots,m-1\}$ such that$d\cdot e = 1 \mod m$ (we use the extended Euclid's algorithm)
  6. We forget the numbers $p$, $q$, $m$.
  7. Private key: $(d,n)$
  8. Public key: $(e,n)$
  9. Encoding function: $E(x) = x^e \mod n$
  10. Decoding function: $D(x) = x^d \mod n$

Let us observe that functions $E$ and $D$ maps the set $\{0,\ldots n-1\}$ into $\{0,\ldots n-1\}$.

Example

  1. We take $p=1009$ oraz $q=1097$
  2. We have $n = 1106873$ oraz $\phi(n) = 1104768$.
  3. We count: $\gcd(2,1104768) = 2$; $\gcd(3,1104768) = 3$; $\gcd(4,1104768) = 4$; $\gcd(5,1104768) = 1$. Hence, we take $d=5$.
  4. We use the extended Euclid's algorithm to solve the equation $5 \cdot X + 1104768\cdot Y = 1$. We find one of its solution: $5\cdot 662861 + 1104768\cdot(-3) = 1$. Bierzemy więc $e=662861$
  5. PUBLIC KEY: $(5, 1106873)$
  6. PRIVATE KEY: $(662861, 1106873)$
  7. Encoding function: $E(x) = x^5 \mod 1106873$
  8. Decoding function: $D(x) = x^{662861} \mod 1106873$

Theorem

$$ (\forall x \in \{0,\ldots n-1\})(D(E(x)) = x) $$

Proof. Let us fix $x \in \{0,\ldots n-1\}$. Let us also fix a number $k$, such that $d\cdot e =1 + k \phi(n)$. Let us observe that $$ D(E(x)) = (x^{e})^{d} = x^{d e} \mod n~. $$ Therefore, we must show that że $x^{de} = x \mod n$.
We shall consider three cases

  • C1. If $x=0$, then $0^{de} = 0 \mod n$.
  • C2. If $\gcd(x,n) = 1$, then from Eulers's theorem we get $x^{\phi(n)} = 1 \mod n$. Hence $$ x^{de} = x^{1+k\phi(n)} = x \cdot (x^{\phi(n)})^k = x \mod n $$
  • C3. Suppose that $\gcd(x,n)\gt 1$. Then $p|x$ or $q|x$. Let us observe that numbers $p$ oraz $q$ cannot divide $x$ simultaneously. Therefore we may assume that, że $p|x$ and $\neg (q|x)$.
    Hence $x = 0 \mod p$, so $x^{de} = 0 \mod p$, hence $x^{de} = x \mod p$, Thereore $p|(x^{de}-x)$.
    From Fermat's Little theorem we get $x^{q-1} = 1 \mod q$. Hence $$ x^{de} - x = x^{1+k(q-1)(p-1)} - x = x\cdot (x^{q-1})^{k(p-1)} - x \equiv_q x \cdot 1^{k(p-1)} - x = x-x =0 ~, $$ so $q|(x^q-x)$.
    Therefore we have $p|(x^{de} - x)$ and $q|(x^{de}-x)$. Hence $(pq)|(x^{de}-x)$, so $x^{de} = x \mod n$.

$\square$

Exercise

Here is the ciphertext of a text:

03f824fd: 033c7a71: 050a6706: 050a6706: 03ffab5e: 03f824fd: 0189a78d: 005bca7d: 00734305: 04046ca6: 017698b6: 005bca7d: 03f824fd: 03d10ac0: 003622e4: 011c1c7e: 030cf03c: 011c1c7e: 03d10ac0: 01b60e5d: 03f824fd: 00734305: 007a18e6: 03ffab5e: 00734305: 0179f797: 037906bb: 050a6706: 007a18e6: 015d897d: 03f824fd: 037906bb: 03f824fd: 0451f198: 059ff1e0: 03d10ac0: 02e6b154: 037906bb: 03f824fd: 00734305: 003622e4: 011c1c7e: 0414fa45: 03f824fd: 00a6891a: 042edbee

The text has been encrypted with your public key. It is known that all letters were encoded separately (first converted to UTF-8 codes, then the numbers were raised to some power modulo 101080891 and the numbers were written in hexadecimal format and joined into a single string, separating the individual strings with a colon. Your private key is (2062465, 101080891).
  1. Decode this text.
  2. Find the factorization of the number $101080891$ into primes.
  3. What is your public key?
Main page For students