Cryptographic algorithms on reconfigurable hardware

Title:

Series:

Signals and communication technology

Publication Information:

New York, NY : Springer, 2006

ISBN:

9780387338835

Subject Term:

Adaptive computing systems

Field programmable gate arrays

Cryptography

Added Author:

Rodriquez-Henriquez, Francisco

Available:*

Library	Item Barcode	Call Number	Material Type	Item Category 1	Status
Searching... PSZ JB	30000010133233	QA76.9.A3 C79 2006	Open Access Book	Book	Searching... Unknown

Cryptographic solutions using software methods can be used for those security applications where data traffic is not too large and low encryption rate is tolerable. On the other hand, hardware methods offer high-speed solutions making them highly suitable for applications where data traffic is fast and large data is required to be encrypted in real time. VLSI (also known as ASIC), and FPGAs (Field Programmable Gate Arrays) are two alternatives for implementing cryptographic algorithms in hardware. FPGAs offer several benefits for cryptographic algorithm implementations over VLSI as they offer high flexibility. Due to its reconfigurable property, keys can be changed rapidly. Moreover, basic primitives in most cryptographic algorithms can efficiently be implemented in FPGAs.

Since the invention of the Data Encryption Standard (DES), some 40 years ago, a considerable amount of cryptographic algorithm implementation literature has been produced both, for software and hardware platforms. Unfortunately, virtually there exists no book explaining how the main cryptographic algorithms can be implemented on reconfigurable hardware devices.

This book will cover 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 to be reviewed in this book will make special emphasis on the practical aspects of reconfigurable hardware design, explaining the basic mathematics related and giving a comprehensive description of state-of-the-art implementation techniques. Thus, the main goal of this monograph is to show how high-speed cryptographic algorithms implementations can be achieved on reconfigurable hardware devices without posing prohibited high requirements for hardware resources.

