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
|
