An Overview of Cryptography

Cryptography:

There are many aspects to security and many applications, ranging from secure commerce and payments to private communications and protecting passwords. One essential aspect for secure communications is that of cryptography.

Cryptography is the study of mathematical techniques related to aspects of information security such as confidentiality, data integrity, authentication, and non-repudiation. In simple terms, cryptography is the practice and study of hiding information; it is the science of writing information in secret code and is an ancient art. Cryptography is necessary while transmitting secrets, personally identifiable information, when communicating over any untrusted medium includes just about any network, particularly the Internet. While modern cryptography is growing increasingly diverse, cryptography is fundamentally based on problems that are difficult to solve. A problem may be difficult because its solution requires some secret knowledge, such as decrypting an encrypted message or signing some digital document, or the problem may be hard because it is intrinsically difficult to complete, such as finding a message which produces a given hash value.

Fundamental goal of cryptography is to adequately address the following four areas:

Privacy/Confidentiality:
Providing secrecy is one of the goals of cryptography. It means, keeping the content of information from all but those authorized to have it. Simply, it is a process of ensuring that no one can read the message or information except the intended receiver.
Data Integrity:
Assuring the receiver that the received message has not been altered in any way either intentionally or otherwise from the original; addresses the unauthorized alteration of data.
Authentication:
The process of proving one's identity. This applies to both entities and information itself. So, this aspect of cryptography is usually subdivided into two major classes: entity authentication and data origin authentication.
Non-repudiation:
It is a mechanism to prove that the sender really sent this message. It prevents an entity from denying previous commitments or actions performed.

Types of Cryptographic Algorithms:

There are several ways of classifying cryptographic algorithms. Mostly these can be classified into three types as follows based on the number of keys that are employed for encryption and decryption, and further defined by their application and use.

• Secret Key Cryptography (SKC) / Symmetric Encryption:
  It uses a single secret key for both encryption and decryption.
• Public Key Cryptography (PKC) / Asymmetric Encryption:
  It uses one key for encryption and another for decryption (public and private key pair).
• Hash Functions / One-way Cryptography:
  It uses a mathematical transformation to irreversibly "encrypt" information.

Secret Key Cryptography (SKC) / Symmetric Encryption:

In secret key cryptography / Symmetric cryptography, a single secret key is used for both encryption and decryption. As the same secret key is used for both encryption and decryption this key must be shared by both sender and receiver. So, this key must be distributed using a secure medium, and both parties need to secure the key. The biggest difficulty with this approach, of course, is to find an efficient method to agree upon and exchange keys securely. This problem is referred to as the key distribution problem. The difficulty of establishing a secret key between two communicating parties, when a secure channel doesn't already exist between them is a considerable practical obstacle for cryptography users in the real world.

Secret key cryptography schemes are generally categorized into two categories as follows:
Stream ciphers:
Stream ciphers operate on a single bit or byte at a time, and in which the transformation of successive bits or bytes varies during the encryption by implementing some form of feedback mechanism so that the key is constantly changing, the encryption transformation can change for each symbol of plaintext being encrypted. In situations where transmission errors are highly probable, stream ciphers are advantageous because they have no error propagation. If, however, a digit is corrupted in transmission, rather than added or lost, only a single digit in the plaintext is affected and the error does not propagate to other parts of the message. A stream cipher applies simple encryption transformations according to the key stream being used. The key stream could be generated at random, or by an algorithm which generates the key stream from an initial small key stream / seed, or from a seed and previous cipher text symbols. Such an algorithm is called a key stream generator.
Stream ciphers come in several flavors but two are worth mentioning: Self-synchronizing stream ciphers and Synchronous stream ciphers.
Block ciphers:
A block cipher is an encryption scheme which breaks up the plaintext messages to be transmitted into blocks of a fixed length, and encrypts one block at a time. When encrypting, a block cipher might take a fixed-bit block of plaintext as input, and output a corresponding fixed-bit block of cipher text.
Some of the symmetric key block ciphers are as follows, in which Triple DES, AES are preferred:

