RSA Example

COMP315 Lectures 2023-03-03

Computing Keys

Take $p=7, q=11$.

1. Therefore $n=pq=77$ and $m=(p-1)(q-1)=60$.
2. Choose $e$ where $\text{gcd}(e, 60)=1$. $e=7$ works in this case.
3. To compute $k=e^{-1}\mod 60$:
   1. $9\times7=63=3\mod60$.
   2. \[\begin{aligned} 1&=7-2\times3\\ &=7-2\times(9\times7)\\ &=1-18)\times7\\ &=-17\times7\mod60 \end{aligned}\]
   3. Therefore $7^{-1}=-17=43\mod60$.

Encryption

Given that the public keys are $n=77,e=7$ and the private key is $k=43$, we wish to encrypt $x=3$:

1. Calculate $x^e\mod 77$.
2. This equals 31.

We can reduce the number of multiplications in the exponent by halving the power:

\[\begin{aligned} c&=3^7\mod n\\ &=3^3\times3^3\times^1\mod 77 \end{aligned}\]

Decryption

\[x=c^k\mod n\]