Information Theory and Cryptography - Essay Example

www.academia-research.com Sumanta Sanyal d: 27/07/06 Information Theory and Cryptography Introduction Information theory can be defined as the mathematical aspect of processing data so that it can be communicated across different media. Such data processing can be compression of computer files, error-correcting codes such as those used in DVD players, digital television, etc. and cryptography. Cryptography is the art (or rather science) of writing in secret code and dates back to the ancient Egyptians (Kessler, Gary C., 1998). It may be said that cryptography is applicable wherever there is need of keeping information from being accessed by undesirable entities. In the present context, with the advent of computers in every aspect of daily routines of individuals and organizations in the 21st century, large amounts of information have to stored in or transmitted through unsafe media. It becomes essential that such information is not accessible to those who are not privy to it. Thus, to this effect of lending exclusivity to information stored or transmitted, the science of cryptography today has pervaded all areas of information technology today. Also in the present context, cryptography serves three major purposes: it prevents information theft, it prevents information from being altered by unauthorized entities, and it allows user authentication. (Kessler, Gary C., 1998) Towards these ends three types of cryptographic schemes are generally used today. The algorithms utilized in these schemes are described by the number of keys used to encrypt and decrypt data and additionally by their applications. Secret Key Cryptography (SKC) - These are symmetric algorithms using only a single key to both encrypt and decrypt. In this case all parties considered privy to the information use the same key. Public Key Cryptography (PKC) - These are asymmetric algorithms that use two keys - one key to encrypt and another to decrypt. One key is called the public key which may be advertised to all and sundry while the other is called the private key and this is only available to privy entities. It does not matter which key is used to encrypt or decrypt but the end-effect is the encryption allows the information to remain exclusive. Hash Function (One-Way Cryptography) - These algorithms have no key and they allow the plaintext to be encrypted once into ciphertext that is not recoverable. These algorithms are usually used to provide a digital fingerprint of data and act as proof that the data has not been altered by unauthorized entities including viruses. Often, these algorithms that primarily prove the integrity of the information encrypt passwords. (Kessler, Gary C., 1998) It should be noted that the above schema have been treated rudimentarily. There are numerous examples of each type of algorithm that are being used regularly in the information technology world but these too have been kept beyond the purview of this paper. Special Significance Cryptography also serves some security requirements specific to application-to-application communications in the information technology world. It serves to authenticate the users' identity. It should be noted in this context that the most widely used network in use today in the world - the Internet - has very weak host-to-host authentication in the forms of name or address based identity. It serves to maintain privacy and confidentiality by ensuring that only intended users have access to the relevant information. Both the sender and the receiver are reassured of these. It serves to non-repudiate - it authenticates that the sender really sent the message. (Kessler, Gary C., 1998) Cryptography is such a vast science today that if this paper was to treat to any extent all the concepts inherent within it this paper would take the semblance of a mere glossary of terms. Thus, to avoid such low denomination, the paper as decided to confine itself to ust two concepts within cryptography - entropy and unicity distance - that it will treat at some length. It will also examine how these two concepts fare within the ambit of a popular coding algorithm - the Huffman coding system. Entropy Entropy can be used to measure the unpredictability of plaintext content. "It is the negative logarithm of the probability of the process's most likely output". (Gennaro, Rosario, 2006). The higher a process's entropy the higher its unpredictability. A process with maximal entropy is absolutely random and its output is uniformly distributed. To understand these properties better the following example should suffice. The process of tossing 'N' coins has entropy 'N' because -log = N. For a more complex process - rolling a die N/4 times - is .65N. This is because each 4-bit string has probability of appearance of 1/6. Since each string is independent the probability of each appearing is . Thus, - log= N/4log 6 .65N. Base 2 logarithms are used here. The coin example has maximal entropy and so has perfect uniform distribution while the die example has relatively high entropy and commensurately uniform distribution. Cryptographers require processes to have random strings in uniform distributions but the physical reality of random processes is that they may have high entropy, that is, high unpredictability, which is not uniformly distributed at all. It is the job of cryptographers to even out such distributions so that their entropy is perfectly distributed. (Gennaro, Rosario, 2006) This makes encoding easy by lending uniformity to the processes. Unicity Distance Another important concept in cryptography that is highly germane to the purpose of this paper is unicity distance. It is a purely notional concept in that it is the logical distance between a ciphertext and the key used to decipher it. By logical distance is being meant that when the key is applied to the ciphertext it is found definitely that there is only one solution - the original plaintext that was initially coded to produce the ciphertext. In other words, unicity distance is a term that refers to the length of an original ciphertext needed to break the cipher by reducing the number of spurious keys to zero in a brute force attack (Schneier, Bruce, 1998). For plaintext messages as in English, the unicity distance is = k/6.8 where k = key length. The 6.8 denotes the redundancy of English in ASCII. Redundancy is the length of ciphertext that is not part of the key that constitutes the unicity distance. Other language plaintexts are more or less but not that much variant. As is obvious from the relation, as redundancy decreases unicity distance increases until, at zero redundancy, unicity distance is infinite. This happens when the plaintext itself wholly is a perfectly random key. In such a case the plaintext cannot be identified correctly through possible decipherment. The following mathematics better illustrates the concept. If the characters of the English alphabet are taken - 26 of them - a huge number of possible messages (N, the key space entropy) can be generated using them. N = under polyalphabetic Vigenere ciphering system, where L is the length of the message. Nevertheless, the rules of the language ensure that only a few of these messages are readable plaintext, say M of them. M is obviously very much smaller than N and has a direct one-to-one relationship with the number of keys that work. If there are K possible keys, K x M/N keys will work. Out of these only one key will be the correct one while the rest will be spurious. It is noted that N is dependent upon L and M upon K. For the relationship: K there is an L for which the relationship has unity value. This L is the unicity distance (Schneier, Bruce, 1998). It should be noted that under monoalphabetic ciphering where there is no periodicity within the source symbols, N = 26!. Cryptographers who use highly compressed files without lossless considerations generate abnormally low redundancy and operate at levels much above the unicity distance of the plaintext. This creates insecure encoding with possibilities of error during deciphering and security breaches. The paper shall next explore one popular coding concept and examine how entropy and the unicity distance fare within its context. Huffman Coding David A. Huffman, a Ph.D. student at MIIT, developed an entropy-encoded algorithm that could be used to generate lossless data compression and published it in his book "A Method for the Construction of Minimum-Redundancy Codes". The book was published in 1952. Later Huffman was appointed Professor Emeritus of Computer Science at the Baskin School of Engineering, University of California, Santa Cruz, and remained at this preeminent post till his death from cancer in 1999. Huffman coding uses variable-length code table that contains codes derived on the basis of probability of occurrence of the source symbol that is coded. The individual codes are prefix-free. No code for any source symbol contains any bit string that is the prefix of another bit string representing any other source symbol. More commonly occurring source symbols have shorter strings than that of those less frequently occurring. (Wikipedia, 2006) The following example best illustrates how Huffman coding works. Example: A frame of 10 values is taken in the following order: 3, 2, 3, 1, 4, 2, 0, 2, 1, 2. In the PCM format the values would get converted into three-bit binary units in the following manner: 001, 010, 011, 001, 100, 000, 000, 000, 001, 010. Thus, altogether 30 bits would be required to encode the entire frame. If Huffman coding is employed the following frame able would result: Original Frame Value Probability Number of Bits 2 0.4 1 1 0.2 2 3 0.2 3 4 0.1 4 0 0.1 4 It is noted in the table that 1 and 3 have the same probabilities but they are encoded in 2 and 3 bits respectively. These are equally valid but different Huffman codes. For 3 and 4 that also have the same probabilities the number of bits used to encode are equal. This is also valid as there is a '0' involved and the example illustrates that Huffman codes are not unique. () The total number of bits per value is: 0.4*1 + 0.2*2 + 0.2*3 + 0.1*4 + 0.1*4 = 2.2. This is quite lower than the number of bits (3) required for encoding the same value frame in the PCM format. Now, the actual Huffman coding employing binary units is being computed through the following reduced frames. Reduced Frame 3 Probability 0.6 0.4 The reduced frames are prepared by adding the smallest probabilities in the original frame till only two entities are left. The last two entities in Frame 3 - 0.6 and 0.4 - are assigned the binary digits 1 and 0 arbitrarily. In this case 0.6 is assigned 1 while 0.4 is assigned 0. In the next step the probabilities that made up the last combination 0.6 - 0.4 and 0.2 - are considered. Since 0.6 is assigned 1, this binary unit is made the first digit that is assigned to the combination. Thus, 0.4 is encoded as 10 while 0.2 is assigned 11. The extended reduced table frames (Fig. 1, Appendix) and the original table with computed final codes (Fig 2., Appendix) clearly demonstrate how the encoding is done. Finally, as Figures 1 & 2 illustrate, the sequence of values will be encoded in the following manner: 100, 0, 100, 11, 1010, 0, 1011, 0, 11, 0. The total number of bits is 22. Huffman Coding: The Extended Binary Tree The previous example of the frame with 10 values can be easily depicted in the form of a binary tree and it is a much more capable demonstration of the methodology applied to encode source symbols using Huffman coding. Figure 3 (Appendix) demonstrates how the values can be assembled in the form of a tree based on the Huffman coding system. The values with the least weights (0 and 4 being the least probable) form the external nodes and their combined weight of 0 + 4 = 4 form the internal node. IT should be noted that the values written within the circles and their probabilities written outside the circles add up perfectly to 10 within the final circle and 1 outside that same circle. Each individual internal node of the tree will be encoded as 0 (left branches) and 1 (right branches). As is evident from the diagram the paths to the larger weights are shorter than those to the smaller weights. The following table of iterations illustrates how each event is related to the other in the tree. (Mathworld, 2006) 2 1 3 4 0 10 3 3 4 0 10 4 6 0 10 0 10 As is usual in Huffman coding, binary units are assigned to each number according to an ascending order of probabilities - that with the highest probability and highest weight being assigned the least number of binary units - 0 - and that with the lowest probability value and least weight being assigned the largest number of binary units. (Mathworld, 2006) The above examples, especially the binary tree, amply demonstrate that the Huffman coding process ensures that each source symbol set is uniformly distributed at optimal entropy. Unicity distance between encoded symbol (ciphertext) and associated key is sustained with optimal redundancy as the compression is lossless. Since the coding treats symbols in pairs the probabilities are all approximated to the power of so that complications arising from actual source symbol probabilities generating non-integral number of binary units are entirely eliminated. Huffman Coding: English Characters The same process as that adopted to construct the binary tree in the previous example has been utilized to construct the one demonstrating how English characters are coded under the Huffman system. Figure 4 (Appendix) demonstrates the tree. It will be observed that 'z' and 'q' have the lowest probabilities at 0.1 and 0.2 respectively while 'e' has the highest probability at 12.8. As is usual, it makes sense to assign the least number of binary units to 'e', possibly 0, while assigning a suitably large number of such units to 'z' and 'q'. Conclusion It is noted in conclusion that cryptography codes that maintain the unicity distance lend high exclusivity to the keys they construct while codes that stray much beyond this limit tend to weaken this exclusivity. Also, the choice of the Huffman coding system is a good one as it is a system that generates both optimum entropy and unicity distance, particularly for source systems whose components tend to repeat themselves according to set patterns as the English characters that repeat according to their grammatical process. The coding also lends itself easily to heuristic designs as later changes in probabilities of the components of the source system can be easily accommodated within the coding system. References Gennaro, Rosario, Randomness in Cryptography, IEEE Security & Privacy, Vol. 4, No: 2, March/April 2006, P. 64-67. Huffman coding. Extracted on 24th July, 2006, from: http://webphysics.davidson.edu/faculty/dmb/py115/huffman_coding.htm Kessler, Gary C., 1998, An Overview of Cryptography. Extracted on 20th July, 2006, from: http://www.garykessler.net/library/crypto.html#intro Mathworld, 2006, Huffman Coding. Extracted on 24th July, 2006, from: http://mathworld.wolfram.com/HuffmanCoding.html Schneier, Bruce, 1998, How to Recognize Plaintext. Extracted on 24th July 2006, from: Wikipedia, 2006, Huffman Coding. Extracted on 20th July, 2006, from: http://en.wikipedia.org/wiki/Huffman_coding Wikipedia, 2006, Unicity Distance. Extracted on 20th July, 2006, from: http://en.wikipedia.org/wiki/Unicity_distance Appendix Figure 1: Extended Reduced Framework Figure 2: Original Frame with Computed Final Codes Original Frame Value Final Code Probability Number of Bits 2 0 0.4 1 1 11 0.2 2 3 100 0.2 3 4 1010 0.1 4 0 1011 0.1 4 Figure 3: Binary Tree (Values Example) Figure 4: Huffman Coding (Binary Tree for English Characters) Read More