Cryptography Arithmetic: Algorithms and Hardware Architectures

Description

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. 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