To understand what public key cryptography really is and its advantages, we must first differentiate between two broad categories of encryption, namely Symmetrical and Asymmetrical encryption systems. Symmetric encryption system makes use of a single key, widely referred to as the ‘common key’. The sender of the message makes use of this unique Common key to encrypt the plaintext to ciphertext and the receiver uses the same key to decrypt it back to plaintext. A recipient will have different common keys with different senders.
However, Public Key Cryptography (PKC) is a form of asymmetric encryption that makes use of two separate sets of keys — a public key and a private key. Here, for the sender to encrypt the plaintext, he must first procure the recipient’s public key, using which the sender encrypts the message into a secure ciphertext format. The recipient, then, uses his/her own private key to decrypt this message into plaintext. The algorithms for setting up a PKC system is such that even if the public key is known to a third party, it is nearly impossible to get the private key. Thus, because of this, the public key of the recipient can be disseminated widely and yet the whole process remains secure. It is important to note that each set of public key and private key is unique and differs from sender to sender.
Why do we prefer PKC systems over that of symmetric cryptography?
For any encryption system, there are two requirements that are to be met — Key distribution and Key management. Asymmetric is superior to symmetric cryptography system when it comes to key distribution. Take the following example.
In a symmetrical system of n users, whenever a new user joins the system, he/she must issue a common key with each of the previous users. Thus the number of keys amounts to:
1+2+3+4+5……+(n-1)= n(n-1)/2 keys
Whereas in an asymmetrical system of n users, whenever a new user joins the system, he/she must issue a separate private key and public key. The number of keys amounts to 2n keys only.
Asymmetric cryptography is superior to symmetric cryptography system in terms of key management. A major part of key management is to ensure the safety and security of the whole encryption and decryption process. In symmetric forms of encryption, the same key is used for encryption as well as decryption, whereas in asymmetric encryption, there are separate keys for encrypting the message and decrypting it — making it more secure.
Analyzing some popular PKC models
Public key cryptography systems are mainly based on three mathematical models — integer factorization, discrete logarithms, and elliptical curve problems.
RSA ( Rivest- Shamir- Adleman) system
The RSA system was made by Ron Rivest, Adi Shamir, and Leonard Adleman, based on whose initials the name of the system was coined in 1977. It is based on an integer factorization model and on the impracticality of factoring large numbers. For example, if n=p*q then it is easy to find n on knowing p and q but the reverse is difficult.
The RSA system has three main parts to it — key generation, encryption, and decryption.
Here are few Key generation of Public Key Cryptography
Generate the RSA modulus (n): Take two large prime numbers (usually of 1024 to 4096 bits) p and q and find n such that n=p*q. The larger the number, the stronger will the encryption be.
Get the derived number (e):
- The number e should be such that 1 < e < (p-1)*(q-1).
- The GCD of e and (p-1)*(q-1) should be 1, that is, they should be co-prime numbers.
Form the public key: The public key is represented by (n,e). Although an external party who has access to the public key will know the n, finding p and q remains largely a mystery.
Generate the private key:
- The private key is represented by (n,d) where d is the multiplicative inverse of e modulo (p-1)*(q-1).
- This is represented as: d*e = 1 mod ((p-1)*(q-1))
Let’s look at an example.
For convenience, we have taken small numbers as examples but in reality, larger numbers are taken (typically from the range of 1024 to 4096 bits)
Let p=61 and q=53
- n= 61*53= 3233
- 60*52=780
- Let e=17 as e lies between 1 and 780 and is coprime with 780
- Thus, d= 413 as 413*17 mod 780 = 1.
- Thus, the public key is represented as (n, e) or (3233, 17).
- The private key is represented as (n, d) or (3233, 413).
Encryption
If Casey were to send a message with plaintext M to Hannah, then she would first convert the non-padded plaintext into a padded number m using the appropriate padding protocol such that 0 < m < n.
To encrypt m into ciphertext c, it can easily be achieved using e from the public key:
C = ( me) mod n
For example to encrypt 65:
For n = 3233 and e = 17, the encryption function can be written as:
C = 6517 mod 3233 = 2790
Decryption
To decrypt the ciphertext c, Hannah would have to make use of d from her private key as:
m = cd mod n = (me)d mod n = m mod n
For example:
m = 2790413 mod 3233 = (6517)413 mod 3233 = 65 mod 3233 = 65
Double security
RSA also offers a double security by enabling Casey to imprint a digital signature with the encrypted message to Hannah. Sometimes a conundrum can arise where Hannah receives an encrypted message but is not sure if it is from Casey so that’s when the digital signature comes in handy.
All that Casey has to do is to accompany the encrypted message with a hash value raised to “d (modulo n)” using her own private key to imprint this ‘signature’. When Hannah receives it, she raises the signature to the power of “e (modulo n)” using her public key and checks the hash value. If they both are the same then it is confirmed to be sent from Casey.
RSA Analysis
- The RSA system makes use of the fact that it is based on an integer factorization model and on the impracticality of factoring large numbers. For example, if n=p*q then it is easy to find n on knowing p and q but the reverse is difficult.
- It offers a double security through digital signatures.
- It is the most popular encryption system today although many programs are emerging that can feasibly factor large numbers making the prime security of the RLA encryption unreliable. Although the largest RSA encrypted message that was cracked 768 bits long and typical messages are about 1024 to 4096 bits long. Hence, it is not very unreliable yet.
ElGamal System
The ElGamal encryption system is an asymmetrical cryptographic system based on the Diffie-Hellman exchange. Its security is based on the difficulty of a problem described in cyclic group G. It’s algorithms make use of discrete logarithmic problems. It was first introduced by Taher Elgamal in 1985 and is superior to the DES because, in this system, it is practically impossible for an external party to hack and decrypt a ciphertext. The ElGamal encryption mechanism has mainly three parts to it — Key generation, Encryption, and Decryption.
Key generation
- First, the receiver of the message, let’s say, Hannah, describes a cyclic group G of order q with generator g.
- Next, Hannah would pick a random number x from {1,………., (q-1)}
- Then she computes h= gx.
- She, then, publishes {G, q, g, h} as her public key and retains x as a secret as her private key.
Encryption
- Suppose the sender, let’s say, Casey, wants to encrypt a message m. She would first pick a random number y from {1, ………. , (q-1)}.
- She then computes C1 = gy.
- She then uses the shared secret (since it is based on the Diffie – Hellman exchange method) to find s = hy = gxy
- She would then map her message m onto an element m’ in the cyclic group G.
- Casey would then calculate C2 = m’ * s.
- She publishes her encrypted message as {C1, C2}
Decryption
- On receiving the encrypted message, Hannah calculates the shared secret: s = C1 x.
She then computes m’ = C2 * s-1 , where s-1 is the multiplicative inverse of cyclic group G. - The process goes as C2* s-1 = m’ * hy * (gxy)-1 = m’ * gxy * g-xy = m’.
After finding m’, she maps it to find m back and thus, the process is complete.
ElGamal encryption system isn’t very efficient, so it is generally used in compound encryption systems. Basically, in simpler terms, the actual message is encrypted using a symmetrical cryptographic system and the common key so produced is encrypted using the ElGamal system.
RSA vs ElGamal
- The RSA system is superior in efficiency whereas the ElGamal system is slower and is used in compound cryptographic system to encrypt common keys.
- The ElGamal system is superior in security because its discrete logarithmic problems and elliptical curve methods offer semantic security if the cyclic group G is based on
- Decisional Diffie – Hellman assumption (however since the system is easily malleable if a proper padding protocol is not in place, it can easily be tampered with) whereas the RSA is based on integer factorization, which is becoming more and more attainable.
- The RSA system is the most widely used and superior in popularity to the ElGamal system.
Stay tuned for more!
