RSA Security 5.2.2 Elliptic Curve Diffie-Hellman Key Agreement

Chapter 3 Cryptography 77

Cryptography Overview

6. Compute an authentication tag, tag = SHA1 (x1 || M’). That is, tag is the SHA1

hash of concatenation of the x-coordinate of the secret point k1Q and the message

M’. Since tag is an SHA1 hash, tag is 20 bytes long.

7. Transmit the ciphertext c=(Q1,M’,tag). The total length of c in bytes is: 21+2 ·(the

length of a field element in bytes) + f.

Decrypting a Message Using the Private Key

A message that had been encrypted in the previous example can be decrypted using

the private key as follows:

1. Parse the received ciphertext c=(Q1,M’,tag) into its components, Q1, M’, and tag.

2. Use the private key k2 to compute the elliptic curve point S2=k2Q1. S2 is a pair

(x2,y2). If the message was transmitted correctly and encoded with the correct

public key, S2 is equal to S1.

3. To ve ri fy t ha t S2 is equal to S1, compute tag' = SHA1 (x2 || M'). If tag' is different

from tag, output an error and stop.

4. Compute a one time pad, otp’, of length f, from x2 using the key derivation

function outlined in Step 4 on page 76. Use x2 instead of x1. Since x1 = x2,

otp’=otp.

5. Compute M=otp XOR M’.

Elliptic Curve Diffie-Hellman Key Agreement

It is possible to construct a version of the Diffie-Hellman key agreement that uses

elliptic curves. (For more information on Diffie-Hellman key agreement, see “Diffie-

Hellman Public Key Agreement” on page 62.) Like Diffie-Hellman, EC Diffie-

Hellman provides for key agreement, but not encryption or authentication.

The elliptic curve Diffie-Hellman key agreement algorithm provides a method for two

parties to each compute the same secret key without exchanging secret information.

The algorithm is made up of two parts: Phase 1 and Phase 2. Before they begin, the

two parties must agree on the elliptic curve parameters: a base field, an elliptic curve

over the base field, and point P of prime order, along with its order n. See the section

“Elliptic Curve Parameters” on page 66 for details. See Figure 3-13 on page 79 for an

illustration of Elliptic Curve Diffie-Hellman key agreement.

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