Foundations of Coding

JEAN-GUILLAUME DUMAS is Professor at the University of Grenoble, where he teaches security, programming languages, cryptology, and computer algebra. JEAN-LOUIS ROCH is Associate Professor at the National Polytechnique Institute of Grenoble (INPG), and teaches security, coding theory, cryptology, parallelism, and algorithms. ÉRIC TANNIER is Research Associate at the National French Institute for Computer Science (INRIA). He works in computational biology in the Biometry and Evolutionary Biology Laboratory (LBBE) of the University of Lyon. SÉBASTIEN VARRETTE is Research Associate at the University of Luxembourg. He works in the High Performance Computing (HPC) area, in particular as regards the security of distributed and/or parallel executions.

• List of Figures, Tables, Algorithms and Acronyms ixForeword xviiIntroduction 11 Foundations of Coding 51.1 From Julius Caesar to Telecopy 61.1.1 The Source: from an Image to a Sequence of Pixels 61.1.2 Message Compression 71.1.3 Error Detection 81.1.4 Encryption 91.1.5 Decryption 91.1.6 Drawbacks of the Fax Code 111.1.7 Orders of Magnitude and Complexity Bounds for Algorithms 121.2 Stream Ciphers and Probabilities 151.2.1 The Vernam Cipher and the One-Time-Pad Cryptosystem 151.2.2 Some Probability 161.2.3 Entropy 181.2.4 Steganography and Watermarking 231.2.5 Perfect Secrecy 241.2.6 Perfect Secrecy in Practice and Kerckhoffs’ Principles 241.3 Block Ciphers, Algebra, and Arithmetic 261.3.1 Blocks and Chaining Modes from CBC to CTR 271.3.2 Algebraic Structure of Codewords 301.3.3 Bijective Encoding of a Block 351.3.4 Construction of Prime Fields and Finite Fields 431.3.5 Implementation of Finite Fields 521.3.6 Curves Over Finite Fields 571.3.7 Pseudo-Random Number Generators (PRNG) 621.4 Decoding, Decryption, Attacks 681.4.1 Decoding without Ambiguity 681.4.2 Noninjective Codes 731.4.3 Cryptanalysis 842 Information Theory and Compression 992.1 Information Theory 1002.1.1 Average Length of a Code 1002.1.2 Entropy as a Measure of the Amount of Information 1012.1.3 Shannon’s Theorem 1022.2 Statistical Encoding 1042.2.1 Huffman’s Algorithm 1042.2.2 Arithmetic Encoding 1092.2.3 Adaptive Codes 1142.3 Heuristics of Entropy Reduction 1172.3.1 Run-Length Encoding (RLE) 1172.3.2 Move-to-Front 1192.3.3 Burrows–Wheeler Transform (BWT) 1202.4 Common Compression Codes 1222.4.1 Lempel–Ziv’s Algorithm and gzip Variants 1232.4.2 Comparisons of Compression Algorithms 1262.4.3 GIF and PNG Formats for Image Compression 1272.5 Lossy Compression 1282.5.1 Deterioration of Information 1282.5.2 Transformation of Audiovisual Information 1282.5.3 JPEG Format 1292.5.4 Motion Picture Experts Group (MPEG) Format 1333 Cryptology 1363.1 General Principles 1373.1.1 Terminology 1373.1.2 What is the Use of Cryptography? 1383.1.3 Main Types of Threats 1393.2 Secret Key Cryptography 1413.2.1 Principle of Symmetric Cryptography 1413.2.2 Classes of Symmetric Encryption Schemes 1433.2.3 Data Encryption Standard (DES) System 1453.2.4 Rijndael: Advanced Encryption Standard (AES) 1513.3 Key Exchange 1613.3.1 Diffie–Hellman Protocol and Man-in-the-Middle Attacks 1613.3.2 Kerberos: a Secret Key Provider 1633.4 Public Key Cryptography 1673.4.1 Motivations and Main Principles 1673.4.2 Rivest–Shamir–Adleman (RSA) Encryption 1693.4.3 El Gamal Encryption 1743.5 Authentication, Integrity, Nonrepudiation, Signatures 1753.5.1 Cryptographic Hash Functions 1763.5.2 Public Key Authentication 1863.5.3 Electronic Signatures 1873.6 Key Management 1923.6.1 Generation of Cryptographically Secure Bits 1923.6.2 Public Key Infrastructure (PKI) 1923.6.3 Securing Channels with the SSH Tool 2034 Error Detection and Correction 2094.1 Principle of Error Detection and Error Correction 2114.1.1 Block Coding 2114.1.2 A Simple Example of Parity Detection 2114.1.3 Correction Using Longitudinal and Transverse Parity 2124.1.4 Encoding, Decoding, and Probability of Error 2134.1.5 Shannon’s Second Theorem 2144.2 Error Detection by Parity – CRC Codes 2184.2.1 Parity Check on Integers: ISBN, EAN, LUHN 2184.2.2 Cyclic Redundancy Checks (CRC) 2214.3 Distance of a Code 2224.3.1 Error Correction Code and Hamming Distance 2224.3.2 Equivalent Codes, Extended Codes, and Shortened Codes 2274.3.3 Perfect Codes 2294.3.4 Binary Hamming Codes 2304.4 Linear Codes and Cyclic Codes 2324.4.1 Linear Codes and Minimum Redundancy 2324.4.2 Encoding and Decoding of Linear Codes 2344.4.3 Low Density Parity Check (LDPC) Codes 2384.4.4 Cyclic Codes 2504.4.5 Bose–Chaudhuri–Hocquenghem (BCH) Codes 2544.4.6 Optimal BCH Codes: Reed–Solomon Codes 2564.5 Bursts of Errors and Interleaving 2624.5.1 Packets of Errors 2624.5.2 Interleaving 2634.5.3 Interleaving with Delay and Interleaving Table 2644.5.4 Cross-Interleaved codes 2654.6 Convolutional Codes and Turbo Codes 2684.6.1 Encoding by Convolution 2684.6.2 Shortest Path Decoding 2694.6.3 Turbo Codes 273Compression, Encryption, Correction: As a Conclusion 277Problem Solutions 281Bibliography 343Index 345

Select Guide Rating