Cryptography: Types, Methods and Uses

Cryptography: Types, Methods and Uses CHAPTER-1 INTRODUCTION 1.1 Introduction to Cryptography Cryptography is art of writing and reading the secret information. It is used to send the information between the various participants. It can be used in such a manner so that it could not be seen by the others. Cryptography is used to prevent the information from the attacker. It provides various services as : Integrity checking Authentication Confidentiality In case of integrity checking recipient thinks that the message is alter by the third party or attacker. Hence the user assures the recipient that the message has not been altered by any other source. In case of authentication the identity of the person is check by the user. The user verifies the identity of the person and handle over the right to use the particular data. In case of confidentiality the attacker watch the data carefully when it send from user to recipient. The third party can’t change the data. The message which is in the original form is known as the plaintext. The user encrypted the message before sending to the recipient is known as cipher text. When the cipher text is produces from plaintext, this process is known as encryption. [1]. The reverse process of encryption is called decryption. In the cryptographic systems an algorithm and a key is used. The key is known as the secret value. Cryptography is a field of computer networks which transforms (encrypts) the information (plain text) into an unreadable form (cipher text). And this cipher text can be decrypted only with the help of a secret key. Cryptography acts as a method of keeping the information secret. Cryptography protects the information by using mathematics in science. Electronic security is a major issue as various forms of electronic media and internet are becoming more prevalent. Cryptography is used to secure the data and to prevent the data from various attacks. Cryptography is necessary when communicating over any un-trusted medium. Authentication, digital signatures, e-commerce are major applications of cryptography. Generally in the cryptographic systems it can broadly classified into two systems. Symmetric key systems. Public key systems. In the symmetric key cryptography, single key is used for the encryption and the decryption purpose. The same key is used at the sender and the recipient side. On the other hand, in case of public key system, two types of keys are required. One is the public key and other one is the private key. Public key is known to all but the private key is known only to the recipient of messages uses. One of the techniques used in Cryptography is known as the visual cryptography. It is a cryptographic technique, which allows visual information to encrypt. The data is encrypted in such a way that decryption becomes a mechanical operation. For these kinds of operations computer is not required. Earlier the developers used visual secret sharing scheme. In this scheme the image was broken into many parts. The third party thinks that all these parts are used to decrypt the image. But the n − 1 parts of the image revealed no information about the original image. In this technique each part has its separate transparency. The decryption is performed by overlaying the parts. When all the parts were overlaid, then the original image would appear. Cryptogra phy is the technique, which is used to protect the information from the external viewers. It plays a vital role in security. The public key encryption and decryption is one of the most important types of cryptography. In public key cryptography the key should be unique. There are two ways of key production. The first one is mathematical like AES, DES and the other one is based on the theory of natural selection. The multimedia technology plays an important role in our society. In this case the digital images play a very important role. The digital images are used to fulfil the security and privacy in various applications. Encryption of image plays a very important role; it helps to save the image from the unauthorized attack. Many solutions are providing to save this image; one of the techniques is mask the image data. For the encryption purpose many algorithms are required, such as [2] : DES AES RSA Broadly, Cryptographic systems provide us three types of cryptographic algorithms namely, Secret Key Cryptography (SKC), Public Key Cryptography (PKC) and Hash Functions [3]. The Secret Key Cryptography (SKC) uses a single (same) key for the process of encryption and decryption. The most commonly SKC algorithms used now-a-days include: 1.2 Data Encryption Standard (DES) It was designed in 1970’s by IBM and was ratified in 1977 by the National Bureau of Standards (NBS) for commercial use. It is a block cipher that operates on 64-bit blocks employing a 56-bit key and 16 rounds [4]. Although DES has been around long back but no real weakness has been identified. The biggest disadvantage of DES is the 56 bit key size. 1.3 Advanced Encryption Standard (AES) It was designed by Vincent Rijmen and Joan Daemen and was introduced in 1998. The algorithm can use fickle key length and block length. The key length can include 128, 192, or 256 bits and block length can be of 128, 192, or 256 bits [5].AES is a highly efficient and secure algorithm. The drawback lies in its processing as it requires more processing. 1.4 Rivest Cipher (RC) Ronald Rivest developed this algorithm and thus, the name of the algorithm was put after Ronald’s Rivest name. It provides a series of RC algorithms including RC1, RC2, RC3, RC4, RC5 and RC6 [6]. 1.5 Blowfish It was developed by Bruce Schneie and was first published in the year 1993. This block cipher has 8 rounds, having the block size is of 64 bits and the key length can vary from 32 to 448 bits. Blowfish was proposed as a substitute was DES [7]. This algorithm is significantly faster than other algorithms and the key strength is excellent. Blowfish algorithm is apt only for applications where the key mostly remains the same. The Public Key Cryptography (PKC) uses one (public) key for encryption and another (private) key for decryption. The PKC algorithms that are in use today are: 1.6 RSA The RSA algorithm was publicly described in 1977 by Ron Rivest,Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames, listed in the same order as on the paper. RSA is a cryptosystem, which is known as one of the first practicable public-key cryptosystems and is widely used for secure data transmission. In such a cryptosystem, the encryption key is public and differs from the decryption key which is kept secret. In RSA, this asymmetry is based on the practical difficulty of factoring the product of two large prime numbers, the factoring problem. RSA stands for Ron Rivest, Adi Shamir and Leonard Adleman, who first publicly described the algorithm in 1977. Clifford Cocks, an English mathematician, had developed an equivalent system in 1973, but it wasnt declassified until 1997. A user of RSA creates and then publishes the product of two large prime numbers, along with an auxiliary value, as their public key. The prime factors must be kept secret. Anyone can use the public key to encrypt a message, but with currently published methods, if the public key is large enough, only someone with knowledge of the prime factors can feasibly decode the message. Breaking RSA encryption is known as the RSA problem. It is an open question whether it is as hard as the factoring problem. The system includes a communications channel coupled to at least one terminal having an encoding device and to at least one terminal having a decoding device. A message-to be- transferred is enciphered to cipher text at the encoding terminal by encoding the message as a number M in a predetermined set. That number is then raised to a first predetermined power (associated with the intended receiver) and finally computed. The remainder or residue, C, is computed when the exponentiated number is divided by the product of two predetermined prime numbers (associated with the intended receiver). Operation of RSA The RSA algorithm involves three steps: Key Generation Encryption Decryption. 1.6.1 Key Generation RSA involves a public key and a private key. The public key can be known by everyone and is used for encrypting messages. Messages encrypted with the public key can only be decrypted in a reasonable amount of time using the private key. The keys for the RSA algorithm are generated the following way: Choose two distinct prime numbers p and q. For security purposes, the integers p and q should be chosen at random, and should be of similar bit-length. Prime integers can be efficiently found using a primarily test. Compute n = pq.n is used as the modulus for both the public and private keys. Its length, usually expressed in bits, is the key length. Compute φ(n) = φ(p)φ(q) = (p − 1)(q − 1), where φ is Eulers totient function Choose an integer e such that 1 e is released as the public key exponent. e having a short bit-length and small Hamming weight results in more efficient encryption – most commonly 216 + 1 = 65,537. However, much smaller values of (such as 3) have been shown to be less secure in some settings. Determine d as d ≠¡ e−1 (mod φ(n)); i.e., d is the multiplicative inverse of e (modulo φ(n)). This is more clearly stated as: solve for d given d.e ≠¡ 1 (mod φ(n)) This is often computed using the extended Euclidean algorithm. Using the pseudo code in the Modular integers section, inputs a and n correspond to e and (n), respectively. d is kept as the private key exponent. The public key consists of the modulus n and the public (or encryption) exponent e. The private key consists of the modulus n and the private (or decryption) exponent d, which must be kept secret. p, q, and φ(n) must also be kept secret because they can be used to calculate d. 1.6.2 Encryption A transmits her public key (n, e) to B and keeps the private key secret. B then wishes to send message M to A. He first turns M into an integer m, such that 0 _ m by using an agreed-upon reversible protocol known as a padding scheme. He then computes the ciphertext c corresponding to c = memod(n) 1.6.3 Decryption We can recover message m from c by using her private key exponent d via computing Given m, we can recover the original message M by reversing the padding scheme.(In practice, there are more efficient methods of calculating cd using the precomputed values below.) 1.7 Enhanced RSA The RSA algorithm based on the variable N which consisting of multiplying each of the P and q, which are relying on that of where to find the variable d, as the variable d is, hence the higher value of n. The variable d increases its size, the higher value of p and q the value of d increases, which means that the algorithm depends entirely on the adoption of the prime numbers because they generate a key d, depending on p and q are already primes numbers. The weaknesses of RSA algorithm when we use two prime’s number are the following points which are used to break the algorithm in most cases. These weaknesses are: (a) Small encryption exponent, if you use a small exponent like e=3 and send the same message to different recipients. (b) Using the same key for encryption and signing. (c) Acting as an oracle: there are techniques to recover the plaintext if a user just blindly returns the RSA transformation of the input. The idea of the new approach is, instead of using two primes numbers to generate a public key and private key, we use three primes numbers with reduced size, generates the variable N Large and the process of analysis of the factors is more difficult than the original algorithm, as well as, increases the ease of generating Public key and private key. The key strength of the RSA depends on the two prime numbers p and q. The process of factorizing of n will lead to gain the values of p and q. It is much easier to find two numbers from factoring n than finding the value of three numbers from n. In this case it is very difficult for the intruder to find the three values from factoring n. 1.7.1 Key Generation in Enhanced RSA (a) Choose three distinct prime numbers p, q and s. (b) Find n such that n = p*q*s.n will be used as the modulus for both the public and private keys. (c) Find the Phi of n, à ¯Ã‚ Ã‚ ¹ (n) = (p-1)(q-1)(s-1). (d) Choose an e such that 1 (e) Determine d which satisfies the congruence relation d*eà ¯Ã¢â‚¬Å¡Ã‚ º 1(modà ¯Ã‚ Ã‚ ¹(n)) In other words, pick d such that de 1 can be evenly divided by (p- 1)(q-1)(s-1), the Phi, or à ¯Ã‚ Ã‚ ¹(n).This is often computed using the Extended Euclidean Algorithm, since e and à ¯Ã‚ Ã‚ ¹(n) are relatively prime and d is to be the modular multiplicative inverse of e*d is kept as the private key exponent. The public key has modulus n and the public (or encryption) exponent e. The private key has modulus n and the private (or decryption) exponent d, which is kept secret .The encryption equation is c à ¯Ã‚ Ã‚ ¹ me (mod n) and the decryption one is m à ¯Ã¢â‚¬Å¡Ã‚ º cd (mod n). 1.8 Diffie Hellman This algorithm was introduced in1976 by Diffie-Hellman. The Diffie-Hellman algorithm grants two users to establish a shared secret key and to communicate over an insecure communication channel [10]. One way authentication is free with this type of algorithm. The biggest limitation of this kind of algorithm is communication made using this algorithm is itself vulnerable to man in the middle attack [11]. Diffie–Hellman establishes a shared secret that can be used for secret communications while exchanging data over a public network. The following diagram illustrates the general idea of the key exchange by using colors instead of a very large number. The crucial part of the process is that Aand B exchange their secret colors in a mix only. Finally this generates an identical key that is mathematically difficult (impossible for modern supercomputers to do in a reasonable amount of time) to reverse for another party that might have been listening in on them. A and B now use this co mmon secret to encrypt and decrypt their sent and received data. Note that the starting color (yellow) is arbitrary, but is agreed on in advance by A and B. The starting color is assumed to be known to any eavesdropping opponent. It may even be public. 1.8.1 Explanation including encryption mathematics The simplest and the original implementation of the protocol uses the multiplicative group of integers modulo p, where p is prime and g is primitive root mod p. Here is an example of the protocol, with nonsecret values in blue, and secret values in red. Small integers are used for clarity, but actual implementations require using much larger numbers to achieve security. Fig 1.1 Process of Diffie Hellman 1. p = 23 and base g = 5. 2. A chooses a secret integer a = 6, then sends B A = ga mod p A = 56 mod 23 A = 15,625 mod 23 A = 8 3. B chooses a secret integer b = 15, then sends A B = gb mod p B = 515 mod 23 B = 30,517,578,125 mod 23 B = 19 4. A computes s = Ba mod p s = 196 mod 23 s = 47,045,881 mod 23 s = 2 5. Bob computes s = Ab mod p s = 815 mod 23 s = 35,184,372,088,832 mod 23 s = 2 6. A and B now share a secret (the number 2) because 6 Ãâ€" 15 is the same as 15 Ãâ€" 6. Both A and B have arrived at the same value, because (ga)b and (gb)a are equal mod p. Note that only a, b, and (gab gba mod p) are kept secret. All the other values – p, g, ga mod p, and gb mod p – are sent in the clear. Once A and B compute the shared secret they can use it as an encryption key, known only to them, for sending messages across the same open communications channel. Of course, much larger values of a, b, and p would be needed to make this example secure, since there are only 23 possible results of n mod 23. However, if p is a prime of at least 300 digits, and a and b are at least 100 digits long, then even the fastest modern computers cannot find a given only g, p, gb mod p and g amod p. The problem such a computer needs to solve is called the discrete logarithm problem. 1.9 El-Gamal It was developed in the year 1984 by Taher Elgamal. It is an asymmetric key algorithm and is based on Diffie-Hellman key exchange. ElGamal encryption can be described over anycyclic groupG. The security relies upon the issue of a problem inGrelated to computing discrete logarithms [12]. Fast generalized encryption for long messages and data expansion rate are the two biggest advantages of this algorithm [13]. The chief drawback of ElGamal is the requirement for randomness and its slower speed [14]. ElGamal encryption can be defined over any cyclic group G. Its security depends upon the difficulty of a certain problem in G related to computing discrete logarithms. The Algorithm ElGamal encryption consists of three components: the key generator, the encryption algorithm, and the decryption algorithm. 1.9.1 Key Generation The key generator works as follows: It generates an efficient description of a multiplicative cyclic group G of order q with generator g. Sender chooses a random x from (1,†¦Ã¢â‚¬ ¦q-1) He computes h= gx A publishes h , along with the description of G,q,g , as her public key. He retains x as her private key which must be kept secret. Fig 1.2 El-Gamal Algorithm 1.9.2 Example of El-Gamal Algorithm: Fig 1.3 Example of El-Gamal Algorithm. Hash Functions, also known as message digest, are the algorithms that do not use any key. Based upon the plain text, a fixed length hash value is generated.Hash algorithms that are commonly used today include: 1.10 Message Digest (MD) algorithms It produces a hash value of 128 bit from an arbitrary length message. The MD series includes MD2, MD4 and MD5 [11]. 1.10.1 MD5 algorithm The MD5 algorithm was developed by Rivest in 1991 and is an extension of the MD4 message-digest algorithm and is bit slower than MD4. This algorithm results in a 128 bit hash value. It is mostly used in security based applications. MD5 is more secure than MD4 [15]. It is suitable to use for standard file verifications but it has some flaws and therefore, it is not useful for advanced encryption applications [16].