BigNum Math: Implementing Cryptographic Multiple Precision ArithmeticBy
- Tom St Denis, senior software developer and cryptographer for the Advanced Micro Devices Corporation.
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.
Any programmer implementing public-key cryptography algorithms needs to grasp BigNum Math. 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.
Published: August 2006
- Introduction 11.1 Multiple Precision Arithmetic1.1.1 What is Multiple Precision Arithmetic? 1.1.2 The Need for Multiple Precision Arithmetic 1.1.3 Benefits of Multiple Precision Arithmetic1.2 Purpose of This Text1.3 Discussion and Notation1.3.1 Notation 1.3.2 Precision Notation 1.3.3 Algorithm Inputs and Outputs 1.3.4 Mathematical Expressions1.4 Exercises1.5 Introduction to LibTomMath 1.5.1 What is LibTomMath? 1.5.2 Goals of LibTomMath 1.6 Choice of LibTomMath1.6.1 Code Base1.6.3 Optimizations1.6.4 Portability and Stability 1.6.5 Choice2 Getting Started 132.1 Library Basics2.2 What is a Multiple Precision Integer?2.2.1 The mp int Structure2.3 Argument Passing 2.5 Initialization and Clearing2.5.1 Initializing an mp int 2.5.2 Clearing an mp int2.6 Maintenance Algorithms2.6.1 Augmenting an mp ints Precision2.6.2 Initializing Variable Precision mp ints 2.6.3 Multiple Integer Initializations and Clearings 2.6.4 Clamping Excess Digit3 Basic Operations 353.1 Introduction 3.2 Assigning Values to mp int Structures3.2.1 Copying an mp int 3.3 Zeroing an Integer .3.4 Sign Manipulation 3.4.1 Absolute Value 3.4.2 Integer Negation3.5.1 Setting Small Constants .3.5.2 Setting Large Constants .3.6 Comparisons .3.6.1 Unsigned Comparisions 3.6.2 Signed Comparisons4 Basic Arithmetic 534.1 Introduction 4.2.2 Low Level Subtraction 4.2.4 High Level Subtractio4.3 Bit and Digit Shifting4.3.2 Division by Two4.4 Polynomial Basis Operation4.4.1 Multiplication by x .4.4.2 Division by x 4.5 Powers of Two 4.5.1 Multiplication by Power of Two4.5.2 Division by Power of Two4.5.3 Remainder of Division by Power of Two5 Multiplication and Squaring 915.1 The Multipliers5.2 Multiplication 5.2.1 The Baseline Multiplication 5.2.2 Faster Multiplication by the Comba Method5.2.3 Polynomial Basis Multiplication5.2.5 Toom-Cook 3-Way Multiplication 5.2.6 Signed Multiplication 5.3 Squaring5.3.1 The Baseline Squaring Algorithm5.3.2 Faster Squaring by the Comba Method 5.3.3 Polynomial Basis Squaring5.3.4 Karatsuba Squaring5.3.5 Toom-Cook Squaring 5.3.6 High Level Squaring6.2 The Barrett Reduction6.2.1 Fixed Point Arithmetic . .6.2.5 The Barrett Algorithm6.2.6 The Barrett Setup Algorithm6.3 The Montgomery Reduction .6.3.1 Digit Based Montgomery Reduction6.3.2 Baseline Montgomery Reduction6.3.3 Faster Comba Montgomery Reduction 6.3.4 Montgomery Setup 6.4 The Diminished Radix Algorithm6.4.1 Choice of Moduli6.4.2 Choice of k6.4.3 Restricted Diminished Radix Reduction 6.4.4 Unrestricted Diminished Radix Reduction6.5 Algorithm Comparison .7 Exponentiation 1877.1 Exponentiation Basics7.1.1 Single Digit Exponentiation7.2.1 Optimal Values of k 7.2.2 Sliding-Window Exponentiation7.3 Modular Exponentiation7.3.1 Barrett Modular Exponentiation 7.4 Quick Power of Two8 Higher Level Algorithms 2118.1 Integer Division with Remainde8.1.1 Quotient Estimation8.1.2 Normalized Integers8.1.3 Radix-ß Division with Remainder 8.2 Single Digit Helpers 8.2.2 Single Digit Multiplication8.2.3 Single Digit Division8.2.4 Single Digit Root Extraction 8.3 Random Number Generation 8.4 Formatted Representations 8.4.1 Reading Radix-n Input 8.4.2 Generating Radix-n Output 9 Number Theoretic Algorithms 9.1 Greatest Common Divisor 9.2 Least Common Multiple9.3 Jacobi Symbol Computation9.3.1 Jacobi Symbol 9.4 Modular Inverse 9.4.1 General Case9.5 Primality Tests 9.5.2 The Fermat Test 9.5.3 The Miller-Rabin Test