CSCE 465 Lecture 10

« previous | Thursday, February 14, 2013 | next »

Lecture Slides

Introduction to Cryptography

(See :Category:MATH 470-502→)

• the art of secret writing
• convert data into untintelligible (random-looking) form
• must be reversible to recover original data without loss or modification

Not the same as compression:

• encryption is usually an $n$ bits in, $n$ bits out operation
• encryption can be combined with compression (encrypt then compress or compress then encrypt?)

Encryption/Decryption

plaintext --> encryption --> ciphertext --> decryption --> plaintext
                  ^                             ^
                  |                             |
                 key                           key

Cryptanalysis

"code breaking"

• Difficulty depends on sophistication of cipher
• amount of information available to code breaker
  • ciphertext only (exhaustive search until recognizable plaintext is found, but need enough ciphertext)
  • known plaintext (secret plaintext revealed, giving plaintext/ciphertext pair)
  • chosen plaintext (put chosen plaintext in, get resulting ciphertext)
• any cipher can be broken by brute force, but this is rarely practical

Cryptography is rarely the weakest link in security: implementation and distribution/protection of keys are weaker links

Evaluation

Unconditionally secure (perfectly secure)

uncertainty/entropy/randomness: $H(p)=H(p\mid c)$

Provably secure

Prove that a cipher system is as difficult to break as solving a well-known and supposedly difficult problem

Computationally Secure

Breaking the cipher requires massive resources

Secret Keys vs. Secret Algorithms

Security by Obscurity

• hard to keep secret if used widely
• reverse/social engineering
• already discussed

Publish Algorithm

• Keep key secret

Caesar Cipher

Shift alphabet by a fixed amount $n$. (|key space| = 26)

Generalized into Mono-Alphabetic Ciphers (|key space| = 26!) Remap letters arbitrarily

Can be broken by statistical analysis of letter frequencies: program letter, written by T. J. O'Connor

Permutation Ciphers

Permute each successive block of $n$ letters in the message according to position offset (+1, +3, −2, 0 −2), for example:

WHYOW|HYCAN|ITFLY
YWWOH|CHNAY|FTYLI

Cannot use frequency analysis

One-time Pad

A perfectly secure cipher requires:

• A key length at least as long as the message
• The key can only be used once

Use is limited due to need to negotiate and distribute long, random keys for every message

Generate random bit string (key) as long as plaintext, share with other communicating party, use XOR to encrypt/decrypt

 plaintext: 01011001 01000101 01010011
       key: 00010111 00001010 01110011
 -------------------------------------
ciphertext: 01001110 01001111 00100000

Types of Cryptography

Number of Keys

• Hash Functions: No key
• Secret Key Cryptography: one (secret) key (a.k.a symmentric)
• Public Key Cryptography: two keys, one public, one private (a.k.a. asymmetric)

• Stream Cipher: encrypt text one symbol at a time
• Block Cipher: divide message into blocks of symbols, and process them in sequence (may require padding)

Secret Key Cryptography

Same key used for encryption and decryption

Examples:

• Block ciphers: DES, IDEA, and AES
• Stream Cipher: RC4

Public Key Cryptography

• Public key used to encrypt
• Private key used to decrypt
• Invented/published in 1975
• Very slow compared to secret key cryptography

Example: RSA

Hash Algorithms

Also known as

• Message digest
• One-way function/transformations

Output is a fixed-length, short message (usually much shorter than message)

Usually fixed lengths: 128 or 160 bits

Examples: MD5, SHA1