Introduction to Cryptography with Coding Theory / Edition 2

by Wade Trappe, Lawrence Washington

Overview

With its lively, conversational tone and practical focus, this edition mixes applied and theoretical aspects for a solid introduction to cryptography and security, including the latest significant advancements in the field.

Product Details

ISBN-13:	9780131862395
Publisher:	Pearson Education
Publication date:	07/15/2005
Series:	Featured Titles for Cryptography Series
Edition description:	2ND
Pages:	600
Product dimensions:	7.40(w) x 9.55(h) x 1.50(d)

About the Author

Wade Trappe is a Professor in the Electrical and Computer Engineering Department at Rutgers University, and Associate Director of the Wireless Information Network Laboratory (WINLAB). He has led several federally funded projects in the area of cybersecurity and communication systems. He was named Fellow of the Institute of Electrical and Electronics Engineers (IEEE) in 2014 for contributions to information and communication security.

Table of Contents

• 1 Overview
  Secure Communications. Cryptographic Applications
• 2 Classical Cryptosystems.
  Shift Ciphers. Affine Ciphers. The Vigen‘ere Cipher. Substitution Ciphers. Sherlock Holmes. The Playfair and ADFGX Ciphers. Block Ciphers. Binary Numbers and ASCII. One-Time Pads. Pseudo-random Bit Generation. LFSR Sequences. Enigma. Exercises. Computer Problems.
• 3 Basic Number Theory.
  Basic Notions. Solving ax + by = d. Congruences. The Chinese Remainder Theorem. Modular Exponentiation. Fermat and Euler. Primitive Roots. Inverting Matrices Mod n. Square Roots Mod n. Legendre and Jacobi Symbols. Finite Fields. Continued Fractions. Exercises. Computer Problems.
• 4 The Data Encryption Standard
  Introduction. A Simplified DES-Type Algorithm. Differential Cryptanalysis. DES. Modes of Operation. Breaking DES. Meet-in-the-Middle Attacks. Password Security. Exercises.
• 5 AES: Rijndael
  The Basic Algorithm. The Layers. Decryption. Design Considerations.
• 6 The RSA Algorithm
  The RSA Algorithm. Attacks on RSA. Primality Testing. Factoring. The RSA Challenge. An Application to Treaty Verification. The Public Key Concept. Exercises. Computer Problems
• 7 Discrete Logarithms
  Discrete Logarithms. Computing Discrete Logs. Bit Commitment Diffie-Hellman Key Exchange. ElGamal Public Key Cryptosystems. Exercises. Computer Problems.
• 8 Hash Functions
  Hash Functions. A Simple Hash Example. The Secure Hash Algorithm. Birthday Attacks. Multicollisions. The Random Oracle Model. Using Hash Functions to Encrypt.
• 9 Digital Signatures
  RSA Signatures. The ElGamal Signature Scheme. Hashing and Signing. Birthday Attacks on Signatures. The Digital Signature Algorithm. Exercises. Computer Problems.
• 10 Security Protocols
  Intruders-in-the-Middle and Impostors. Key Distribution. Kerberos Public Key Infrastructures (PKI). X.509 Certificates. Pretty Good Privacy. SSL and TLS. Secure Electronic Transaction. Exercises.
• 11 Digital Cash
  Digital Cash. Exercises.
• 12 Secret Sharing Schemes
  Secret Splitting. Threshold Schemes. Exercises. Computer Problems.
• 13 Games
  Flipping Coins over the Telephone. Poker over the Telephone. Exercises.
• 14 Zero-Knowledge Techniques
  The Basic Setup. The Feige-Fiat-Shamir Identification Scheme. Exercises.
• 15 Information Theory
  Probability Review. Entropy. Huffman Codes. Perfect Secrecy. The Entropy of English. Exercises.
• 16 Elliptic Curves
  The Addition Law. Elliptic Curves Mod n. Factoring with Elliptic Curves. Elliptic Curves in Characteristic 2. Elliptic Curve Cryptosystems. Identity-Based Encryption. Exercises. Computer Problems.
• 17 Lattice Methods
  Lattices. Lattice Reduction. An Attack on RSA. NTRU. Exercises
• 18 Error Correcting Codes
  Introduction. Error Correcting Codes. Bounds on General Codes. Linear Codes. Hamming Codes. Golay Codes. Cyclic Codes. BCH Codes. Reed-Solomon Codes. The McEliece Cryptosystem. Other Topics. Exercises. Computer Problems.
• 19 Quantum Techniques in Cryptography
  A Quantum Experiment. Quantum Key Distribution. Shor’s Algorithm. 4 Exercises.
• Mathematica Examples
• Maple Examples
• MATLAB Examples
• Further Reading
• Bibliography
• Index

Preface

This book is based on a course in cryptography at the upper level undergraduate and beginning graduate level that has been given at the University of Maryland since 1997. When designing the course, we decided on the following requirements.

• The course should be up-to-date and cover a broad selection of topics from a mathematical point of view.
• The material should be accessible to mathematically mature students having little background in number theory and computer programming.
• There should be examples involving numbers large enough to demonstrate how the algorithms really work.

We wanted to avoid concentrating solely on RSA and discrete logarithms, which would have made the course mostly a number theory course. We also did not want to teach a course on protocols and how to hack into friends' computers. That would have made the course less mathematical than desired.

There are numerous topics in cryptology that can be discussed in an introductory course. We have tried to include many of them. The chapters represent, for the most part, topics that were covered during the different semesters we taught the course. There is certainly more material here than could be treated in most one-semester courses. The first eight chapters represent the core of the material. The choice of which of the remaining chapters are used depends on the level of the students.

The chapters are numbered, thus giving them an ordering. However, except for Chapter 3 on number theory, which pervades the subject, the chapters are fairly independent of each other and can be covered in almost any reasonable order. Although we don't recommend doing so, adaring reader could possibly read Chapters 4 through 17 in reverse order, with only having to look ahead/behind a few times.

The chapters on Information Theory, Elliptic Curves, (quantum Methods, and Error Correcting Codes are somewhat more mathematical than the others. The chapter on Error Correcting Codes was included, at the suggestion of several reviewers, because courses that include introductions to both cryptology and coding theory are fairly common.

Computer examples. Suppose you want to give an example for RSA. You could choose two one-digit primes and pretend to be working with fifty-digit primes, or you could use your favorite software package to do an actual example with large primes. Or perhaps you are working with shift ciphers and are trying to decrypt a message by trying all 26 shifts of the ciphertext. This should also be done on a computer. At the end of the book are appendices containing Computer Examples written in each of Mathematica^®, Maple^®, and MATLAB^® that show how to do such calculations. These languages were chosen because they are user friendly and do not require prior programming experience. Although the course has been taught successfully without computers, these examples are an integral part of the book and should be studied, if at all possible. Not only do they contain numerical examples of how to do certain computations but also they demonstrate important ideas and issues that arise. They were placed at the end of the book because of the logistic and aesthetic problems of including extensive computer examples in three languages at the ends of chapters.

Programs available in each of the three languages can be downloaded from the Web site
www.prenhall.com/washington

In a classroom, all that is needed is a computer (with one of the languages installed) and a projector in order to produce meaningful examples as the lecture is being given. Homework problems (the Computer Problems in various chapters) based on the software allow students to play with examples individually. Of course, students having more programming background could write their own programs instead.