Cryptographic algorithms on reconfigurable hardware / by Francisco Rodriguez-Henriquez, N.A. Saqib, A. Diaz-Perez, Cetin Kaya Koc.

Format:

Book

Author/Creator:

Rodríguez-Henríquez, Francisco.

Contributor:

Saqib, N. A. (Nazar Abbas)

Díaz-Pérez, A. (Arturo)

Koc, Cetin Kaya.

Hazel M. Hussong Fund.

Language:

English

Subjects (All):

Adaptive computing systems.

Field programmable gate arrays.

Cryptography.

Physical Description:

xxvi, 362 pages : illustrations ; 24 cm

Place of Publication:

New York : Springer, [2006]

Summary:

Cryptographic Algorithms on Reconfigurable Hardware covers the study of computational methods, computer arithmetic algorithms, and design improvement techniques needed to implement efficient cryptographic algorithms in FPGA reconfigurable hardware platforms.

The concepts and techniques reviewed in this book emphasize the practical aspects of reconfigurable hardware design, discussing the basic mathematics involved and giving a comprehensive description of state-of-the-art implementation techniques. The authors show how high-speed cryptographic algorithms can be implemented on reconfigurable hardware devices without posing prohibitive requirements for hardware resources. This material will be of interest to engineering professionals, programmers, hardware designers, and graduate students interested in the development of security and cryptographic mechanisms at a beginning/intermediate level.

Contents:

1.1 Main goals 1

1.2 Monograph Organization 3

2.2 Secret Key Cryptography 9

2.3 Hash Functions 11

2.4 Public Key Cryptography 12

2.5 Digital Signature Schemes 15

2.5.1 RSA Digital Signature 16

2.5.2 RSA Standards 17

2.5.3 DSA Digital Signature 18

2.5.4 Digital Signature with Elliptic Curves 19

2.5.5 Key Exchange 23

2.6 A Comparison of Public Key Cryptosystems 24

2.7 Cryptographic Security Strength 26

2.8 Potential Cryptographic Applications 27

2.9 Fundamental Operations for Cryptographic Algorithms 29

2.10 Design Alternatives for Implementing Cryptographic Algorithms 31

3 Reconfigurable Hardware Technology 35

3.1 Antecedents 36

3.2 Field Programmable Gate Arrays 38

3.2.1 Case of Study I: Xilinx FPGAs 39

3.2.2 Case of Study II: Altera FPGAs 44

3.3 FPGA Platforms versus ASIC and General-Purpose Processor Platforms 48

3.3.1 FPGAs versus ASICs 48

3.3.2 FPGAs versus General-Purpose Processors 49

3.4 Reconfigurable Computing Paradigm 50

3.4.1 FPGA Programming 52

3.4.2 VHSIC Hardware Description Language (VHDL) 52

3.4.3 Other Programming Models for FPGAs 53

3.5 Implementation Aspects for Reconfigurable Hardware Designs 53

3.5.1 Design Flow 53

3.5.2 Design Techniques 55

3.5.3 Strategies for Exploiting FPGA Parallelism 58

3.6 FPGA Architecture Statistics 59

3.7 Security in Reconfigurable Hardware Devices 61

4 Mathematical Background 63

4.1 Basic Concepts of the Elementary Theory of Numbers 63

4.1.1 Basic Notions 64

4.1.2 Modular Arithmetic 67

4.2 Finite Fields 70

4.2.1 Rings 70

4.2.2 Fields 70

4.2.3 Finite Fields 70

4.2.4 Binary Finite Fields 71

4.3 Elliptic curves 73

4.3.2 Elliptic Curve Operations 74

4.3.3 Elliptic Curve Scalar Multiplication 76

4.4 Elliptic Curves over GF(2m) 77

4.4.1 Point Addition 78

4.4.2 Point Doubling 78

4.4.3 Order of an Elliptic Curve 79

4.4.4 Elliptic Curve Groups and the Discrete Logarithm Problem 79

4.5 Point Representation 82

4.5.1 Projective Coordinates 83

4.5.2 Lopez-Dahab Coordinates 84

4.6 Scalar Representation 85

4.6.1 Binary Representation 85

4.6.2 Recoding Methods 85

4.6.3 [omega]-NAF Representation 87

5 Prime Finite Field Arithmetic 89

5.1 Addition Operation 90

5.1.1 Full-Adder and Half-Adder Cells 90

5.1.2 Carry Propagate Adder 91

5.1.3 Carry Completion Sensing Adder 92

5.1.4 Carry Look-Ahead Adder 94

5.1.5 Carry Save Adder 96

5.1.6 Carry Delayed Adder 97

5.2 Modular Addition Operation 98

5.2.1 Omura's Method 99

5.3 Modular Multiplication Operation 100

5.3.1 Standard Multiplication Algorithm 101

5.3.2 Squaring is Easier 104

5.3.3 Modular Reduction 105

5.3.4 Interleaving Multiplication and Reduction 108

5.3.5 Utilization of Carry Save Adders 110

5.3.6 Brickell's Method 114

5.3.7 Montgomery's Method 116

5.3.8 High-Radix Interleaving Method 123

5.3.9 High-Radix Montgomery's Method 124

5.4 Modular Exponentiation Operation 124

5.4.1 Binary Strategies 125

5.4.2 Window Strategies 126

5.4.3 Adaptive Window Strategy 129

5.4.4 RSA Exponentiation and the Chinese Remainder Theorem 132

5.4.5 Recent Prime Finite Field Arithmetic Designs on FPGAs 136

6 Binary Finite Field Arithmetic 139

6.1 Field Multiplication 139