List of Figures	p. XIII
List of Tables	p. XIX
List of Algorithms	p. XX
Acronyms	p. XXIII
Preface	p. XXV
1 Introduction	p. 1
1.1 Main goals	p. 1
1.2 Monograph Organization	p. 3
1.3 Acknowledgments	p. 4
2 A Brief Introduction to Modern Cryptography	p. 7
2.1 Introduction	p. 8
2.2 Secret Key Cryptography	p. 9
2.3 Hash Functions	p. 11
2.4 Public Key Cryptography	p. 12
2.5 Digital Signature Schemes	p. 15
2.5.1 RSA Digital Signature	p. 16
2.5.2 RSA Standards	p. 17
2.5.3 DSA Digital Signature	p. 18
2.5.4 Digital Signature with Elliptic Curves	p. 19
2.5.5 Key Exchange	p. 23
2.6 A Comparison of Public Key Cryptosystems	p. 24
2.7 Cryptographic Security Strength	p. 26
2.8 Potential Cryptographic Applications	p. 27
2.9 Fundamental Operations for Cryptographic Algorithms	p. 29
2.10 Design Alternatives for Implementing Cryptographic Algorithms	p. 31
2.11 Conclusions	p. 32
3 Reconfigurable Hardware Technology	p. 35
3.1 Antecedents	p. 36
3.2 Field Programmable Gate Arrays	p. 38
3.2.1 Case of Study I: Xilinx FPGAs	p. 39
3.2.2 Case of Study II: Altera FPGAs	p. 44
3.3 FPGA Platforms versus ASIC and General-Purpose Processor Platforms	p. 48
3.3.1 FPGAs versus ASICs	p. 48
3.3.2 FPGAs versus General-Purpose Processors	p. 49
3.4 Reconfigurable Computing Paradigm	p. 50
3.4.1 FPGA Programming	p. 52
3.4.2 VHSIC Hardware Description Language (VHDL)	p. 52
3.4.3 Other Programming Models for FPGAs	p. 53
3.5 Implementation Aspects for Reconfigurable Hardware Designs	p. 53
3.5.1 Design Flow	p. 53
3.5.2 Design Techniques	p. 55
3.5.3 Strategies for Exploiting FPGA Parallelism	p. 58
3.6 FPGA Architecture Statistics	p. 59
3.7 Security in Reconfigurable Hardware Devices	p. 61
3.8 Conclusions	p. 62
4 Mathematical Background	p. 63
4.1 Basic Concepts of the Elementary Theory of Numbers	p. 63
4.1.1 Basic Notions	p. 64
4.1.2 Modular Arithmetic	p. 67
4.2 Finite Fields	p. 70
4.2.1 Rings	p. 70
4.2.2 Fields	p. 70
4.2.3 Finite Fields	p. 70
4.2.4 Binary Finite Fields	p. 71
4.3 Elliptic curves	p. 73
4.3.1 Definition	p. 73
4.3.2 Elliptic Curve Operations	p. 74
4.3.3 Elliptic Curve Scalar Multiplication	p. 76
4.4 Elliptic Curves over GF(2m)	p. 77
4.4.1 Point Addition	p. 78
4.4.2 Point Doubling	p. 78
4.4.3 Order of an Elliptic Curve	p. 79
4.4.4 Elliptic Curve Groups and the Discrete Logarithm Problem	p. 79
4.4.5 An Example	p. 79
4.5 Point Representation	p. 82
4.5.1 Projective Coordinates	p. 83
4.5.2 Lopez-Dahab Coordinates	p. 84
4.6 Scalar Representation	p. 85
4.6.1 Binary Representation	p. 85
4.6.2 Recoding Methods	p. 85
4.6.3 [omega]-NAF Representation	p. 87
4.7 Conclusions	p. 88
5 Prime Finite Field Arithmetic	p. 89
5.1 Addition Operation	p. 90
5.1.1 Full-Adder and Half-Adder Cells	p. 90
5.1.2 Carry Propagate Adder	p. 91
5.1.3 Carry Completion Sensing Adder	p. 92
5.1.4 Carry Look-Ahead Adder	p. 94
5.1.5 Carry Save Adder	p. 96
5.1.6 Carry Delayed Adder	p. 97
5.2 Modular Addition Operation	p. 98
5.2.1 Omura's Method	p. 99
5.3 Modular Multiplication Operation	p. 100
5.3.1 Standard Multiplication Algorithm	p. 101
5.3.2 Squaring is Easier	p. 104
5.3.3 Modular Reduction	p. 105
5.3.4 Interleaving Multiplication and Reduction	p. 108
5.3.5 Utilization of Carry Save Adders	p. 110
5.3.6 Brickell's Method	p. 114
5.3.7 Montgomery's Method	p. 116
5.3.8 High-Radix Interleaving Method	p. 123
5.3.9 High-Radix Montgomery's Method	p. 124
5.4 Modular Exponentiation Operation	p. 124
5.4.1 Binary Strategies	p. 125
5.4.2 Window Strategies	p. 126
5.4.3 Adaptive Window Strategy	p. 129
5.4.4 RSA Exponentiation and the Chinese Remainder Theorem	p. 132
5.4.5 Recent Prime Finite Field Arithmetic Designs on FPGAs	p. 136
5.5 Conclusions	p. 138
6 Binary Finite Field Arithmetic	p. 139
6.1 Field Multiplication	p. 139
6.1.1 Classical Multipliers and their Analysis	p. 141
6.1.2 Binary Karatsuba-Ofman Multipliers	p. 142
6.1.3 Squaring	p. 151
6.1.4 Reduction	p. 152
6.1.5 Modular Reduction with General Polynomials	p. 156
6.1.6 Interleaving Multiplication	p. 159
6.1.7 Matrix-Vector Multipliers	p. 161
6.1.8 Montgomery Multiplier	p. 164
6.1.9 A Comparison of Field Multiplier Designs	p. 165
6.2 Field Squaring and Field Square Root for Irreducible Trinomials	p. 166
6.2.1 Field Squaring Computation	p. 167
6.2.2 Field Square Root Computation	p. 168
6.2.3 Illustrative Examples	p. 171
6.3 Multiplicative Inverse	p. 173
6.3.1 Inversion Based on the Extended Euclidean Algorithm	p. 175
6.3.2 The IToh-Tsujii Algorithm	p. 176
6.3.3 Addition Chains	p. 178
6.3.4 ITMIA Algorithm	p. 178
6.3.5 Square Root ITMIA	p. 179
6.3.6 Extended Euclidean Algorithm versus Itoh-Tsujii Algorithm	p. 181
6.3.7 Multiplicative Inverse FPGA Designs	p. 183
6.4 Other Arithmetic Operations	p. 183
6.4.1 Trace function	p. 183
6.4.2 Solving a Quadratic Equation over GF(2m)	p. 184
6.4.3 Exponentiation over Binary Finite Fields	p. 185
6.5 Conclusions	p. 186
7 Reconfigurable Hardware Implementation of Hash Functions	p. 189
7.1 Introduction	p. 189
7.2 Some Famous Hash Functions	p. 191
7.3 MD5	p. 193
7.3.1 Message Preprocessing	p. 194
7.3.2 MD Buffer Initialization	p. 196
7.3.3 Main Loop	p. 197
7.3.4 Final Transformation	p. 198
7.4 SHA-1, SHA-256, SHA-384 and SHA-512	p. 201
7.4.1 Message Preprocessing	p. 202
7.4.2 Functions	p. 204
7.4.3 SHA-1	p. 205
7.4.4 Constants	p. 206
7.4.5 Hash Computation	p. 207
7.5 Hardware Architectures	p. 210
7.5.1 Iterative Design	p. 211
7.5.2 Pipelined Design	p. 212
7.5.3 Unrolled Design	p. 212
7.5.4 A Mixed Approach	p. 213
7.6 Recent Hardware Implementations of Hash Functions	p. 213
7.7 Conclusions	p. 220
8 General Guidelines for Implementing Block Ciphers in FPGAs	p. 221
8.1 Introduction	p. 221
8.2 Block Ciphers	p. 222
8.2.1 General Structure of a Block Cipher	p. 223
8.2.2 Design Principles for a Block Cipher	p. 224
8.2.3 Useful Properties for Implementing Block Ciphers in FPGAs	p. 227
8.3 The Data Encryption Standard	p. 232
8.3.1 The Initial Permutation (IP[superscript -1])	p. 233
8.3.2 Structure of the Function f[subscript k]	p. 234
8.3.3 Key Schedule	p. 237
8.4 FPGA Implementation of DES Algorithm	p. 238
8.4.1 DES Implementation on FPGAs	p. 238
8.4.2 Design Testing and Verification	p. 240
8.4.3 Performance Results	p. 240
8.5 Other DES Designs	p. 240
8.6 Conclusions	p. 244
9 Architectural Designs For the Advanced Encryption Standard	p. 245
9.1 Introduction	p. 245
9.2 The Rijndael Algorithm	p. 247
9.2.1 Difference Between AES and Rijndael	p. 247
9.2.2 Structure of the AES Algorithm	p. 248
9.2.3 The Round Transformation	p. 249
9.2.4 ByteSubstitution (BS)	p. 249
9.2.5 ShiftRows (SR)	p. 251
9.2.6 MixColumns (MC)	p. 252
9.2.7 AddRoundKey (ARK)	p. 253
9.2.8 Key Schedule	p. 254
9.3 AES in Different Modes	p. 254
9.3.1 CTR Mode	p. 255
9.3.2 CCM Mode	p. 256
9.4 Implementing AES Round Basic Transformations on FPGAs	p. 259
9.4.1 S-Box/Inverse S-Box Implementations on FPGAs	p. 260
9.4.2 MC/IMC Implementations on FPGA	p. 264
9.4.3 Key Schedule Optimization	p. 267
9.5 AES Implementations on FPGAs	p. 268
9.5.1 Architectural Alternatives for Implementing AES	p. 269
9.5.2 Key Schedule Algorithm Implementations	p. 273
9.5.3 AES Encryptor Cores - Iterative and Pipeline Approaches	p. 276
9.5.4 AES Encryptor/Decryptor Cores- Using Look-Up Table and Composite Field Approaches for S-Box	p. 278
9.5.5 AES Encryptor/Decryptor, Encryptor, and Decryptor Cores Based on Modified MC/IMC	p. 281
9.5.6 Review of This Chapter Designs	p. 284
9.6 Performance	p. 285
9.6.1 Other Designs	p. 285
9.7 Conclusions	p. 288
10 Elliptic Curve Cryptography	p. 291
10.1 Introduction	p. 291
10.2 Hessian Form	p. 294
10.3 Weierstrass Non-Singular Form	p. 296
10.3.1 Projective Coordinates	p. 296
10.3.2 The Montgomery Method	p. 297
10.4 Parallel Strategies for Scalar Point Multiplication	p. 300
10.5 Implementing scalar multiplication on Reconfigurable Hardware	p. 302
10.5.1 Arithmetic-Logic Unit for Scalar Multiplication	p. 303
10.5.2 Scalar multiplication in Hessian Form	p. 304
10.5.3 Montgomery Point Multiplication	p. 306
10.5.4 Implementation Summary	p. 306
10.6 Koblitz Curves	p. 308
10.6.1 The [tau] and [tau superscript -1] Frobenius Operators	p. 309
10.6.2 [omega tau]NAF Scalar Multiplication in Two Phases	p. 312
10.6.3 Hardware Implementation Considerations	p. 313
10.7 Half-and-Add Algorithm for Scalar Multiplication	p. 317
10.7.1 Efficient Elliptic Curve Arithmetic	p. 318
10.7.2 Implementation	p. 321
10.7.3 Performance Estimation	p. 324
10.8 Performance Comparison	p. 326
10.9 Conclusions	p. 328
References	p. 329
Index	p. 359

Available:*

On Order

Summary

Summary

Table of Contents