1st Edition

Introduction to Cryptography with Open-Source Software

By Alasdair McAndrew Copyright 2011
    462 Pages 58 B/W Illustrations
    by CRC Press

    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