A Hearty welcome everyone, it’s gutsytechster!!
Well, we did something in last blog, do you remember. Oh nice then, even if you don’t, just have a quick look at it, that would fresh up your memory. This time we are going to know about Asymmetric encryption. Last time we learnt some basic terminology related to cryptography and about symmetric encryption. Let’s start then.
Problems with Symmetric Encryption
- Key Exchange Problem: The key exchange problem arises from the fact that communicating parties must somehow share the secret key before any secure communication can be initiated. Encryption keys aren’t simple text strings, they are essentially blocks of gibberish. Of course, if we have a safe way to share the key, we probably don’t need to be using encryption in the first place.
- The Trust Problem: When someone gets their hands on a symmetric key, they can decrypt everything encrypted with that key. When you’re using symmetric encryption for two-way communications, this means that both sides of the conversation get compromised.
Asymmetric Encryption is a form of cryptosystem in which encryption and decryption are performed using two different keys, one is public and one is private. It is also known as Public-key encryption. It transforms the plaintext into ciphertext using one of the two keys and an encryption algorithm. Using the paired key and a decryption algorithm, the plaintext can be generated back by ciphertext.It can be used for both confidentiality, authentication or both.
Asymmetric algorithms rely on one key for encryption and the paired key for decryption.These algorithms have following characteristics:
- It is unfeasible to determine the decryption key, given only the knowledge of the cryptographic algorithm and the encryption key.
- In some algorithms such as RSA (to be discussed later), either of the two keys can be used for encryption and the other for decryption.
A Public key encryption cryptosystem has six ingredients:
- Plaintext: This is the intelligible message which has to be encrypted.
- Encryption algorithm: The Encryption algorithm performs various transformations on the plaintext.
- Public and Private keys: This is the pair of keys which are selected such that if one is used for encryption, then the other is used for decryption.
- Ciphertext: This is the unintelligible message produced as an output. It depends on the plaintext and the key. For a given message, two different keys will produce two different ciphertext.
- Decryption algorithm: This algorithm takes the ciphertext and the paired key as an input and produces the plaintext as an output.
The first picture depicts the confidentiality as Alice uses Bob’s public key to encrypt data which can only be decrypted by Bob’s private key. So, only Bob has his private key and the encrypted data can only be seen by him. In the second picture, Alice encrypts data using his private key which is only possesed by him and can be decrypted by her Public key which is available to the receiver. Hence, depicts the authenticity.
The RSA scheme stands for the name of scientists who developed this algorithm as Rivest-Shamir-Adleman scheme. RSA scheme is a block cipher in which plaintext and ciphertext are integers between 0 and n, for some value of n.
Key Generation Algorithm
- Select two large prime numbers p and q, of approximately equal size such that their product will be n=pq.
- Compute n=pq and Φ(phi)=(p-1)(q-1).
- Choose an integer e (1 < e < Φ), such that gcd(e,Φ)=1.
- Calculate the secret exponent d (1 < d < Φ), such that ed ≡ 1 (mod Φ).
- The public key is (n,e) and the private key is (n,d). Keep all values of d,n and Φ secret.
where n is known as the modulus.
e is the public exponent or encryption exponent.
d is known as the secret exponent or decryption exponent.
Sender does the following:
- Obtain the recipient’s public key (n,e).
- Represent the plaintext message as a positive integer m such that 1 < m < n.
- Computes the ciphertext c = (m**e) mod n.
- Send c to the recipient.
Recipient does the following:
- Uses his private key (n,d) to compute m = (c**d) mod n.
- Extracts the plaintext from the message equivalent m.
One of the major roles of public-key encryption has been to address the problem of key distribution.There are actually two aspects to use the public key cryptography in this regard.
- The distribution of public keys : The public keys can be distributed by the following ways:
- Public announcement
- Publicly available directory
- Public-key authority
- Public-key certificates
- The use of Public key encryption to distribute secret keys: Since due to slow data rates of Public key encryption, user prefer to go with conventional encryption techniques. So public key encryption cryptosystem can be used for the distribution of secret keys to be used for symmetric encryption. This can be described by Diffie-Hellman key exchange algorithm.
Diffie-Hellman Key Exchange Algorithm
The Diffie-Hellman algorithm was created to address the issue of secure encrypted keys from being attacked over the internet when in transmission, through using the Diffie-Hellman algorithm in distributing symmetric keys securely over the internet.
The steps of the algorithm are:
- Initially, both sender and receiver agree on two numbers g and p with 0<g<p. These numbers are not private and can be known to anyone.
- Sender picks a private number a>0, and computes α = (g**a) mod p. Sender then sends this α to receiver.
- Meanwhile, receiver picks a private number b>0, and computes β = (g**b) mod p. Receiver then sends β to sender.
- Sender computes k = (β**a) mod p and receiver computes k = (α**b) mod p. Both of them obtain the same no. k which can be used as a secret key.
Now, you must be thinking, how sender and receiver possess the same key. Let’s understand above algorithm with an example. Let Alice and Bob be sender and receiver respectively.
- Suppose they agree on numbers with g=327 and p=919.
- Alice chooses a=400, this is her private key. She then computes α=(327**400)mod919 which comes out to be 231. Hence α=231. This is Alice’s public key and can be known by anyone. She then send this to Bob.
- Bob chooses b=729, this is his private key. He then computes β=(327**729)mod919 which comes out to be 162. Hence β=162 and sends this ( his public key ) to Alice.
- Alice computes k = (162**400) mod 919 = 206.
- Bob computes k = (231**729) mod 919 =206.
- k=206 is the secret key, which both Bob and Alice will use to encrypt their message to each other.
Limitations of Asymmetric Encryption
- Speed : Public key encryption works very well and is extremely secure, but it’s based on complicated mathematics. Because of this, your computer has to work very hard to both encrypt and decrypt data using the system. In applications where you need to work with large quantities of encrypted data on a regular basis, the computational overhead means that public key systems can be very slow.
- Certification Problem : Many Public key system uses a third party to certify the reliability of Public keys. However, if certification authority gets compromised, the results can be catastrophic.
Well with this, we have reached the conclusion. I hope this would be helpful to you and now you will have an idea of what is asymmetric encryption. To learn in depth you can refer here.
Meet you in the next blog.