COMPUTER SECURITY AND CRYPTOGRAPHY
CONTENTS CHAPTER THE LEXICON OF CRYPTOGRAPHY CRYPTOGRAPHIC SYSTEMS CRYPTANALYSIS SIDE INFORMATION CRYPTOGRAPHY AND HISTORY CRYPTOGRAPHY AND COMPUTERS THE NATIONAL SECURITY AGENCY THE GIANTS NO SEX, MONEY, CRIME OR LOVE AN EXAMPLE OF THE INFERENCE PROCESS IN CRYPTANALYSIS WARNING! CHAPTER SHANNON’S CLASSI?CATION OF SECRECY TRANSFORMATIONS THE RULES OF COLUMNAR TRANSPOSITION ENCIPHERMENT CRIBBING EXAMPLES OF CRIBBING PLAINTEXT LANGUAGE MODELS COUNTING K-GRAMS DERIVING THE PARAMETERS OF A MARKOV MODEL FROM SLIDING WINDOW COUNTS MARKOV SCORING THE ADFGVX TRANSPOSITION SYSTEM CODA COLUMNAR TRANSPOSITION PROBLEMS MONOALPHABETIC SUBSTITUTION CAESAR’S CIPHER CRIBBING USING ISOMORPHS THE X2-TEST OF A HYPOTHESIS PRUNING FROM THE TABLE OF ISOMORPHS PARTIAL MAXIMUM LIKELIHOOD ESTIMATION OF A MONOALPHABETIC SUBSTITUTION THE HIDDEN MARKOV MODEL (HMM) HILL ENCIPHERMENT OF ASCII N-GRAMS GAUSSIAN ELIMINATION MONOALPHABETIC SUBSTITUTION PROBLEMS RUNNING KEYS BLAISE DE VIGENE`RE GILBERT S VERNAM THE ONE-TIME PAD FINDING THE KEY OF VERNAM–VIGENE`RE CIPHERTEXT WITH KNOWN PERIOD BY CORRELATION COINCIDENCE VENONA POLYALPHABETIC SUBSTITUTION PROBLEMS WEAKNESSES IN A CRYPTOSYSTEM THE KOLMOGOROV–SMIRNOV TEST NIST’S PROPOSED STATISTICAL TESTS DIAGNOSIS STATISTICAL TESTS PROBLEMS THE ROTOR ROTOR SYSTEMS ROTOR PATENTS A CHARACTERISTIC PROPERTY OF CONJUGACY ANALYSIS OF A 1-ROTOR SYSTEM: CIPHERTEXT ONLY THE DISPLACEMENT SEQUENCE OF A PERMUTATION ARTHUR SCHERBIUS ENIGMA KEY DISTRIBUTION PROTOCOL CRYPTANALYSIS OF THE ENIGMA CRIBBING ENIGMA CIPHERTEXT THE LORENZ SCHLU¨SSELZUSATZ THE SZ40 PIN WHEELS SZ40 CRYPTANALYSIS PROBLEMS CRIBBING SZ40 CIPHERTEXT JAPANESE SIGNALING CONVENTIONS HALF-ROTORS COMPONENTS OF THE RED MACHINE CRIBBING RED CIPHERTEXT GENERALIZED VOWELS AND CONSONANTS “CLIMB MOUNT ITAKA” – WAR! COMPONENTS OF THE PURPLE MACHINE THE PURPLE KEYS CRIBBING PURPLE: FINDING THE V-STEPPER CRIBBING PURPLE: FINDING THE C-STEPPERS STREAM CIPHERS FEEDBACK SHIFT REGISTERS THE CHARACTERISTIC POLYNOMIAL OF A LINEAR FEEDBACK SHIFT REGISTER PROPERTIES OF MAXIMAL LENGTH LFSR SEQUENCES LINEAR EQUIVALENCE COMBINING MULTIPLE LINEAR FEEDBACK SHIFT REGISTERS MATRIX REPRESENTATION OF THE LFSR CRIBBING OF STREAM ENCIPHERED ASCII PLAINTEXT NONLINEAR FEEDBACK SHIFT REGISTERS NONLINEAR KEY STREAM GENERATION IRREGULAR CLOCKING STREAM ENCIPHERMENT PROBLEMS LUCIFER DES THE DES S-BOXES, P-BOX, AND INITIAL PERMUTATION (IP) DES KEY SCHEDULE SAMPLE DES ENCIPHERMENT CHAINING IS DES A RANDOM MAPPING? DES IN THE OUTPUT-FEEDBACK MODE (OFB) CRYPTANALYSIS OF DES DIFFERENTIAL CRYPTANALYSIS THE EFS DES-CRACKER WHAT NOW? THE FUTURE ADVANCED DATA ENCRYPTION STANDARD AND THE WINNER IS! THE RIJNDAEL OPERATIONS THE RIJNDAEL CIPHER RIJNDAEL’S STRENGTH: PROPAGATION OF PATTERNS WHEN IS A PRODUCT BLOCK-CIPHER SECURE? GENERATING THE SYMMETRIC GROUP A CLASS OF BLOCK CIPHERS THE IDEA BLOCK CIPHER IN THE BEGINNING KEY DISTRIBUTION E-COMMERCE PUBLIC-KEY CRYPTOSYSTEMS: EASY AND HARD COMPUTATIONAL PROBLEMS DO PKCS SOLVE THE PROBLEM OF KEY DISTRIBUTION? P S SUBSET SUM AND KNAPSACK PROBLEMS MODULAR ARITHMETIC AND THE EUCLIDEAN ALGORITHM A MODULAR ARITHMETIC KNAPSACK PROBLEM TRAP-DOOR KNAPSACKS KNAPSACK ENCIPHERMENT AND DECIPHERMENT OF ASCII-PLAINTEXT CRYPTANALYSIS OF THE MERKLE–HELLMAN KNAPSACK SYSTEM (MODULAR MAPPING) DIOPHANTINE APPROXIMATION SHORT VECTORS IN A LATTICE KNAPSACK-LIKE CRYPTOSYSTEMS KNAPSACK CRYPTOSYSTEM PROBLEMS A SHORT NUMBER-THEORETIC DIGRESSION RSA THE RSA ENCIPHERMENT AND DECIPHERMENT OF ASCII-PLAINTEXT ATTACK ON RSA WILLIAMS VARIATION OF RSA MULTIPRECISION MODULAR ARITHMETIC NUMBER THEORY AND CRYPTOGRAPHY PRIME NUMBERS AND THE SIEVE OF ERATOSTHENES POLLARD’S P 2 1 METHOD POLLARD’S R-ALGORITHM QUADRATIC RESIDUES RANDOM FACTORIZATION THE QUADRATIC SIEVE (QS) TESTING IF AN INTEGER IS A PRIME THE RSA CHALLENGE PERFECT NUMBERS AND THE MERSENNE PRIMES MULTIPRECISION ARITHMETIC PRIME NUMBER TESTING AND FACTORIZATION PROBLEMS THE DISCRETE LOGARITHM PROBLEM MODULO P SOLUTION OF THE DLP MODULO P GIVEN A FACTORIZATION OF P 2 ADELMAN’S SUBEXPONENTIAL ALGORITHM FOR THE DISCRETE LOGARITHM PROBLEM THE BABY-STEP, GIANT-STEP ALGORITHM THE INDEX-CALCULUS METHOD EXTENSION FIELDS THE CURRENT STATE OF DISCRETE LOGARITHM RESEARCH ELLIPTIC CURVES THE ELLIPTIC GROUP OVER THE REALS LENSTRA’S FACTORIZATION ALGORITHM THE ELLIPTIC GROUP OVER ZP ( P 3) COMPUTATIONS IN THE ELLIPTIC GROUP EZM,2(A, B) SUPERSINGULAR ELLIPTIC CURVES DIF?E–HELLMAN KEY EXCHANGE USING AN ELLIPTIC CURVE THE MENEZES–VANSTONE ELLIPTIC CURVE CRYPTOSYSTEM THE ELLIPTIC CURVE DIGITAL SIGNATURE ALGORITHM THE CERTICOM CHALLENGE NSA AND ELLIPTIC CURVE CRYPTOGRAPHY KEY DISTRIBUTION IN A NETWORK SPOO?NG EL GAMAL’S EXTENSION OF DIF?E–HELLMAN SHAMIR’S AUTONOMOUS KEY EXCHANGE X9 17 KEY EXCHANGE ARCHITECTURE THE NEEDHAM–SCHROEDER KEY DISTRIBUTION PROTOCOL THE NEED FOR SIGNATURES THREATS TO NETWORK TRANSACTIONS SECRECY, DIGITAL SIGNATURES, AND AUTHENTICATION THE DESIDERATA OF A DIGITAL SIGNATURE PUBLIC-KEY CRYPTOGRAPHY AND SIGNATURE SYSTEMS RABIN’S QUADRATIC RESIDUE SIGNATURE PROTOCOL HASH FUNCTIONS THE SECURE HASH ALGORITHM NIST’S DIGITAL SIGNATURE ALGORITHM EL GAMAL’S SIGNATURE PROTOCOL THE FIAT–SHAMIR IDENTI?CATION AND SIGNATURE SCHEMA THE OBLIVIOUS TRANSFER UNIX PASSWORD ENCIPHERMENT MAGNETIC STRIPE TECHNOLOGY PROTECTING ATM TRANSACTIONS KEYED-ACCESS CARDS SMART CARDS WHO CAN YOU TRUST?: KOHNFELDER’S CERTI?CATES X 509 CERTI?CATES THE SECURE SOCKET LAYER (SSL) MAKING A SECURE CREDIT CARD PAYMENT ON THE WEB WHAT IS A PATENT? PATENTABILITY OF IDEAS THE FORMAT OF A PATENT PATENTABLE VERSUS NONPATENTABLE SUBJECTS INFRINGEMENT THE ROLE OF PATENTS IN CRYPTOGRAPHY PKS/RSADSI LITIGATION LEON STAMBLER THE LEXICON OF CRYPTOGRAPHY THE WORD “CRYPTOGRAPHY” IS DERIVED FROM THE GREEK WORDS KRYPTOS, MEANING HIDDEN, AND GRA- PHIEN, MEANING TO WRITE HISTORIANS BELIEVE EGYPTIAN HIEROGLYPHICS, WHICH BEGAN ABOUT ARE BOTH EXAMPLES OF ASCII TEXT THE DECIPHERMENT TRANSFORMATION THE MESSAGE AUTHENTICATION MAC APPENDED TO TRANSACTION DATA 1 1 THE LEXICON OF CRYPTOGRAPHY THE SOFTWARE ENCIPHERMENT/DECIPHERMENT PROCESSES 1JEAN-GUIULLAUME-HUBERT-VICTOR-FRANCOIS-ALEXANDRE-AUGUSTE-KERCKHOFFS VON NIUEWENOF, BORN IN 1835 IN NUTH (NETHERLANDS), WAS A PROFESSOR OF GERMAN IN PARIS THE KERCKHOFFS MUST HAVE HAD SPECTACULAR TOWELS!