An Introduction to Cryptology and Coding Theory

An Introduction to Cryptology and Coding Theory : An Introduction to Cryptology and Coding Theory Discrete Math 2006

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 (?) Frequency analysis

One-Time Pads : One-Time Pads Map A, B, C, … Z to 0, 1, 2, …25 Plaintext: MATHISUSEFULANDFUN Key: NGUJKAMOCTLNYBCIAZ Encryption: “Add” key to message mod 26 Decryption: “Subtract” key from ciphertext mod 26

One-Time Pads : One-Time Pads Unconditionally secure Problem: Exchanging the key There are some clever ways to exchange the key….

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 (Duc and Andrew) 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

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?

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…