Day1Fall06

Information about Day1Fall06

Published on January 12, 2008

Author: Saverio

Source: authorstream.com

Content

An Introduction to Cryptology and Coding Theory :  An Introduction to Cryptology and Coding Theory Sarah Spence Adams Olin College [email protected] Gordon Prichett Babson College [email protected] 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…

Related presentations


Other presentations created by Saverio

satellites
13. 02. 2008
0 views

satellites

3d sensor
07. 02. 2008
0 views

3d sensor

Kharzeev
09. 01. 2008
0 views

Kharzeev

ThesisWritingClinic
13. 01. 2008
0 views

ThesisWritingClinic

PPT PUNE Optical Illusions
14. 01. 2008
0 views

PPT PUNE Optical Illusions

07 Infant Mortality
15. 01. 2008
0 views

07 Infant Mortality

unit 10 the world around us
15. 01. 2008
0 views

unit 10 the world around us

unit 3 web
17. 01. 2008
0 views

unit 3 web

Welding Safety 2003
17. 01. 2008
0 views

Welding Safety 2003

HVAC Part1b
18. 01. 2008
0 views

HVAC Part1b

AF071018 jules and cable
18. 01. 2008
0 views

AF071018 jules and cable

SITE DRAINAGE student
20. 01. 2008
0 views

SITE DRAINAGE student

GNIS
22. 01. 2008
0 views

GNIS

Geo5 Vol Class Notes
11. 02. 2008
0 views

Geo5 Vol Class Notes

Opt Out HIV Testing Dr Brudney
12. 01. 2008
0 views

Opt Out HIV Testing Dr Brudney

CIMS 03 Comet
16. 01. 2008
0 views

CIMS 03 Comet

20080120
29. 01. 2008
0 views

20080120

TV AnytimeP2 kawamori final1a
31. 01. 2008
0 views

TV AnytimeP2 kawamori final1a

Mat Prod L13
13. 02. 2008
0 views

Mat Prod L13

KOHUT
14. 02. 2008
0 views

KOHUT

07 21 05 AQ 101
21. 02. 2008
0 views

07 21 05 AQ 101

Collage Portraits
25. 02. 2008
0 views

Collage Portraits

MET PRESENTATION longole
05. 03. 2008
0 views

MET PRESENTATION longole

ID Theft Class
04. 02. 2008
0 views

ID Theft Class

Entretiens
03. 03. 2008
0 views

Entretiens

whowerethecelts
08. 03. 2008
0 views

whowerethecelts

LeclercqECCMunich2003
06. 02. 2008
0 views

LeclercqECCMunich2003

Pollack0903
14. 03. 2008
0 views

Pollack0903

big17china
19. 03. 2008
0 views

big17china

Covering Conflict RTV310
24. 03. 2008
0 views

Covering Conflict RTV310

Leadership for followers
26. 03. 2008
0 views

Leadership for followers

APCH1
31. 03. 2008
0 views

APCH1

Travel Medicine Website
02. 04. 2008
0 views

Travel Medicine Website

key5
10. 04. 2008
0 views

key5

2003112714256586
15. 04. 2008
0 views

2003112714256586

pps 313
14. 02. 2008
0 views

pps 313

IC30203pt3 2
17. 04. 2008
0 views

IC30203pt3 2

Conference Programme 190308
22. 04. 2008
0 views

Conference Programme 190308

CarltonPresentation
24. 04. 2008
0 views

CarltonPresentation

trade presentation
07. 05. 2008
0 views

trade presentation

the world trade organisation
08. 05. 2008
0 views

the world trade organisation

sma
30. 04. 2008
0 views

sma

Intro to Legislation
02. 05. 2008
0 views

Intro to Legislation

Grammar Past participle
02. 05. 2008
0 views

Grammar Past participle

SportsNutrition2007
24. 01. 2008
0 views

SportsNutrition2007

The Bilities
30. 01. 2008
0 views

The Bilities

RAD Annapolis
22. 01. 2008
0 views

RAD Annapolis

Spammer X
24. 01. 2008
0 views

Spammer X

SKOS Catch 25nov05
17. 01. 2008
0 views

SKOS Catch 25nov05

UCSF STATE AIRFARE PROGRAM
21. 03. 2008
0 views

UCSF STATE AIRFARE PROGRAM

solarenergypolicy
21. 01. 2008
0 views

solarenergypolicy

odysseybackgroundnot es
10. 01. 2008
0 views

odysseybackgroundnot es

Kang LEAP model
12. 02. 2008
0 views

Kang LEAP model

ranskareseptitengxva lmis
14. 01. 2008
0 views

ranskareseptitengxva lmis

1430 A Roberts
03. 03. 2008
0 views

1430 A Roberts

DANE PP
15. 01. 2008
0 views

DANE PP

2007 12 behovsinventering
05. 02. 2008
0 views

2007 12 behovsinventering