# Digital Media Concepts/RSA (cryptosystem)
## What is RSA

It is one of the first asymmetric cryptography algorithms which uses a pair of keys to encrypt and decrypt data. This algorithm is now widely used to transmit sensitive data over insecure network like the Internet.

## History

Before mid-1970s, people used symmetric cryptography algorithms to encrypt data. With these algorithms, data encrypted with a particular cryptographic key could only be decrypted with the same key. Anyone without the key cannot decrypt the data. Therefore people could safely send sensitive information through insecure communication channel. However, people could not find a way to safely exchange their keys between them. Asymmetric cryptography algorithms were invented to solve this problem, and RSA is one of them. In April 1977, RSA was invented by three people from Massachusetts Institute of Technology, including two computer scientists, Ron Rivest, Adi Shamir, and a mathematician Leonard Adleman, and was later publicized in August of the same year.
RSA is now in public domain, and can be freely implemented and used by anyone.

## Steps
#### Generate the keys

As an asymmetric cryptography algorithm, RSA cryptosystem involves two keys, the public key and the private key. Data encrypted by one key can only be decrypted with the other.
* Randomly choose two prime numbers, $p$ and $q$.
* Multiply them together: $n=p\cdot q$
* Get the least common multiple of $p-1$ and $q-1$: $\phi =lcm(p-1,q-1)$
* Randomly choose a positive integer $e$ which is less than $\phi$ and coprime to $\phi$.
* Calculate modular multiplicative inverse $d$ of $e$ modulo $\phi$. Which means, find a positive integer $d$ which is less than $\phi$ that satisfies: $e\cdot d\equiv 1{\pmod {\phi }}$
* Now the key pair is generated. $(d,n)$ is the private key, and $(e,n)$ is the public key

###### Sample Code

Here's a sample implementation of generating RSA keys written in Python 3.6

#### Send the public key to others

Let's say Alice and Bob want to have a secure communication. They may exchange their public keys without encryption. After that, a sender should always encrypt the data with the receiver's public key before sending it.
For example, Bob's data is encrypted with Bob's public key, and only people who know Alice's private key can decrypt the data. So Alice is the only person that meets this requirement. The same works with Bob.

#### Encryption and Decryption

* Let's say the original data is an positive integer $m$ which should be less than $n$. Encrypted data, positive integer $c$, can be generated with a public key: $c=m^{e}{\bmod {n}}$
* The encrypted data $c$ can be decrypted with the corresponding private key: $m=c^{d}{\bmod {n}}$

#### Proof of correctness
## Safety

The public key, which is $e$ and $n$, can be known to everyone. As far as $d$ is kept private, no one except the private key owner is able to decrypt the data encrypted by the public key. However, number $n$ has two prime factors $p$ and $q$. If one can find $p$ and $q$ by factoring $n$, then this person can also find out $\phi =lcm(p-1,q-1)$, and eventually $d$. So the problem of how safe RSA is, is equivalent to how hard it is to factor $n$.
It is proved that, currently with traditional (non-quantum) computer, factoring a big number is an NP problem. It may or may not be an NP-complete problem. RSA remains safe when integer factorization can't be solved in polynomial time.

## External Links

The original paper published by its inventors could be found here.