CS 161 Computer SecurityFall 2008 Dawn Song Notes 21 Brief History of CryptographyThe word “cryptography” comes from the latin root crypt meaning secret, and graphia, meaning writing. Socryptography is literally the study of how to send secret messages. In the next few lectures we shall studyencryption schemes as well as some other fundamental goals of cryptography: authentication and digitalsignatures.Schemes for sending secret messages go back to antiquity - the Romans used the “Caesar cypher” whichconsists of permuting the alphabet by simply shifting each letter forward by a fixed amount. For example,Caesar used a shift by 3 so the message “cryptography” would be encoded as ”fubswrjudskb”. With thedevelopement of the telegraph (wireless communication) at the end of the nineteenth century, the need forencryption in military and diplomatic communications became particularly important. The codes that wereused during this “pen and ink” period were relatively simple since messages had to be decoded by hand.The codes were not very secure especially with the use of mathematical and statistical techniques.The second phase of cryptography, the “mechanical era” was the result of an intense German project tocreate a mechanical device for encrypting messages in an unbreakable code. The resulting Enigma machinewas a remarkable engineering feat. Even more remarkable was the massive British effort to break the code.The breaking of the Enigma code was an important event that determined the course of World War II, andaccording to most experts shortened the war by about a year. There were two important factors in the break-ing of the Enigma code: first, the British managed to obtain a replica of a working Enigma machine fromPoland, which had cracked a simpler version of the code. The second factor was scale and sophistication ofthe code breaking effort, first by the Poles, who employed a large contingent of mathematicians to crack thestructure, and then by the British, whose massive effort included Alan Turing, one of the founding fathersof computer science.Modern cryptography is distinguished by its reliance on mathematics and electronic computers. It has itsearly roots in the work of Claude Shannon following World War II. The analysis of the one-time pad later inthis lecture is due to Shannon. The early seventies saw the the introduction of the cryptosystem DES by NIST(the National Institute for Standards in Technology). DES answered the growing need for digital encryptionstandards in banking and other business. The decade starting in the late seventies saw an explosion of workon a computational theory of cryptography.The most basic problem in cryptography is one of ensuring the security of communications across an in-secure medium. The two main members of the cast of characters in cryptography are Alice and Bob whowish to communicate securely as though they were in the same room or were provided with a dedicated,untappable line. In actual fact they have available a telephone line or an internet connection which can betapped by Eve, the eavesdropper. The goal is to design a scheme for scrambling the messages between Aliceand Bob in such a way that Eve has no clue about the content of their exchange. In other words we wish tosimulate the ideal commuication channel with the available insecure channel.In a symmetric trust model or the shared-key model, Alice and Bob share a random key K that is unknown toEve. Alice encrypts her message A based on the key K, and Bob decrypts the received ciphertext (to recoverCS 161, Fall 2008, Notes 2 1the original message, the plaintext) using the same key K.Let us now examine the threat model, which in this setting involves answering the question, how powerful isEve? We will assume that Eve knows the encryption and decryption algorithms. The only information sheis missing is the secret key K. There are several possibilities about how much access Eve has to the insecurechannel:1. Eve has managed to intercept a single encrypted message and wishes to recover the plaintext (theoriginal message).2. Eve has intercepted an encrypted message and also has some partial information about the plaintext.3. Eve can trick Alice to encrypt messages of her choice (this might happen if Eve has access to theencryption program).4. Eve can trick Bob into decrypting some ciphertexts.2 One time Pad:The one time pad is a simple and idealized encryption scheme that will help illustrate some importantconcepts. Alice and Bob share an n-bit secret key K = k1...knwhere the bits k1,...knare picked at random(they are the outcomes of independent unbiased coinflips).Suppose Alice wishes to send the n-bit message A = a1,...an.The desired properties of the encryption scheme are:1. It should scramble up the message. i.e. map it to a ciphertext B = b1...bn.2. Given knowledge of the secret key K, it should be easy to recover A from B.3. Eve, who does not know K, should get no information about A.The encryption scheme is very simple: bj= aj⊕ kj, where ⊕ is the xor or exclusive-or of the two bits (0 ifthe two bits are the same and 1 if they are different).Decryption is equally simple: aj= bj⊕ kj.To sum up, the one-time pad (or any symmetric encryption scheme) is described by specifying three proce-dures:Key generation: Alice and Bob pick a shared random key K. Encryption algorithm: B = A ⊕ K. Decryptionalgorithm: A = B ⊕ K.Let us now analyze how much information Eve gets about the plaintext A by intercepting the ciphertext B.What is the correct measure of this information gained by Eve. It might be the case that Eve had some partialinformation about A to begin with. Perhaps she knew that the last bit of A is a 0 or that 90% of the bits of Aare 10s. We wish to show that after intercepting B, Eve gets no additional information about A.We will show this by proving that no matter what the value of A is, the transmitted value b is a uniformlyrandom n-bit string.Another way of saying this is the following:CS 161, Fall 2008, Notes 2 2Consider the following experiment - suppose Alice has sent one of two messages A or A0. Eve tries todistinguish which by looking at the ciphertext. We will show that Eve’s success probability is 1/2, which isno different than it would be if she had not intercepted the ciphertext at all.The proof is very simple: how does the one-time pad encrypt a particular message A? Each possible value ofthe ciphertext B can be achieved by an appropriate
View Full Document
Unlocking...