Day1Fall06

67 %
33 %
Information about Day1Fall06
Entertainment

Published on January 12, 2008

Author: Saverio

Source: authorstream.com

An Introduction to Cryptology and Coding Theory :  An Introduction to Cryptology and Coding Theory Sarah Spence Adams Olin College sarah.adams@olin.edu Gordon Prichett Babson College prichett@babson.edu Communication System:  Communication System Cryptology:  Cryptology Cryptography Inventing cipher systems; protecting communications and storage Cryptanalysis Breaking cipher systems Cryptography:  Cryptography Cryptanalysis:  Cryptanalysis What is used in Cryptology?:  What is used in Cryptology? Cryptography: Linear algebra, abstract algebra, number theory Cryptanalysis: Probability, statistics, combinatorics, computing Caesar Cipher:  Caesar Cipher ABCDEFGHIJKLMNOPQRSTUVWXYZ Key = 3 DEFGHIJKLMNOPQRSTUVWXYZABC Example Plaintext: OLINCOLLEGE Encryption: Shift by KEY = 3 Ciphertext: ROLQFROOHJH Decryption: Shift backwards by KEY = 3 Cryptanalysis of Caesar:  Cryptanalysis of Caesar Try all 26 possible shifts Frequency analysis Substitution Cipher:  Substitution Cipher Permute A-Z randomly: A B C D E F G H I J K L M N O P… becomes H Q A W I N F T E B X S F O P C… Substitute H for A, Q for B, etc. Example Plaintext: OLINCOLLEGE Key: PSEOAPSSIFI Cryptanalysis of Substitution Ciphers:  Cryptanalysis of Substitution Ciphers Try all 26! permutations – TOO MANY! Bigger than Avogadro's Number! Frequency analysis One-Time Pads:  One-Time Pads Map A, B, C, … Z to 0, 1, 2, …25 A B … M N … T U 0 1 … 13 14 … 20 21 Plaintext: MATHISUSEFULANDFUN Key: NGUJKAMOCTLNYBCIAZ Encryption: “Add” key to message mod 26 Ciphertext: BGO….. Decryption: “Subtract” key from ciphertext mod 26 Modular Arithmetic:  Modular Arithmetic One-Time Pads:  One-Time Pads Unconditionally secure Problem: Exchanging the key There are some clever ways to exchange the key – we will study some of them! Public-Key Cryptography:  Public-Key Cryptography Diffie & Hellman (1976) Known at GCHQ years before Uses one-way (asymmetric) functions, public keys, and private keys Public Key Algorithms:  Public Key Algorithms Based on two hard problems Factoring large integers The discrete logarithm problem WWII Folly: The Weather-Beaten Enigma:  WWII Folly: The Weather-Beaten Enigma Need more than secrecy….:  Need more than secrecy…. Need reliability! Enter coding theory….. What is Coding Theory?:  What is Coding Theory? Coding theory is the study of error-control codes Error control codes are used to detect and correct errors that occur when data are transferred or stored What IS Coding Theory?:  What IS Coding Theory? A mix of mathematics, computer science, electrical engineering, telecommunications Linear algebra Abstract algebra (groups, rings, fields) Probability&Statistics Signals&Systems Implementation issues Optimization issues Performance issues General Problem:  General Problem We want to send data from one place to another… channels: telephone lines, internet cables, fiber-optic lines, microwave radio channels, cell phone channels, etc. or we want to write and later retrieve data… channels: hard drives, disks, CD-ROMs, DVDs, solid state memory, etc. BUT! the data, or signals, may be corrupted additive noise, attenuation, interference, jamming, hardware malfunction, etc. General Solution:  General Solution Add controlled redundancy to the message to improve the chances of being able to recover the original message Trivial example: The telephone game The ISBN Code:  The ISBN Code x1 x2… x10 x10 is a check digit chosen so that S = x1 + 2x2 + … + 9x9 + 10x10 = 0 mod 11 Can detect all single and all transposition errors ISBN Example:  ISBN Example Cryptology by Thomas Barr: 0-13-088976-? Want 1(0) + 2(1) + 3(3) + 4(0) + 5(8) + 6(8) + 7(9) + 8(7) + 9(6) + 10(?) = multiple of 11 Compute 1(0) + 2(1) + 3(3) + 4(0) + 5(8) + 6(8) + 7(9) + 8(7) + 9(6) = 272 Ponder 272 + 10(?) = multiple of 11 Modular arithmetic shows that the check digit is 8!! UPC (Universal Product Code):  UPC (Universal Product Code) x1 x2… x12 x12 is a check digit chosen so that S = 3x1 + 1x2 + … + 3x11 + 1x12 = 0 mod 10 Can detect all single and most transposition errors What transposition errors go undetected? The Repetition Code :  The Repetition Code Send 0 and 1 Noise may change 0 to 1 or change 1 to 0 Instead, send codewords 00000 and 11111 If noise corrupts up to 2 bits, decoder can use majority vote and decode received word as 00000 The Repetition Code:  The Repetition Code The distance between the two codewords is 5, because they differ in 5 spots Large distance between codewords is good! The “rate” of the code is 1/5, since for every bit of information, we need to send 5 coded bits High rate is good! When is a Code “Good”?:  When is a Code “Good”? Important Code Parameters (n, M, d) Length (n) Number of codewords (M) Minimum Hamming distance (d): Directly related to probability of decoding correctly Code rate: Ratio of information bits to codeword bits How Good Does It Get?:  How Good Does It Get? What are the ideal trade-offs between rate, error-correcting capability, and number of codewords? What is the biggest distance you can get given a fixed rate or fixed number of codewords? What is the best rate you can get given a fixed distance or fixed number of codewords? 1969 Mariner Mission:  1969 Mariner Mission We’ll learn how Hadamard matrices were used on the 1969 Mariner Mission to build a rate 6/32 code that is approximately 100,000x better at correcting errors than the binary repetition code of length 5 1980-90’s Voyager Missions:  1980-90’s Voyager Missions Better pictures need better codes need more sophisticated mathematics… Picture transmitted via Reed-Solomon codes Summary:  Summary From Caesar to Public-Key…. from Repetition Codes to Reed-Solomon Codes…. More sophisticated mathematics  better ciphers/codes Cryptology and coding theory involve abstract algebra, finite fields, rings, groups, probability, linear algebra, number theory, and additional exciting mathematics! Who Cares?:  Who Cares? You and me! Shopping and e-commerce ATMs and online banking Satellite TV & Radio, Cable TV, CD players Corporate/government espionage Who else? NSA, IDA, RSA, Aerospace, Bell Labs, AT&T, NASA, Lucent, Amazon, iTunes…

