Understanding cryptography : a textbook for students and practitioners

Cryptography is now ubiquitous - moving beyond the traditional environments, such as government communications and banking systems, we see cryptographic techniques realized in Web browsers, e-mail programs, cell phones, manufacturing systems, embedded software, smart buildings, cars, and even medical implants. Today's designers need a comprehensive understanding of applied cryptography.

After an introduction to cryptography and data security, the authors explain the main techniques in modern cryptography, with chapters addressing stream ciphers, the Data Encryption Standard (DES) and 3DES, the Advanced Encryption Standard (AES), block ciphers, the RSA cryptosystem, public-key cryptosystems based on the discrete logarithm problem, elliptic-curve cryptography (ECC), digital signatures, hash functions, Message Authentication Codes (MACs), and methods for key establishment, including certificates and public-key infrastructure (PKI). Throughout the book, the authors focuson communicating the essentials and keeping the mathematics to a minimum, and they move quickly from explaining the foundations to describing practical implementations, including recent topics such as lightweight ciphers for RFIDs and mobile devices, and current key-length recommendations.

The authors have considerable experience teaching applied cryptography to engineering and computer science students and to professionals, and they make extensive use of examples, problems, and chapter reviews, while the book's website offers slides, projects and links to further resources. This is a suitable textbook for graduate and advanced undergraduate courses and also for self-study by engineers.

