|
|
|
Cryptography, Information Theory, and Error-Correction : A Handbook for the 21st Century
|
|
|
Bruen, Aiden A.
¤Ó
WILEY
|
|
|
|
- Á¦ÈÞ¸ô ÁÖ¹® ½Ã °í°´º¸»ó, ÀϺΠÀ̺¥Æ® Âü¿© ¹× ÁõÁ¤Ç° ÁõÁ¤, ÇÏ·ç/´çÀÏ ¹è¼Û¿¡¼ Á¦¿ÜµÇ¹Ç·Î Âü°í ¹Ù¶ø´Ï´Ù.
-
-
-
Preface xvii
I Mainly Cryptography 1
1 History Introduction and the Life and Work of Claude E. Shannon 3
2 Classical Ciphers and their Cryptanalysis 21
3 RSA, Key Searches, TLS, and Encrypting Email 47
4 The Fundamentals of Modern Cryptography 83
5 Modes of Operation for AES and Symmetric Algorithms 109
6 Elliptic Curve Cryptography (ECC) 125
7 General and Mathematical Attacks in Cryptography 143
8 Practical Issues in Modern Cryptography and Communications 165
II Mainly Information Theory 183
9. Information Theory and its Applications 185
10 Random Variables and Entropy 201
11 Source Coding, Redundancy 233
12 Channels, Capacity, the Fundamental Theorem 255
13 Signals, Sampling, Coding Gain, Shannon¡¯s Information Capacity Theorem 287
14. Ergodic and Markov Sources,Language Entropy
15 Perfect Secrecy: the New Paradigm 319
16 Shift Registers (LFSR) and Stream Ciphers 333
17 Compression and Applications 355
III Mainly Error-Correction 379
18 Error-Correction, Had...amard, and Bruen-Ott 381
19 Finite Fields, Modular Arithmetic, Linear Algebra, Number Theory 401
20 Introduction to Linear Codes 429
21.Cyclic Linear Codes,Shift Registers, and CRC 453
22 Reed-Solomon and MDS Codes, and the Main Linear Coding Theory Problem (LCTP) 463
23 MDS Codes, Secret Sharing, Invariant Theory 493
24. Key Reconciliation,Linear Codes, and New Algorithgms 507
25. New Identities for the Shannom Funciton with Applications 535
26. Blockchain and Bitcoin 549
27 IoT, the Internet of Things 561
28 In the Cloud 573
29 Review Problems and Solutions 589
Appendix A
Appendix B
Glossary 607
References 615
Index 643 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.4 Public Key Versus Symmetric Key . . . . . . . . . . . . . . . . . . . . . . . . 55
3.5 Attacks, Security, Catch-22 of Cryptography . . . . . . . . . . . . . . . . . . . 58
3.6 Summary of Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.7 The Diffie-Hellman Key Exchange . . . . . . . . . . . . . . . . . . . . . . . . 61
3.8 Intruder-in-the-Middle - Diffie-Hellman Key-Exchange . . . . . . . . . . . . 65
3.9 TLS (Transport Layer Security) . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.10 PGP and GPG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.11 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.12 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4 The Fundamentals of Modern Cryptography 79
4.1 Encryption Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.2 Block Ciphers, Shannon¡¯s Confusion and Diffusion . . . . . . . . . . . . . . . 82
4.3 Perfect Secrecy, Stream Ciphers, One-Time Pad . . . . . . . . . . . . . . . . . 83
4.4 Hash Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.5 Message Integrity Using Symmetric Cryptography . . . . . . . . . . . . . . . 89
4.6 General Public Key Cryptosystems . . . . . . . . . . . . . . . . . . . . . . . . 91
4.7 Digital Signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.8 Modifying Encrypted Data and Homomorphic Encryption . . . . . . . . . . . 95
4.9 Quantum Encryption using Polarized Photons . . . . . . . . . . . . . . . . . . 95
4.10 Quantum Encryption using Entanglement . . . . . . . . . . . . . . . . . . . . 98
4.11 Quantum Key Distribution is Not a Silver Bullet . . . . . . . . . . . . . . . . 99
4.12 Post-Quantum Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
4.13 Key Management and Kerberos . . . . . . . . . . . . . . . . . . . . . . . . . . 100
4.14 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
4.15 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5 Modes of Operation for AES and Symmetric Algorithms 105
5.1 Modes of Operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5.2 The Advanced Encryption Standard Code . . . . . . . . . . . . . . . . . . . . 107
6 Elliptic Curve Cryptography (ECC) 119
6.1 Abelian Integrals, Fields, Groups . . . . . . . . . . . . . . . . . . . . . . . . . 120
6.2 Curves, Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
6.3 Nonsingularity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
6.4 The Hasse Theorem, and an Example . . . . . . . . . . . . . . . . . . . . . . 123
6.5 More Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
6.6 The Group Law on Elliptic Curves . . . . . . . . . . . . . . . . . . . . . . . . 125
6.7 Key Exchange with Elliptic Curves . . . . . . . . . . . . . . . . . . . . . . . . 128
6.8 Elliptic Curves mod n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
6.9 Encoding Plain Text . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
6.10 Security of ECC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
6.11 More Geometry of Cubic Curves . . . . . . . . . . . . . . . . . . . . . . . . . 129
6.12 Cubic Curves and Arcs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
6.13 Homogeneous Coordinates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
6.14 Fermat¡¯s Last Theorem, Elliptic Curves, Gerhard Frey . . . . . . . . . . . . . 131
6.15 A Modification of the Standard Version of Elliptic Curve Cryptography . . . 132
6.16 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
6.17 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
7 Attacks in Cryptography 139
7.1 Cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
7.2 Soft Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
7.3 Brute-Force Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
7.4 Man-in-the-Middle Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
7.5 Relay Attacks, Car Key Fobs . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
7.6 Known Plain Text Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
7.7 Known Cipher Text Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
7.8 Chosen Plain Text Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
7.9 Chosen Cipher Text Attacks, Digital Signatures . . . . . . . . . . . . . . . . . 147
7.10 Replay Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
7.11 Birthday Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
7.12 Birthday Attack on Digital Signatures . . . . . . . . . . . . . . . . . . . . . . 150
7.13 Birthday Attack on the Discrete Log Problem . . . . . . . . . . . . . . . . . . 150
7.14 Attacks on RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
7.15 Attacks on RSA using Low-Exponents . . . . . . . . . . . . . . . . . . . . . . 151
7.16 Timing Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
7.17 Differential Cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
7.18 Attacks utilizing Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . 153
7.19 Cold Boot Attacks on Encryption Keys . . . . . . . . . . . . . . . . . . . . . 154
7.20 Implementation Errors and Unforeseen States . . . . . . . . . . . . . . . . . . 155
7.21 Tracking. Bluetooth, WiFi, and Your Smart Phone . . . . . . . . . . . . . . . 159
7.22 Keep Up with the Latest Attacks, (If You Can) . . . . . . . . . . . . . . . . . 160
8 Practical Issues in Modern Cryptography and Communications 161
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
8.2 Hot Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
8.3 Authentication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
8.4 User Anonymity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
8.5 E-commerce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
8.6 E-government . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
8.7 Key Lengths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
8.8 Digital Rights . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
8.9 Wireless Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
8.10 Communication Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
II Information Theory 179
9 Information Theory and its Applications 181
9.1 Axioms, Physics, Computation . . . . . . . . . . . . . . . . . . . . . . . . . . 181
9.2 Entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
9.3 Information Gained, Cryptography . . . . . . . . . . . . . . . . . . . . . . . . 184
9.4 Practical Applications of Information Theory . . . . . . . . . . . . . . . . . . 186
9.5 Information Theory and Physics . . . . . . . . . . . . . . . . . . . . . . . . . 188
9.6 Axiomatics of Information Theory . . . . . . . . . . . . . . . . . . . . . . . . 189
9.7 Number Bases, Erdos and the Hand of God . . . . . . . . . . . . . . . . . . . 190
9.8 Weighing Problems and Your MBA . . . . . . . . . . . . . . . . . . . . . . . . 192
9.9 Shannon Bits, the Big Picture . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
10 Random Variables and Entropy 197
10.1 Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
10.2 Mathematics of Entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
10.3 Calculating Entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
10.4 Conditional Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
10.5 Bernoulli Trials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
10.6 Typical Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
10.7 Law of Large Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
10.8 Joint and Conditional Entropy . . . . . . . . . . . . . . . . . . . . . . . . . . 211
10.9 Applications of Entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
10.10Calculation of Mutual Information . . . . . . . . . . . . . . . . . . . . . . . . 217
10.11Mutual Information and Channels . . . . . . . . . . . . . . . . . . . . . . . . 219
10.12The Entropy of X + Y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
10.13Subadditivity of the Function £¿x log x . . . . . . . . . . . . . . . . . . . . . . 221
10.14Entropy and Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
10.15Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
10.16Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
11 Source Coding, Redundancy 229
11.1 Introduction, Source Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . 230
11.2 Encodings, Kraft, McMillan . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
11.3 Block Coding, the Oracle, Yes-No Questions . . . . . . . . . . . . . . . . . . . 237
11.4 Optimal Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
11.5 Huffman Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
11.6 Optimality of Huffman Coding . . . . . . . . . . . . . . . . . . . . . . . . . . 245
11.7 Data Compression, Redundancy . . . . . . . . . . . . . . . . . . . . . . . . . 246
11.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
11.9 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
12 Channels, Capacity, the Fundamental Theorem 251
12.1 Abstract Channels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
12.2 More Specific Channels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
12.3 New Channels from Old, Cascades . . . . . . . . . . . . . . . . . . . . . . . . 254
12.4 Input Probability, Channel Capacity . . . . . . . . . . . . . . . . . . . . . . . 257
12.5 Capacity for General Binary Channels, Entropy . . . . . . . . . . . . . . . . . 261
12.6 Hamming Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
12.7 Improving Reliability of a Binary Symmetric Channel . . . . . . . . . . . . . 264
12.8 Error Correction, Error Reduction, Good Redundancy . . . . . . . . . . . . . 264
12.9 The Fundamental Theorem of Information Theory . . . . . . . . . . . . . . . 268
12.10Proving the Fundamental Theorem . . . . . . . . . . . . . . . . . . . . . . . . 275
12.11Summary, the Big Picture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
12.12Postscript: The Capacity of the Binary Symmetric Channel . . . . . . . . . . 278
12.13Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
12.14Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
13 Shannon¡¯s Information Capacity Theorem 283
13.1 Continuous Signals, Shannon¡¯s Sampling Theorem . . . . . . . . . . . . . . . 284
13.2 The Band-Limited Capacity Theorem . . . . . . . . . . . . . . . . . . . . . . 286
13.3 The Coding Gain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
14 Ergodic and Markov Sources, Language Entropy 295
14.1 General and Stationary Sources . . . . . . . . . . . . . . . . . . . . . . . . . . 296
14.2 Ergodic Sources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
14.3 Markov Chains and Markov Sources . . . . . . . . . . . . . . . . . . . . . . . 300
14.4 Irreducible Markov Sources, Adjoint Source . . . . . . . . . . . . . . . . . . . 303
14.5 Cascades and the Data Processing Theorem . . . . . . . . . . . . . . . . . . . 305
14.6 The Redundancy of Languages . . . . . . . . . . . . . . . . . . . . . . . . . . 307
14.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
14.8 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
15 Perfect Secrecy: the New Paradigm 313
15.1 Symmetric Key Cryptosystems . . . . . . . . . . . . . . . . . . . . . . . . . . 313
15.2 Perfect Secrecy and Equiprobable Keys . . . . . . . . . . . . . . . . . . . . . 315
15.3 Perfect Secrecy and Latin Squares . . . . . . . . . . . . . . . . . . . . . . . . 316
15.4 The Abstract Approach to Perfect Secrecy . . . . . . . . . . . . . . . . . . . . 318
15.5 Cryptography, Information Theory, Shannon . . . . . . . . . . . . . . . . . . 319
15.6 Unique Message from Ciphertext, Unicity . . . . . . . . . . . . . . . . . . . . 319
15.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
15.8 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
16 Shift Registers (LFSR) and Stream Ciphers 327
16.1 Vernam Cipher, Psuedo-Random Key . . . . . . . . . . . . . . . . . . . . . . 328
16.2 Construction of Feedback Shift Registers . . . . . . . . . . . . . . . . . . . . 329
16.3 Periodicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
16.4 Maximal Periods, Pseudo-Random Sequences . . . . . . . . . . . . . . . . . . 334
16.5 Determining the Output from 2m Bits . . . . . . . . . . . . . . . . . . . . . 336
16.6 The Tap Polynomial and the Period . . . . . . . . . . . . . . . . . . . . . . . 340
16.7 Short Linear Feedback Shift Registers and the Berlekamp-Massey Algorithm . 341
16.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345
16.9 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346
17 Compression and Applications 349
17.1 Introduction, Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
17.2 The Memory Hierarchy of a computer . . . . . . . . . . . . . . . . . . . . . . 351
17.3 Memory Compression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352
17.4 Lempel-Ziv Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355
17.5 The WKdm algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
17.6 Main Memory - to Compress or Not to Compress. . . . . . . . . . . . . . . . 364
17.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
17.8 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368
III Error-Correction 371
18 Error-Correction, Hadamard, and Bruen-Ott 373
18.1 General Ideas of Error Correction . . . . . . . . . . . . . . . . . . . . . . . . . 373
18.2 Error Detection, Error Correction . . . . . . . . . . . . . . . . . . . . . . . . . 374
18.3 A Formula for Correction and Detection . . . . . . . . . . . . . . . . . . . . . 375
18.4 Hadamard Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
18.5 Mariner, Hadamard and Reed-Muller . . . . . . . . . . . . . . . . . . . . . . . 379
18.6 Reed-Muller Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380
18.7 Block Designs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
18.8 The Rank of Incidence Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . 382
18.9 The Main Coding Theory Problem, Bounds . . . . . . . . . . . . . . . . . . . 383
18.10Update on the Reed-Muller Codes . . . . . . . . . . . . . . . . . . . . . . . . 388
18.11Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390
18.12Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390
19 Finite Fields, Modular Arithmetic, Linear Algebra, Number Theory 393
19.1 Modular Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393
19.2 A Little Linear Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397
19.3 Applications to RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399
19.4 Primitive Roots for Primes and Diffie-Hellman . . . . . . . . . . . . . . . . . 400
19.5 The Extended Euclidean Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 403
19.6 Proof that the RSA Algorithm Works . . . . . . . . . . . . . . . . . . . . . . 404
19.7 Constructing Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404
19.8 Pollard¡¯s p £¿ 1 Factoring Algorithm . . . . . . . . . . . . . . . . . . . . . . . 409
19.9 Latin Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410
19.10Complexity, Turing Machines, Quantum Computing . . . . . . . . . . . . . . 412
19.11Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415
19.12Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416
20 Introduction to Linear Codes 419
20.1 Repetition Codes and Parity Checks . . . . . . . . . . . . . . . . . . . . . . . 419
20.2 Details of Linear Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 421
20.3 Parity Checks, the Syndrome, Weights . . . . . . . . . . . . . . . . . . . . . . 425
20.4 Hamming Codes, an Inequality . . . . . . . . . . . . . . . . . . . . . . . . . . 427
20.5 Perfect Codes, Errors and the BSC . . . . . . . . . . . . . . . . . . . . . . . . 429
20.6 Generalizations of Binary Hamming Codes . . . . . . . . . . . . . . . . . . . . 429
20.7 The Football Pools Problem, Extended Hamming Codes . . . . . . . . . . . . 430
20.8 Golay Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431
20.9 McEliece Cryptosystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433
20.10Historical Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434
20.11Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435
20.12Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437
21 Cyclic Linear Codes, Shift Registers and CRC 443
21.1 Cyclic Linear Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443
21.2 Generators for Cyclic Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446
21.3 The Dual Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450
21.4 Linear Feedback Shift Registers and Codes . . . . . . . . . . . . . . . . . . . 452
21.5 Finding the Period of a LFSR . . . . . . . . . . . . . . . . . . . . . . . . . . . 455
21.6 Cyclic Redundancy Check (CRC) . . . . . . . . . . . . . . . . . . . . . . . . . 455
21.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457
21.8 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459
22 Reed-Solomon, MDS Codes, the Main LCTP Problem 463
22.1 Cyclic Linear Codes and Vandermonde . . . . . . . . . . . . . . . . . . . . . . 464
22.2 The Singleton Bound for Linear Codes . . . . . . . . . . . . . . . . . . . . . . 466
22.3 Reed-Solomon Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 468
22.4 Reed-Solomon Codes and the Fourier Transform Approach . . . . . . . . . . . 469
22.5 Correcting Burst Errors, Interleaving . . . . . . . . . . . . . . . . . . . . . . . 471
22.6 Decoding Reed-Solomon Codes . . . . . . . . . . . . . . . . . . . . . . . . . . 472
22.7 An Algorithm for Decoding and an Example . . . . . . . . . . . . . . . . . . . 474
22.8 MDS Codes, a Partial Solution of a Sixty Year-Old Problem . . . . . . . . . . 477
22.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480
22.10Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480
23 MDS Codes, Secret Sharing, Invariant Theory 483
23.1 Some Facts Concerning MDS Codes . . . . . . . . . . . . . . . . . . . . . . . 483
23.2 The Case k = 2, Bruck Nets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484
23.3 Upper bounds on MDS Codes, Bruck-Ryser . . . . . . . . . . . . . . . . . . . 486
23.4 MDS Codes and Secret Sharing Schemes . . . . . . . . . . . . . . . . . . . . . 489
23.5 MacWilliams Identities, Invariant Theory . . . . . . . . . . . . . . . . . . . . 490
23.6 Codes, Planes, Blocking Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . 490
23.7 Long Binary Linear Codes of Minimum Weight at Least 4 . . . . . . . . . . . 494
23.8 An Inverse Problem and a Basic Question in Linear Algebra . . . . . . . . . . 495
24 Key Reconciliation, Linear Codes, New Algorithms 497
24.1 Symmetric and Public Key Cryptography . . . . . . . . . . . . . . . . . . . . 498
24.2 General Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 498
24.3 The Secret Key and the Reconciliation Algorithm . . . . . . . . . . . . . . . . 500
24.4 Equality of Remnant Keys: the Halting Criterion . . . . . . . . . . . . . . . . 504
24.5 Linear Codes: the Checking Hash Function . . . . . . . . . . . . . . . . . . . 506
24.6 Convergence and Length of Keys . . . . . . . . . . . . . . . . . . . . . . . . . 508
24.7 Main Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 510
24.8 Some Details on the Random Permutation . . . . . . . . . . . . . . . . . . . . 516
24.9 The Case where Eve has Non-Zero Initial Information . . . . . . . . . . . . . 516
24.10Hash Functions using Block Designs . . . . . . . . . . . . . . . . . . . . . . . 517
24.11Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 518
25 New Identities for the Shannon Function and an Application 521
25.1 Extensions of a Binary Symmetric Channel . . . . . . . . . . . . . . . . . . . 522
25.2 A Basic Entropy Equality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 524
25.3 The New Identities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 526
25.4 Applications to Cryptography and a Shannon-type Limit . . . . . . . . . . . 529
25.5 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531
25.6 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531
26 Blockchain and Bitcoin 535
26.1 Ledgers, Blockchains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537
26.2 Hash Functions, Cryptographic Hashes . . . . . . . . . . . . . . . . . . . . . . 538
26.3 Digital Signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539
26.4 Bitcoin and Cryptocurrencies . . . . . . . . . . . . . . . . . . . . . . . . . . . 539
26.5 The Append-Only Network, Identities, Timestamp, Bitcoin . . . . . . . . . . 542
26.6 The Bitcoin Blockchain and Merkle Roots . . . . . . . . . . . . . . . . . . . . 542
26.7 Mining, Proof-of-Work, Consensus . . . . . . . . . . . . . . . . . . . . . . . . 543
26.8 Thwarting Double Spending . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545
27 IoT, the Internet of Things 547
27.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 548
27.2 Analog to Digital (A/D) Converters . . . . . . . . . . . . . . . . . . . . . . . 548
27.3 Programmable Logic Controller . . . . . . . . . . . . . . . . . . . . . . . . . . 549
27.4 Embedded Operating Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . 549
27.5 Evolution, From SCADA to the Internet of Things . . . . . . . . . . . . . . . 550
27.6 Everything is Fun and Games until Somebody Releases a Stuxnet . . . . . . . 551
27.7 Securing the IoT, a Mammoth Task . . . . . . . . . . . . . . . . . . . . . . . 553
27.8 Privacy and Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553
28 In the Cloud 559
28.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 560
28.2 Distributed Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 562
28.3 Cloud Storage - Availability and Copyset Replication . . . . . . . . . . . . 563
28.4 Homomorphic Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 569
28.5 Cybersecurity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 571
28.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573
28.7 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573
29 Additional Problems and Solutions 575
29.1 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 575
29.2 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 579
Appendices 589
A ASCII . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 590
B Shannon¡¯s Entropy Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 591
Glossary 593
Bibliography 628
Index 644
-
-
|
Bruen, Aiden A. [Àú]
|
|
-
-
-
Àüü 0°³ÀÇ ±¸¸ÅÈıⰡ ÀÖ½À´Ï´Ù.
|
ÀÎÅÍÆÄÅ©µµ¼´Â °í°´´ÔÀÇ ´Ü¼ø º¯½É¿¡ ÀÇÇÑ ±³È¯°ú ¹ÝÇ°¿¡ µå´Â ºñ¿ëÀº °í°´´ÔÀÌ ÁöºÒÄÉ µË´Ï´Ù.
´Ü, »óÇ°À̳ª ¼ºñ½º ÀÚüÀÇ ÇÏÀÚ·Î ÀÎÇÑ ±³È¯ ¹× ¹ÝÇ°Àº ¹«·á·Î ¹ÝÇ° µË´Ï´Ù. |
|
±³È¯ ¹× ¹ÝÇ°ÀÌ °¡´ÉÇÑ °æ¿ì |
»óÇ°À» °ø±Þ ¹ÞÀº ³¯·ÎºÎÅÍ 7ÀÏÀ̳» °¡´É
°ø±Þ¹ÞÀ¸½Å »óÇ°ÀÇ ³»¿ëÀÌ Ç¥½Ã, ±¤°í ³»¿ë°ú ´Ù¸£°Å³ª ´Ù¸£°Ô ÀÌÇàµÈ °æ¿ì¿¡´Â °ø±Þ¹ÞÀº ³¯·ÎºÎÅÍ 3°³¿ù À̳», ȤÀº ±×»ç½ÇÀ» ¾Ë°Ô µÈ ³¯ ¶Ç´Â ¾Ë ¼ö ÀÖ¾ú´ø ³¯·ÎºÎÅÍ 30ÀÏ À̳»
»óÇ°¿¡ ¾Æ¹«·± ÇÏÀÚ°¡ ¾ø´Â °æ¿ì ¼ÒºñÀÚÀÇ °í°´º¯½É¿¡ ÀÇÇÑ ±³È¯Àº »óÇ°ÀÇ Æ÷Àå»óÅ µîÀÌ ÀüÇô ¼Õ»óµÇÁö ¾ÊÀº °æ¿ì¿¡ ÇÑÇÏ¿© °¡´É |
|
±³È¯ ¹× ¹ÝÇ°ÀÌ ºÒ°¡´ÉÇÑ °æ¿ì |
±¸¸ÅÈ®Á¤ ÀÌÈÄ(¿ÀǸ¶ÄÏ»óÇ°¿¡ ÇÑÇÔ)
°í°´´ÔÀÇ Ã¥ÀÓ ÀÖ´Â »çÀ¯·Î »óÇ° µîÀÌ ¸ê½Ç ¶Ç´Â ÈÑ¼ÕµÈ °æ¿ì
(´Ü, »óÇ°ÀÇ ³»¿ëÀ» È®ÀÎÇϱâ À§ÇÏ¿© Æ÷Àå µîÀ» ÈѼÕÇÑ °æ¿ì´Â Á¦¿Ü)
½Ã°£ÀÌ Áö³²¿¡ µû¶ó ÀçÆǸŰ¡ °ï¶õÇÒ Á¤µµ·Î ¹°Ç°ÀÇ °¡Ä¡°¡ ¶³¾îÁø °æ¿ì
Æ÷Àå °³ºÀµÇ¾î »óÇ° °¡Ä¡°¡ ÈÑ¼ÕµÈ °æ¿ì |
|
´Ù¹è¼ÛÁöÀÇ °æ¿ì ¹ÝÇ° ȯºÒ |
´Ù¹è¼ÛÁöÀÇ °æ¿ì ´Ù¸¥ Áö¿ªÀÇ ¹ÝÇ°À» µ¿½Ã¿¡ ÁøÇàÇÒ ¼ö ¾ø½À´Ï´Ù.
1°³ Áö¿ªÀÇ ¹ÝÇ°ÀÌ ¿Ï·áµÈ ÈÄ ´Ù¸¥ Áö¿ª ¹ÝÇ°À» ÁøÇàÇÒ ¼ö ÀÖÀ¸¹Ç·Î, ÀÌÁ¡ ¾çÇØÇØ Áֽñ⠹ٶø´Ï´Ù. |
|
Áß°í»óÇ°ÀÇ ±³È¯ |
Áß°í»óÇ°Àº Á¦ÇÑµÈ Àç°í ³»¿¡¼ ÆǸŰ¡ ÀÌ·ç¾îÁö¹Ç·Î, ±³È¯Àº ºÒ°¡´ÉÇÕ´Ï´Ù. |
|
¿ÀǸ¶ÄÏ »óÇ°ÀÇ È¯ºÒ |
¿ÀǸ¶ÄÏ»óÇ°¿¡ ´ëÇÑ Ã¥ÀÓÀº ¿øÄ¢ÀûÀ¸·Î ¾÷ü¿¡°Ô ÀÖÀ¸¹Ç·Î, ±³È¯/¹ÝÇ° Á¢¼ö½Ã ¹Ýµå½Ã ÆǸÅÀÚ¿Í ÇùÀÇ ÈÄ ¹ÝÇ° Á¢¼ö¸¦ ÇϼžßÇϸç, ¹ÝÇ°Á¢¼ö ¾øÀÌ ¹Ý¼ÛÇϰųª, ¿ìÆíÀ¸·Î º¸³¾ °æ¿ì »óÇ° È®ÀÎÀÌ ¾î·Á¿ö ȯºÒÀÌ ºÒ°¡´ÉÇÒ ¼ö ÀÖÀ¸´Ï À¯ÀÇÇϽñ⠹ٶø´Ï´Ù. |
|
|
|
¹è¼Û¿¹Á¤ÀÏ ¾È³» |
ÀÎÅÍÆÄÅ© µµ¼´Â ¸ðµç »óÇ°¿¡ ´ëÇØ ¹è¼Û¿Ï·á¿¹Á¤ÀÏÀ» À¥»çÀÌÆ®¿¡ Ç¥½ÃÇÏ°í ÀÖ½À´Ï´Ù.
|
<ÀÎÅÍÆÄÅ© Á÷¹è¼Û »óÇ°> |
»óÇ°Àº ¿ù~Åä¿äÀÏ ¿ÀÀü 10½Ã ÀÌÀü ÁÖ¹®ºÐ¿¡ ´ëÇÏ¿© ´çÀÏ Ãâ°í/´çÀÏ ¹è¼Û¿Ï·á¸¦ º¸ÀåÇÏ´Â »óÇ°ÀÔ´Ï´Ù. |
»óÇ°Àº ¼¿ïÁö¿ª/ÆòÀÏ ÁÖ¹®ºÐÀº ´çÀÏ Ãâ°í/ÀÍÀÏ ¹è¼Û¿Ï·á¸¦ º¸ÀåÇϸç,
¼¿ï¿ÜÁö¿ª/ÆòÀÏ ÁÖ¹®ºÐÀÇ °æ¿ì´Â ¿ÀÈÄ 6½Ã±îÁö ÁÖ¹®ºÐ¿¡ ´ëÇÏ¿© ÀÍÀÏ ¹è¼Û¿Ï·á¸¦ º¸ÀåÇÏ´Â »óÇ°ÀÔ´Ï´Ù.
(´Ü, ¿ù¿äÀÏÀº 12½Ã±îÁö ÁÖ¹®¿¡ ÇÑÇÔ)
|
»óÇ°Àº, ÀÔ°í¿¹Á¤ÀÏ(Á¦Ç°Ãâ½ÃÀÏ)+Åùè»ç¹è¼ÛÀÏ(1ÀÏ)¿¡ ¹è¼Û¿Ï·á¸¦ º¸ÀåÇÕ´Ï´Ù. |
~
»óÇ°Àº À¯ÅëƯ¼º»ó ÀÎÅÍÆÄÅ©¿¡¼ Àç°í¸¦ º¸À¯ÇÏÁö ¾ÊÀº »óÇ°À¸·Î ÁÖ¹®ÀÏ+±âÁØÃâ°íÀÏ+Åùè»ç¹è¼ÛÀÏ(1ÀÏ)¿¡ ¹è¼Û¿Ï·á¸¦ º¸ÀåÇÕ´Ï´Ù.(Åä/°øÈÞÀÏÀº ¹è¼Û±â°£¿¡ Æ÷ÇÔµÇÁö ¾Ê½À´Ï´Ù.)
¡Ø±âÁØÃâ°íÀÏ:ÀÎÅÍÆÄÅ©°¡ »óÇ°À» ¼ö±ÞÇÏ¿© ¹°·ùâ°í¿¡¼ Æ÷Àå/Ãâ°íÇϱâ±îÁö ¼Ò¿äµÇ´Â ½Ã°£
|
|
<¾÷ü Á÷Á¢¹è¼Û/¿ÀǸ¶ÄÏ »óÇ°> |
~
»óÇ°Àº ¾÷ü°¡ ÁÖ¹®À» È®ÀÎÇÏ°í, Ãâ°íÇϱâ±îÁö °É¸®´Â ½Ã°£ÀÔ´Ï´Ù. ÁÖ¹®ÀÏ+±âÁØÃâ°íÀÏ+Åùè»ç¹è¼ÛÀÏ(2ÀÏ)¿¡ ¹è¼Û¿Ï·á¸¦ º¸ÀåÇÕ´Ï´Ù.(Åä/°øÈÞÀÏÀº ¹è¼Û±â°£¿¡ Æ÷ÇÔµÇÁö ¾Ê½À´Ï´Ù.)
¡Ø5ÀÏÀ̳» Ãâ°í°¡ ½ÃÀÛµÇÁö ¾ÊÀ»½Ã, ¿ÀǸ¶ÄÏ »óÇ°Àº ÀÚµ¿À¸·Î ÁÖ¹®ÀÌ Ãë¼ÒµÇ¸ç, °í°´´Ô²² Ç°Àýº¸»ó±ÝÀ» Áö±ÞÇØ µå¸³´Ï´Ù.
|
|
|
¹è¼Ûºñ ¾È³» |
µµ¼(Áß°íµµ¼ Æ÷ÇÔ)¸¸ ±¸¸ÅÇϽøé : ¹è¼Ûºñ 2,000¿ø (1¸¸¿øÀÌ»ó ±¸¸Å ½Ã ¹«·á¹è¼Û) À½¹Ý/DVD¸¸ ±¸¸ÅÇϽøé : ¹è¼Ûºñ 1,500¿ø (2¸¸¿øÀÌ»ó ±¸¸Å ½Ã ¹«·á¹è¼Û)
ÀâÁö/¸¸È/±âÇÁÆ®¸¸ ±¸¸ÅÇϽøé : ¹è¼Ûºñ 2,000¿ø (2¸¸¿øÀÌ»ó ±¸¸Å ½Ã ¹«·á¹è¼Û)
µµ¼¿Í À½¹Ý/DVD¸¦ ÇÔ²² ±¸¸ÅÇϽøé : ¹è¼Ûºñ 1,500¿ø 1¸¸¿øÀÌ»ó ±¸¸Å ½Ã ¹«·á¹è¼Û)
µµ¼¿Í ÀâÁö/¸¸È/±âÇÁÆ®/Áß°íÁ÷¹è¼Û»óÇ°À» ÇÔ²² ±¸¸ÅÇϽøé : 2,000¿ø (1¸¸¿øÀÌ»ó ±¸¸Å ½Ã ¹«·á¹è¼Û)
¾÷üÁ÷Á¢¹è¼Û»óÇ°À» ±¸¸Å½Ã : ¾÷üº°·Î »óÀÌÇÑ ¹è¼Ûºñ Àû¿ë
* ¼¼Æ®»óÇ°ÀÇ °æ¿ì ºÎºÐÃë¼Ò ½Ã Ãß°¡ ¹è¼Ûºñ°¡ ºÎ°úµÉ ¼ö ÀÖ½À´Ï´Ù.
* ºÏÄ«Æ®¿¡¼ ¹è¼Ûºñ¾ø¾Ö±â ¹öÆ°À» Ŭ¸¯Çϼż, µ¿ÀϾ÷ü»óÇ°À» Á¶±Ý ´õ ±¸¸ÅÇϽøé, ¹è¼Ûºñ¸¦ Àý¾àÇÏ½Ç ¼ö ÀÖ½À´Ï´Ù.
|
|
Çؿܹè¼Û ¾È³» |
ÀÎÅÍÆÄÅ©µµ¼¿¡¼´Â ±¹³»¿¡¼ ÁÖ¹®ÇϽðųª ÇØ¿Ü¿¡¼ ÁÖ¹®ÇÏ¿© ÇØ¿Ü·Î ¹è¼ÛÀ» ¿øÇÏ½Ç °æ¿ì DHL°ú Ư¾àÀ¸·Î Ã¥Á¤µÈ ¿ä±ÝÇ¥¿¡
ÀÇÇØ °³ÀÎÀÌ ÀÌ¿ëÇÏ´Â °æ¿ìº¸´Ù ¹è¼Û¿ä±ÝÀ» Å©°Ô ³·Ã߸ç DHL(www.dhl.co.kr)·Î Çؿܹè¼Û ¼ºñ½º¸¦ Á¦°øÇÕ´Ï´Ù.
Çؿܹè¼ÛÀº µµ¼/CD/DVD »óÇ°¿¡ ÇÑÇØ ¼ºñ½ºÇÏ°í ÀÖÀ¸¸ç, ´Ù¸¥ »óÇ°À» ºÏÄ«Æ®¿¡ ÇÔ²² ´ãÀ¸½Ç °æ¿ì Çؿܹè¼ÛÀÌ ºÒ°¡ÇÕ´Ï´Ù.
ÇØ¿ÜÁÖ¹®¹è¼Û ¼ºñ½º´Â ÀÎÅÍÆÄÅ© µµ¼ ȸ¿ø °¡ÀÔÀ» Çϼž߸¸ ½Åû °¡´ÉÇÕ´Ï´Ù. |
|
¾Ë¾ÆµÎ¼¼¿ä!!! |
µµ¸Å»ó ¹× Á¦ÀÛ»ç »çÁ¤¿¡ µû¶ó Ç°Àý/ÀýÆÇ µîÀÇ »çÀ¯·Î Ãë¼ÒµÉ ¼ö ÀÖ½À´Ï´Ù.
¿ÀǸ¶ÄϾ÷üÀÇ ¹è¼ÛÁö¿¬½Ã ÁÖ¹®ÀÌ ÀÚµ¿À¸·Î Ãë¼ÒµÉ ¼ö ÀÖ½À´Ï´Ù.
Ãâ°í°¡´É ½Ã°£ÀÌ ¼·Î ´Ù¸¥ »óÇ°À» ÇÔ²² ÁÖ¹®ÇÒ °æ¿ì Ãâ°í°¡´É ½Ã°£ÀÌ °¡Àå ±ä ±âÁØÀ¸·Î ¹è¼ÛµË´Ï´Ù.
À¯ÅëÀÇ Æ¯¼º»ó Ãâ°í±â°£Àº ¿¹Á¤º¸´Ù ¾Õ´ç°ÜÁö°Å³ª ´ÊÃçÁú ¼ö ÀÖ½À´Ï´Ù.
Åùè»ç ¹è¼ÛÀÏÀÎ ¼¿ï ¹× ¼öµµ±ÇÀº 1~2ÀÏ, Áö¹æÀº 2~3ÀÏ, µµ¼, »ê°£, ±ººÎ´ë´Â 3ÀÏ ÀÌ»óÀÇ ½Ã°£ÀÌ ¼Ò¿äµË´Ï´Ù. |
|
|
|
|