Cryptography, Information Theory, and Error-Correction. Aiden A. Bruen
Читать онлайн книгу.
We discuss perfect security in detail in Part II of the book where it is shown that, under appropriate conditions, perfect security corresponds precisely to a Latin square. Shannon's paper makes it quite clear that he was aware of this phenomenon though he did not explicitly state it.
In the paper, Shannon clearly differentiates between computational and unconditional security. Whether or not he “missed” public key cryptography is far from clear. However, in [Mas02] Massey points out that Hellman of Diffie–Hellman fame, has credited the following words from Shannon's paper as the inspiration for their discovery:
The problem of good cipher design is essentially one of finding difficult problems
Of course, the jury is still out, as Massey [Mas02] points out, on whether one‐way functions, the foundations of public key cryptography, really exist. We refer to Chapters 3 and 4 on this point.
Shannon theory: information compression and communication.
Shannon's revolutionary paper [Sha49b] on information theory electrified the scientific world and has dominated the area of communication theory for over 50 years. No other work of the twentieth century has had greater impact on science and engineering.
First of all, Shannon unified what had been a diverse set of communications – voice, data, telegraphy, and television. He quantified and explained exactly what information means. The unit of information is the Shannon bit. As Golomb et al. [GBC+02] so elegantly puts it, this is the “amount of information gained (or entropy removed) upon learning the answer to a question whose two possible answers were equally likely, a priori.”
In the above, we can think of entropy as “uncertainty” analogous to entropy in physics (which is the key idea in the second law of thermodynamics). An example would be the tossing of a fair coin and learning which turned up – heads or tails. If the coin were biased, so that the probability of a head was
Note that when
It can be mathematically proven that the only information function that gives sensible results is the appropriate generalization to a probability distribution of Formula (1.1) above. Formula (1.1) ties in to the fundamental notion of entropy (or uncertainty). There are many examples of redundancy in the English language, i.e. the use of more letters or words or phrases than are necessary to convey the information content being transmitted. As Shannon points out, the existence of redundancy in the language is what makes crosswords possible.
This redundancy can be reduced in various ways. An example is by writing acronyms such as “U.S.” for “United States.” When information is to be electronically transmitted, we remove redundancy by data‐compression. Shannon's formula for data compression is intimately related to entropy which is in turn related to the average number of yes–no questions needed to pin down a fact. Shannon showed that it is possible to obtain a bound for the maximum compression which is the best possible. The actual technique for compressing to that ultimate degree is embodied in the construction of the so‐called Huffman codes, well known to all computer science undergraduates. Later, other compression techniques followed, leading to modern technologies used in, for example, mp3's (music compression). This part of Shannon's work is also connected to the later work of Kolmogorov on algorithmic complexity and the minimum length binary program needed for a Turing machine to print out a given sequence.
But this was only the beginning. Shannon then went on to prove his fundamental result on communication, based on entropy and the mathematical ideas delineated above. He showed that any given communications channel has a maximum capacity for reliably transmitting information which he calculated. One can approach this maximum by certain coding techniques – random coding and now turbo coding – but one can never quite reach it. To put it succinctly: Capacity is the bound to error‐free coding. Thus, for the last 50 years, the study of error correction has boiled down to attempts to devise techniques of encoding in order to come close to the Shannon capacity. We will have much to say about this bound in Parts II and III of this book.
Shannon's work, theoretical and practical, still dominates the field and the landscape. To quote Cover in [Cov02]:
This ability to create new fields and develop their form and depth surely places Shannon in the top handful of creative minds of the century.
Few can disagree with this assessment. Indeed, in Part III of this book, we describe protocols in cryptography and error‐correction based squarely on C.E. Shannon's work in information theory.
1.6 The Data Encryption Standard Code, DES, 1977–2005
The Data Encryption Standard, or DES, was originally approved in 1977 as a block cipher algorithm that provides good cryptographic protection. Computational power has increased dramatically since 1977. DES is no longer considered to be secure. Since May 2005, it is recommended that DES no longer be used [Cen19].
The Advanced Encryption Standard, or AES, the replacement for DES, is detailed in Section 5.2.
1.7 Post‐Shannon Developments
Cybersecurity
The first two decades of the twenty‐first century have witnessed an explosive growth of global need for secure communications and the secure storage of data. Cybersecurity has become an area of major concern to governments and companies. Universities now offer entire degrees in cybersecurity. We discuss this more in Section 28.5.
Big data
In this big data era in which governments and private companies collect more and more information from, and make more information available to individuals in a variety of electronic formats. Along with the usual technological advances in the hardware and software of computers and networks that took place at the end of the twentieth century, there has been an increase in the variety and the uses of technology, including new devices such as smart phones, tablets, smart watches, apps on these devices, a multitude of devices from the Internet of Things (IoT), and cloud computing.