# RSA(Rivest–Shamir–Adleman) Encryption System

*What is Cryptography?*

Cryoptography is the method of keeping information secret by converting it to a form that only desired recepient can undestand and use it. That is, it turns a simple plain text message to unintelligible text. Intended user of that message can convert it back to plain text and use it. For this whole process, the source and user of message should establish a method for encrypting and decrypting the message.
RSA is a cryptographic algorithm which is also known as *Public Key cryptography, Asymmetric cryptography*

Why *Encryption* is needed in a communication network?
* Ensure secure transfer of message/ stop unwanted interception of message
* Prevent modification (insert/delete) of the message or parts of it
* Mitigate spoofing of source address in a packet
* Mitigate risks of hijacking any ongoing communication and replacing the sender/receiver
* Ensure service to the users. An wanted used may prevente service from being used by others by overloading resources.

### What is RSA?
RSA is an algorithm to encrypt and decrypt messages so that only intended receiver can decrypt the message.

It involves two different keys (that's why it's asymmetric algorithm) - public and private. The message is *encrypted using the public key* which can be shared with anyone. This encrypted message can be decrypted *only* using the *private key* which is only available to the receiver.

**Who can be a sender/receiver?**
* Any person
* Web browser/server (e.g. online transactions)
* online banking client/server
* DNS servers
* Routers exhcanging routing table updates
* Updating database information etc

### How does RSA work?

**Steps In Simple Words**
*source: Computer Networking: A Top Down Approach (6th Edition) by Jim Kurose, Keith Ross Addision-Wesley*

**1.** Public/Private keys are generated
* Select 2 prime key numbers p,q (e.g. 1024 bits each). The larger the numbers, the harder it is to figure them out.
* Calculate x = p * q and z = (p-1) * (q-1)
* Select e such that e is co-prime to z and 1 < e < z
* Pair (n, e) makes up *public* key
* Calculate d such that e * d = 1 mod z
* Pair (n, d) makes up *private* key
**2.** Plaintext message is encrypted using the public key of sender (which is known to receiver as well)
* PlaintextP, represented as a number is calculated as cipher text, C.
* C = P^e mod n
**3.** The ciphertext C is received by intended user Bob
**4.** Using Bob's private key, (n, d) which is only known to Bob, the ciphertext is decoded to acquire the original plain text message by Bob
* P = C^d mod n

[**Pseudocode**](https://play.golang.org/p/X6ufpwaSdbQ)

**Mathematical Explanation**
RSA mechanism works by the *Diffie–Hellman key exchange scheme*. Check [this video](https://www.youtube.com/watch?v=64geP_LAZ5U) for understanding of the mathematics behind this.

### Why RSA for encryption?

1. In case of using simple substitution encryption (monoalphabetic), encryption can be easily decrpyted.
2. There are different encryption methods available among which RSA has proved to be a hard one to crack making it a widely used algorithm
3. In RSA, encrypted data doesn't have obvious formatting like substitution encryption which makes it hard to decrypt
4. To make RSA more secure padding schemes like OAEP may be added to it.
**Padding** is adding randomized data to hide original formatting clues that could lead to an encrypted message being broken
1. RSA can be used for signing messages besides encryption.
**Signing** means confirming that a message -
* has been sent by the entity who claims to have sent it
* not been altered or tampered with

### RSA for future?
1. RSA encryption needs to be implemented correctly for it to be safe
2. Key must be at least 1024 bit

### Practical Usage

* RSA is often used in combination with another encryption scheme. RSA isn't used to encrypt a whole file as it is *less-efifcient* and *more resource-heavy*. Rather a file would be encrypted with a symmetric key, then the key would be encrypted with RSA.

#### Links
1. Computer Networking: A Top Down Approach (6th Edition) by Jim Kurose, Keith Ross Addision-Wesley
2. [What is RSA](https://www.educative.io/edpresso/what-is-the-rsa-algorithm)
3. [RSA Encryption](https://www.comparitech.com/blog/information-security/rsa-encryption/)
4. [RSA wikipedia](https://simple.wikipedia.org/wiki/RSA_algorithm)
5. [Cryptography with RSA](https://www.tutorialspoint.com/cryptography_with_python/cryptography_with_python_understanding_rsa_algorithm.htm)
6. [Extended Euclidean algorithm](https://sites.millersville.edu/bikenaga/number-theory/extended-euclidean-algorithm/extended-euclidean-algorithm.html)
7. [Inverse modulo calculator](https://www.omnicalculator.com/math/inverse-modulo#:~:text=For%20every%20number%20x%20from,remainder%20is%20equal%20to%201%20.)
8. [Diffie-Hellman](https://www.youtube.com/watch?v=64geP_LAZ5U)