INTRODUCTION TO CRYPTOGRAPHY
CONTENTS 1 INTRODUCTION ENCRYPTION AND SECRECY THE OBJECTIVES OF CRYPTOGRAPHY ATTACKS CRYPTOGRAPHIC PROTOCOLS PROVABLE SECURITY 2 SYMMETRIC-KEY ENCRYPTION STREAM CIPHERS BLOCK CIPHERS DES AES MODES OF OPERATION 3 PUBLIC-KEY CRYPTOGRAPHY THE CONCEPT OF PUBLIC-KEY CRYPTOGRAPHY MODULAR ARITHMETIC THE INTEGERS THE INTEGERS MODULO N RSA KEY GENERATION AND ENCRYPTION DIGITAL SIGNATURES ATTACKS AGAINST RSA PROBABILISTIC RSA ENCRYPTION CRYPTOGRAPHIC HASH FUNCTIONS SECURITY REQUIREMENTS FOR HASH FUNCTIONS CONSTRUCTION OF HASH FUNCTIONS DATA INTEGRITY AND MESSAGE AUTHENTICATION HASH FUNCTIONS AS RANDOM FUNCTIONS SIGNATURES WITH HASH FUNCTIONS THE DISCRETE LOGARITHM ELGAMAL’S ENCRYPTION ELGAMAL’S SIGNATURE SCHEME DIGITAL SIGNATURE ALGORITHM MODULAR SQUARING RABIN’S ENCRYPTION RABIN’S SIGNATURE SCHEME 4 CRYPTOGRAPHIC PROTOCOLS KEY EXCHANGE AND ENTITY AUTHENTICATION KERBEROS DI?E-HELLMAN KEY AGREEMENT KEY EXCHANGE AND MUTUAL AUTHENTICATION STATION-TO-STATION PROTOCOL PUBLIC-KEY MANAGEMENT TECHNIQUES IDENTI?CATION SCHEMES INTERACTIVE PROOF SYSTEMS SIMPLI?ED FIAT-SHAMIR IDENTI?CATION SCHEME ZERO-KNOWLEDGE FIAT-SHAMIR IDENTI?CATION SCHEME FIAT-SHAMIR SIGNATURE SCHEME COMMITMENT SCHEMES A COMMITMENT SCHEME BASED ON QUADRATIC RESIDUES A COMMITMENT SCHEME BASED ON DISCRETE LOGARITHMS HOMOMORPHIC COMMITMENTS ELECTRONIC ELECTIONS SECRET SHARING A MULTI-AUTHORITY ELECTION SCHEME PROOFS OF KNOWLEDGE NON-INTERACTIVE PROOFS OF KNOWLEDGE EXTENSION TO MULTI-WAY ELECTIONS ELIMINATING THE TRUSTED CENTER DIGITAL CASH BLINDLY ISSUED PROOFS A FAIR ELECTRONIC CASH SYSTEM UNDERLYING PROBLEMS 5 PROBABILISTIC ALGORITHMS COIN-TOSSING ALGORITHMS MONTE CARLO AND LAS VEGAS ALGORITHMS 6 ONE-WAY FUNCTIONS AND THE BASIC ASSUMPTIONS A NOTATION FOR PROBABILITIES DISCRETE EXPONENTIAL FUNCTION UNIFORM SAMPLING ALGORITHMS MODULAR POWERS QUADRATIC RESIDUOSITY PROPERTY FORMAL DE?NITION OF ONE-WAY FUNCTIONS HARD-CORE PREDICATES 7 BIT SECURITY OF ONE-WAY FUNCTIONS BIT SECURITY OF THE EXP FAMILY BIT SECURITY OF THE RSA FAMILY BIT SECURITY OF THE SQUARE FAMILY 8 ONE-WAY FUNCTIONS AND PSEUDORANDOMNESS COMPUTATIONALLY PERFECT PSEUDORANDOM BIT GENERATORS YAO’S THEOREM 9 PROVABLY SECURE ENCRYPTION CLASSICAL INFORMATION-THEORETIC SECURITY PERFECT SECRECY AND PROBABILISTIC ATTACKS PUBLIC-KEY ONE-TIME PADS PASSIVE EAVESDROPPERS CHOSEN-CIPHERTEXT ATTACKS A SECURITY PROOF IN THE RANDOM ORACLE MODEL SECURITY UNDER STANDARD ASSUMPTIONS UNCONDITIONAL SECURITY OF CRYPTOSYSTEMS THE BOUNDED STORAGE MODEL THE NOISY CHANNEL MODEL 10 PROVABLY SECURE DIGITAL SIGNATURES 101 ATTACKS AND LEVELS OF SECURITY 102 CLAW-FREE PAIRS AND COLLISION-RESISTANT HASH FUNCTIONS 103 AUTHENTICATION-TREE-BASED SIGNATURES 104 A STATE-FREE SIGNATURE SCHEME