Public Key Cryptography

Securing Computer Networks using Public Key

Symmetric Key Cryptographic Techniques getting obsolete with the increasing number of user over the Internet, public key cryptographic techniques came into existence and are playing a vital role in today's computer network.

In Public Key Cryptography, inspite of having a shared key between sender and receiver, there are 2 keys.
Let us Suppose, James is the sender and Steve is the receiver.
Steve will have 2 keys , one is Public Key- that is available to the whole world and the second is Private
Key- that is only known to Steve. We will use Us   for the public key of Steve and Ks   for the private key of Steve.


James in order to to send message to Steve securely, will 1st fetch the public key of Steve (that is known to everyone). Now James will encrypt message, m , using an encryption algorithm and the public key if Steve. That means, James will perform, Us (m). On receiving the encrypted message from James, Steve will use a decryption algorithm and his private key, to get the plain text. Steve will compute Ks(Us (m)). You can clearly see that, James and Steve can securely send message to each other, without sharing or distribution of any key ( that has to be done in Symmetric Key Cryptography).

But a problem arises in such cases. As the public key of Steve is well known to everyone around the globe, thus anyone can encrypt a message using using his public and send it to Steve, impersonating himself as James. In Symmetric Key cryptography, as sender and receiver share the key, they both are verified of each other identity. But this is no longer available in Public Key Cryptography, as the public key is known to everyone. Therefore, to overcome this problem of authentication, we have a phenomenon , known as Digital Signature, that I will discuss with you later.


Let us now start with some Public Key Encryption Algorithms.


RSA Encryption Algorithm


RSA was named after the scientists who developed it i.e. Ron Rivest , Adi Shamir , Leonard Adleman . Lets now see the working of of RSA. But before directly coming to the implementation of RSA, lets have a look at some mathematical calculations, as RSA makes a large use of modulo-n for computing and encrypting a data. In modulo,  if you compute A modulo n, then the result will be the remainder lest after dividing A by n. For example : If you compute 24 mod 5, the result will be 4. There are various operations associated with modulo. These are as follows.

• [( (a mod n) + ( b mod n )] mod n = (a + b) mod n

• [( (a mod n) - ( b mod n )] mod n = (a - b) mod n

• [( (a mod n) * ( b mod n )] mod n = (a * b) mod n

• ( ( a mod n)^d ) mod n = ( a^d) mod n

While you send a message to someone, it is nothing but a stream of bytes , that is following a bit pattern. And a bit pattern can be easily represented by an Integer. For Example : The bit pattern 0110 can be written as 6 , 1001 can be written as 9 and so on every bit pattern. Therefore, when you are encrypting a message using RSA, you are actually encrypting an Integer.

Now to generate a public key and a private key in RSA algorithm, Steve will perform the following steps :

1. Choose two large prime numbers  a and b.

Now a question arises, how large the numbers must be ? The answer is, as mush the numbers are large, the more harder is to break the RSA algorithm. But also, it will takes more time to compute encryption and decryption. Thus it is recommended that you use prime numbers of the order 1024 bits.

2. Calculate n = a * b and  y = ( a-1) * ( b-1 )

3. Select a number e , less than n ( e < n ) such that e and n doesn't have any common factor other than 1. Hence m and n are said to be as relatively prime.

e will be used in encrypting the message.

• 5 and 11 are relatively prime , as they have only 1 as common factor. 

4. Find a number z such that ez-1 is exactly divisible by y. We can also write it as that select z such that 

                                                         ez mod y =1.

z will be used decrypting the message.

5.  Now the public and the private key of Steve are ready. The public key , Us that will be available to the whole world is  ( n, e) and his private key , Ks is  ( n, z ).

\

James is sending a message m to Steve. Message will be represented by some integer that can be mathematically computed. Thus James will encrypt the message in this way.

Cipher text or Encrypted Message ( c ) = ( m^e ) mod n

The bit pattern corresponding to c, will be sent to Steve.

On the receiving side, to get the original message, Steve will decrypt it in the following way.

Plain text ( m ) = ( c^z ) mod n.

Let us take an Example that will make clear , how the RSA algorithm works.

Suppose James has a message , m=5 that he wants to send to Steve. So he start with RSA algorithm.

1. He chooses two prime numbers, say a = 17 and b = 7 .

2. Calculate n= a * b= 17 * 7 = 119 and y = ( 17-1 ) * ( 7-1 ) = 16 * 6 = 96.

3. Select e=5. Thus 5 and 119 are relatively prime.

4. To calculate in order to fulfill ez mod y=1. We will get z as 77. 

5. Therefore Steve public key = ( 119, 5) and private key = ( 119, 77). 

Thus while encrypting the message before sending it, James will do the following computation. 

Cipher Text ( c ) = ( m^e) mod n  = ( 5^5) mod 119 = 3125 mod 119 = 31

On the receiving side, while decrypting the cipher text, Steve will do the following computation.

Plain Text ( m ) = (c^z) mod n = ( 31^77) mod 119 = 5

So you must have noticed that , RSA is secure in the sense, there are numerous number of prime numbers are there for computation. Hence it will be a very brainstorming task for an Intruder to break the code and get the plain text.