RSA Explained: Intro for Layman, Number Theory Basics

[matqkks]

I am looking for any resources which explain the RSA algorithm for the layman. I have found a number of sources but they all tend to end with a morass of technical details. This is for a first year undergraduate course in number theory who have covered some basic work on modular arithmetic.

 

[I like Serena]

I am looking for any resources which explain the RSA algorithm for the layman. I have found a number of sources but they all tend to end with a morass of technical details. This is for a first year undergraduate course in number theory who have covered some basic work on modular arithmetic.

Hi matqkks,

It seems to me the explanation here is about as simple as it gets.Long story short, we encrypt numbers $m$ with the public key as:
$$\text{encrypted number} = m^{\text{public key}} \bmod n$$
and we decrypt them with the private key:
$$m = \text{encrypted number}^{\text{private key}} \bmod n$$
where $n = pq$ is the product of 2 large prime numbers.The schema hinges on the fact that it's very difficult to find $p$ and $q$ given $n$.
The article explains how to get a $(\text{public key}, \text{private key})$ pair given $p$ and $q$.
It also means that anyone can encrypt a message, but only someone with access to the $\text{private key}$ can decrypt a message.

 

[johng1]

I agree completely with the previous post. You should read the Wikipedia article. Using the notation there, given an integer x, the encoded x is $x^e\text{ mod}(n)$ The decoding $f$ is such that $ef\equiv1\text{ mod}(\phi(n))$ Then for $x$ prime to $n$, $x^{ef}\equiv x\text{ mod}(n)$. However, it should still work for x's not prime to n. You might try your hand at this. Hint: the Chinese remainder theorem is helpful.