Contents	6
	Preface	14
	1 Introduction	16
	1.1 Introduction and Terminology	16
	1.2 Shannon's Description of a Conventional Cryptosystem	17
	1.3 Statistical Description of a Plaintext Source	19
	1.4 Problems	22
	2 Classical Cryptosystems	24
	2.1 Caesar, Simple Substitution, Vigenère	24
	2.2 The Incidence of Coincidences, Kasiski's Method	31
	2.3 Vernam, Playfair, Transpositions, Hagelin, Enigma	35
	2.4 Problems	40
	3 Shift Register Sequences	42
	3.1 Pseudo-Random Sequences	42
	3.2 Linear Feedback Shift Registers	46
	3.3 Non- Linear Algorithms	64
	3.4 Problems	75
	4 Block Ciphers	78
	4.1 Some General Principles	78
	4.2 DES	82
	4.3 IDEA	85
	4.4 Further Remarks	87
	4.5 Problems	88
	5 Shannon Theory	90
	5.1 Entropy, Redundancy, and Unicity Distance	90
	5.2 Mutual Information and Unconditionally Secure Systems	95
	5.3 Problems	100
	6 Data Compression Techniques	102
	6.1 Basic Concepts of Source Coding for Stationary Sources	102
	6.2 Huffman Codes	108
	6.3 Universal Data Compression - The Lempel-Ziv Algorithms	112
	6.4 Problems	118
	7 Public-Key Cryptography	120
	7.1 The Theoretical Model	120
	7.2 Problems	124
	8 Discrete Logarithm Based Systems	126
	8.1 The Discrete Logarithm System	126
	8.2 Other Discrete Logarithm Based Systems	131
	8.3 How to Take Discrete Logarithms	136
	8.4 Problems	160
	9 RSA Based Systems	162
	9.1 The RSA System	162
	9.2 The Security of RSA: Some Factorization Algorithms	171
	9.3 Some Unsafe Modes for RSA	184
	9.4 How to Generate Large Prime Numbers	197
	9.5 The Rabin Variant	212
	9.6 Problems	224
	9.5 The Rabin Variant	212
	10 Elliptic Curves Based Systems	228
	10.1 Some Basic Facts of Elliptic Curves	228
	10.2 The Geometry of Elliptic Curves	231
	10.3 Addition of Points on Elliptic Curves	239
	10.4 Cryptosystems Defined over Elliptic Curves	245
	10.5 Problems	251
	11 Coding Theory Based Systems	252
	11.1 Introduction to Goppa codes	252
	11.2 The McEliece Cryptosystem	256
	11.3 Another Technique to Decode Linear Codes	270
	11.4 The Niederreiter Scheme	275
	11.5 Problems	276
	12 Knapsack Based Systems	278
	12.1 The Knapsack System	278
	12.2 The L3- Attack	285
	12.3 The Chor-Rivest Variant	294
	12.4 Problems	301
	13 Hash Codes & Authentication Techniques	302
	13.1 Introduction	302
	13.2 Hash Functions and MAC's	303
	13.3 Unconditionally Secure Authentication Codes	305
	13.4 Problems	329
	14 Zero Knowledge Protocols	330
	14.1 The Fiat-Shamir Protocol	330
	14.2 Schnorr's Identification Protocol	332
	14.3 Problems	335
	15 Secret Sharing Systems	336
	15.1 Introduction	336
	15.2 Threshold Schemes	338
	15.3 Threshold Schemes with Liars	341
	15.4 Secret Sharing Schemes	343
	15.5 Visual Secret Sharing Schemes	348
	15.6 Problems	356
	Appendix A Elementary Number Theory	358
	A.1 Introduction	358
	A.2 Euclid's Algorithm	363
	A.3 Congruences, Fermat, Euler, Chinese Remainder Theorem	367
	A.4 Quadratic Residues	379
	A.5 Continued Fractions	384
	A.6 Möbius Inversion Formula, the Principle of Inclusion and Exclusion	393
	A.7 Problems	397
	Appendix B Finite Fields	398
	B.1 Algebra	398
	B.2 Constructions	410
	B.3 The Number of Irreducible Polynomials over GF(q)	416
	B.4 The Structure of Finite Fields	420
	B.5 Problems	438
	Appendix C Relevant Famous Mathematicians	440
	Euclid of Alexandria	440
	Leonhard Euler	441
	Pierre de Fermat	443
	Evariste Galois	449
	Johann Carl Friedrich Gauss	454
	Karl Gustav Jacob Jacobi	460
	Adrien-Marie Legendre	461
	August Ferdinand Möbius	462
	Joseph Henry Maclagen Wedderburn	466
	Appendix D New Functions	468
	References	476
	Symbols and Notations	484
	Index	486
	More eBook at www.ciando.com	0