Cryptography in C and C++ (eBook)

Michael Welschenbach works for SRC Security Research & Consulting GmbH in Bonn, Germany. He graduated with a master's degree in mathematics from the University of Cologne, and has extensive experience in both pure and applied cryptological research. Currently, his favorite programming languages are C and C++. When not working, he enjoys spending time with his wife and two sons, programming, reading, and playing music.

Cover 1
Title 2
Copyright 3
Dedication 4
Contents 5
Foreword 12
About the Author 14
About the Translator 15
Preface to the Second American Edition 16
Preface to the First American Edition 17
Preface to the First German Edition 20
I Arithmetic and Number Theory in C 23
1 Introduction 24
2 Number Formats: The Representation of Large Numbers in C 33
3 Interface Semantics 38
4 The Fundamental Operations 41
4.1 Addition and Subtraction 42
4.2 Multiplication 51
4.2.1 The Grade SchoolMethod 52
4.2.2 Squaring Is Faster 58
4.2.3 Do Things Go Better with Karatsuba? 63
4.3 Division with Remainder 68
5 Modular Arithmetic: Calculating with Residue Classes 84
6 Where All RoadsMeet:Modular Exponentiation 97
6.1 First Approaches 97
6.2 M-ary Exponentiation 102
6.3 Addition Chains andWindows 117
6.4 Montgomery Reduction and Exponentiation 122
6.5 Cryptographic Application of Exponentiation 134
7 Bitwise and Logical Functions 140
7.1 Shift Operations 140
7.2 All or Nothing: Bitwise Relations 146
7.3 Direct Access to Individual Binary Digits 152
7.4 Comparison Operators 155
8 Input, Output, Assignment, Conversion 160
9 Dynamic Registers 171
10 Basic Number-Theoretic Functions 180
10.1 Greatest Common Divisor 181
10.2 Multiplicative Inverse in Residue Class Rings 188
10.3 Roots and Logarithms 196
10.4 Square Roots in Residue Class Rings 204
10.4.1 The Jacobi Symbol 205
10.4.2 Square Roots Modulo pk 211
10.4.3 Square RootsModulo n 216
10.4.4 Cryptography with Quadratic Residues 224
10.5 A Primality Test 227
11 Rijndael: A Successor to the Data Encryption Standard 249
11.1 Arithmetic with Polynomials 251
11.2 The Rijndael Algorithm 256
11.3 Calculating the Round Key 259
11.4 The S-Box 260
11.5 The ShiftRowsTransformation 261
11.6 The MixColumnsTransformation 262
11.7 The AddRoundKeyStep 264
11.8 Encryption as a Complete Process 265
11.9 Decryption 268
11.10 Performance 271
11.11 Modes of Operation 272
12 Large Random Numbers 273
12.1 A Simple Random Number Generator 277
12.2 Cryptographic Random Number Generators 280
12.2.1 The Generation of Start Values 281
12.2.2 The BBS Random Number Generator 285
12.2.3 The AES Generator 291
12.2.4 The RMDSHA-1 Generator 295
12.3 Quality Testing 298
12.3.1 Chi-Squared Test 299
12.3.2 Monobit Test 301
12.3.3 Poker Test 301
12.3.4 Runs Test 301
12.3.5 Longruns Test 301
12.3.6 Autocorrelation Test 302
12.3.7 Quality of the FLINT/C Random Number Generators 302
12.4 More Complex Functions 303
13 Strategies for Testing LINT 317
13.1 Static Analysis 319
13.2 Run-Time Tests 321
II Arithmetic in C++ with the Class LINT 328
14 Let C++ Simplify Your Life 329
14.1 Not a Public Affair: The Representation of Numbers in LINT 334
14.2 Constructors 335
14.3 Overloaded Operators 339
15 The LINTPublic Interface:Members and Friends 346
15.1 Arithmetic 346
15.2 Number Theory 356
15.3 Stream I/O of LINTObjects 361
15.3.1 Formatted Output of LINTObjects 362
15.3.2 Manipulators 369
15.3.3 File I/O for LINTObjects 371
16 Error Handling 376
16.1 (Don't) Panic 376
16.2 User-Defined Error Handling 378
16.3 LINTExceptions 379
17 An Application Example: The RSA Cryptosystem 385
17.1 Asymmetric Cryptosystems 386
17.2 The RSA Algorithm 388
17.3 Digital RSA Signatures 403
17.4 RSA Classes in C++ 411
18 Do It Yourself: Test LINT 41319 Approaches for Further Extensions 424
III Appendices 426
A Directory of C Functions 427
A.1 Input/Output, Assignment, Conversions, Comparisons 427
A.2 Basic Calculations 428
A.3 Modular Arithmetic 429
A.4 Bitwise Operations 431
A.5 Number-Theoretic Functions 432
A.6 Generation of Pseudorandom Numbers 433
A.7 RegisterManagement 437
B Directory of C++ Functions 438
B.1 Input/Output, Conversion, Comparison:Member Functions 438
B.2 Input/Output, Conversion, Comparison: Friend Functions 441
B.3 Basic Operations:Member Functions 443
B.4 Basic Operations: Friend Functions 444
B.5 Modular Arithmetic:Member Functions 445
B.6 Modular Arithmetic: Friend Functions 447
B.7 Bitwise Operations:Member Functions 448
B.8 Bitwise Operations: Friend Functions 449
B.9 Number-TheoreticMember Functions 450
B.10 Number-Theoretic Friend Functions 451
B.11 Generation of Pseudorandom Numbers 455
B.12 Miscellaneous Functions 455
C Macros 456
C.1 Error Codes and Status Values 456
C.2 Additional Constants 456
C.3 Macros with Parameters 458
D Calculation Times 463
E Notation 465
F Arithmetic and Number-Theoretic Packages 467
References 469
Index 476