1st Edition

Introduction to Cryptography with Mathematical Foundations and Computer Implementations

By Alexander Stanoyevitch Copyright 2010
    672 Pages 75 B/W Illustrations
    by Chapman & Hall

    From the exciting history of its development in ancient times to the present day, Introduction to Cryptography with Mathematical Foundations and Computer Implementations provides a focused tour of the central concepts of cryptography. Rather than present an encyclopedic treatment of topics in cryptography, it delineates cryptographic concepts in chronological order, developing the mathematics as needed.

    Written in an engaging yet rigorous style, each chapter introduces important concepts with clear definitions and theorems. Numerous examples explain key points while figures and tables help illustrate more difficult or subtle concepts. Each chapter is punctuated with "Exercises for the Reader;" complete solutions for these are included in an appendix. Carefully crafted exercise sets are also provided at the end of each chapter, and detailed solutions to most odd-numbered exercises can be found in a designated appendix. The computer implementation section at the end of every chapter guides students through the process of writing their own programs. A supporting website provides an extensive set of sample programs as well as downloadable platform-independent applet pages for some core programs and algorithms.

    As the reliance on cryptography by business, government, and industry continues and new technologies for transferring data become available, cryptography plays a permanent, important role in day-to-day operations. This self-contained sophomore-level text traces the evolution of the field, from its origins through present-day cryptosystems, including public key cryptography and elliptic curve cryptography.

    An Overview of the Subject
    Basic Concepts
    Functions
    One-to-One and Onto Functions, Bijections
    Inverse Functions
    Substitution Ciphers
    Attacks on Cryptosystems
    The Vigenère Cipher
    The Playfair Cipher
    The One-Time Pad, Perfect Secrecy

    Divisibility and Modular Arithmetic
    Divisibility
    Primes
    Greatest Common Divisors and Relatively Prime Integers
    The Division Algorithm
    The Euclidean Algorithm
    Modular Arithmetic and Congruencies
    Modular Integer Systems
    Modular Inverses
    Extended Euclidean Algorithm
    Solving Linear Congruencies
    The Chinese Remainder Theorem

    The Evolution of Codemaking until the Computer Era
    Ancient Codes
    Formal Definition of a Cryptosystem
    Affine Ciphers
    Steganography
    Nulls
    Homophones
    Composition of Functions
    Tabular Form Notation for Permutations
    The Enigma Machines
    Cycles (Cyclic Permutations)
    Dissection of the Enigma Machine into Permutations
    Special Properties of All Enigma Machines

    Matrices and the Hill Cryptosystem
    The Anatomy of a Matrix
    Matrix Addition, Subtraction, and Scalar Multiplication
    Matrix Multiplication
    Preview of the Fact That Matrix Multiplication Is Associative
    Matrix Arithmetic
    Definition of an Invertible (Square) Matrix
    The Determinant of a Square Matrix
    Inverses of 2×2 Matrices
    The Transpose of a Matrix
    Modular Integer Matrices
    The Classical Adjoint (for Matrix Inversions)
    The Hill Cryptosystem

    The Evolution of Codebreaking until the Computer Era
    Frequency Analysis Attacks
    The Demise of the Vigenère Cipher
    The Index of Coincidence
    Expected Values of the Index of Coincidence
    How Enigmas Were Attacked
    Invariance of Cycle Decomposition Form

    Representation and Arithmetic of Integers in Different Bases
    Representation of Integers in Different Bases
    Hex(adecimal) and Binary Expansions
    Arithmetic with Large Integers
    Fast Modular Exponentiation

    Block Cryptosystems and the Data Encryption Standard (DES)
    The Evolution of Computers into Cryptosystems
    DES Is Adopted to Fulfill an Important Need
    The XOR Operation
    Feistel Cryptosystems
    A Scaled-Down Version of DES
    DES
    The Fall of DES
    Triple DES
    Modes of Operation for Block Cryptosystems

    Some Number Theory and Algorithms
    The Prime Number Theorem
    Fermat’s Little Theorem
    The Euler Phi Function
    Euler’s Theorem
    Modular Orders of Invertible Modular Integers
    Primitive Roots
    Order of Powers Formula
    Prime Number Generation
    Fermat’s Primality Test
    Carmichael Numbers
    The Miller–Rabin Test
    The Miller–Rabin Test with a Factoring Enhancement
    The Pollard p – 1 Factoring Algorithm

    Public Key Cryptography
    An Informal Analogy for a Public Key Cryptosystem
    The Quest for Secure Electronic Key Exchange
    One-Way Functions
    Review of the Discrete Logarithm Problem
    The Diffie–Hellman Key Exchange
    The Quest for a Complete Public Key Cryptosystem
    The RSA Cryptosystem
    Digital Signatures and Authentication
    The El Gamal Cryptosystem
    Digital Signatures with El Gamal
    Knapsack Problems
    The Merkle–Hellman Knapsack Cryptosystem
    Government Controls on Cryptography
    A Security Guarantee for RSA

    Finite Fields in General and GF(28) in Particular
    Binary Operations
    Rings
    Fields
    Zp[X] = the Polynomials with Coefficients in Zp
    Addition and Multiplication of Polynomials in Zp[X]
    Vector Representation of Polynomials
    Zp[X] Is a Ring
    Divisibility in Zp[X]
    The Division Algorithm for Zp[X]
    Congruencies in Zp[X] Modulo a Fixed Polynomial
    Building Finite Fields from Zp[X]
    The Fields GF(24) and GF(28)
    The Euclidean Algorithm for Polynomials

    The Advanced Encryption Standard (AES) Protocol
    An Open Call for a Replacement to DES
    Nibbles
    A Scaled-Down Version of AES
    Decryption in the Scaled-Down Version of AES
    AES
    Byte Representation and Arithmetic
    The AES Encryption Algorithm
    The AES Decryption Algorithm
    Security of the AES

    Elliptic Curve Cryptography
    Elliptic Curves over the Real Numbers
    The Addition Operation for Elliptic Curves
    Groups
    Elliptic Curves over Zp
    The Variety of Sizes of Modular Elliptic Curves
    The Addition Operation for Elliptic Curves over Zp
    The Discrete Logarithm Problem on Modular Elliptic Curves
    An Elliptic Curve Version of the Diffie–Hellman Key Exchange
    Fast Integer Multiplication of Points on Modular Elliptic Curves
    Representing Plaintexts on Modular Elliptic Curves
    An Elliptic Curve Version of the El Gamal Cryptosystem
    A Factoring Algorithm Based on Elliptic Curves

    Appendix A: Sets and Basic Counting Principles
    Appendix B: Randomness and Probability
    Appendix C: Solutions to All Exercises for the Reader
    Appendix D: Answers and Brief Solutions to Selected Odd-Numbered Exercises
    Appendix E: Suggestions for Further Reading

    References

    Exercises and Computer Implementations appear at the end of each chapter.

    Biography

    Alexander Stanoyevitch is a professor at California State University–Dominguez Hills. He completed his doctorate in mathematical analysis at the University of Michigan, Ann Arbor, and has held academic positions at the University of Hawaii and the University of Guam. Dr. Stanoyevitch has taught many upper-level classes to mathematics and computer science students, has published several articles in leading mathematical journals, and has been an invited speaker at numerous lectures and conferences in the United States, Europe, and Asia. His research interests include areas of both pure and applied mathematics.

    This book is a very comprehensible introduction to cryptography. It will be very suitable for undergraduate students. There is adequate material in the book for teaching one or two courses on cryptography. The author has provided many mathematically oriented as well as computer-based exercises. I strongly recommend this book as an introductory book on cryptography for undergraduates.
    —IACR Book Reviews, April 2011

    … a particularly good entry in a crowded field. … As someone who has taught cryptography courses in the past, I was particularly impressed with the scaled-down versions of DES and AES that the author describes … . Stanoyevitch’s writing style is clear and engaging, and the book has many examples illustrating the mathematical concepts throughout. … One of the many smart decisions that the author made was to also include many computer implementations and exercises at the end of each chapter. … It is also worth noting that he has many MATLAB implementations on his website. … It is clear that Stanoyevitch designed this book to be used by students and that he has taught this type of student many times before. The book feels carefully structured in a way that builds nicely … it is definitely a solid choice and will be on the short list of books that I would recommend to a student wanting to learn about the field.
    MAA Reviews, May 2011

    I perused the structure, the writing, the pedagogical approach/layout: I can recognize a labor of pedagogical love when I see one. Certainly, the colloquial but still rigorous approach makes the concepts accessible, and the worked out solutions for the student, the much-needed and appreciated chapter on finite fields, and the division of problems into theory and programming are sensible. But it is the little thoughtful touches that make the book truly shine: the position of the notation index right on the front cover; the historical excursions as mental relief to keep students’ interest peaked; judicious use of accessible examples plus step-by-step worked out math to illustrate concepts; and whitespace in the margin for notes, the text layout with breathing room to offset the inevitable terseness of mathematical cryptology. It is apparent that Prof. Stanoyevitch put a lot of pedagogical and intellectual effort into making a textbook — a book aimed at students that makes life easier for the instructor. In addition, the book’s companion site features short MATLAB m-files and applets for quick demos. The Index of Algorithms is useful. In short, this is a very well done, thoughtful introduction to cryptography.
    —Daniel Bilar, Department of Computer Science, University of New Orleans, Louisiana, USA