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.

Alasdair McAndrew is a senior lecturer in the School of Engineering and Science at Victoria University in Melbourne, Australia.

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.