RSA Security 5.2.2 Elliptic Curve Key Pair Generation

Cryptography Overview

72 RSA BSAFE Crypto-C Developer’s Guide

Representing Fields of Even Characteristic

For fields of even characteristic (fields of the form F2m), Crypto-C allows you to choose

how you want the field to be represented. The representation you choose is internal to

Crypto-C and affects how field arithmetic is performed. The choice of representation

is also one of the formal elliptic curve parameters that must be transmitted along with

the public key. Some representations lead to more efficient implementations in

hardware or software.

When we talk about representations of F2m, we use the term basis to reflect the original

mathematics underlying the construction of F2m. From our point of view, it is most

important to know that a different basis corresponds to a different representation in

Crypto-C. Crypto-C offers two types of representation for fields of even characteristic:

•Polynomial basis: this representation closely reflects how the field was originally

constructed by mathematicians. Every field of even characteristic has a

polynomial basis representation.

•Optimal normal basis (ONB): this representation is constructed to optimize certain

multiplicative operations. Not all fields have an ONB representation; it can be

constructed only for certain values of m.

The difference in the choice of basis shows up most clearly in how multiplication is

defined. For example, for any polynomial basis representation, the multiplicative

identity is represented as (000…01). For any optimal normal basis, the multiplicative

identity is (111…11).

Note: Although arithmetic looks different when you choose a different

representation, the field is still the same. Just as you can represent

“normal”arithmetic using a hexadecimal or a decimal system, you can

represent F2m inmore than one way.

Elliptic Curve Key Pair Generation

Elliptic curve parameters can be used to generate a public/private key pair. Elliptic

curve parameters can either be common to several key pairs or specific to one key

pair. The elliptic curve parameters can be public; the security of the system does not

rely on these parameters being secret.

Contents

