DOC PREVIEW
UT CS 361 - Lecture Notes

This preview shows page 1-2-3 out of 8 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Foundations of Computer SecurityLecture 42: A Perfect CipherDr. Bill YoungDepartment of Computer SciencesUniversity of Texas at AustinLecture 42: 1 A Perfect CipherA Perfect Cipher... ...... ...{M}K?SenderAnalystA perfect cipher wouldbe one for which no reduction of thesearch space is gained from knowing:1the encryption algorithm, and2the ciphertext.Shannon proved that a perfectcipher requires as many possible keys asplaintexts, with the key chosen randomly.Lecture 42: 2 A Perfect CipherOne Time PadA one-time pad, invented by Miller (1882) and independently byVernam and Mauborgne (1917), is a theoretically perfect cipher.The idea is to use a key that is the same length as the plaintext,and to use it only once. The key is XOR’d with the plaintext.Example: Given a 15-bit binary message:plaintext: 10110010111001key: 11010001010100ciphertext: 01100011101101Notice the space of plaintexts, ciphertexts, and keys are all thesame: 15-bit binary strings.Lecture 42: 3 A Perfect CipherOne Time Pad000001111...000001111...SenderAnalyst ?101 = P xor KWhy is the one-time pad perfect? Consider the space of three-bitmessages.Suppose the attackerintercepts the ciphertext (“101”)and knows that a one-time pad is in use.Every possible plaintextcould be the pre-image of that ciphertextunder a plausible key. Therefore, noreduction of the search space is possible.Why does it matter that the key berandom?Lecture 42: 4 A Perfect CipherKey DistributionThe main problem with the one-time pad is practical, rather thantheoretical.Given the need to communicate securely, how do the sender andreceiver agree on a secret (key) that they can use in the algorithm.If sender and receiver already have a secure channel, why dothey need the key?If they don’t, how do they distribute the key securely?This is the key distribution problem.Lecture 42: 5 A Perfect CipherVernam CipherThe Vernam cipher is a type of one-time pad suitable for use oncomputers.XOR- - -plaintext ciphertextoriginalplaintextXORlong seq. of numbers¡¡¡¡¡ª@@@@@RLecture 42: 6 A Perfect CipherOne Time Pad ApproximationApproximate the one-time pad using a PRNG to generate a key.Another computer running the same random number generatorfunction can produce the key from the seed. This works wellbecause a pseudorandom sequence may have a very long period.It is susceptible to compromise by someone who knows thealgorithm and the seed.Lecture 42: 7 A Perfect CipherLessonsThe one-time pad is a theoretically perfect encryptionalgorithm.However, it requires as much key material as there isplaintext, and suffers from the key distribution problem.An approximation suitable for computers uses a PRNG togenerate a seed.Next lecture: Transposition CiphersLecture 42: 8 A Perfect


View Full Document

UT CS 361 - Lecture Notes

Documents in this Course
Load more
Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?