Public Key CryptographyUnlike symmetric key cryptography, we do not find historical use of public-key cryptography. It is a relatively new concept. Show
Symmetric cryptography was well suited for organizations such as governments, military, and big financial corporations were involved in the classified communication. With the spread of more unsecure computer networks in last few decades, a genuine need was felt to use cryptography at larger scale. The symmetric key was found to be non-practical due to challenges it faced for key management. This gave rise to the public key cryptosystems. The process of encryption and decryption is depicted in the following illustration − The most important properties of public key encryption scheme are −
There are three types of Public Key Encryption schemes. We discuss them in following sections − RSA CryptosystemThis cryptosystem is one the initial system. It remains most employed cryptosystem even today. The system was invented by three scholars Ron Rivest, Adi Shamir, and Len Adleman and hence, it is termed as RSA cryptosystem. We will see two aspects of the RSA cryptosystem, firstly generation of key pair and secondly encryption-decryption algorithms. Generation of RSA Key PairEach person or a party who desires to participate in communication using encryption needs to generate a pair of keys, namely public key and private key. The process followed in the generation of keys is described below −
The Extended Euclidean Algorithm takes p, q, and e as input and gives d as output. ExampleAn example of generating RSA Key pair is given below. (For ease of understanding, the primes p & q taken here are small values. Practically, these values are very high).
Encryption and DecryptionOnce the key pair has been generated, the process of encryption and decryption are relatively straightforward and computationally easy. Interestingly, RSA does not directly operate on strings of bits as in case of symmetric key encryption. It operates on numbers modulo n. Hence, it is necessary to represent the plaintext as a series of numbers less than n. RSA Encryption
RSA Decryption
RSA AnalysisThe security of RSA depends on the strengths of two separate functions. The RSA cryptosystem is most popular public-key cryptosystem strength of which is based on the practical difficulty of factoring the very large numbers.
If either of these two functions are proved non one-way, then RSA will be broken. In fact, if a technique for factoring efficiently is developed then RSA will no longer be safe. The strength of RSA encryption drastically goes down against attacks if the number p and q are not large primes and/ or chosen public key e is a small number. ElGamal CryptosystemAlong with RSA, there are other public-key cryptosystems proposed. Many of them are based on different versions of the Discrete Logarithm Problem. ElGamal cryptosystem, called Elliptic Curve Variant, is based on the Discrete Logarithm Problem. It derives the strength from the assumption that the discrete logarithms cannot be found in practical time frame for a given number, while the inverse operation of the power can be computed efficiently. Let us go through a simple version of ElGamal that works with numbers modulo p. In the case of elliptic curve variants, it is based on quite different number systems. Generation of ElGamal Key PairEach user of ElGamal cryptosystem generates the key pair through as follows −
Encryption and DecryptionThe generation of an ElGamal key pair is comparatively simpler than the equivalent process for RSA. But the encryption and decryption are slightly more complex than RSA. ElGamal EncryptionSuppose sender wishes to send a plaintext to someone whose ElGamal public key is (p, g, y), then −
ElGamal Decryption
ElGamal AnalysisIn ElGamal system, each user has a private key x. and has three components of public key − prime modulus p, generator g, and public Y = gx mod p. The strength of the ElGamal is based on the difficulty of discrete logarithm problem. The secure key size is generally > 1024 bits. Today even 2048 bits long key are used. On the processing speed front, Elgamal is quite slow, it is used mainly for key authentication protocols. Due to higher processing efficiency, Elliptic Curve variants of ElGamal are becoming increasingly popular. Elliptic Curve Cryptography (ECC)Elliptic Curve Cryptography (ECC) is a term used to describe a suite of cryptographic tools and protocols whose security is based on special versions of the discrete logarithm problem. It does not use numbers modulo p. ECC is based on sets of numbers that are associated with mathematical objects called elliptic curves. There are rules for adding and computing multiples of these numbers, just as there are for numbers modulo p. ECC includes a variants of many cryptographic schemes that were initially designed for modular numbers such as ElGamal encryption and Digital Signature Algorithm. It is believed that the discrete logarithm problem is much harder when applied to points on an elliptic curve. This prompts switching from numbers modulo p to points on an elliptic curve. Also an equivalent security level can be obtained with shorter keys if we use elliptic curve-based variants. The shorter keys result in two benefits −
These benefits make elliptic-curve-based variants of encryption scheme highly attractive for application where computing resources are constrained. RSA and ElGamal Schemes – A ComparisonLet us briefly compare the RSA and ElGamal schemes on the various aspects.
What is D value in RSA?To compute the value for d, use the Extended Euclidean Algorithm to calculate d=e−1modϕ, also written d=(1/e)modϕ. This is known as modular inversion . Note that this is not integer division. The modular inverse d is defined as the integer value such that ed=1modϕ.
What are the attacks that are possible on RSA?These are explained as following below.. Plain text attacks: It is classified into 3 subcategories:- ... . Chosen cipher attack: In this attacker is able to find out plain text based on cipher text using the Extended Euclidean Algorithm.. Factorization attack: ... . Attacks on Encryption key: ... . Attacks on Decryption key:. How do you find the value of e in RSA algorithm?Explanation: Step 1: Select two large prime numbers, p, and q. Step 2: Multiply these numbers to find n = p x q, where n is called the modulus for encryption and decryption. Step 3: Choose a number e less that n, such that n is relatively prime to (p - 1) x (q -1).
What is RSA used for?RSA encryption, in full Rivest-Shamir-Adleman encryption, type of public-key cryptography widely used for data encryption of e-mail and other digital transactions over the Internet. RSA is named for its inventors, Ronald L. Rivest, Adi Shamir, and Leonard M.
|