1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
Introduction ....................................................... 1

1: Foundations of Coding ........................................... 7 
    1.1 From Julius Caesar to telecopy ............................. 8
        1.1.1 The source: from an image to a sequence of pixels	.... 8 
        1.1.2 Message compression .................................. 9 
        1.1.3 Error detection ...................................... 10 
        1.1.4 Encryption ........................................... 11 
        1.1.5 Decryption ........................................... 13 
        1.1.6 Attack and decryption ................................ 13 
              Decompression and data loss .......................... 13 
              Drawbacks of the fax code ............................ 14 
        1.1.7 Orders of magnitude and complexity of the algorithms . 15 
              Size of numbers ...................................... 15 
              Computer speed ....................................... 16  
              Comparison with the size and age of the universe ..... 16 
              Complexity of the algorithms ......................... 16
    1.2 Stream ciphers and probabilities ........................... 18
        1.2.1 The Vernam cipher and the One-time-pad cryptosystem .. 19 
        1.2.2 Some probability ..................................... 20 
              Events and probability measure ....................... 21 
              Conditional probabilities and Bayes' Formula ......... 22 
        1.2.3 Entropy .............................................. 23 
              Source of information ................................ 23 
              Entropy of a source................................... 23
              Joint entropies, conditional entropies ............... 24  
              Extension of a source................................. 25 
        1.2.4 Steganography and watermarking........................ 28 
        1.2.5 Perfect secrecy ...................................... 29 
        1.2.6 Perfect secrecy in practice and Kerckhoffs' principles 30
    1.3 Block ciphers, algebra and arithmetic ...................... 32 
        1.3.1 Blocks and chaining modes from CBC to CTR	............ 33
        1.3.2 Algebraic structure of codewords ..................... 36
              Groups ............................................... 36 
              Rings ................................................ 38 
              Fields ............................................... 40 
              Vector spaces and linear algebra ..................... 40 
        1.3.3 Bijective encoding of a block ........................ 42 
              Modular inverse: Euclidean algorithm ................. 42 
              Euler's totient function and Fermat's theorem ........ 46 
              Modular exponentiation and discrete logarithm ........ 49 
              One-way functions .................................... 51
        1.3.4 Construction of prime fields and finite fields ....... 52 
              Primality tests and prime number generation .......... 52 
              Arithmetic of polynomials ............................ 55 
              The ring V[X]/P and finite fields .................... 58 
              Irreducible polynomials .............................. 59 
              Construction of finite fields ........................ 61 
        1.3.5 Implementation of finite fields ...................... 63 
              Operations on polynomials ............................ 63 
              Use of generators .................................... 64 
              Primitive roots ...................................... 66 
        1.3.6 Curves over finite fields ............................ 68 
              WeierstraƟ model ..................................... 69
              The group of points of an elliptic curve ............. 70  
        1.3.7 Pseudo-Random Number Generators (PRNG) ............... 73 
              Congruential generators .............................. 74 
              Linear Feedback Shift Register (LFSR) ................ 75 
              Cryptographically secure generators .................. 77 
              Several statistical tests ............................ 78
    1.4 Decoding, decryption, attacks .............................. 80   
        1.4.1 Decoding without ambiguity ........................... 81 
              Prefix property ...................................... 83 
              Huffman trees ........................................ 84 
              Representation of instantaneous codes ................ 85 
              McMillan's theorem ................................... 86 
        1.4.2 Non-injective codes .................................. 87 
              Fingerprint integrity check .......................... 87 
              Hash functions ....................................... 87 
              Lossy transformations ................................ 92 
              Fourier Transform and Discrete Fourier Transform (DFT) 93 
              DFT algorithm ........................................ 95 
              DFT and n-th roots of unity in a finite field ........ 97 
              Fast product of polynomials using DFT ................ 98
        1.4.3 Cryptanalysis ........................................ 99 
              Attacks on Linear Congruential Generator ............. 99 
              Berlekamp-Massey algorithm for the synthesis of LFSRs  100 
              The Birthday Paradox ................................. 103 
              Yuval's attack on hash functions ..................... 104 
              Factoring composite numbers .......................... 105 
              Strong prime numbers ................................. 110 
              Solving the discrete logarithm problem ............... 111

