List of Figures, Tables, Algorithms and Acronyms

List of Figures

I.1 Fundamental coding scheme

I.2 Notions introduced in Chapter 1

1.1 Spartan Scytale principle to transmit the text " HELLOWORLD"

1.2 Bitwise encryption (Stream cipher)

1.3 Block ciphers: ECB mode

1.4 Block ciphers: CBC mode

1.5 Block ciphers: CFB mode

1.6 Block ciphers: OFB mode

1.7 Block ciphers: CTR mode

1.8 Principle of a one-way function

1.9 (a) Elliptic curve addition and (b) doubling on

1.10 Functional diagram of an LFSR

1.11 Bluetooth encryption

1.12 Example of a Huffman tree

1.13 Principle of a hash function

1.14 Compression function of a hash function

1.15 Merkle-Damgård construction

1.16 Davies-Meyer construction

1.17 Miyaguchi-Preneel construction

1.18 Fourier transform

1.19 Discrete Fourier Transform (DFT)

1.20 Discrete Cosine Transform (DCT)

1.21 Floyd's cycle detection, in the form of a rho

2.1 Huffman encoding: beginning of the algorithm

2.2 Huffman's encoding: first step ()

2.3 Example of a construction of the Huffman code

2.4 Fax code

2.5 BWT on COMPRESSED

2.6 bzip2

2.7 The RGB image with white background (here in gray-levels)

2.8 JPEG zigzag scan

2.9 JPEG compression

2.10 MPEG-1 compression

2.11 MP3 sound compression

3.1 Fundamental relation of cryptography

3.2 Principle of an integrity checking algorithm

3.3 Principle of symmetric cryptography

3.4 Stream cipher

3.5 Block cipher

3.6 One round of DES

3.7 DES: Function f

3.8 DES key derivation

3.9 Matricial representation of a 16-byte block

3.10 SubBytes operation in AES

3.11 ShiftRows stage in AES

3.12 MixColumns operation in AES

3.13 KeySchedule operation in AES

3.14 Representation of the expanded key W as a sequence of columns

3.15 Kerberos authentication steps

3.16 Principle of public key encryption

3.17 History of the main hash functions

3.18 Rounds 1, 2, 3, and 4 in MD5 ()

3.19 Round i in SHA-1 ()

3.20 Keccak's sponge construct (SHA-3)

3.21 Integrity check with hash functions using a secure channel

3.22 Integrity check with hash functions using an encryption function

3.23 Optimal Asymmetric Encryption Padding (OAEP)

3.24 Principle of the use of an MAC

3.25 MAC using symmetric encryption

3.26 Principle of public key signatures and verification

3.27 Principle of the creation of certificates

3.28 Issuing a certificate

3.29 Generation and content of an X.509 certificate

3.30 Verification of certificate and public key extraction

3.31 PKI model for X-509 certificates

3.32 Authenticated registration

3.33 Authentication via public key cryptography

3.34 An example of the PGP trust

3.35 Format of an SSH packet

4.1 Binary Symmetric Channel (BSC) with error probability p

4.2 The EAN-128 code for foundations of coding

4.3 Example of a (10,5) regular LDPC code and its representation by a Tanner graph. The six bold edges show a length-6 cycle in the graph

4.4 Example of the bit-flipping decoding over the Hamming code (7,4) for the received word when the codeword has been transmitted. (a) Step 2: parity checks, (b) step 3: codeword update, and (c) stopping criteria (success)

4.5 Illustration of the extrinsic information passed to compute the messages (a, step 2) and (b, step 3)

4.6 QR-code and pattern locations

4.7 3-L, , QR-code for http://foundationsofcoding.imag.fr

4.8 State diagram of the convolutional code of generator polynomials and

4.9 Lattice of the convolutional code generated by and

4.10 Systematic convolutional code of constraint length 3 transformed into a RSC code

4.11 Parallel composition and interleaving of two RSC encoders

4.12 Iterative decoding of a turbo code

1 Encoding of a message M

2 Decoding of a message

3 Viterbi's algorithm on the message 10010010011101111010

List of Tables

1.1 Letter Distribution in this LaTeX Script

1.2 Typical Complexity Bounds Obtained from an Algorithm Analysis

1.3 Extract of the ASCII Code

1.4 Zech's Construction on Invertible Elements in Odd Characteristic

1.5 Discrete Logarithm and Exponentiation in Finite Fields and Generic Groups

