Survey on asymmetric key cryptography algorithms
Survey on asymmetric key cryptography algorithms - Download as a PDF or view online for free
https://public.slidesharecdn.com/_next/static/media/favicon.7bc3d920.ico
SlideShare
1. Journal of Advanced Computing and Communication Technologies (ISSN: 2347 - 2804) Volume No. 2 Issue No. 1, February 2014 Survey on Asymmetric Key Cryptography Algorithms S. Nithya , Dr. E. George Dharma Prakash Raj Computer Science and Engineering, Bharathidasan University, Trichy, India. Computer Science and Engineering ,Bharathidasan University, Trichy, India. niyaa20@yahoo.co.in,georgeprakashraj@yahoo.com ABSTRACT II. PUBLIC KEY CRYPTOGRAPHY ALGORITHMS Asymmetric key encryption is also called public key encryption. It uses two keys known as a public and a private key. Data encrypted with one key can be decrypted only with the other key. This paper discusses some public key algorithms and its advantages and disadvantages such as Rivest Shamir Adleman, Diffi-Hellman, Elliptic Curve Cryptography, Elliptic Curve Diffi-Hellman, ElGamal Encryption Algorithm, Knapsack Algorithm, Digital Signature Algorithm and Short Range Natural Numbers. A. Rivest Adi Adleman (RSA) In 1978, Ron Rivest, Adi Shamir, and Leonard Adleman introduced a cryptographic algorithm, which was essentially to replace the less secure National Bureau of Standards (NBS) algorithm. In RSA, this asymmetry is based on the practical difficulty of factoring the product of two large prime numbers, the factoring problem [2]. In such a cryptosystem, the encryption key is public and differs from the decryption key which is kept secret. The RSA algorithm involves three steps: key generation, encryption and decryption. (i) Key generation: R1. Users of RSA must determine two primes at random: p, q R2. Select either e or d and compute the other Primes p, q must not be easily derived from modulus N=p*q R3. Exponent e, d is inverses, so use inverse algorithm to compute the other. Keywords Cryptography, Rivest Shamir Adleman, Elliptic Curve Cryptography, Diffi - Hellman, Digital Signature. I. INTRODUCTION All public key cryptosystems are based on the notion of a one-way function. Which depending on the public key, converts plaintext into cipher text using are relatively small amount of computing power but whose inverse function is extremely expensive to compute, so that an attacker is not able to derive the original plaintext from the transmitted cipher text within a reasonable time frame. In public key cryptography, each user or the device taking part in the communication have a pair of keys, a public key and a private key, and a set of operations associated with the keys to do the cryptographic operations. Only the particular user/device knows the private key whereas the public key is distributed to all users/devices taking part in the communication. It increased security and convenience: private keys never need to be transmitted or revealed to anyone [1]. This paper work focuses on brief descriptions of various public key cryptography algorithms which are discussed on section II and in section III advantages and disadvantages of these algorithms were made in the form of comparative study. (ii) Encryption: R4. To encrypt a message m the sender R5. Obtains public key of recipient Pu= {e.N} R6. Computes: C=Me mod N, where 0≤M<N (iii) Decryption: R7.To decrypts the cipher text c the owner R8.Uses their private key PR= {d, p, q} R9. Computes: M=Md mod N B. Diffi-Hellman key exchange (D-H) The DH algorithm, introduced by Whitfield Diffie and Martin Hellman in 1976, was the first system to utilize “public-key” or “asymmetric” cryptographic keys. These systems overcome the difficulties of “private-key” or “symmetric” key systems because asymmetric key management is much easier [3]. DH is a mathematical algorithm that allows two computers to generate an identical shared secret on both systems, even though those systems may never have communicated with each 1