2: Information theory and compression .............................. 115 
    2.1 Information theory ......................................... 116
        2.1.1 Average length of a code ............................. 116 
        2.1.2 Entropy as a measure of the amount of information .... 117
        2.1.3 Shannon's theorem .................................... 118        
    2.2 Statistical encoding ....................................... 120
        2.2.1 Huffman's algorithm .................................. 120 
              Huffman's algorithm is optimal ....................... 123 
        2.2.2 Arithmetic encoding .................................. 125
              Floating point arithmetics ........................... 126
              Integer arithmetics .................................. 128
              In practice .......................................... 129 
        2.2.3 Adaptive codes ....................................... 131 
              Dynamic Huffman algorithm-pack ....................... 131 
              Dynamic compression .................................. 132 
              Dynamic decompression ................................ 133 
              Adaptive arithmetic encoding ......................... 134
    2.3 Heuristics of entropy reduction ............................ 135
        2.3.1 Run-Length Encoding (RLE) ............................ 135 
              The fax code(end) .................................... 136 
        2.3.2 Move-to-Front ........................................ 137 
        2.3.2 Burrows-Wheeler Transform (BWT) ...................... 139
    2.4 Common compression codes ................................... 141
        2.4.1 Lempel-Ziv algorithm and gzip variants ............... 142 
        2.4.2 Comparisons of compression algorithms ................ 145 
        2.4.3 GIF and PNG formats for image compression ............ 147
    2.5 Lossy Compression .......................................... 147
        2.5.1 Deterioration of information ......................... 147 
        2.5.2 Transformation of audiovisual information ............ 148
        2.5.3 Joint Photographic Experts Group (JPEG) format ....... 149
              Discrete Cosinus Transform (DCT)-JPEG ................ 149 
              Watermarking JPEG images ............................. 152 
              Secure JPEG-2000 (JPSEC) ............................. 153
        2.5.4 Motion Picture Experts Group (MPEG) format ........... 154

3: Cryptology ...................................................... 157 
    3.1 General principles ......................................... 157
        3.1.1 Terminology .......................................... 157 
        3.1.2 What is the use of cryptography? ..................... 159 
        3.1.3 Main types of threats ................................ 161 
              Passive/active attacks ............................... 161 
              Cryptanalysis and attacks on encryption schemes ...... 161
    3.2 Secret key cryptography .................................... 162
        3.2.1 Principle of symmetric cryptography .................. 162
        3.2.2 Classes of symmetric encryption schemes .............. 164 
              Symmetric stream ciphers ............................. 165 
              Symmetric block ciphers .............................. 166 
              Unconditionally secure encryption .................... 167 
        3.2.3 Data Encryption Standard (DES) system ................ 167 
              Exhaustive description of DES ........................ 167 
              DES Key Derivation ................................... 170 
              Advantages and practical uses of DES ................. 170 
              Cryptanalysis of DES ................................. 171 
        3.2.4 Rijndael: Advanced Encryption Standard (AES) ......... 173 
              Principle of the algorithm ........................... 176 
              Key schedule in AES .................................. 181 
              Security of the AES .................................. 183
    3.3 Key exchange ............................................... 184
        3.3.1 Diffie-Hellman key exchange protocol and Man-in-the-
              middle attacks ....................................... 185
        3.3.2 Kerberos: a secret key provider ...................... 187 
              General description of the Kerberos protocol ......... 188 
              Details of Kerberos messages ......................... 189 
              Weaknesses of Kerberos ............................... 191
    3.4 Public key cryptography .................................... 192
        3.4.1 Motivations and main principles ...................... 192
        3.4.2 Rivest-Shamir-Adleman (RSA) encryption ............... 194 
              Efficiency and robustness of RSA ..................... 197 
              Attacks on RSA ....................................... 199
        3.4.3 El Gamal encryption .................................. 200
    3.5 Authentication, Integrity, Non-repudiation, Signatures ..... 202
        3.5.1 Cryptographic hash functions ......................... 202 
              Message-DigestAlgorithm5(MD5) ........................ 204 
              SHA-1 ................................................ 205 
              SHA-256 .............................................. 206
              Whirlpool ............................................ 207 
              Status of the resistance to collisions ............... 207 
              Integrity check for hash functions ................... 208 
              Message Authentication Code(MAC) ..................... 211
        3.5.2 Public key authentication ............................ 213 
        3.5.3 Electronic signatures ................................ 215 
              RSA signature ........................................ 216 
              Digital Signature Standard(DSS) ...................... 217
    3.6 Key management ............................................. 220
        3.6.1 Generation of cryptographically secure bits .......... 220 
        3.6.2 Public Key Infrastructure(PKI) ....................... 221 
              General principle .................................... 221 
              Elements of the infrastructure ....................... 222 
              Electronic certificates .............................. 225 
              The PKIX model ....................................... 226 
              Non-hierarchical architectures, PGP .................. 231
              Drawbacks of PKIs .................................... 232
        3.6.3 Securing channels with the SSH tool .................. 233 
              Secure SHel l(SSH), a hybrid protocol ................ 235 
              Server authentication ................................ 235 
              Setting-up a secure session .......................... 236
              Client authentication ................................ 237 
              Security, integrity and compression .................. 238 
              Major differences between SSH-1 and SSH-2 ............ 238