• DES (Data Encryption Standard): DES was designed by IBM in the 1970s. It is a cipher selected as an official Federal Information Processing Standard (FIPS) for the United States in 1976, and which has subsequently enjoyed widespread use internationally. DES is a block-cipher employing a 56-bit key that operates on 64-bit blocks. DES has a complex set of rules and transformations that were designed specifically to yield fast hardware implementations and slow software implementations. In 1998, there was a brute force attack that demonstrated that DES could be attacked very practically, and highlighted the need for a replacement algorithm.
• 3DES (Triple Data Encryption Standard): When it was found that a 56-bit key of DES is not enough to guard against brute force attacks, TDES was chosen as a simple way to enlarge the key space without a need to switch to a new algorithm. It is a variant of DES that employs up to three 56-bit keys and makes three encryption/decryption passes over the block. Simply, DES(k3;DES(k2;DES(k1;M))), where M is the message block to be encrypted and k1, k2, and k3 are DES keys. TDES with three different keys has a key length of 168 bits: three 56-bit DES keys, with parity bits it has the total storage length of 192 bits.
• AES (Advanced Encryption Standard): Generally Rijndael is known as AES, Rijndael is a block cipher designed by Belgian cryptographers Joan Daemen and Vincent Rijmen. AES is not precisely Rijndael as Rijndael supports a larger range of block and key sizes; AES has a fixed block size of 128 bits and a key size of 128, 192 or 256 bits, whereas Rijndael can be specified with key and block sizes in any multiple of 32 bits, with a minimum of 128 bits and a maximum of 256 bits. It is adopted as an encryption standard by the U.S. government. It has been analyzed extensively and is now used widely worldwide. The algorithm can use a variable block length and key length; the latest specification allowed any combination of keys lengths of 128, 192, or 256 bits and blocks of length 128, 192, or 256 bits.
• IDEA (International Data Encryption Algorithm): In 1992, a secret key cryptosystem is written by Xuejia Lai and James Massey; with a 64-bit block length using a 128-bit key.
• Blow Fish: It is a symmetric 64-bit block cipher invented by Bruce Schneier; optimized for 32-bit processors with large data caches, it is significantly faster than DES on a highly configured machines. Key lengths can vary from 32 to 448 bits in length. Blowfish, available freely and intended as a substitute for DES or IDEA.
• Rivest Ciphers / Ron’s Code (RC1, RC2, RC3, RC4, RC5, and RC6): In Rivest ciphers, up to RC4 algorithm are found to be breakable. RC5 is a block-cipher supporting a variety of block sizes, key sizes, and number of encryption passes over the data, while using RC5 it is recommended to use larger key sizes and larger number of passes like eighteen to twenty passes, and RC6 is a block-cipher that is an improvement over RC5, RC6 was one of the AES Round 2 algorithms.

Public Key Cryptography (PKC) / Asymmetric Encryption:

Public Key Cryptography was first described publicly by Stanford University professor Martin Hellman and graduate student Whitfield Diffie in 1976. Public Key Cryptography involves a key pair; a key pair consists of two keys that are mathematically related designated as public and private keys, in which two parties could engage in a secure communication over a non-secure communications channel without having to share a secret key. Although knowledge of one key does not allow someone to easily determine the other key. This makes it possible for sender and receiver to simply send their public keys to one another, even if the channel they are using to do so is insecure. One key is used to encrypt the plaintext and the other key is used to decrypt the ciphertext.
In simple words, if the public key is used to encrypt some data, then it can be decrypted only using the corresponding private key. And similarly, if the private key is used to encrypt some data, then it can be decrypted only using the corresponding public key. This encryption mechanism can also be called as asymmetric encryption.

Compared with symmetric-key encryption, public-key encryption requires more computation and is therefore very slow. So, this technique is not appropriate for large amounts of data. Commonly, this PKC is used to transmit the secret keys between the parties and thereafter parties use these transmitted keys to encrypt their further communications. A central problem for public key cryptography is proving that a public key is authentic and not tampered by a malicious third party or an attacker. The usual approach to this problem is to certify ownership of key pairs by third parties known as certificate authorities.

Some of the asymmetric key block ciphers are as follows:
RSA(Rivest, Shamir, Adleman Algorithm): Ronald Rivest, Adi Shamir, and Leonard Adleman are developed this algorithm, hence called as RSA. It uses a variable size encryption block and a variable size key. Unlike few other algorithms, RSA can be used for key exchange, digital signatures, and the encryption of small blocks of data. RSA is a cipher based on the concept of a trapdoor function. This is a function which is easily calculated, but whose inverse is extremely difficult to calculate. RSA's mathematical hardness comes from the ease in calculating large numbers and the difficulty in finding the prime factors of those large numbers.
Diffie-Hellman: The Diffie-Hellman algorithm was developed by Diffie and Hellman in 1976 and published in the "New Directions in Cryptography” paper. The protocol allows two users to exchange a secret key over an insecure medium without any prior secrets. This key can then be used to encrypt subsequent communications using a symmetric key cipher. This algorithm works based on the multiplicative group of integers modulo p, where p is prime and g is primitive root mod p, these are system parameters. For example:

