# Public Key Cryptography

Cryptography is the art of protecting information by encrypting it into an unreadable format, called cipher text. The person with the secret key can decrypt the cipher text back into plain text. Cryptography can be traced back to Julius Caesar days. Caesar used shift cipher to protect his private correspondence. In the example given below I am using a right shift of 1. In this a -> b , x -> y etc…

```Plain Text  : cryptography is hard
Cipher Text : dszquphsbqiz!jt!ibse```

This type is called as Symmetric Key Algorithm. It uses the same key for both encryption and decryption. The keys can be identical or there may be a simple transformation to go between the two keys. Caesar shift cipher can be broken with a quick glance and hence it is not used in practice. The common symmetric key cryptography used today are AES, DES, Triple DES. Given below is a simple python code using caesar cipher with shift 1. The output of encrypt function is the input to the decrypt function and both of them use the same key. This is why it is called as symmetric.

```def encrypt(plainText,shift):
cipherText = ''
for i in plainText:
cipherText += chr(ord(i) + shift)
return cipherText

def decrypt(cipherText,shift):
plainText = ''
for i in cipherText:
plainText += chr(ord(i) - shift)
return plainText

key = 1
plainText = 'this is a test'
assert plainText == decrypt(encrypt(plainText,key),key)

plainText = 'cryptography is hard'
assert plainText == decrypt(encrypt(plainText,key),key)
```

## Challenges

The main challenge with symmetric key cryptography is the key itself. If Alice and Bob wants to communicate securely they need to exchange the keys. How do they exchange the key securely? If they have a channel to exchange it securely then why not use the same channel to communicate the actual information? Why not exchange the keys in person? That will not work for Internet scale. We need a better solution.

## Solution

In public key cryptography you have 2 keys. One is private and the other one is public. If Alice wants to send information securely to Bob

1. Bob creates 2 keys. 1 private which Bob keeps it with himself. 1 public which is known to everyone.
2. Alice uses the public key and encrypts the message and then sends it to Bob.
3. Bob gets the encrypted message and using the private key decrypts the message. Only Bob can decrypt as he has the private key.

## How does it work

1. RSA is one implementation of public key cryptography.
2. Bob selects 2 prime numbers P = 23 and Q = 41. In practice it is going to be much larger. The reason for that is given in Number Sense.
3. The 2 prime numbers are multiplied N = P * Q => 23 * 41 = 943. This is one part of the Public Key
4. Bob choses another number e which is relatively prime to (P – 1) * (Q – 1). In this case it is (23 – 1) * (41 – 1) => (22) * (40) = 880. Let e be 7.
5. e is also a part of public key. The public key is (e,N)
6. Now Alice wants to encode a message M = 35
7. Using the public key C = M ^ e (MOD N) where C is the cipher text. This becomes 35 ^ 7 MOD 943 = 545. Hence this encrypted message 545 is sent to Bob.
8. Bob needs to decrypt the message for which he needs a secret key which is d. To calculate e * d = 1(MOD (P – 1)*(Q – 1)) => 7 * d = 1 MOD (880). One solution is d = 503. (d,N) is the private key
9. Bob uses M = C ^ d (MOD N). This becomes (545 ^ 503) (MOD 943) = 35 which is the original message.

## Why does this work

There are several mathematical concepts that are in play for this to work.

1. Modulo Arithmetic
2. Greatest Common Divisor
3. Prime Number Factorization and Relative Primes
4. Fermat Little Theorem
5. Euler’s Totient Theorem
6. Exponents

```C = M ^ e (MOD N) -> Encryption
D = C ^ d (MOD N) -> Decryption

Substituting the value of C in Decryption we get

D = (M ^ e) ^ d (MOD N)
D = (M ^ ed) (MOD N)

Since we know that the result of decryption is the original message

(M ^ ed) (MOD N) = M```

Let us see why is this true?

Fermat’s little theorem states that if p be a prime which does not divide the integer a, then a ^ (p-1) = 1 (MOD p).

Euler’s Totient Theorem states that if GCD(T,R) = 1 and T < R then T ^ phi(R) = 1 (MOD R)

1. GCD(T,R) = 1 means there are no common divisors between T and R. In other words they are relatively prime. One example is 2 and 7.
2. phi(R) means total numbers between 1 and R – 1 that are relatively prime to R. Given below is a simple python code to calculate phi of any number.
```import fractions
def phi(n):
p = 1
i = 2
while i < n:
if fractions.gcd(i,n) == 1:
p = p + 1
i = i + 1
return p
```
1. Multiply Euler’s totient theorem by T both sides we get (T ^ phi(R)) * T= T * 1 (MOD R) => T ^(phi(R) + 1) = T (MOD R)
2. In our example R = N => P * Q. What is phi(P * Q) if both P and Q are prime. It is (P – 1) * (Q – 1)
3. Remember we calculated e * d = 1(MOD (P – 1)*(Q – 1)). This was done for a reason.
4. So (M ^ ed) can be written as M ^ ((P – 1) * (Q – 1) + 1) => M ^ ((P – 1) * (Q – 1)) * M = M (MOD N)

Finally we got the message M back.

## Symmetric and Public Key Cryptography

In the Internet let us see how this works.

1. Let us imagine we have a secure website. It creates 2 keys 1 private and the other one public.
2. The client will get the public key, generate a secret key(symmetric) and using the public key it will encrypt the secret key.
3. The website receives the encrypted secret key and decrypts it with the private key and will get the decrypted secret key.
4. During the rest of the conversation between the client and the website all the messages will be encrypted/decrypted with the symmetric secret key.

Thus public key cryptography solves the problem of key exchange and makes Internet a secure place to communicate.