1.6 Group Laws in Characteristics 2 and 3 with and

1.7 Table (Extract)

1.8 Distribution of the Multiples of p Modulo m

1.9 Quadratic Sieve for

2.1 Arithmetic Encoding of "bebecafdead"

2.2 Arithmetic Decoding of "0.15633504500"

2.3 Integer Arithmetic Encoding of "bebecafdead"

2.4 Integer Arithmetic Decoding of "156335043840"

2.5 Comparison of the Compression of an Email File (15.92 Mo: Text, Images, Programs, etc.) with Several Algorithms, on a PIV 1.5 GHz

3.1 Frequency of the Letters in French

3.2 Frequency Analysis of the Ciphertext

3.3 Rabbit Stream Internal State Evolution and Bit Extraction

3.4 Complexities of Cryptanalysis Methods on DES

3.5 Cost and Efficiency of Attacks on DES in 1996

3.6 Performance of Several Block Ciphers

3.7 Configurations for AES

3.8 Value of the Shift According to the Value of in ShiftRows

3.9 Man-in-the-Middle Attack on the Diffie-Hellman Protocol

3.10 Sending of a Message Intercepted by the Man-in-the-Middle

3.11 Frequential Repartition of Symbols in a Text Written in French

3.12 Conjectured Compared Security of Block Ciphers

3.13 Main Differences between W and Rijndael

3.14 SHA-3 Candidates Speed (Cycles/Byte) on an Intel i7

3.15 Resistance to Collisions for the Most Famous Hash Functions

4.1 Order of Magnitude of Raw Error Rates

4.2 Encoding with a Parity Bit

4.3 Error Correction using Parity Bits

4.4 Examples of CRC Codes

4.5 Comparison of MPAs

4.6 Initial Interleaving Table with Delay 2 for Codewords of Length 5

4.7 Interleaving Table with Delay 2 After One Round

1 Several Primitive Polynomials in

2 Die Simulation by Coin Toss

List of Algorithms

1.1 Simplified Fax Encoding for a Line of Pixels

1.2 Fax Decoding for a Decrypted and Checked Line

1.3 GCD: Euclidean Algorithm

1.4 GCD: Extended Euclidean Algorithm

1.5 Modular Exponentiation

1.6 Miller--Rabin Primality Test

1.7 Horner Polynomial Evaluation

1.8 Ben-Or's Irreducibility Test

1.9 Generation of a sparse irreducible polynomial

1.10 Test Primitive Root

1.11 Test Generator Polynomial

1.12 Discrete Fast Fourier Transform

1.13 Fast product of two polynomials

1.14 Berlekamp--Massey Algorithm

1.15 Yuval's birthday attack

1.16 Pollard's Factoring

1.17 Lenstra's elliptic curve factoring

1.18 Gordon's algorithm

2.1 Description of Huffman's Algorithm

2.2 Arithmetic Encoding

2.3 Arithmetic Decoding

2.4 Dynamic Huffman Algorithm: Compression

2.5 Dynamic Huffman's Algorithm Decompression

2.6 Inverse of BWT

2.7 LZW: compression

2.8 LZW: decompression

3.1 AES Encryption

3.2 Key Schedule in AES

3.3 GCM

3.4 Shamir's Trick for Simultaneous Double-And-Add

4.1 Hard-Decision Decoder by Bit-Flipping Algorithm

4.2 Generic BPA for LDPC Code Decoding

4.3 Decoding of a Reed-Solomon code

4.4 Viterbi's Algorithm (Decoding of Convolutional Codes)

1 AES Decryption

2 Factoring n from (n,e,d) in RSA (Special Case: e is Small)

3 Factoring n from (n,e,d) in RSA

4 RSA Cryptographic Pseudo-Random Generator

5 Repetition Code Decoding with Maximum Detection

6 Repetition Code Decoding with Maximum Correction

7 Repetition Code Decoding with Detection and Correction

8 Minimum Distance of a Code (|V|=2)

acronym

ADSL Asymmetric Digital Subscriber Line

AES Advanced Encryption Standard

AKS Agrawal--Kayal--Saxena

APP A posteriori probability

ARQ Automatic Repeat reQuest

BBAN Basic Bank Account Number

BCH Bose--Chaudhuri--Hocquenghem

BEC Binary Erasure Channel

BI-AWGNC Binary-input Additive White Gaussian Noise Channel

BPA Belief Propagation Algorithm

BSC Binary Symmetric Channel

BWT...