Like A and B are openly shared; these are the private and public keys, respectively. Based on their own private key and the public key learned from the other party, Alice and Bob have computed their secret keys. This derived key later used as an encryption key for further communication.
Digital Signature Algorithm (DSA): The algorithm specified in NIST's Digital Signature Standard (DSS), provides digital signature capability for the authentication of messages. As the DSA authenticates both the identity of the signer and the integrity of the signed information, it can be used in a variety of applications like mail, electronic funds transfer applications, etc.
Elliptic Curve Cryptography (ECC): A PKC algorithm based upon elliptic curves, it was designed for devices with limited compute power and/or memory, such as smartcards and PDAs. In 1985, ECC was proposed by cryptographers Victor Miller (IBM) and Neal Koblitz (University of Washington). It is based on the difficulty of solving the Elliptic Curve Discrete Logarithm Problem. Given two points, P and Q, on an elliptic curve, find the integer n, if it exists, such that P = nQ. ECC can offer levels of security with small keys comparable to RSA and other PKC methods.

Hash Functions / One-way Cryptography:

The essential cryptographic properties of a hash function are that it is both one-way and collision-free. It uses a mathematical transformation to irreversibly "encrypt" information. Hashing is the transformation of a string of characters into a usually shorter fixed-length value which is called the hash value that represents the original string. The hashing algorithm is called the hash function. In addition to faster data retrieval, hashing is also used to encrypt and decrypt digital signatures.
The most basic attack we might mount on a hash function is to choose inputs to the hash function at random until either we find some input that will give us the target output value we are looking for (thereby contradicting the one-way property), or we find two inputs that produce the same output (thereby contradicting the collision-free property). A good hash function should not produce the same hash value from two different inputs. If it does, this is known as a collision. A hash function that offers an extremely low risk of collision may be considered acceptable. To avoid an attack that depends on brute-force methods, the output from the hash function must be sufficiently long.

Some of the Hash functions are as follows:
Message Digest (MD) algorithms: A series of byte-oriented algorithms that produce a 128-bit hash value from an arbitrary-length message.

• MD2: It was developed by Rivest in 1989. The message or data is first padded so that its length in bytes is divisible by 16. A 16-byte checksum is then appended to the message or data, and the hash value is computed on this resulting message. It creates 128-bit hash value from data input of any length. It is optimized for 8-bit machines. The collisions for MD2 can be constructed if the calculation of the checksum is omitted. This is the only cryptanalytic result known for MD2. It is designed for systems with limited memory, such as smart cards.
• MD4: It was developed by Rivest in 1990. The message is padded to ensure that its length in bits plus 448 is divisible 512. A 64-bit binary representation of the original length of the message is then concatenated to the message. The message is processed in 512-bit blocks in the Damgård/Merkle iterative structure, and each block is processed in three distinct rounds. It is designed specifically for fast processing in software. It is optimized for 32-bit machines. MD4 should now be considered broken.
• MD5: It was developed by Rivest in 1991. It is basically MD4 with "safety-belts" and while it is slightly slower than MD4, it is more secure. The algorithm consists of four distinct rounds, which have a slightly different design from that of MD4. Message-digest size, as well as padding requirements, remains the same. MD5 is developed after potential weaknesses were reported in MD4, it is also optimized for 32-bit machines. Den Boer and Bosselaers have found pseudo-collisions for MD5, but there are no other known cryptanalytic results.

Secure Hash Algorithm (SHA): The Secure Hash Algorithm specified in the Secure Hash Standard (SHS), was developed by NIST (National Institute of Standards and Technology, a division of the U.S. Department of Commerce; it was formerly known as the National Bureau of Standards (NBS)) and published as a federal information processing standard. SHA-1 was a revision to SHA that was published in 1994. The revision corrected an unpublished flaw in SHA. Its design is very similar to the MD4 family of hash functions developed by Rivest. It takes a message of less than 2 to the power of 64 bits in length and produces a 160-bit message digest. The algorithm is slightly slower than MD5, but the larger message digest makes it more secure against brute-force collision and inversion attacks.
Whirlpool: It is designed by Vincent Rijmen and Paulo S. L. M. Barreto that operates on messages less than 2 to the power of 256 bits in length, and produces a message digest of 512 bits. Historically, WHIRLPOOL had three versions. The first version is WHIRLPOOL-0, its successor WHIRLPOOL-T, and WHIRLPOOL. Whirlpool was adopted by the International Organization for Standardization (ISO) in the ISO/IEC 10118-3:2004 standard.

References:

http://www.garykessler.net/library/crypto.html
http://www.x5.net/faqs/crypto/
http://en.wikipedia.org/wiki/Main_Page