Main Page Contents Preface xv Page Page Page Page Page Page Glossary 339 Index 349 List of Figures Page List of Tables Page Preface Whats New in Version 5.2.2? Improved performance Hardware support MultiPrime RSA Serialization for algorithm objects performing RC4, Diffie Hellman key exchange Organization of This Manual Conventions Used in This Manual Terms and Abbreviations Related Documents Page How to Contact RSA Security RSA Security Web Site Getting Support and Service SecurCare Online Technical Support Telephone Numbers Introduction The Crypto-C Toolkit Algorithms Symmetric Ciphers Message Digests Message Authentication Hardware Support Cryptographic Standards and Crypto-C PKCS Standards and Crypto-C NIST Standards and Crypto-C NIST Approval and Windows 32-bit Platforms PKCS Compared with NIST ANSI X9 Standards and Crypto-C Quick Start The Six-Step Sequence Introductory Example Step 0: Include Files Page Page Page Step 3b: Setting a Key Object Page Selecting an Algorithm Chooser Surrender Context Saving the Object State (optional) Page Page Page Page Page Putting It All Together Chapter 2 Quick Start 23 Introductory Example 24 RSA BSAFE Crypto-C Developers Guide Page Decrypting the Introductory Example Step 3a: Creating the Key Object Step 3b: Setting the Key Object Page Multiple Updates Multiple Updates 30 RSA BSAFE Crypto-C Developers Guide Page Summary of the Six Steps Step 0: Include Page Page Cryptography Cryptography Overview Symmetric-Key Cryptography Ciphers Block Ciphers Padding Ciphers in Crypto-C DES Trip le DES DESX RC2 RC5 RC6 AES Modes of Operation Four Modes Electronic Codebook (ECB) Mode Cipher Block Chaining (CBC) Mode Cipher Feedback (CFB) Mode Page Output Feedback (OFB) Mode Stream Ciphers RC4 The RC4 algorithm with MAC Message Digests Message Digests and Pseudo-Random Numbers Hash-Based Message Authentication Codes (HMAC) Password-Based Encryption Public-Key Cryptography The RSA Algorithm Modular Math Prime Numbers MultiPrime Numbers The RSA Algorithm Page Summary Security Digital Envelopes Optimal Asymmetric Encryption Padding (OAEP) Page Authentication and Digital Signatures Page Digital Signature Algorithm (DSA) The Math Digital Certificates Diffie-Hellman Public Key Agreement The Algorithm Parameter Generation Phase 1 Phase 2 The Math Security Multiple-Party Key Agreement Elliptic Curve Cryptography Elliptic Curve Parameters The Finite Field Odd Prime Fields Fields of Even Characteristic Coefficients Over an Odd Prime Field Coefficients Over a Field of Even Characteristic The Point P and its Order The Points of an Elliptic Curve The Order of an Elliptic Curve The Order of a Point A Point of Prime Order The Cofactor Summary of Elliptic Curve Terminology Representing Fields of Even Characteristic Elliptic Curve Key Pair Generation Creating the Key Pair ECDSA Signature Scheme Signing a Message Verifying a Signature The Math Elliptic Curve Authenticated Encryption Scheme (ECAES) Encrypting a Message Using the Public Key Decrypting a Message Using the Private Key Elliptic Curve Diffie-Hellman Key Agreement Phase 1 Phase 2 The Math Secret Sharing Working with Keys Key Generation Key Management Key Escrow ASCII Encoding and Decoding Applications of Cryptography Local Applications Point-to-Point Applications Client/Server Applications Peer-to-Peer Applications Choosing Algorithms Public-Key vs. Symmetric-Key Cryptography Stream vs. Block Symmetric-Key Algorithms Block Symmetric-Key Algorithms Key Agreement vs. Digital Envelopes Secret Sharing and Key Escrow Elliptic Curve Algorithms Interoperability Elliptic Curve Standards Security Considerations Handling Private Keys Temporary Buffers Pseudo-Random Numbers and Seed Generation Choosing Passwords Initialization Vectors and Salts DES Weak Keys Stream Ciphers Timing Attacks and Blinding Page Choosing Key Sizes RSA Keys Diffie-Hellman Parameters and DSA Keys RC2 Effective Key Bits RC4 Key Bits RC5 Key Bits and Rounds Triple DES Keys Page Using Crypto-C Algorithms in Crypto-C Information Formats Provided by Crypto-C Basic Algorithm Info Types BER-Based Algorithm Info Types PEM-Based Algorithm Info Types Summary of AIs Page Page Page Page Page Page Page Page Page Keys In Crypto-C Summary of KIs Page Keys In Crypto-C System Considerations In Crypto-C Algorithm Choosers An Encryption Algorithm Chooser An RSA Algorithm Chooser The Surrender Context A Sample Surrender Function Saving State When to Allocate Memory Memory-Management Routines Memory-Management Routines and Standard C Libraries Memory Allocation Binary Data BER/DER Encoding Page Page Input and Output Symmetric Block Algorithms Input constraints Output considerations The RSA Algorithm Input constraints General Considerations Key Size DES Keys RSA Keys Public Key Size Private Key Size Page Using Cryptographic Hardware Interfacing with a BHAPI Implementation Page PKCS #11 Support Using a PKCS #11 Device with Crypto-C Page Page Page Page Page Page Page Chapter 4 Using Crypto-C 143 Using Cryptographic Hardware PKCS #11 Support for DSA Key Pair Generation Chapter 4 Using Crypto-C 145 Using Cryptographic Hardware Page Advanced PKCS #11 Random Numbers Hardware Issues Page Page Non-Cryptographic Operations Message Digests Creating a Digest Page Page BER-Encoding the Digest Saving the State of a Digest Algorithm Object Saved State Page Page Chapter 5 Non-Cryptographic Operations 159 Message Digests Page Hash-Based Message Authentication Code (HMAC) Step 3a: Creating the Key Object Step 3b: Setting the Key Object Page Page Generating Random Numbers Generating Random Numbers with SHA1 Page Step 4a: The Random Seed Page Page Generating Independent Streams of Randomness Steps 4, 5, 6 Converting Data Between Binary and ASCII Encoding Binary Data To ASCII Page Decoding ASCII-Encoded Data Page Page Symmetric-Key Operations Block Ciphers DES with CBC Page Step 3a: Creating the Key Object Step 3b: Setting the Key Object Page Page The RC2 Cipher Page Step 3b: Setting the Key Object Page Page Remember to destroy all objects created and free up any memory allocated: Chapter 6 Symmetric-Key Operations 189 The RC5 Cipher Page Step 3b: Setting The Key Object Page Page Chapter 6 Symmetric-Key Operations 195 Remember to destroy all objects that you created and free up any memory that you allocated. The RC6 Cipher Step 2: Set Page Step 3b: Setting the Key Data Page 200 RSA BSAFE Crypto-C Developers Guide for the surrender context: Remember to destroy any objects that you created and to free up any memory that has The AES Cipher Step 2: Set Page Step 3b: Setting the Key Data Page Chapter 6 Symmetric-Key Operations 205 Remember to destroy any objects that you created and to free up any memory that has been allocated: Password-Based Encryption Page Step 3b: Setting The Key Object Page Page Page Page Public-Key Operations Performing RSA Operations Generating a Key Pair Page Page Page MultiPrime What is MultiPrime? How Many Primes? Sample Chapter 7 Public-Key Operations 221 MultiPrime Generating an RSA MultiPrime Key Step 1: Prepare A_RSA_MULTI_PRIME_KEY_GEN_PARAMS Structure Step 2: Set the Algorithm Object Distributing an RSA Public Key Crypto-C Format BER/DER Encoding Page RSA Public-Key Encryption Page Page RSA Private-Key Decryption Page Optimal Asymetric Encryption Padding (OAEP) Raw RSA Encryption and Decryption Page RSA Digital Signatures Page Page Page Page Page Performing DSA Operations Generating DSA Parameters Page Page Generating a DSA Key Pair DSA Signatures Page Page Page Page Page Performing Diffie-Hellman Key Agreement Generating Diffie-Hellman Parameters Page Page Page Distributing Diffie-Hellman Parameters Crypto-C Format BER Format Page Diffie-Hellman Key Agreement Step 4: Phase 1 Step 5: Phase 2 Saving the Object State Performing Elliptic Curve Operations Generating Elliptic Curve Parameters Page Page Page Retrieving Elliptic Curve Parameters Page The following procedure, 266 RSA BSAFE Crypto-C Developers Guide Page Generating an Elliptic Curve Key Pair Page Step 3: Initialize Retrieving an Elliptic Curve Key Page Generating Acceleration Tables Generating a Generic Acceleration Table Step 2a: Retrieve the elliptic curve parameters Step 2b: Format the information Page Step 5a: Allocate memory Step 5b: Build the acceleration table Generating a Public-Key Acceleration Table Step 2a: Retrieve the public key information Step 2b: Put the information retrieved in the proper format Step 5a: Allocate memory Step 5b: Build the public-key acceleration table Performing EC Diffie-Hellman Key Agreement Page Step 2b (optional): Set Acceleration Table Info Step 3: Initialize Step 4: Phase 1 Step 5: Phase 2 Performing ECDSA in Compliance with ANSI X9.62 Generating EC Parameters Generating an EC Key Pair Page Step 2b (optional): Set Acceleration Table Info Page Page Step 2b (Optional): Set Public Key Acceleration Table Info Performing ECDSA with X9.62-Compliant BER Generating EC Parameters Page Generating an EC Key Pair Page Page Page Using ECAES Using Elliptic Curve Parameters Using an EC Key Pair ECAES Public-Key Encryption Step 2b (optional) Acceleration Table Page Chapter 7 Public-Key Operations 301 ECAES Private-Key Decryption Step 4: Update Chapter 7 Public-Key Operations 303 Page Secret Sharing Operations Secret Sharing Generating Shares Page Page Page Reconstructing the Secret Page Page Page Putting It All Together: An X9.31 Example 314 RSA BSAFE Crypto-C Developers Guide The X9.31 Sample Program Generating Random Bytes 316 RSA BSAFE Crypto-C Developers Guide To create a random algorithm object and set the parameters: Providing the Seed Generating a Key Pair Chapter 9 Putting It All Together: An X9.31 Example 319 Computing a Digital Signature Page 322 RSA BSAFE Crypto-C Developers Guide Chapter 9 Putting It All Together: An X9.31 Example 323 Verifying the Signature Verifying an X9.31 RSA signature is almost identical to signing, except that you pass in Ai_SignVerify. 324 RSA BSAFE Crypto-C Developers Guide Chapter 9 Putting It All Together: An X9.31 Example 325 Surrendering Control 326 RSA BSAFE Crypto-C Developers Guide Printing the Buffer Contents The following procedure prints the current contents of the buffer. Command-Line Demos Overview of the Demos Command-Line Demo Users Guide BDEMO Starting BDEMO Specifying User Keys Using BDEMO Sign a File Create a File Envelope Verify a Signed File Open a File Envelope Generate a Key Pair BDEMODSA Running BDEMODSA Using BDEMODSA Sign a File Verify a Signed File BDEMOEC Running BDEMOEC Using BDEMOEC File Reference File Reference BSLite Page Page Page Page Page Page Page Page Page Page Page Page Index 350 RSA BSAFE Crypto-C Developers Guide Page 352 RSA BSAFE Crypto-C Developers Guide Page 354 RSA BSAFE Crypto-C Developers Guide