2. Journal of Advanced Computing and Communication Technologies (ISSN: 2347 - 2804) Volume No. 2 Issue No. 1, February 2014 S7.Compute r= (αk mod p) mod q S8.Compute k-1 mod q S9.Compute s=k-1 ∗(h (m) + ar) mod q S10.Signature = (r, s) other before. That shared secret can then be used to securely exchange a cryptographic encryption key. That key then encrypts traffic between the two systems. The Diffi-Hellman Key Exchange is one of the more popular and interesting methods of key distribution. It is a public-key cryptographic system whose sole purpose is for distributing keys. (iii) Verification: S11.Verify 0<r<q and 0<s<q, if not, invalid S12.Compute w= s-1mod q and h (m) S13.Compute u1=w∗h (m) mod q, u2=r∗w mod q S14. Compute v = (αu1yu2 mod p) mod q S15. Valid if v=r (i) Key algorithm: It is also possible to use Diffi–Hellman as part of a public key infrastructure. D1. First, both Alice and Bob agree upon a prime number and another number that has no factor in common. Let’s call the prime number as p and the other number as g. Note that g is also known as the generator and p is known as prime modulus. D2. Now, g a mod p and g b mod p is the public key for Alice and Bob respectively. D3. Alice and Bob exchanged their public keys. D4. Alice computes (g b mod p) a mod p that is equal to g ba mod p. D5. Bob computes (g a mod p) b mod p that is equal to g ab mod p. D6. K= g ba mod p=g ab mod p, shared secret =k. D. Elliptic curve cryptography (ECC) Elliptic curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblit and Victor S. Millerin 1985. Elliptic curves are also used in several integer factorization algorithms that have applications in cryptography [5]. E. Elliptic curve Diffie–Hellman (ECDH) Elliptic curve Diffie-Hellman is an anonymous key agreement protocol that allows two parties, each having an elliptic curve public–private key pair, to establish a shared secret over an insecure channel. This shared secret may be directly used as a key, or better yet, to derive another key which can then be used to encrypt subsequent communications using a symmetric key cipher. It is a variant of the Diffie–Hellman protocol using elliptic curve cryptography [6]. C. Digital Signature Algorithm (DSA) The Digital Signature Algorithm (DSA) is a Federal Information Processing Standard for digital signatures. It was proposed by the National Institute of Standards and Technology (NIST) in August 1991 for use in their Digital Signature Standard (DSS) and adopted as FIPS 186 in 1993. A digital signature scheme typically consists of three algorithms: A key generation algorithm that selects a private key uniformly at random from a set of possible private keys. The algorithm outputs the private key and a corresponding public key [4]. A signing algorithm that, given a message and a private key, produces a signature. A signature verifying algorithm that, give a message, public key and a signature, either accepts or rejects the message's claim to authenticity. (i) Key generation algorithm: E1. Alice wants to establish a shared key with Bob. E2. The domain parameters must be agreed upon. E3. Let Alice's key pair be ( 𝑑 𝐴 ,𝑄 𝐴 ) and Bob's key pair be (𝑑 𝐵 , 𝑄 𝐵 ). E4. Alice computes (𝑥 𝐾 ,𝑦 𝑘 ) =𝑑 𝐴 𝑄 𝐵 . Bob computes (𝑥 𝐾 ,𝑦 𝑘 ) =𝑑 𝐵 𝑄 𝐴 . E5. The shared secret calculated by both parties is equal 𝑑 𝐴 𝑄 𝐵 =𝑑 𝐴 𝑑 𝐵 G=𝑑 𝐵 𝑑 𝐴 G=𝑑 𝐵 𝑄 𝐴 . (i) Key generation: S1.select a prime q of 160 bits S2.Choose 0≤t≤8, select 2511+64t <p< 2512+64t with q|p-1 S3.Select g in Zp*, and α = g (p-1)/q mod p, α≠1 S4.Select 1 ≤ a ≤q-1, compute y= αa mod p S5.public key (p, q,α, y), private key a F. ElGamal Encryption Algorithm In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange. It was described by Taher Elgamal in 1984. ElGamal encryption (ii) Signing: S6.Select a random integer k, 0 < k < q 2

