**Charles Blair**

*Business Administration Dept.*

**©1991,1993,1994 by the author**

University of Illinois

- Contents
- Traditional Encryption Systems
- Example 1: Simple substitution
- Example 2: The Vigenère cipher and one-time pads
- Example 3: A Transposition System

- Introduction to Number Theory

- Encryption techniques based on powers and congruences
- The Diffie-Hellman key exchange procedure
- The Rivest-Shamir-Adleman public key system
- A public key system as hard as factoring

- Subset-Sum (Knapsack) problems and their uses
- Subset-sum problems are hard
- A proposed public-key system based on subset-sum
- Breaking Knapsack Cryptosystems
- Other uses of the subset-sum problem

- Subset-Sum Problems and NP-Completeness
- The Satisfiability Problem
- Converting (SP) to (SSP)
- Converting (SSP) to (SP)
- Cook's Theorem
- Terminology

- A probabilistic test for primality

- Probabilistic Encryption
- The Goldwasser-Micali encryption system
- Weak laws of large numbers
- The magic of sampling
- Determining algorithm performance by sampling
- Two versions of QRA
- Knowing a pseudo-square does not help much
- The inability to distinguish two plaintexts
- Semantic Security
- How to play poker over the telephone

- Pseudo-random number generators

- Further results on pseudo-random generators
- Hard-Core Predicates and Pseudo-Random Numbers
- Construction of hard-core predicates
- A recent pseudo-random number generator

- About this document ...

2002-12-14