Kıvanç's Pancake House
İstanbul, Turkey

Notes on Cryptology

None of us would like to have third party who is able to sense our message. For this reason we usually change -technically encrypt, our message in a way that third party can not realize, whereas our communication partner can, since he is aware of how we changed it.

Let's say that we have a message M. Instead of directly transmitting it, we use a function E(M) = C to encrypt it. Even third party has an access to C. However, she can't get M from C since she is not aware of our encryption function. However, our destination has a function, that produces M from this encrypted C. Mathematically speaking, this one is called as decryption function which is an inverse of encryption function: D( E(M) ) = D(C) = M

For beginning, we examine Substitution Cipher method which used by Julius Caesar. The method is quite simple: substitute each letter in phrase with N shift.



Roman Emperor Julius Caesar. BC 44 – BC 100


So, if N = 1 and Caesar wants to say "hello" to his soldiers, had written "ifmmp" on paper, then sent. Third party would get encrypted version of message and could not understand what he was saying, whereas his soldiers could, since they know encryption method of their Emperor.

Another method that used from him -as an improved cipher- was Transposition Cipher. So instead of shifting each character, he uses a key to change locations of letters. Here we need to have a key. Let's assume that our key is 24153. So, our "hello" becomes "elhol". This seems useless for only "hello". However let's say that he has a longer phrase:

When the power of love overcomes the love of power the world will know peace

Here, we'll use previous key 24153. So, if we parse our message for each consecutive 5 letters, we would have:

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

and encrypted version with key would be:

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

If Caesar would also not use blank-spaces after encryption, message becomes harder to understand:

  • hnwteeohwprfelovooveroemcsheetoelovpwfeoterwhrdowllkinlweoapec



American musician Jimi Hendrix
(November 1942 – September 1970)


In summary: Transmitter encrypts his message M before sending with key K_1 and produces C. Consequently, receiver uses his key K_2 to decrypt it. If those keys are same -such as in last example, we call this procedure as symmetric cryptosystem. On the other hand, if they are not equal, we call this as asymmetric crpytosystem.

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 public key algorithm developed by Ron Rivest, Adi Shamir and Len Adleman which named RSA.



Adi Shamir, Ron Rivest and Leonard Adleman on curve,


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:

  1. I send a signal message to Bob which denotes my communication intend and encryption approach.
    Third party can realize the situation.

  2. 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.

  3. 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.

  4. 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 RSA is commonly used, he knows how to follow step's of it.

Here we start from Step 2.

After obtaining my intention, Bob needs to produce public key for my encryption and private key for his decryption. In order to produce a public key, Bob selects two different prime numbers p and q, then calculates modulus n = p.q
Say, p = 19, q = 11, n = 209.

Afterwards, he computes \phi(n) which is called totient function of n and gives amount of numbers that are smaller than n and relatively prime with n.

Since p and q are prime numbers, we can say that \phi(n) = (p-1).(q-1). If you are not comfortable with value of \phi(n), you could check the link that I provide for totient function. Otherwise, go on. \phi(209) = 180.

Following, he selects an integer e where 1 < e < \phi(n) and gcd(e, \phi(n)) = 1. Let's assume e = 29. Here, public key is (n,e) pair, where Bob sends me to use for encryption. For his decryption purposes, Bob needs a private key (d) which satisfies \bmod(e.d, \phi(n)) = 1. Value d is also called as multiplicative inverse of e modulo \phi(n) and d = 149 satisfies for numbers above.

Now we are in Step 3.

I get my public key from Bob, which is (n,e). Here undesirable third party also aware of what public key is. Consequently, I produce encrypt version C of my message M by using public key. Here my message M should be less than my modulus, M = p.q. In practice people use huge numbers for p and q, which increases security of method. So, my M is an integer, if it is greater than n, I can first parse then send it etc. Followingly, I encrypt my message C = \bmod(M^e, n). Let's assume that I would like to send a single integer as a message, which equals to 15. So, E(15) = C = \bmod(15^{29}, 209) .

Since calculating 15^{29} might take significant amount of time, we need to get benefits of modular arithmetic:

\bmod(15^2, 209) = 16

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

Similarly,

\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

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

Finally we are in Step 4.

So, Bob and third party received my encrypted message C. Here, they both would try to get message (M) from it. Here, we prove that Bob can get it by using his private key. Before doing so, we need proof of two following little theorems.

Small Theorem 1:

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

Small Proof 1:

Since C = \bmod(M^e, n), we can say that M^e = K.n + C. Therefore, \bmod(M^{ed}, n) = \bmod((KN + C)^d, n) = \bmod(C^d, n)

Small Theorem 2:

Let M be an integer. Let p and q be prime numbers which have different values. Then if \bmod(a, p) = M and \bmod(a,q) = M equation \bmod(a, p.q) = M should also satisfy.

Small Proof 2:

We can say that a = M + p.i and a = M + q.j. So, p.i = q.j. This implies that, q.j is a multiple of p. We also now that, p can not be a divisor of q, since they both are prime and they have different values. So, we can say that, j = p.K hence a = M + q.p.K Following, we conclude this small proof: \bmod(a, p.q) = \bmod(M + q.p.K, p.q) = M.

Now we are so close to conclude working principle of RSA!

So, Bob received C from me. Here we use, first small theorem than try to show that \bmod(M^{ed}, n) = M. If we can, we conclude!.

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.

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