Instructor's Solutions Manual for Introduction to Cryptography with Coding Theory

1. Overview of Cryptography and Its Applications 

1.1 Secure Communications 

1.2 Cryptographic Applications




2. Classical Cryptosystems

2.1 Shift Ciphers 

2.2 Affine Ciphers 

2.3 The Vigenère Cipher

2.4 Substitution Ciphers

2.5 Sherlock Holmes

2.6 The Playfair and ADFGX Ciphers 

2.7 Enigma 

2.8 Exercises 

2.9 Computer Problems 




3. Basic Number Theory

3.1 Basic Notions

3.2 The Extended Euclidean Algorithm 

3.3 Congruences 

3.4 The Chinese Remainder Theorem

3.5 Modular Exponentiation 

3.6 Fermat and Euler

3.7 Primitive Roots 

3.8 Inverting Matrices Mod n

3.9 Square Roots Mod n 

3.10 Legendre and Jacobi Symbols 

3.11 Finite Fields 

3.12 Continued Fractions 

3.13 Exercises 

3.14 Computer Problems 




4. The One-Time Pad

4.1 Binary Numbers and ASCII 

4.2 One-Time Pads 

4.3 Multiple Use of a One-Time Pad 

4.4 Perfect Secrecy of the One-Time Pad 

4.5 Indistinguishability and Security 

4.6 Exercises 




5. Stream Ciphers

5.1 Pseudo-Random Bit Generation 

5.2 LFSR Sequences 

5.3 RC4

5.4 Exercises 

5.5 Computer Problems 




6. Block Ciphers

6.1 Block Ciphers 

6.2 Hill Ciphers 

6.3 Modes of Operation 

6.4 Multiple Encryption 

6.5 Meet-in-the-Middle Attacks 

6.6 Exercises 

6.7 Computer Problems 




7. The Data Encryption Standard

7.1 Introduction

7.2 A Simplified DES-Type Algorithm 

7.3 Differential Cryptanalysis 

7.4 DES 

7.5 Breaking DES 

7.6 Password Security 

7.7 Exercises

7.8 Computer Problems 




8. The Advanced Encryption Standard: Rijndael

8.1 The Basic Algorithm

8.2 The Layers

8.3 Decryption 

8.4 Design Considerations 

8.5 Exercises




9. The RSA Algorithm

9.1 The RSA Algorithm 

9.2 Attacks on RSA 

9.3 Primality Testing 

9.4 Factoring 

9.5 The RSA Challenge 

9.6 An Application to Treaty Verification

9.7 The Public Key Concept 

9.8 Exercises

9.9 Computer Problems 




10. Discrete Logarithms

10.1 Discrete Logarithms 

10.2 Computing Discrete Logs 

10.3 Bit Commitment

10.4 Diffie-Hellman Key Exchange 

10.5 The ElGamal Public Key Cryptosystem 

10.6 Exercises 

10.7 Computer Problems 




11. Hash Functions

11.1 Hash Functions 

11.2 Simple Hash Examples 

11.3 The Merkle-Damg ̊ard Construction 

11.4 SHA-2 

11.5 SHA-3/Keccak 

11.6 Exercises 




12. Hash Functions: Attacks and Applications

12.1 Birthday Attacks

12.2 Multicollisions

12.3 The Random Oracle Model 

12.4 Using Hash Functions to Encrypt 

12.5 Message Authentication Codes 

12.6 Password Protocols 

12.7 Blockchains 

12.8 Exercises

12.9 Computer Problems 




13. Digital Signatures

13.1 RSA Signatures

13.2 The ElGamal Signature Scheme 

13.3 Hashing and Signing 

13.4 Birthday Attacks on Signatures

13.5 The Digital Signature Algorithm 

13.6 Exercises 

13.7 Computer Problems 




14. What Can Go Wrong

14.1 An Enigma “Feature” 

14.2 Choosing Primes for RSA

14.3 WEP

14.4 Exercises 




15. Security Protocols

15.1 Intruders-in-the-Middle and Impostors 

15.2 Key Distribution

15.3 Kerberos

15.4 Public Key Infrastructures (PKI) 

15.5 X.509 Certificates

15.6 Pretty Good Privacy 

15.7 SSL and TLS 

15.8 Secure Electronic Transaction 

15.9 Exercises




