Cryptography Arithmetic: Algorithms and Hardware Architectures

✍ Scribed by Amos R. Omondi

• Publisher: Springer-Nature New York Inc
• Year: 2020
• Tongue: English
• Leaves: 338
• Series: Advances in Information Security
• Edition: 1
• Category: Library

✦ Synopsis

Modern cryptosystems, used in numerous applications that require secrecy or privacy - electronic mail, financial transactions, medical-record keeping, government affairs, social media etc. - are based on sophisticated mathematics and algorithms that in implementation involve much computer arithmetic. And for speed it is necessary that the arithmetic be realized at the hardware (chip) level. This book is an introduction to the implementation of cryptosystems at that level.

The aforementioned arithmetic is mostly the arithmetic of finite fields, and the book is essentially one on the arithmetic of prime fields and binary fields in the context of cryptography. The book has three main parts. The first part is on generic algorithms and hardware architectures for the basic arithmetic operations: addition, subtraction, multiplication, and division. The second part is on the arithmetic of prime fields. And the third part is on the arithmetic of binary fields. The mathematical fundamentals necessary for the latter two parts are included, as are descriptions of various types of cryptosystems, to provide appropriate context.

This book is intended for advanced-level students in Computer Science, Computer Engineering, and Electrical and Electronic Engineering. Practitioners too will find it useful, as will those with a general interest in "hard" applications of mathematics.

✦ Table of Contents

Preface
Acknowledgements
Contents
Part I
1 Basic Computer Arithmetic
1.1 Addition
1.1.1 Serial
1.1.2 Carry-Ripple
1.1.3 Parallel-Prefix
1.1.4 Carry-Select
1.1.5 High Precision
1.1.6 Signed Numbers and Subtraction
Ones'-Complement
Two's Complement
Subtraction
1.2 Multiplication
1.2.1 Sequential
1.2.2 High Radix
1.2.3 Parallel and Sequential-Parallel
1.2.4 High Precision
1.2.5 Signed Numbers
1.2.6 Squaring
1.3 Division
Signed Operands
References
Part II
2 Mathematical Fundamentals I: Number Theory
2.1 Congruences
2.2 Modular-Arithmetic Operations
2.2.1 Addition, Subtraction, and Multiplication
2.2.2 Division
2.3 Generators and Primitive Roots
Discrete Logarithm Problem
2.4 Quadratic Residues and Square Roots
Quadratic Residuosity Problem
2.5 The Chinese Remainder Theorem
2.6 Residue Number Systems
References
3 Modular-Arithmetic Cryptosystems
3.1 Message Encryption
3.1.1 RSA Algorithm
3.1.2 Rabin Algorithm
3.1.3 El-Gamal Algorithm
3.1.4 Massey-Omura Algorithm
3.1.5 Goldwasser-Micali Algorithm
3.2 Key Agreement
3.3 Digital Signatures
3.3.1 El-Gamal Algorithm
3.3.2 NIST Algorithm
References
4 Modular Reduction
4.1 Barrett Reduction
4.1.1 Basic Algorithm
4.1.2 Extension of Basic Algorithm
4.1.3 Implementation
4.2 Montgomery Reduction
4.2.1 Algorithm
4.2.2 Implementation
4.3 Lookup-Table Reduction
4.4 Special-Moduli Reduction
Implementation
References
5 Modular Addition and Multiplication
5.1 Addition
5.1.1 Generic Structures
5.1.2 Special-Moduli
5.1.3 Subtraction
Special Moduli
5.2 Multiplication
5.2.1 Multiplication with Direct Reduction
5.2.2 Multiplication with Barrett Reduction
5.2.3 Multiplication with Montgomery Reduction
5.2.4 Multiplication with Special Moduli
References
6 Modular Exponentiation, Inversion, and Division
6.1 Exponentiation
Exponentiation with Direct Reduction
Exponentiation with Montgomery Reduction
6.2 Inversion and Division
References
Part III
7 Mathematical Fundamentals II: Abstract Algebra
7.1 Groups and Fields
7.1.1 Groups
Discrete Logarithm Problem
7.1.2 Fields
7.2 Ordinary Polynomial Arithmetic
7.3 Polynomial Arithmetic Over Finite Fields
7.4 Construction of GF(pm)
References
8 Elliptic-Curve Basics
8.1 Basic Curves
8.1.1 Point Addition: Geometric Interpretation
8.1.2 Point Addition and Multiplication: Algebraic Interpretation
8.2 Elliptic Curves Over Finite Fields
8.2.1 y2 = x3 + ax + b Over GF(p)
8.2.2 y2 + xy = x3 + ax + b Over GF(2m)
8.3 Point-Multiplication Implementation
8.4 Projective Coordinates
References
9 Elliptic-Curve Cryptosystems
9.1 Message Encryption
9.1.1 El-Gamal System
9.1.2 Massey-Omura System
9.1.3 Menezes-Vanstone System
9.2 Key Agreement
9.2.1 Diffie-Hellman System
9.2.2 Matsumoto-Takashima-Imai System
9.2.3 Menezes-Qu-Vanstone System
9.3 Digital Signatures
9.4 Message Embedding
References
10 Polynomial-Basis Arithmetic
10.1 Addition and Subtraction
10.2 Multiplication and Squaring
10.2.1 Direct Multiplication
10.2.2 Montgomery Multiplication and Squaring
10.3 Reduction
10.4 Exponentiation, Inversion, and Division
References
11 Normal-Basis Arithmetic
11.1 Addition, Subtraction, and Squaring
11.2 Multiplication
Implementation
11.3 Exponentiation, Inversion, and Division
References
A Mathematical Proofs
A.1 Part II of Main Text
A.2 Part III of Main Text
References
Index