Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 3022-1Computational Public-Key Cryptography•The scheme that we’ve created has advantages and disadvantages–In practice, cryptography tries to achieve a compromise22-2Real Cryptography•In practice, we utilize schemes that are practically secure–we drop the requirement for information-theoretical security; in effect, the scheme can be broken.–these schemes are designed such that breaking them is exceedingly difficult.•in fact, we don’t settle for exceedingly difficult, we establish the likelihood that a scheme may be broken mathematically•we rely on unproven mathematical conjectures and leverage them to create schemes that would take (literally) billions of years of computation on computers the size of many galaxies (given the current state of mathematics)22-3Real Cryptography•In return, for relaxing our security requirements we obtain the ability to:–use the same key for many transmissions–design schemes that work without a private channel even when establishing a shared secret key!•Of course, we need to ensure that the computation for encoding and legitimate decoding is quick, while the computation for breaking the scheme is a task of “cosmic proportions”22-4A Toy Example•let’s see a “toy” scheme that allows Alice and Bob to establish a shared secret key without relying on private channel at all.•invented in 1974. by Ralph Merkle at Stanford, “Merkle’s Puzzles”22-5Merkle’s Puzzles, Step I•Alice prepares 1000 puzzles–solution of each puzzle contains distinct number from 1 to 1000, and result of coin toss–Imagine: Alice gets 1000 blank sliding puzzles•on each puzzle, she writes a number and a coin toss•she records all 1000 numbers and coin toss results on a piece of paper for her later use22-6Merkle’s Puzzles, Step I•preparing the puzzles shouldn’t take long•if each takes 10 seconds, then all of them take about three hours1, Hscramblebg%;?2, Tscramble1*((J999, Tscrambleg&Hja1000, Hscramblel)(nb...... ...22-7Merkle’s Puzzles, Step I•but solving each puzzle should take much longer, –say 10 minutes•In this way, solving all of them would take about a week1, Hsolvebg%;?22-8Merkle’s Puzzles, Step II•Alice gives all the scrambled puzzles to Bob•We don’t care who else might see thembg%;?1*((JBlaBlZZZZZAB22-9Merkle’s Puzzles, Step III•Bob picks one puzzle at random and solves it–which takes him 10 minutesbg%;?1*((JBlaBlZZZZZABsolve2, T22-10Merkle’s Puzzles, Step IV•Bob sends back to Alice the number from the puzzle he solved, he knows the key associated with that number (tails) because he solved the puzzle.AB2, T222-11Merkle’s Puzzles, Step V•Alice looks up the key that she wrote next to that number (tails)AB2, T22, T22-12Merkle’s Puzzles, Result•both Alice and Bob agreed on a secret value, and they’ve done so in public!AB2, T2, T22-13Merkle’s Puzzles, Security•So, how would our Eavesdropper try to break this? –That is, learn the secret value they agree onAB22-14Merkle’s Puzzles, Security•she sees scrambled puzzles Alice gave to Bob•and the number that Bob sent to AliceABbg%;?1*((JBlaBlZZZZZ222-15Merkle’s Puzzles, Security•to find the puzzle to which this number belongs Eve must solve many puzzles•it would take three to four days to find the one with the specific number (on average)ABbg%;?1*((JBlaBlZZZZZ222-16Merkle’s Puzzles, Security•by the time she found it, Alice and Bob may have done what they wanted, so the solution no longer mattersbg%;?2solve2, T22-17Merkle’s Puzzles, Conclusion•In this example, legitimate parties (Alice and Bob) can establish a private secret key, in presence of eavesdroppers–the key can then be used for other cryptographic tasks, like our previous encryption examples•Of course, the security of this is not absolute–breaking the scheme merely takes much more resources than executing it legitimately, which is a risk22-18Merkle’s Puzzles, Conclusion•the gap between legitimate users’ work (three hours for Alice, ten minutes for Bob) and malicious ones’ (several days) measures the security•in real cryptographic schemes this gap is much larger: fractions of a second for legitimate users, billions of years for illegitimate ones22-19Compression22-20Why do we need compression?•If we can represent “something” digitally, isn’t that representation good enough?•What will we do with these bits?–Have them in memory–Store them on a disk–Transfer them across a network–Etc22-21Naughty bits•Why would it be better if we could represent the “same” digital data with less bits?–It takes time to transfer bits around in the computer. –Media capacity may be limited–Time to send across the network is greater than time to send bits around your computer.22-22What does it mean?•We need two algorithms:•One capable of taking bits that represent some data and producing a smaller set of bits.•One capable of take the smaller set of bits and reproducing the complete datacompression algorithm Aadecompression algorithmaA22-23Compression Schemes•Two general classifications of compression schemes–Lossless – the process of encoding then decoding will produce the original data *exactly*–Lossy – the process of encoding then decoding will lose some data in the process•How could this be okay?•Lossy compression is characterized by some amount of degradation.•What happens if we compress, decompress, compress again and decompress again ?22-24Compression Schemes•Run Length Encoding:–Imagine we have data to send111111111000010101011000000000110101111111000–Notice there are repeating values of consecutive 1’s or 0’s –We call each sequence of like characters a “run”–Instead of representing each character, we represent a number of characters followed by the character.–91 40 11 10 11 10 11 10 21 90 21 10 11 10 71 30–To maximize savings, it would be ideal if we could specify runs separately•*91*40101010*21*90*21010*71*3022-25Run Length Encoding•RLE can be applied at a higher level as well (instead of the eventual bits, we can use RLE on the text)–AAAAGGHSSSSSSINFEEEEESRL•*4A*2GH*6SINF*5ESRL•Is RLE lossy or lossless?•Would RLE work well on all files?–Text