Number Theory Home

## RSA Cryptography

Alice wants to send a secure message to Bob where the message is converted from a plaintext to an integer $$m$$ which can be done by ASCII codes: A is 065, B is 066,..., Z is 090, full stop is 046, space is 032, 0 is 048, 1 is 049,..., 9 is 057 etc.

1. Key Generation: Bob has a public key $$(n,e)$$ where $$n>m$$ is a product of two large primes (only known to Bob) and $$e$$ is in $$(1,\phi(n))$$ and relatively prime to $$\phi(n)$$. Bob also has a private key $$d$$ (only known to Bob) in $$(1,\phi(n))$$ which satisfies $$ed\equiv 1 \:\left(\mathrm{mod}\:\phi(n)\right)$$.

2. Encryption: Alice uses Bob's public key $$(n,e)$$ and calculates the ciphertext $$c\equiv m^e \:\left(\mathrm{mod}\: n \right)$$. Alice sends $$c$$ to Bob.

3. Decryption: Using $$c$$ and his private key $$d$$, Bob calculates $$c^d \:\left(\mathrm{mod}\: n \right)$$ which turns out to be $$m\equiv m^{ed}\equiv c^d \:\left(\mathrm{mod}\: n \right)$$, the original message (why?).

Theorem. Let $$n=pq$$ where $$p$$ and $$q$$ are distinct primes. Suppose $$e$$ and $$d$$ are integers in $$(1,\phi(n))$$ such that $$ed\equiv 1 \:\left(\mathrm{mod}\: \phi(n)\right)$$. Then for any positive integers $$m < n$$ relatively prime to $$n$$, we have $$m^{ed}\equiv m \:\left(\mathrm{mod}\: n \right)$$.

Proof. Consider a positive integers $$m < n$$ relatively prime to $$n$$. By the Euler's Theorem $$m^{\phi(n)}\equiv 1 \:\left(\mathrm{mod}\: n \right)$$. Since $$ed\equiv 1 \:\left(\mathrm{mod}\: \phi(n)\right)$$, $$ed=1+d\phi(n)$$ for some integer $$d$$. Then $m^{ed}\equiv m^{1+d\phi(n)}\equiv m^1(m^{\phi(n)})^d \equiv m^1(1)^d\equiv m \:\left(\mathrm{mod}\: n\right). ◼$

In case $$m$$ is not relatively prime to $$n=pq$$, $$m$$ is one of $$n-1-\phi(n)=p+q-2$$ integers in $$[1,n)$$. The probability of choosing such $$m$$ is $$\displaystyle\frac{p+q-2}{pq}= \frac{1}{p}+\frac{1}{q}-\frac{2}{pq}$$ which is very small.

To find $$d$$ in $$(1,\phi(n))$$ satisfying $$ed\equiv 1 \:\left(\mathrm{mod}\:\phi(n) \right)$$, note that $$xe+y\phi(n)=\gcd(e,\phi(n))=1$$, i.e., $$xe\equiv 1 \:\left(\mathrm{mod}\: \phi(n)\right)$$. We find the unique solution $$x=d$$ by the extended Euclidean algorithm.

Example. Alice converts the plaintext "NO" to $$m=078\;079$$. Bob has public key $$(n,e)=(295927,\; 1081)$$. Alice uses Bob's public key $$(n,e)$$ and calculates the ciphertext $$c\equiv m^e \:\left(\mathrm{mod}\: n \right)$$, i.e., $$(078\;079)^{1081}\equiv 120818 \:\left(\mathrm{mod}\: 295927 \right)$$. Alice sends $$c=120,818$$ to Bob. Now Bob has produced his public key $$(n,e)$$ with this secret calculation: $n=pq \text{ for } p=541 \text{ and } q=547 \text{ where } e=1+2*(p-1)=1081.$ Now Bob calculates his private key $$d=160921$$ for which $$ed\equiv 1 \:\left(\mathrm{mod}\: \phi(n) \right)$$. To decrypt Alice's ciphertext, Bob calculates $$c^d \:\left(\mathrm{mod}\: n \right)$$, i.e., $$(120,818)^{160921}\equiv 78079 \:\left(\mathrm{mod}\: 295927 \right)$$. Note that $$e=1081$$ is known to be relatively prime to $$\phi(n)=294,840$$. But it is hard to calculate Bob's private key $$d$$ for which $$ed\equiv 1 \:\left(\mathrm{mod}\: \phi(n) \right)$$.

Why is it a good cryptosystem?
Suppose that some third party gains access to the number $$c$$. In order to recover the number $$m$$ he has to extract the $$e$$th root of $$c$$ modulo $$n$$. There seems to be no other feasible method for this than to find the number $$d$$, and for that he need to know $$\phi(n)$$, and for that he has to factor the number $$n$$. But factorization of integers with 1000 binary digits seems to be beyond the reach of most of today's algorithms and computers.

Last edited