Public key Algorithms in Cryptography
Introduction
Asymmetric algorithms are also called public-key algorithms. As the name itself says an asymmetric key, two different keys are used for the public key encryption. One key is used for the encryption process and another key is used for the decryption process. Once the key is decided for encryption and decryption, no other key will be used. From these two keys, one key is called a public key and another one is called a private key.
Brief History
The first public key algorithm was the Diffie-Hellman key exchange, which allowed, at least initially, only for key distribution between known parties. It was extended by ElGamal to a full encrypt and signature public key scheme, and is used for ECC encryption. Shortly after Diffie-Hellman was published, another algorithm known as RSA (Rivest Shamir Adleman) was publicly presented. RSA allowed for both encryption and signatures while using half of the bandwidth as ElGamal. Subsequently, RSA became standardized in various forms.
Let’s See this example to understand the scenario.
We are going to have a communication with my friend via internet, to start the secure communication i (A) need to get both public and private key. The private key is a secret key, i should keep it as a secret. If the private key is disposed to my friend (B), there is a chance of attack through the third party.
Suppose A wants to communicate with B securely, then both A and B should have a public key and private key.
- A should keep her private key secret.
- A should inform her public key to B
- B should keep her private key secret.
- B should inform her public key to A.
Scene 1:
When A wants to communicate with B, A encrypts the message using the B’s public key, because B’s Public Key is shared with A
- A sends the encrypted message to B.
- B receives the message from A.
- B decrypts the message using B’s private key.
Note: Only Y know her private key and message can be decrypted using B’s private key. The advantage of this is the party cannot decrypt the message because he/ she does not know the private key of B. Only B’s private key can decrypt the message.
Scene 2:
When B wants to communicate with A, B encrypt the message using A’s public key. This is possible because A shares her public key to B.
- B sends the encrypted message to A.
- A receives the message from B
- A decrypts the message using her i.e. A’s private key.
Functionalities
Public-key encryption, is capable to encrypt a message using public key of an entity, where only the entity with the corresponding private key is capable of decrypting the cipher text.
Public key algorithms are used (primarily) to solve two problems.
1. Helps solve privacy problems
2. Helps solve authenticity problems.
Public key algorithms accomplish these goals by operating asymmetrically; that is,
1. The key is split into two corresponding parts, a public key and a private key. 2. The public key is secure to give out publicly to all those who ask for it.
3. The public key enables people to encrypt messages and verify signatures.
4. The private key is so named as it must remain private and cannot be given to public.
5. The private key is typically owned by a single person or device.
6. The private key allows for decrypting messages and the generation of signatures.
Public-key algorithms are asymmetric algorithms based on the use of two different keys, instead of one
- Private key — This key must be know only by its owner.
- Public key — This key is known to everyone (it is public).
The key used for encryption is different from the key used for decryption.
• However, the decryption key cannot, in any reasonable amount of time, be calculated from the encryption key and vice versa.
Public-key systems have a clear advantage over symmetric algorithms.
• There is no need to agree on a common key for both the sender and the receiver.
Either key can be used for encryption, but the complementary matched key is required for decryption.
• If a public key encrypts data, the matching private key decrypts data.
• If a private key encrypts data, the matching public key decrypts data.
The confidentiality objective of asymmetric algorithms is achieved when the encryption process is started with the public key.
The following are the Algorithms of public-key encryption.
RSA Algorithm
RSA is the most popular public-key encryption algorithm. RSA algorithm is based on the mathematical calculation. The private and public keys used in the RSA are large prime numbers.
Steps for RSA Algorithms:
- Select two large prime numbers A and B.
- Calculate the product N = A*B.
- Choose the public key E such that it is not a factor of (A — 1) and (B — 1).
- Chose the private key D such that the following equation becomes true.
- (D * E) mod (A — 1) * (B — 1) = 1
- For encryption calculate CT as CT = PT^E mod N.
- Send the CT to the receiver.
- For decryption calculate PT as PT = CT^D mod N.
ElGamal Cryptography Algorithm
ElGamal is another popular public-key encryption algorithm.
ElGamal Key Generation:
- Select large prime number P as public key and Q as the private key.
- Select the second encryption key as E1.
- Select the third encryption key as E2 such that E2 = E^Q mod P ElGamal Key encryption.
- Select random number R.
- Calculate ciphertext as CT = E1 ^R mod P.
- Calculate second Cipher text CT2 = (PT * E2^R) mod P ElGamal key decryption
- Calculate plain text as PT = (CT2 *(CT^Q)^-1) mod P.