3. Journal of Advanced Computing and Communication Technologies (ISSN: 2347 - 2804) Volume No. 2 Issue No. 1, February 2014 consists of three components: the key generator, the encryption algorithm, and the decryption algorithm [7]. q is larger than the sum of every subset of w, no sums are congruent mod q and therefore none of the private key's sums will be equal. r must be co prime to q or else it will not have an inverse mod q. The existence of the inverse of r is necessary so that decryption is possible. (i) Key generation: G1. Alice generates an efficient description of a multiplicative cyclic group G of order q with generator g. See below for a discussion on the required properties of this group. G2. Alice chooses a random x from {1... q-1}. G3. Alice computes h=𝑔 𝑥 . G4. Alice publishes h, along with the description of g, q, g, as her public key. Alice retains x as her private key which must be kept secret. Now calculate the sequence β = (β1, β2... βn) where βi = rwi mod q. The public key is β, while the private key is (w, q, and r). (ii) Encryption: To encrypt an n-bit message α = (α1, α2... αn), Where Is the i-th bit of the message and calculate (ii) Encryption: The encryption algorithm works as follows: to encrypt a message m to Alice under her public key (g, q, g, h) G5. Bob chooses a random y from {1..., q-1}, then calculates 𝑐1 =𝑔 𝑦 . G6. Bob calculates the shared secret s=ℎ 𝑦 . G7. Bob converts his secret message m into an element 𝑚′ of G. G8. Bob calculates 𝑐2 =𝑚′ .s. G9. Bob sends the ciphertext (𝑐1 , 𝑐2 = (𝑔 𝑦 , 𝑚′ . ℎ 𝑦 ) = 𝑔 𝑦 , 𝑚′ . (𝑔 𝑥𝑦 ) to Alice. {0, 1}, The cryptogram then is c. (iii) Decryption: In order to decrypt a cipher text c a receiver has to find the message bits αi such that they satisfy (iii) Decryption: The decryption algorithm works as follows: to decrypt a ciphertext (𝑐1 , 𝑐2 ) with her private key x, G10. Alice calculates the shared secret s= 𝑐1𝑥 . G11. Then computes 𝑚′ = 𝑐2 . 𝑠 −1 which she then converts back into the plaintext message m, where 𝑠 −1 is inverse of in the group G. The decryption algorithm produces the intended message. This would be a hard problem if the βi were random values because the receiver would have to solve an instance of the subset sum problem, which is known to be NP-hard. However, the values βi were chosen such that decryption is easy if the private key (w, q, and r) is known [8]. H. Short Range Natural Numbers Algorithm (SRNN) G. Knapsack Algorithm The Merkle–Hellman knapsack cryptosystem was one of the earliest public key cryptosystems invented by Ralph Merkle and Martin Hellman in 1978. In asymmetric key cryptography, also called Public Key cryptography, two different keys are used. One key is used for encryption & only the other corresponding key must be used for decryption. No other key can decrypt the message not even the original (i.e. the first) key used for encryption [9]. The beauty of this scheme is that every communicating party needs just a key pair for communicating with any number of other communicating parties. Once someone obtains a key pair, he /she can communicate with anyone else. The Short Range Natural Number (SRNN) algorithm is similar to RSA algorithm with some modification. This modification increases the security of the cryptosystem [10]. (i) Key generation: To encrypt n-bit messages, choose a super increasing sequence w = (w1, w2... wn) of n nonzero natural numbers. Pick a random integer q, such that 𝑛 q> ∑ 𝑖=1 𝑤𝑖 , And a random integer, r, such that gcd (r, q) = 1 (i.e. r and q are co prime). q Is chosen this way to ensure the uniqueness of the cipher text. If it is any smaller, more than one plaintext may encrypt to the same cipher text. Since (i) Key generation: N1. Generate two large random prime p, q. 3