I have got following example at the lecture, however we went through it quite fast.
I understand the calculation of the following inverse modulo: 7 · 103 = 1 (mod 120).
However here I am puzzled with inverse modulo. How come the result is 53 In $C_1$ and $115$ in $C_2$ ? :
$C_1$ =$M_1^e \pmod n = 14^7 \pmod {143} = 53$
$C_2 =M_2 ^ e \pmod n=15^7 \pmod {143}=115$.
RSA cryptography (III)
1 Alice chooses two prime numbers, say $p = 11$ and $q = 13$, and computes pq = 143.
2 She chooses a positive integer $e$ that is relatively prime to $(p-1)(q-1)$. In this
case, $(p-1)(q-1) = 10·12 = 120$, so she may take $e = 7$ (note $120 = 2^3 ·3·5$).
3 Now she thinks of an integer $d$ such that $d$ is an inverse of $e$ modulo
$(p-1)(q-1)$. In this case , $d = 103$. Note that, indeed by inverse formula $ed=1 \pmod n$
$7 · 103 = 1 \pmod {120}$.
Public key: $(e, n) = (7, 143)$.
Secret key: $(p, q, d) = (11, 13, 103)$.
Example Given an RSA cipher with public key $(e, n) = (7, 143)$, encrypt the message
“NO”.
“N” is encoded as $M_1 = 14$ and
“O” as $M_2 = 15$
So the encryption of the message are the following two blocks
and
$C_1 =M_1 ^ e \pmod n=14^7 \pmod {143}=53$;
$C_2 =M_2 ^ e \pmod n=15^7 \pmod {143}=115$.
Best Answer
$$ 14^7 = 14^4\cdot 14^2\cdot 14^1, $$ $$ 14^1 \equiv 14 (\bmod 143), \\ 14^2 \equiv 14^1\cdot 14^1 = 14\cdot 14 = 196 \equiv 53 (\bmod 143), \\ 14^4 \equiv 14^2\cdot 14^2 \equiv 53\cdot 53 = 2809 \equiv 92 (\bmod 143); $$
$$ 14^7 \equiv 92\cdot 53 \cdot 14 = 92\cdot 742 \equiv 92 \cdot 27 = 2484 \equiv 53 (\bmod 143). $$
$15^7 (\bmod 143)$ $-$ the same way.
Decryption.
Following Euler's theorem, we have $$ x^{\varphi(n)} \equiv 1 (\bmod n), $$ where $GCD(x,n)=1$.
Now,
So, one can write $$ (M^e)^d = M^{k\varphi(n)+1} =(M^{\varphi(n)})^k\cdot M^1 \equiv M (\bmod n) $$ where $GCD(M,n)=1$. If $GCD(M,n)\ne 1$, then it must be considered more accurate.
Decrypting of $C_1=53$:
$$ M_1' \equiv C_1^d (\bmod n) $$
$$ M_1' \equiv 53^{103} (\bmod 143). $$
A few steps:
First, decompose $103$ as sum of powers of $2$: 103 = 64+32+4+2+1 = 2^6+2^5+2^2+2^1+2^0.
So, $53^{103} = 53^{64}\cdot 53^32\cdot 53^4\cdot 53^2\cdot 53^1$.
a) $53^1 \equiv 53 (\bmod 143)$;
b) $53^2 = 53^1\cdot 53^1 \equiv 53\cdot 53 = 2809 \equiv 92 (\bmod 143)$;
c) $53^4 = 53^2\cdot 53^2 \equiv 92\cdot 92 = 8464 \equiv 27 (\bmod 143)$;
d) $53^8= 53^4\cdot 53^4 \equiv 27\cdot 27 = 729 \equiv 14 (\bmod 143)$;
e) $53^{16}= 53^8\cdot 53^8 \equiv 14\cdot 14 = 196 \equiv 53 (\bmod 143)$; (see a) )
f) $53^{32}= 53^{16}\cdot 53^{16} \equiv 53\cdot 53 = 2809 \equiv 92 (\bmod 143)$; (see b) )
g) $53^{64}= 53^{32}\cdot 53^{32} \equiv 92\cdot 92 = 8464 \equiv 27 (\bmod 143)$.
Finally,
$M_1' = 53^{103} = 53^{64}\cdot 53^{32}\cdot 53^4\cdot 53^2\cdot 53^1 \equiv 27\cdot 92 \cdot 27 \cdot 92 \cdot 53 \equiv 14 (\bmod 143)$.
Note, that $M_1' = M_1 (\bmod n)$. $M_1$ $-$ original number; $M_1'$ $-$ decrypted number.