The Notebook

Let's say that we have a message

For beginning, we examine

So, if

Another method that used from him -as an improved cipher- was

When the power of love overcomes the love of power the world will know peaceHere, we'll use previous key

**whent hepow erofl oveov ercom esthe loveo fpowe rthew orldw illkn owpea ce.**

**hnwte eohwp rfelo voove roemc sheet oelov pwfeo terwh rdowl lkinl weoap ec**

**hnwteeohwprfelovooveroemcsheetoelovpwfeoterwhrdowllkinlweoapec**

Caesar and soldiers of him used a kind of private method in between them. In other words, they had a deal to change locations of letters in phrase -or shift letters, before transmission of message. However, today's world is quite different.

For example, you would like to send an e-mail to one that you have never ever met before. Since this message travels on many different machines -routers, e-mail servers etc. you need to encrypt it as well. However, you can not use an approach like Caesar's transposition or key-shift at all, since your prospective receiver does not have any idea about what would you do.

For this reason, you need to express how would you encrypt your message -which should be a common technique that everyone knows. Third party may realize your technique as well, but still this technique needs to provide your privacy against her. Below, I provide most common

Let's suppose that I aim to send an e-mail to Bob. Also, assume that there is a third party who has an access to router in between me and Bob.

Here is a symbolic step-by-step pattern about operation:

- I send a signal message to Bob which denotes my communication intend and encryption approach.

Third party can realize the situation. - Bob produces
**public key**and**private key**. Consequently, he keeps private key for his own use and sends public key to me.

Third party can get this public key as well. - Afterwards, I use this public key to
**encrypt**my data(**M**) message than send encrypted version(**C**) of it to Bob. Third party can get this encrypted message as well, however can't decrypt -or we can say that he can't effortless decrypt, since he does not have the private key. - Alice receives encrypted message(C) and uses her private key to decrypt it

From now on, we break into math to support this symbolic pattern and follow the structure of RSA. There is no math in first step. Simply, I would only denote that "I would like to have communication with you and I'll use RSA encryption". Since

After obtaining my intention, Bob needs to produce

Say,

** p = 19, q = 11, n = 209**

I get my public key from Bob, which is

** \bmod(15^2, 209) = 16**

** \bmod(15^4,209) = \bmod( (209 + 16)(209 + 16), 209) = \bmod(16^2, 209) = 47**

** \bmod(15^8,209) = \bmod(15^{4} .15^{4}, 209)**

** \rightarrow \bmod( (209K + 47).(209K + 47), 209)**

** \rightarrow \bmod(47^2,209) = \bmod(2209,209) = 119**

** \bmod(15^{16},209) = \bmod(119^2,209) = \bmod(14161,209) = 158**

** C = \bmod(15^{29},209) = \bmod(15.47.119.158, 209) = \bmod(78.201, 209) = 3**

So, Bob and third party received my encrypted message

** \bmod(M^{ed}, n) = \bmod(C^{d}, n)**

Since

Let M be an integer. Let p and q be prime numbers which have different values. Then if

We can say that

So, Bob received C from me. Here we use, first small theorem than try to show that

Here we go for final time:

- If
**M**is a multiple of**p**,**\bmod(M, p) = 0**since**M = p.w**.

We can say that**M^{ed} = (p.w)^{ed} = p.p^{ed-1}.w^{ed} \rightarrow \bmod(M^{ed}, p) = \bmod(M, p)**.

Therefore, we have**\bmod(M^{ed}, p) = \bmod(M, p) = 0**

This is similar for**q**as well. If**M**is a multiple of**q**, then we have**\bmod(M^{ed}, q) = \bmod(M, q) = 0**

At the very beginning, we assumed that**M < p \times q**. By using this assumtion and**small theorem 2**, we can say that**\bmod(M^{ed}, pq) = \bmod(M, p.q) = M** - As a second case, we consider:
**p is not a divisor of M.**

**M^{ed} = M^{ed-1}. M**

**\rightarrow M^{(p-1).(q-1).k}. M**

**\rightarrow M^{(p-1)^{(q-1).k}}.M**

Here, we would consider**\bmod( M^{ed}, p) = \bmod( M^{(p-1)^{(q-1).k}}, p)**

From Fermat's Little Theorem, we know that, for any prime p and integer M**\bmod(M^{p-1}, p) = 1**

So,**\bmod( M^{(p-1)^{(q-1).k}}, p) = \bmod( (Kp + 1)^{(q-1).k}.M, p) = \bmod(M, p)**

The equations for second case would be exactly same for**\bmod(M^{ed}, q)**as well.

So, since**\bmod(M^{ed}, p) = \bmod(M,p)**and**\bmod(M^{ed},q) = \bmod(M,q)**, by using small theorem 2, we have**\bmod(M^{ed}, pq) = \bmod(M, pq)**Lastly, since we assumed that**M < p.q**, we can proudly say that**\bmod(M^{ed}, pq) = \bmod(M, pq) = M**which completes proof.

Here we numerically conclude as well:**C = 3**and**M = \bmod(C^{d}, n) = \bmod(3^{149}, 209) = 15**So, a third party should find prime coefficients of**n**-which are. If she could, she could get private key**d**as well and decode message just as receiver. However, since people generally uses huge numbers for**p**and**q**, it's hard to factorize**n**, which provides security of method.

- RSA, wiki page
- Matematik Dünyası, Sayı:71 -Turkish Popular Science Journal
- http://www.braingle.com/brainteasers/codes/caesar.php
- http://practicalcryptography.com/ciphers/simple-substitution-cipher/
- http://www.richkni.co.uk/php/crypta/trans0.php
- http://exploringnumbertheory.wordpress.com/2013/07/08/fermats-little-theorem-and-rsa-algorithm/