# RSA asymmetric key encryption protocol

### what is encryption ?

we want to send message to recepient without revealing it to the network

### what does is it mean by asymmetric key ?

it means there are two keys involved in the encryption protocol, one is the public key and other is called the private key

### algorithm details

### Short idea

- let p and q be two very large prime numbers, and N = p*q
- since two primes are distributed apart by N/logN gap it shouldn't be computationally hard to generate these
- phi(N) be the euler totient function
- we know that a^(phi(N)+1) = 1 (mod N)
- i.e we know a^(k* phi(N)+1 ) = 1 (mod N)
- if we could break k.phi(N)+1 into two smaller numbers c & d then we could use it for decryption and encryption

### Long idea

- Let M be the message encoded as a single number less than N
- we call N the modulus and let's say M and N are relatively prime, this can be ensured by picking N as prime
- By euler's theorem we can say that M^(phi(N)) = 1 (mod N)
- let us choose a random number e, then M^e is the encrypted message
- here (e, N) are known to the public
- let d = e^(-1) (mod phi(N))
- that is e.d = 1 (mod phi(N))
- so now to decrypt a message we just have to raise M^e to d . i.e the actual message M = (M^e)^d mod N
- the above holds true because since e.d = 1 mod phi(N), M^e.d = 1 mod N
- a^b^c mod N = a^ (b^c mod phi(N)) modN (you might remember this from some cp problem)

- phi(N) = (p-1)*(q-1)

Usually p = 2^16 +1 = 65537