16. Digital Cash

16.1 Setting the Stage for Digital Economies 

16.2 A Digital Cash System 

16.3 Bitcoin Overview

16.4 Cryptocurrencies 

16.5 Exercises 




17. Secret Sharing Schemes

17.1 Secret Splitting 

17.2 Threshold Schemes 

17.3 Exercises 

17.4 Computer Problems 




18. Games

18.1 Flipping Coins over the Telephone

18.2 Poker over the Telephone

18.3 Exercises 




19. Zero-Knowledge Techniques

19.1 The Basic Setup 

19.2 The Feige-Fiat-Shamir Identification Scheme 

19.3 Exercises 




20. Information Theory

20.1 Probability Review 

20.2 Entropy 

20.3 Huffman Codes 

20.4 Perfect Secrecy

20.5 The Entropy of English 

20.6 Exercises




21. Elliptic Curves

21.1 The Addition Law

21.2 Elliptic Curves Mod p 

21.3 Factoring with Elliptic Curves 

21.4 Elliptic Curves in Characteristic 2 

21.5 Elliptic Curve Cryptosystems 

21.6 Exercises 

21.7 Computer Problems




22. Pairing-Based Cryptography

22.1 Bilinear Pairings

22.2 The MOV Attack 

22.3 Tripartite Diffie-Hellman 

22.4 Identity-Based Encryption 

22.5 Signatures

22.6 Keyword Search 

22.7 Exercises




23. Lattice Methods

23.1 Lattices 

23.2 Lattice Reduction 

23.3 An Attack on RSA 

23.4 NTRU 

23.5 Another Lattice-Based Cryptosystem 

23.6 Post-Quantum Cryptography? 

23.7 Exercises 




24. Error Correcting Codes

24.1 Introduction 

24.2 Error Correcting Codes 

24.3 Bounds on General Codes

24.4 Linear Codes

24.5 Hamming Codes 

24.6 Golay Codes

24.7 Cyclic Codes 

24.8 BCH Codes

24.9 Reed-Solomon Codes 

24.10 The McEliece Cryptosystem 

24.11 Other Topics

24.12 Exercises 

24.13 Computer Problems 




25. Quantum Techniques in Cryptography

25.1 A Quantum Experiment 

25.2 Quantum Key Distribution

25.3 Shor’s Algorithm 

25.4 Exercises 




A. Mathematica® Examples

A.1 Getting Started with Mathematica 

A.2 Some Commands

A.3 Examples for Chapter 2

A.4 Examples for Chapter 3

A.5 Examples for Chapter 5 

A.6 Examples for Chapter 6

A.7 Examples for Chapter 9 

A.8 Examples for Chapter 10

A.9 Examples for Chapter 12

A.10 Examples for Chapter 17 

A.11 Examples for Chapter 18 

A.12 Examples for Chapter 21 




B. Maple® Examples

B.1 Getting Started with Maple

B.2 Some Commands

B.3 Examples for Chapter 2

B.4 Examples for Chapter 3 

B.5 Examples for Chapter 5 

B.6 Examples for Chapter 6 

B.7 Examples for Chapter 9 

B.8 Examples for Chapter 10

B.9 Examples for Chapter 12

B.10 Examples for Chapter 17 

B.11 Examples for Chapter 18

B.12 Examples for Chapter 21




C. MATLAB® Examples

C.1 Getting Started with MATLAB 

C.2 Examples for Chapter 2

C.3 Examples for Chapter 3 

C.4 Examples for Chapter 5

C.5 Examples for Chapter 6 

C.6 Examples for Chapter 9

C.7 Examples for Chapter 10 

C.8 Examples for Chapter 12 

C.9 Examples for Chapter 17

C.10 Examples for Chapter 18 

C.11 Examples for Chapter 21




D. Sage Examples

D.1 Computations for Chapter 2 

D.2 Computations for Chapter 3 

D.3 Computations for Chapter 5

D.4 Computations for Chapter 6

D.5 Computations for Chapter 9 

D.6 Computations for Chapter 10 

D.7 Computations for Chapter 12 

D.8 Computations for Chapter 17

D.9 Computations for Chapter 18 

D.10 Computations for Chapter 21 




E. Answers and Hints for Selected Odd-Numbered Exercises




F. Suggestions for Further Reading




Bibliography 

Index