Fundamentals of Cryptology (eBook)

A Professional Reference and Interactive Tutorial

Henk C.A. van Tilborg (Autor)

eBook Download: PDF

2006 | 1. Auflage
507 Seiten
Springer US (Verlag)
978-0-306-47053-0 (ISBN)

Infos

The protection of sensitive information against unauthorized access or fraudulent changes has been of prime concern throughout the centuries. Modern communication techniques, using computers connected through networks, make all data even more vulnerable to these threats. In addition, new issues have surfaced that did not exist previously, for example, adding a signature to an electronic document. Cryptology addresses the above issues - it is at the foundation of all information security.

The techniques employed to this end have become increasingly mathematical in nature. This work serves as an introduction to modern cryptographic methods. After a brief survey of classical cryptosystems, it concentrates on three main areas. First, stream ciphers and block ciphers are discussed. These systems have extremely fast implementations, but sender and receiver must share a secret key. Second, the book presents public key cryptosystems, which make it possible to protect data without a prearranged key. Their security is based on intractable mathematical problems, such as the factorization of large numbers.

The remaining chapters cover a variety of topics, including zero-knowledge proofs, secret sharing schemes and authentication codes. Two appendices explain all mathematical prerequisites in detail: one presents elementary number theory (Euclid's Algorithm, the Chinese Remainder Theorem, quadratic residues, inversion formulas, and continued fractions) and the other introduces finite fields and their algebraic structure. The text is an updated and improved version of "An Introduction to Cryptology," originally published in 1988.

Apart from a revision of the existing material, there are many new sections, and two new chapters on elliptic curves and authentication codes, respectively. In addition, the book is accompanied by a full text electronic version on CD-ROM as an interactive Mathematica manuscript. "Basic Concepts in Cryptology" should be of interest to computer scientists, mathematicians, and researchers, students, and practitioners in the area of cryptography.

 

---

The protection of sensitive information against unauthorized access or fraudulent changes has been of prime concern throughout the centuries. Modern communication techniques, using computers connected through networks, make all data even more vulnerable for these threats. Also, new issues have come up that were not relevant before, e. g. how to add a (digital) signature to an electronic document in such a way that the signer can not deny later on that the document was signed by him/her. Cryptology addresses the above issues. It is at the foundation of all information security. The techniques employed to this end have become increasingly mathematical of nature. This book serves as an introduction to modern cryptographic methods. After a brief survey of classical cryptosystems, it concentrates on three main areas. First of all, stream ciphers and block ciphers are discussed. These systems have extremely fast implementations, but sender and receiver have to share a secret key. Public key cryptosystems (the second main area) make it possible to protect data without a prearranged key. Their security is based on intractable mathematical problems, like the factorization of large numbers. The remaining chapters cover a variety of topics, such as zero-knowledge proofs, secret sharing schemes and authentication codes. Two appendices explain all mathematical prerequisites in great detail. One is on elementary number theory (Euclid's Algorithm, the Chinese Remainder Theorem, quadratic residues, inversion formulas, and continued fractions). The other appendix gives a thorough introduction to finite fields and their algebraic structure.

Inhalt

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 Some Primality Tests
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
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

Produkt-Details

• Erscheint lt. Verlag: 18.4.2006
• Sprache: englisch
• Themenwelt: Informatik ► Theorie / Studium ► Kryptologie
• Themenwelt: Naturwissenschaften
• Themenwelt: Technik
• ISBN-10: 0-306-47053-5 / 0306470535
• ISBN-13: 978-0-306-47053-0 / 9780306470530