Next:
Contents
Contents
Notes on Cryptography
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
One-time pads
Example 3: A Transposition System
Introduction to Number Theory
Congruences
The Greatest Common Divisor
Powers modulo a prime
Primitive roots
Proof of Theorem 5
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
Computing square roots modulo a prime
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
Computer passwords
Message verification
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
Analysis of the Rabin test
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
The procedure
Pseudo-random number generators
The Quadratic Generator
The Next Bit Theorem
The Efficient Test Theorem
A consequence involving symmetry
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 ...
Translated from LaTeX by Scott Sutherland
2002-12-14