Add a comment

Related presentations

Related pages

The "rate" of the code is 1/5, since for every ...

The "rate" of the code is 1/5, since for every bit of information, we need to send 5 coded bits from MATH 110 at BYU
Read more

NGUJKAMOCTLNYBCIAZ Encryption: “Add” key to message ...

Day1Fall06. Download Document. Showing pages : 11 - 20 of 32. This preview has blurred sections. Sign up to view the full version! View Full Document .
Read more

Rings,Fields | PPT Directory

Rings,Fields 1. Rings, Integral Domains and Fields . 1.1.Rings; A ring (R,+, ?) is a set R, together with two binary operations + and ? on R satisfying the
Read more

Cryptology | PPT Directory

Cryptology What is Cryptology? Cryptology is the umbrella word that represents the art of enciphering words so as to protect their original meaning
Read more

San Bernardino Valley College MATH 942 - Ace ...

Improve your grade in San Bernardino Valley College MATH 942 with videos, lecture notes, exams, and interactive tutorials from Learning Ace!
Read more

University of Toledo MATH 4330 - Ace Recommendation Platform

Improve your grade in University of Toledo MATH 4330 with videos, lecture notes, exams, and interactive tutorials from Learning Ace!
Read more

Mathematics powerpoint presentation files – slides ...

Mathematics powerpoint presentation files – slides – ppt files ... http://faculty.olin.edu/~sadams/CCT/Day1Fall06.ppt.
Read more