4: Error detection and correction .................................. 241 
    4.1 Principle of error detection and error correction .......... 243
        4.1.1 Block coding ......................................... 243  
        4.1.2 A simple example of parity detection ................. 244 
        4.1.3 Correction using longitudinal and transverse parity .. 245 
        4.1.4 Encoding, decoding and probability of error .......... 246
        4.1.5 Shannon's second theorem ............................. 247 
              Code rate and efficiency ............................. 247 
              Channel capacity ..................................... 248 
              Transmission without error on a constant capacity 
              channel .............................................. 249
    4.2 Error detection by parity - CRC codes ...................... 251
        4.2.1 Parity check on integers: ISBN, EAN, LUHN ............ 252 
              EAN bar code ......................................... 252 
              The ISBN code ........................................ 253 
              The Basic Bank Account Number(BBAN) .................. 254 
              Credit card:LUHN-10 .................................. 254 
        4.2.2 Cyclic Redundancy Checks (CRC) ....................... 254
              CRC encoding ......................................... 255 
              CRC decoding ......................................... 255 
              Number of detected bit errors ........................ 256 
              Examples of CRC codes ................................ 256
    4.3 Distance of a code ......................................... 257
        4.3.1 Error correction code and Hamming distance ........... 257
        4.3.2 Equivalent codes, extended codes and shortened codes . 261 
              Equivalent codes ..................................... 262 
              Extended codes ....................................... 262 
              Punctured codes ...................................... 263 
              Shortened code ....................................... 263 
        4.3.3 Perfect codes ........................................ 264
        4.3.4 Binary Hamming codes ................................. 265                 
    4.4 Linear codes and cyclic codes .............................. 267
        4.4.1 Linear codes and minimum redundancy .................. 267
        4.4.2 Encoding and decoding of linear codes ................ 270 
              Encoding by matrix-vector multiplication ............. 271 
              Decoding by matrix-vector multiplication ............. 271 
        4.4.3 Low Density Parity Check (LDPC) codes ................ 275 
              LDPC codes description ............................... 275 
              Encoding of LDPC codes ............................... 276 
              LDPC code representation by Tanner graphs ............ 277 
              Iterative Decoding of LDPC codes ..................... 279 
              Practical applications of LDPC codes ................. 286 
        4.4.4 Cyclic codes ......................................... 287 
              Characterization: generator polynomial ............... 288 
              Encoding process ..................................... 291 
              Error detection and decoding process.................. 291
        4.4.5 Bose-Chaudhuri-Hocquenghem (BCH) codes ............... 292 
              Minimum distance of a code............................ 292 
              Construction of BCH generator polynomials ............ 293 
        4.4.6 Optimal BCH codes: Reed-Solomon codes ................ 295 
              Decoding of Reed-Solomon codes ....................... 296 
              PAR-2 protocol ....................................... 299 
              Quick Response code(QR-code) ......................... 300
    4.5 Bursts of errors and interleaving .......................... 302
        4.5.1 Packets of errors .................................... 302 
        4.5.2 Interleaving ......................................... 302 
        4.5.3 Interleaving with delay and interleaving table ....... 303 
        4.5.4 Cross-interleaved codes .............................. 305 
        4.5.5 Interleaving ......................................... 305 
              Cross-Interleaved Reed-Solomon Code (CIRC) ........... 306
    4.6 Convolutional codes and turbo-codes ........................ 309
        4.6.1 Encoding by convolution .............................. 309 
        4.6.2 Shortest path decoding ............................... 310 
              State diagram ........................................ 310 
              Encoding lattice ..................................... 311 
              Viterbi's algorithm .................................. 312 
              Systematic codes, rate and puncturing ................ 314 
              Recursive convolutional codes ........................ 314 
        4.6.3 Turbo-codes .......................................... 315 
              Parallel composition ................................. 315 
              Turbo decoding ....................................... 316 
              Block turbo-codes and hybrid turbo-codes ............. 317 
              Performances and practical applications of turbo-codes 318
Compression, encryption, correction: as a conclusion ............... 319

Solutions of the exercises ......................................... 323 
    Solutions of the exercises given in chapter 1 .................. 323 
    Solutions of the exercises given in chapter 2 .................. 338 
    Solutions of the exercises given in chapter 3 .................. 347 
    Solutions of the exercises given in chapter 4 .................. 369 
    Solution of the "Casino" exercise .............................. 389

List of figures, tables, algorithms and used acronyms .............. 391 
    List of figures................................................. 391 
    List of tables ................................................. 393 
    List of algorithms.............................................. 394 
    List of used acronyms .......................................... 396

Bibliography ....................................................... 399 

Index .............................................................. 403-419