6.1.1 Classical Multipliers and their Analysis 141

6.1.2 Binary Karatsuba-Ofman Multipliers 142

6.1.3 Squaring 151

6.1.4 Reduction 152

6.1.5 Modular Reduction with General Polynomials 156

6.1.6 Interleaving Multiplication 159

6.1.7 Matrix-Vector Multipliers 161

6.1.8 Montgomery Multiplier 164

6.1.9 A Comparison of Field Multiplier Designs 165

6.2 Field Squaring and Field Square Root for Irreducible Trinomials 166

6.2.1 Field Squaring Computation 167

6.2.2 Field Square Root Computation 168

6.3 Multiplicative Inverse 173

6.3.1 Inversion Based on the Extended Euclidean Algorithm 175

6.3.2 The IToh-Tsujii Algorithm 176

6.3.3 Addition Chains 178

6.3.4 ITMIA Algorithm 178

6.3.5 Square Root ITMIA 179

6.3.6 Extended Euclidean Algorithm versus Itoh-Tsujii Algorithm 181

6.3.7 Multiplicative Inverse FPGA Designs 183

6.4 Other Arithmetic Operations 183

6.4.1 Trace function 183

6.4.2 Solving a Quadratic Equation over GF(2m) 184

6.4.3 Exponentiation over Binary Finite Fields 185

7 Reconfigurable Hardware Implementation of Hash Functions 189

7.2 Some Famous Hash Functions 191

7.3 MD5 193

7.3.1 Message Preprocessing 194

7.3.2 MD Buffer Initialization 196

7.3.3 Main Loop 197

7.3.4 Final Transformation 198

7.4 SHA-1, SHA-256, SHA-384 and SHA-512 201

7.4.1 Message Preprocessing 202

7.4.2 Functions 204

7.4.3 SHA-1 205

7.4.4 Constants 206

7.4.5 Hash Computation 207

7.5 Hardware Architectures 210

7.5.1 Iterative Design 211

7.5.2 Pipelined Design 212

7.5.3 Unrolled Design 212

7.5.4 A Mixed Approach 213

7.6 Recent Hardware Implementations of Hash Functions 213

8 General Guidelines for Implementing Block Ciphers in FPGAs 221

8.2 Block Ciphers 222

8.2.1 General Structure of a Block Cipher 223

8.2.2 Design Principles for a Block Cipher 224

8.2.3 Useful Properties for Implementing Block Ciphers in FPGAs 227

8.3 The Data Encryption Standard 232

8.3.1 The Initial Permutation (IP[superscript -1]) 233

8.3.2 Structure of the Function f[subscript k] 234

8.3.3 Key Schedule 237

8.4 FPGA Implementation of DES Algorithm 238

8.4.1 DES Implementation on FPGAs 238

8.4.2 Design Testing and Verification 240

8.4.3 Performance Results 240

8.5 Other DES Designs 240

9 Architectural Designs For the Advanced Encryption Standard 245

9.2 The Rijndael Algorithm 247

9.2.1 Difference Between AES and Rijndael 247

9.2.2 Structure of the AES Algorithm 248

9.2.3 The Round Transformation 249

9.2.4 ByteSubstitution (BS) 249

9.2.5 ShiftRows (SR) 251

9.2.6 MixColumns (MC) 252

9.2.7 AddRoundKey (ARK) 253

9.2.8 Key Schedule 254

9.3 AES in Different Modes 254

9.3.1 CTR Mode 255

9.3.2 CCM Mode 256

9.4 Implementing AES Round Basic Transformations on FPGAs 259

9.4.1 S-Box/Inverse S-Box Implementations on FPGAs 260

9.4.2 MC/IMC Implementations on FPGA 264

9.4.3 Key Schedule Optimization 267

9.5 AES Implementations on FPGAs 268

9.5.1 Architectural Alternatives for Implementing AES 269

9.5.2 Key Schedule Algorithm Implementations 273

9.5.3 AES Encryptor Cores - Iterative and Pipeline Approaches 276

9.5.4 AES Encryptor/Decryptor Cores- Using Look-Up Table and Composite Field Approaches for S-Box 278

9.5.5 AES Encryptor/Decryptor, Encryptor, and Decryptor Cores Based on Modified MC/IMC 281

9.5.6 Review of This Chapter Designs 284

9.6 Performance 285

9.6.1 Other Designs 285

10 Elliptic Curve Cryptography 291

10.2 Hessian Form 294

10.3 Weierstrass Non-Singular Form 296

10.3.1 Projective Coordinates 296

10.3.2 The Montgomery Method 297

10.4 Parallel Strategies for Scalar Point Multiplication 300

10.5 Implementing scalar multiplication on Reconfigurable Hardware 302

10.5.1 Arithmetic-Logic Unit for Scalar Multiplication 303

10.5.2 Scalar multiplication in Hessian Form 304

10.5.3 Montgomery Point Multiplication 306

10.5.4 Implementation Summary 306

10.6 Koblitz Curves 308

10.6.1 The [tau] and [tau superscript -1] Frobenius Operators 309

10.6.2 [omega tau]NAF Scalar Multiplication in Two Phases 312

10.6.3 Hardware Implementation Considerations 313

10.7 Half-and-Add Algorithm for Scalar Multiplication 317

10.7.1 Efficient Elliptic Curve Arithmetic 318

10.7.2 Implementation 321

10.7.3 Performance Estimation 324

10.8 Performance Comparison 326.

Notes:

Includes bibliographical references and index.

Local Notes:

Acquired for the Penn Libraries with assistance from the Hazel M. Hussong Fund.

ISBN:

0387338837

9780387338835

OCLC:

77006029