1st Edition
Introduction to Cryptography with Open-Source Software
Once the privilege of a secret few, cryptography is now taught at universities around the world. Introduction to Cryptography with Open-Source Software illustrates algorithms and cryptosystems using examples and the open-source computer algebra system of Sage. The author, a noted educator in the field, provides a highly practical learning experience by progressing at a gentle pace, keeping mathematics at a manageable level, and including numerous end-of-chapter exercises.
Focusing on the cryptosystems themselves rather than the means of breaking them, the book first explores when and how the methods of modern cryptography can be used and misused. It then presents number theory and the algorithms and methods that make up the basis of cryptography today. After a brief review of "classical" cryptography, the book introduces information theory and examines the public-key cryptosystems of RSA and Rabin’s cryptosystem. Other public-key systems studied include the El Gamal cryptosystem, systems based on knapsack problems, and algorithms for creating digital signature schemes.
The second half of the text moves on to consider bit-oriented secret-key, or symmetric, systems suitable for encrypting large amounts of data. The author describes block ciphers (including the Data Encryption Standard), cryptographic hash functions, finite fields, the Advanced Encryption Standard, cryptosystems based on elliptical curves, random number generation, and stream ciphers. The book concludes with a look at examples and applications of modern cryptographic systems, such as multi-party computation, zero-knowledge proofs, oblivious transfer, and voting protocols.
Introduction to Cryptography
Hiding information: confidentiality
Some basic definitions
Attacks on a cryptosystem
Some cryptographic problems
Cryptographic protocols
Some simple ciphers
Cryptography and computer security
Basic Number Theory
Introduction
Some basic definitions
Some number theoretic calculations
Primality testing
Classical Cryptosystems
Introduction
The Caesar cipher
Translation ciphers
Transposition ciphers
The Vigenère cipher
The one-time pad
Permutation ciphers
Matrix ciphers
Introduction to Information Theory
Entropy and uncertainty
Perfect secrecy
Estimating the entropy of English
Unicity distance
Public-Key Cryptosystems Based on Factoring
Introduction
The RSA cryptosystem
Attacks against RSA
RSA in Sage
Rabin’s cryptosystem
Rabin’s cryptosystem in Sage
Some notes on security
Factoring
Public-Key Cryptosystems Based on Logarithms and Knapsacks
El Gamal’s cryptosystem
El Gamal in Sage
Computing discrete logarithms
Diffie-Hellman key exchange
Knapsack cryptosystems
Breaking the knapsack
Digital Signatures
Introduction
RSA signature scheme
Rabin digital signatures
The El Gamal digital signature scheme
The Digital Signature Standard
Block Ciphers and the Data Encryption Standard
Block ciphers
Some definitions
Substitution/permutation ciphers
Modes of encryption
Exploring modes of encryption
The Data Encryption Standard (DES)
Feistel ciphers
Simplified DES: sDES
The DES algorithm
Security of S-boxes
Security of DES
Using DES
Experimenting with DES
Lightweight ciphers
Finite Fields
Groups and rings
Introduction to fields
Fundamental algebra of finite fields
Polynomials mod 2
A field of order 8
Other fields GF(2n)
Multiplication and inversion
Multiplication without power tables
The Advanced Encryption Standard
Introduction and some history
Basic structure
The layers in detail
Decryption
Experimenting with AES
A simplified Rijndael
Security of the AES
Hash Functions
Uses of hash functions
Security of hash functions
Constructing a hash function
Provably secure hash functions
New hash functions
Message authentication codes
Using a MAC
Elliptic Curves and Cryptosystems
Basic definitions
The group on an elliptic curve
Background and history
Multiplication
Elliptic curve cryptosystems
Elliptic curve signature schemes
Elliptic curves over binary fields
Pairing based cryptography
Exploring pairings in Sage
Random Numbers and Stream Ciphers
Introduction
Pseudo-random number generators
Some cryptographically strong generators
The shrinking generator
ISAAC and Fortuna
Stream ciphers
RC4
The Blum-Goldwasser cryptosystem
Advanced Applications and Protocols
Secure multi-party computation
Zero knowledge proofs
Oblivious transfer
Digital cash
Voting protocols
Appendix A: Introduction to Sage
Appendix B: Advanced Computational Number Theory
Bibliography
Index
Exercises appear at the end of each chapter.
Biography
Alasdair McAndrew is a senior lecturer in the School of Engineering and Science at Victoria University in Melbourne, Australia.
"This very well-written book is recommended to graduate or final-year undergraduate students intended to start research work on both theoretical and experimental cryptography. Most of the cryptographic protocols are illustrated by various examples and implemented using the open-source algebra software Sage. The book provides a rigorous introduction to the mathematics used in cryptography and covers almost all modern practical cryptosystems. Also, the book is certainly a valuable resource for practitioners looking for experimental cryptography with a computer algebra system."
—Abderrahmane Nitaj (LMNO, Université de Caen Basse Normandie), IACR book reviews, February 2014"It would make a great first course in cryptography but it is also easy enough to read to make it suitable for solitary study. … Overall this is an excellent book. It is far from the theorem-proof format and it does try to explain the ideas and motivate the reader. The pattern of mixing some theory followed by some practice is good at keeping the less theory-minded reader rolling along as the need for the theory becomes all too apparent. … this is a really good book. If you want to master cryptography, this is a great place to start."
—Mike James, IProgrammer, August 2011