RSA with p=5 and q=7

Question

With $p=5$, $q=7$, $e=5$: compute $n$, $\varphi(n)$, $d$, and use RSA to encode and decode $m=2$.

Solution

Keys. $n = pq = 35$; $\varphi(n) = (p-1)(q-1) = 4\cdot 6 = 24$. The public exponent is $e=5$ (coprime with $24$). The private exponent $d$ satisfies $5d\equiv 1\pmod{24}$: since $5\cdot 5 = 25 = 24+1$, we have $d = 5$.

Encoding of $m=2$: $c = m^e\bmod n = 2^5\bmod 35 = 32.$

Decoding of $c=32$: $m = c^d\bmod n = 32^5\bmod 35.$ It is convenient to use $32\equiv -3\pmod{35}$: $(-3)^5 = -243$, and $243 = 6\cdot 35 + 33$, so $-243\equiv -33\equiv 2\pmod{35}$. We recover $\boxed{m=2}$, as expected.

Links

Topics: Probability distributions
Concepts: Modular arithmetic · RSA cryptography
Methods: RSA encryption
Skills: Computing · Using formulae
Exercise type: Probability problem