The authors' website (http://www.crypto-textbook.com/) provides extensive notes, slides, video lectures; the authors' YouTube channel (https://www.youtube.com/channel/UC1usFRN4LCMcflV7UjHNuQg) includes video lectures.

Author Notes

Prof. Dr.-Ing. Christof Paa r has the Chair for Embedded Security at the University of Bochum, Germany, and is Adjunct Professor at the University of Massachusetts at Amherst, USA. Prof. Paar has taught cryptography for 15 years to engineering and computer science students in the US and in Europe, and he has taught many industrial practitioners at organizations such as Motorola, Philips and NASA. He has more than 100 publications in applied cryptography and is a cofounder of the Workshop on Cryptographic Hardware and Embedded Systems (CHES), the key academic event in this field.

Prof. Dr.-Ing. January Pelzl started his career at Bosch Telecom GmbH. He has a Ph.D. in applied cryptography, and as a researcher he investigated the practical aspects of elliptic-curve-based cryptography and cryptanalysis. He has published extensively about his theoretical and industrial work through leading international conferences and journals, and he has taught many IT security and cryptography courses in industry. He was the Managing Director of "ESCRYPT GmbH" in Bochum. Since January 2015 he is the professor of "Computer Security" in Hochschule Hamm-Lippstadt.

1 Introduction to Cryptography and Data Security	p. 1
1.1 Overview of Cryptography (and This Book)	p. 2
1.2 Symmetric Cryptography	p. 4
1.2.1 Basics	p. 4
1.2.2 Simple Symmetric Encryption: The Substitution Cipher	p. 6
1.3 Cryptanalysis	p. 9
1.3.1 General Thoughts on Breaking Cryptosystems	p. 9
1.3.2 How Many Key Bits Are Enough?	p. 11
1.4 Modular Arithmetic and More Historical Ciphers	p. 13
1.4.1 Modular Arithmetic	p. 13
1.4.2 Integer Rings	p. 16
1.4.3 Shift Cipher (or Caesar Cipher)	p. 18
1.4.4 Affine Cipher	p. 19
1.5 Discussion and Further Reading	p. 20
1.6 Lessons Learned	p. 22
Problems	p. 24
2 Stream Ciphers	p. 29
2.1 Introduction	p. 30
2.1.1 Stream Ciphers vs. Block Ciphers	p. 30
2.1.2 Encryption and Decryption with Stream Ciphers	p. 31
2.2 Random Numbers and an Unbreakable Stream Cipher	p. 34
2.2.1 Random Number Generators	p. 34
2.2.2 The One-Time Pad	p. 36
2.2.3 Towards Practical Stream Ciphers	p. 38
2.3 Shift Register-Based Stream Ciphers	p. 41
2.3.1 Linear Feedback Shift Registers (LFSR)	p. 41
2.3.2 Known-Plaintext Attack Against Single LFSRs	p. 45
2.3.3 Trivium	p. 46
2.4 Discussion and Further Reading	p. 49
2.5 Lessons Learned	p. 50
Problems	p. 52
3 The Data Encryption Standard (DES) and Alternatives	p. 55
3.1 Introduction to DES	p. 56
3.1.1 Confusion and Diffusion	p. 57
3.2 Overview of the DES Algorithm	p. 58
3.3 Internal Structure of DES	p. 61
3.3.1 Initial and Final Permutation	p. 61
3.3.2 The â-Function	p. 62
3.3.3 Key Schedule	p. 67
3.4 Decryption	p. 69
3.5 Security of DES	p. 72
3.5.1 Exhaustive Key Search	p. 73
3.5.2 Analytical Attacks	p. 75
3.6 Implementation in Software and Hardware	p. 75
3.7 DES Alternatives	p. 77
3.7.1 The Advanced Encryption Standard (AES) and the AES Finalist Ciphers	p. 77
3.7.2 Triple DES (3DES) and DESX	p. 78
3.7.3 Lightweight Cipher PRESENT	p. 78
3.8 Discussion and Further Reading	p. 81
3.9 Lessons Learned	p. 82
Problems	p. 83
4 The Advanced Encryption Standard (AES)	p. 87
4.1 Introduction	p. 88
4.2 Overview of the AES Algorithm	p. 89
4.3 Some Mathematics: A Brief Introduction to Galois Fields	p. 90
4.3.1 Existence of Finite Fields	p. 90
4.3.2 Prime Fields	p. 93
4.3.3 Extension Fields GF(2m)	p. 94
4.3.4 Addition and Subtraction in GF(2m)	p. 95
4.3.5 Multiplication in GF{{2m)	p. 96
4.3.6 Inversion in GF(2m)	p. 98
4.4 Internal Structure of AES	p. 99
4.4.1 Byte Substitution Layer	p. 101
4.4.2 Diffusion Layer	p. 103
4.4.3 Key Addition Layer	p. 106
4.4.4 Key Schedule	p. 106
4.5 Decryption	p. 110
4.6 Implementation in Software and Hardware	p. 115
4.7 Discussion and Further Reading	p. 116
4.8 Lessons Learned	p. 117
Problems	p. 118
5 More About Block Ciphers	p. 123
5.1 Encryption with Block Ciphers: Modes of Operation	p. 124
5.1.1 Electronic Codebook Mode (ECB)	p. 124
5.1.2 Cipher Block Chaining Mode (CBC)	p. 128
5.1.3 Output Feedback Mode (ORB)	p. 130
5.1.4 Cipher Feedback Mode (CFB)	p. 131
5.1.5 Counter Mode (CTR)	p. 132
5.1.6 Galois Counter Mode (GCM)	p. 134
5.2 Exhaustive Key Search Revisited	p. 136
5.3 Increasing the Security of Block Ciphers	p. 137
5.3.1 Double Encryption and Meet-in-the-Middle Attack	p. 138
5.3.2 Triple Encryption	p. 140
5.3.3 Key Whitening	p. 141
5.4 Discussion and Further Reading	p. 143
5.5 Lessons Learned	p. 144
Problems	p. 145
6 Introduction to Public-Key Cryptography	p. 149
6.1 Symmetric vs. Asymmetric Cryptography	p. 150
6.2 Practical Aspects of Public-Key Cryptography	p. 153
6.2.1 Security Mechanisms	p. 154
6.2.2 The Remaining Problem: Authenticity of Public Keys	p. 154
6.2.3 Important Public-Key Algorithms	p. 155
6.2.4 Key Lengths and Security Levels	p. 156
6.3 Essential Number Theory for Public-Key Algorithms	p. 157
6.3.1 Euclidean Algorithm	p. 157
6.3.2 Extended Euclidean Algorithm	p. 160
6.3.3 Euler's Phi Function	p. 164
6.3.4 Fermat's Little Theorem and Euler's Theorem	p. 166
6.4 Discussion and Further Reading	p. 168
6.5 Lessons Learned	p. 169
Problems	p. 170
7 The RSA Cryptosystem	p. 173
7.1 Introduction	p. 174
7.2 Encryption and Decryption	p. 174
7.3 Key Generation and Proof of Correctness	p. 175
7.4 Encryption and Decryption: Fast Exponentiation	p. 179
7.5 Speed-up Techniques for RSA	p. 183
7.5.1 Fast Encryption with Short Public Exponents	p. 183
7.5.2 Fast Decryption with the Chinese Remainder Theorem	p. 184
7.6 Finding Large Primes	p. 187
7.6.1 How Common Are Primes?	p. 187
7.6.2 Primality Tests	p. 188
7.7 RSA in Practice: Padding	p. 192
7.8 Attacks	p. 194
7.9 Implementation in Software and Hardware	p. 197
7.10 Discussion and Further Reading	p. 198
7.11 Lessons Learned	p. 199
Problems	p. 200
8 Public-Key Cryptosystems Based on the Discrete Logarithm Problem	p. 205
8.1 Difne-Hellman Key Exchange	p. 206
8.2 Some Algebra	p. 208
8.2.1 Groups	p. 208
8.2.2 Cyclic Groups	p. 210
8.2.3 Subgroups	p. 214
8.3 The Discrete Logarithm Problem	p. 216
8.3.1 The Discrete Logarithm Problem in Prime Fields	p. 216
8.3.2 The Generalized Discrete Logarithm Problem	p. 218
8.3.3 Attacks Against the Discrete Logarithm Problem	p. 219
8.4 Security of the Difne-Hellman Key Exchange	p. 225
8.5 The Elgamal Encryption Scheme	p. 226
8.5.1 From Difne-Hellman Key Exhange to Elgamal Encryption	p. 226
8.5.2 The Elgamal Protocol	p. 227
8.5.3 Computational Aspects	p. 229
8.5.4 Security	p. 230
8.6 Discussion and Further Reading	p. 232
8.7 Lessons Learned	p. 233
Problems	p. 234
9 Elliptic Curve Cryptosystems	p. 239
9.1 How to Compute with Elliptic Curves	p. 239
9.1.1 Definition of Elliptic Curves	p. 240
9.1.2 Group Operations on Elliptic Curves	p. 242
9.2 Building a Discrete Logarithm Problem with Elliptic Curves	p. 245
9.3 Difne-Hellman Key Exchange with Elliptic Curves	p. 249
9.4 Security	p. 251
9.5 Implementation in Software and Hardware	p. 252
9.6 Discussion and Further Reading	p. 253
9.7 Lessons Learned	p. 255
Problems256
10 Digital Signatures	p. 259
10.1 Introduction	p. 260
10.1.1 Odd Colors for Cars, or: Why Symmetric Cryptography Is Not Sufficient	p. 260
10.1.2 Principles of Digital Signatures	p. 261
10.1.3 Security Services	p. 263
10.2 The RSA Signature Scheme	p. 264
10.2.1 Schoolbook RSA Digital Signature	p. 265
10.2.2 Computational Aspects	p. 267
10.2.3 Security	p. 267
10.3 The Elgamal Digital Signature Scheme	p. 270
10.3.1 Schoolbook Elgamal Digital Signature	p. 270
10.3.2 Computational Aspects	p. 273
10.3.3 Security	p. 274
10.4 The Digital Signature Algorithm (DSA)	p. 277
10.4.1 The DSA Algorithm	p. 277
10.4.2 Computational Aspects	p. 280
10.4.3 Security	p. 281
10.5 The Elliptic Curve Digital Signature Algorithm (ECDSA)	p. 282
10.5.1 The ECDSA Algorithm	p. 282
10.5.2 Computational Aspects	p. 285
10.5.3 Security	p. 286
10.6 Discussion and Further Reading	p. 287
10.7 Lessons Learned	p. 288
Problems	p. 289
11 Hash Functions	p. 293
11.1 Motivation: Signing Long Messages	p. 294
11.2 Security Requirements of Hash Functions	p. 296
11.2.1 Preimage Resistance or One-Wayness	p. 297
11.2.2 Second Preimage Resistance or Weak Collision Resistance	p. 297
11.2.3 Collision Resistance and the Birthday Attack	p. 299
11.3 Overview of Hash Algorithms	p. 303
11.3.1 Dedicated Hash Functions: The MD4 Family	p. 304
11.3.2 Hash Functions from Block Ciphers	p. 305
11.4 The Secure Hash Algorithm SHA-1	p. 307
11.4.1 Preprocessing	p. 308
11.4.2 Hash Computation	p. 309
11.4.3 Implementation	p. 312
11.5 Discussion and Further Reading	p. 312
11.6 Lessons Learned	p. 313
Problems	p. 315
12 Message Authentication Codes (MACs)	p. 319
12.1 Principles of Message Authentication Codes	p. 320
12.2 MACs from Hash Functions: HMAC	p. 321
12.3 MACs from Block Ciphers: CBC-MAC	p. 325
12.4 Galois Counter Message Authentication Code (GMAC)	p. 327
12.5 Discussion and Further Reading	p. 327
12.6 Lessons Learned	p. 328
Problems	p. 329
13 Key Establishment	p. 331
13.1 Introduction	p. 332
13.1.1 Some Terminology	p. 332
13.1.2 Key Freshness and Key Derivation	p. 332
13.1.3 The n2 Key Distribution Problem	p. 334
13.2 Key Establishment Using Symmetric-Key Techniques	p. 336
13.2.1 Key Establishment with a Key Distribution Center	p. 336
13.2.2 Kerberos	p. 339
13.2.3 Remaining Problems with Symmetric-Key Distribution	p. 341
13.3 Key Establishment Using Asymmetric Techniques	p. 342
13.3.1 Man-in-the-Middle Attack	p. 342
13.3.2 Certificates	p. 344
13.3.3 Public-Key Infrastructures (PKI) and CAs	p. 347
13.4 Discussion and Further Reading	p. 351
13.5 Lssons Learned	p. 352
Problems	p. 353
References	p. 359
Index	p. 367

Available:*

On Order

Summary

Summary

Author Notes

Table of Contents