O'Reilly logo

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

BigNum Math: Implementing Cryptographic Multiple Precision Arithmetic

BigNum Math: Implementing Cryptographic Multiple Precision Arithmetic

by Tom St Denis
Publisher: Syngress
Release Date: August 2006
ISBN: 9781597491129
View table of contents
Start reading

Book Description

Implementing cryptography requires integers of significant magnitude to resist cryptanalytic attacks. Modern programming languages only provide support for integers which are relatively small and single precision. The purpose of this text is to instruct the reader regarding how to implement efficient multiple precision algorithms.

Bignum math is the backbone of modern computer security algorithms. It is the ability to work with hundred-digit numbers efficiently using techniques that are both elegant and occasionally bizarre. This book introduces the reader to the concept of bignum algorithms and proceeds to build an entire library of functionality from the ground up. Through the use of theory, pseudo-code and actual fielded C source code the book explains each and every algorithm that goes into a modern bignum library. Excellent for the student as a learning tool and practitioner as a reference alike BigNum Math is for anyone with a background in computer science who has taken introductory level mathematic courses. The text is for students learning mathematics and cryptography as well as the practioner who needs a reference for any of the algorithms documented within.

* Complete coverage of Karatsuba Multiplication, the Barrett Algorithm, Toom-Cook 3-Way Multiplication, and More

* Tom St Denis is the developer of the industry standard cryptographic suite of tools called LibTom.

* This book provides step-by-step exercises to enforce concepts

Table of Contents

  1. Cover
  2. Title page
  3. Table of Contents
  4. Copyright
  5. List of Figures
  6. Preface
  7. Chapter 1: Introduction
    1. 1.1 Multiple Precision Arithmetic
    2. 1.2 Purpose of This Text
    3. 1.3 Discussion and Notation
    4. 1.4 Exercises
    5. 1.5 Introduction to LibTomMath
    6. 1.6 Choice of LibTomMath
  8. Chapter 2: Getting Started
    1. 2.1 Library Basics
    2. 2.2 What Is a Multiple Precision Integer?
    3. 2.3 Argument Passing
    4. 2.4 Return Values
    5. 2.5 Initialization and Clearing
    6. 2.6 Maintenance Algorithms
    7. 2.6.1 Augmenting an mp_int’s Precision
    8. 2.6.2 Initializing Variable Precision mp_ints
  9. Chapter 3: Basic Operations
    1. 3.1 Introduction
    2. 3.2 Assigning Values to mp_int Structures
    3. 3.3 Zeroing an Integer
    4. 3.4 Sign Manipulation
    5. 3.5 Small Constants
    6. 3.6 Comparisons
  10. Chapter 4: Basic Arithmetic
    1. 4.1 Introduction
    2. 4.2 Addition and Subtraction
    3. 4.3 Bit and Digit Shifting
    4. 4.4 Polynomial Basis Operations
    5. 4.5 Powers of Two
  11. Chapter 5: Multiplication and Squaring
    1. 5.1 The Multipliers
    2. 5.2 Multiplication
    3. 5.3 Squaring
  12. Chapter 6: Modular Reduction
    1. 6.1 Basics of Modular Reduction
    2. 6.3 The Montgomery Reduction
    3. 6.4 The Diminished Radix Algorithm
    4. 6.5 Algorithm Comparison
  13. Chapter 7: Exponentiation
    1. 7.1 Exponentiation Basics
    2. 7.2 k–ary Exponentiation
    3. 7.3 Modular Exponentiation
    4. 7.4 Quick Power of Two
  14. Chapter 8: Higher Level Algorithms
    1. 8.1 Integer Division with Remainder
    2. 1.1 Single Digit Helpers
    3. 8.3 Random Number Generation
    4. 8.4 Formatted Representations
  15. Chapter 9: Number Theoretic Algorithms
    1. 9.1 Greatest Common Divisor
    2. 9.1.1 Complete Greatest Common Divisor
    3. 9.2 Least Common Multiple
    4. 9.3 Jacobi Symbol Computation
    5. 9.4 Modular Inverse
    6. 9.5 Primality Tests
  16. Bibliography
  17. Index