Elliptic Curve Diffie-Hellman Key Agreement | RSA Security 5.2.2

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

C h a p t e r 3 C r y p t o g r a p h y

7 7

Image 99

RSA Security 5.2.2 manual Elliptic Curve Diffie-Hellman Key Agreement, Decrypting a Message Using the Private Key

Contents

Cryptographic Components for C Crypto-C Limit distribution of this document to trusted personnel TrademarksLicense agreement Distribution Contents Cryptography Quick Start N t e n t s Algorithms in Crypto-C Using Crypto-C 101 Saved State Non-Cryptographic Operations 151 Public-Key Operations 213 Symmetric-Key Operations 177 Putting It All Together An X9.31 Example Secret Sharing Operations 305 Glossary 339 Index 349 Appendix a Command-Line Demos 327 List of Figures A B S a F E C r y p t o C D e v e l o p e r ’s G u i d e List of Tables A B S a F E C r y p t o C D e v e l o p e r ’s G u i d e Preface MultiPrime RSA What’s New in Version 5.2.2?Improved performance Hardware support E f a c e Organization of This ManualAdvanced Encryption Standard AES Organization of This Manual Crypto-C procedures to use with algorithm object Conventions Used in This ManualConventions Used in This Manual Terms and Abbreviations Terms and Abbreviations Related Documents Related DocumentsA B S a F E C r y p t o C D e v e l o p e r ’s G u i d e Http//stdsbbs.ieee.org/groups/1363/index.html Ieee Standard Specifications for Public-Key Cryptography on You can get technical support as follows How to Contact RSA SecurityRSA Security Web Site Getting Support and Service How to Contact RSA Security Introduction Algorithms Crypto-C Toolkit Secret Sharing Public-Key AlgorithmsDigital Signatures Elliptic Curve Public-Key Algorithms Nist Approval and Windows 32-bit Platforms Cryptographic Standards and Crypto-CPkcs Standards and Crypto-C Nist Standards and Crypto-C Nist Approval and Windows NT Platforms Pkcs Compared with Nist Ansi X9 Standards and Crypto-C Quick Start Six-Step Sequence Six-Step Sequence Introductory Example Introductory ExampleInclude Files Creating an Algorithm Object #define Nullptr POINTER0 Where Pointer is defined in aglobal.hNullptr is also defined in aglobal.h Typedef unsigned char *POINTER Setting the Algorithm Object Balgorithmobj algorithmObject Algorithm objectAlgorithm information Break Init Setting a Key Object Creating a Key ObjectFor our example, we use Key information Int BSetKeyInfo Now we can complete the call to BSetKeyInfo Selecting an Algorithm Chooser We can now complete our call to BEncryptInit UpdateSaving the Object State optional Surrender Context Input data Output data bufferUnsigned int Length of output data Unsigned int outputLenUpdate For now, we declareUnsigned char *encryptedData = Nullptr Final If status = BEncryptUpdate Asurrenderctx *surrenderContext Surrender context Destroy Pointer block For our example, we use the followingPointer to key object Balgorithmobj * algorithmObject If rc4KeyItem.data != Nullptr Putting It All TogetherFor this example, call Tfree as follows Tfree encryptedData Init If status = BEncryptInit Introductory Example EncryptedData = Nullptr End main If encryptedData != Nullptr First create the algorithm object Decrypting the Introductory ExampleCreating the Key Object Decrypting the Introductory Example Setting the Key Object DecryptedData = Nullptr Always destroy objects when you no longer need them Multiple Updates Multiple Updates Break End while Updatesize Multiple Updates Set Summary of the Six StepsInclude Create Final Page Cryptography Cryptography Overview Cryptography OverviewSymmetric-Key Cryptography Ciphers Crypto-C implements the following block ciphers Block CiphersPadding Ciphers in Crypto-C 2Triple DES Encryption as Implemented in Crypto-C Triple DES RC5 RC6 Four Modes Modes of Operation 3Electronic Codebook ECB Mode Electronic Codebook ECB Mode Cipher Feedback CFB Mode Cipher Block Chaining CBC Mode 5Cipher Feedback CFB Mode Output Feedback OFB Mode Stream Ciphers 6Output Feedback Mode OFB RC4 algorithm with MAC Message Digests Message Digests and Pseudo-Random Numbers Hash-Based Message Authentication Codes Hmac Password-Based Encryption Public-Key Cryptography 8DES Key and IV Generation for Password Based Encryption 9Public-Key Cryptography RSA Algorithm RSA Algorithm Modular MathPrime Numbers MultiPrime Numbers Cryptography Overview 1Calculation of 827 mod SummarySecurity Calculation is shown in Table Optimal Asymmetric Encryption Padding Oaep Digital Envelopes 10Digital Envelope Authentication and Digital Signatures Cryptography Overview 11RSA Digital Signature Digital Signature Algorithm DSA Math Digital Certificates Algorithm Diffie-Hellman Public Key Agreement Phase PhaseParameter Generation Math Multiple-Party Key Agreement Elliptic Curve Cryptography Finite Field Elliptic Curve Parameters Odd Prime Fields Fields of Even Characteristic = 0·I ≡ 2·2m-1·Imod2m Coefficients Over an Odd Prime Field Elliptic curve parameters Coefficients Over a Field of Even CharacteristicPoint P and its Order Points of an Elliptic Curve Is written EFq Order of an Elliptic CurveOrder of a Point Point of Prime Order 2Elliptic Curve Parameters Summary of Elliptic Curve TerminologyCofactor Order n of P Is sometimes called the base point Elliptic Curve Key Pair Generation Representing Fields of Even Characteristic Ecdsa Signature Scheme Creating the Key PairSigning a Message Math Verifying a Signature Elliptic Curve Authenticated Encryption Scheme Ecaes Recall that Q = dP, soNow recall that s = k-1e+dr mod n, so Encrypting a Message Using the Public Key Elliptic Curve Diffie-Hellman Key Agreement Decrypting a Message Using the Private Key Phase 13Elliptic Curve Diffie-Hellman Key Agreement First coordinate of S, xS, is their agreed-upon secret key Secret Sharing Key Generation Working with Keys Key Escrow Key Management Applications of Cryptography Applications of CryptographyAscii Encoding and Decoding Local Applications Point-to-Point Applications Client/Server Applications Peer-to-Peer Applications Choosing Algorithms Choosing AlgorithmsPublic-Key vs. Symmetric-Key Cryptography Stream vs. Block Symmetric-Key Algorithms Key Agreement vs. Digital Envelopes Block Symmetric-Key Algorithms Elliptic Curve Algorithms Secret Sharing and Key Escrow Interoperability Security Considerations Security ConsiderationsHandling Private Keys Elliptic Curve Standards Pseudo-Random Numbers and Seed Generation Temporary Buffers Choosing Passwords Initialization Vectors and Salts DES Weak Keys3DES Weak and Semi-Weak Keys Timing Attacks and Blinding Stream Ciphers = mre mod n Pick a random value r and compute MD5p padP MD5q padQ m Choosing Key Sizes 4Summary of Recommended Key Sizes RSA Keys RC5 Key Bits and Rounds Diffie-Hellman Parameters and DSA KeysRC2 Effective Key Bits RC4 Key Bits Elliptic Curve Keys Algorithms in Crypto-C Using Crypto-C Algorithms in Crypto-C Information Formats Provided by Crypto-CBasic Algorithm Info Types BER-Based Algorithm Info Types 1Message Digests Summary of AIsPEM-Based Algorithm Info Types BSAFE1 Algorithm Info Types 5Symmetric Stream Ciphers Algorithms in Crypto-C 2Message Authentication3ASCII Encoding 4Pseudo-Random Number Generation 6Symmetric Block Ciphers Algorithms in Crypto-C 5Symmetric Stream Ciphers RC2 Algorithms in Crypto-C 6Symmetric Block Ciphers Key Generation 7RSA Public-Key Cryptography Oaep Algorithms in Crypto-C 7RSA Public-Key Cryptography Digital Signatures 8DSA Public-Key Cryptography 10Elliptic Curve Public-Key Cryptography Algorithms in Crypto-C 9Diffie-Hellman Key Agreement 10 Elliptic Curve Public-Key Cryptography 11Bloom-Shamir Secret Sharing12Hardware Interface Algorithm Info Type Algorithms in Crypto-C 13Advanced Encryption Standard AES 15Block Cipher Keys Keys In Crypto-CSummary of KIs Keys In Crypto-C Keys In Crypto-C 15Block Cipher Keys 16RSA Public and Private Keys17DSA Public and Private Keys Keys In Crypto-C 18Elliptic Curve Keys System Considerations In Crypto-C System Considerations In Crypto-CAlgorithm Choosers An Encryption Algorithm Chooser An RSA Algorithm Chooser Description of AIX962RandomV0 instead of AISHA1Random Surrender Context Int *Surrender Pointer handle Sample Surrender FunctionAlso gives the form that a surrender function must have Reserved for future use Saving State When to Allocate Memory Tmalloc Trealloc Tfree Tmemset Tmemcpy Tmemmove Tmemcmp Memory-Management RoutinesMemory-Management Routines and Standard C Libraries Crypto-C uses the following memory-management routines BER/DER Encoding Memory AllocationBinary Data Typedef struct unsigned char *data unsigned int len System Considerations In Crypto-C Output considerations Input and OutputSymmetric Block Algorithms Input constraints 20Input Limits for RSA Pkcs Encryption General Considerations Key Size DES KeysPublic Key Size Private Key Size 00 C2 58 60 B1 C2 58 60 B1 Using Cryptographic Hardware Using Cryptographic HardwareInterfacing with a Bhapi Implementation 2Algorithm Object in a Hardware Implementation Pkcs #11 Support Using a Pkcs #11 Device with Crypto-C Using Cryptographic Hardware Balgorithmmethod *RSASIGNHWCHOOSER = &AMMD5 Using Cryptographic Hardware Tfprivate KeypairGenParams.privateKeyAttributes.tokenFlag = Now generate Using Cryptographic Hardware Using Cryptographic Hardware Return Behardware Pkcs #11 Support for DSA Key Pair Generation Balgorithmmethod *DSAKEYGENCHOOSER = &AMDSAKEYGEN POINTER&pubKeyData-params P11KeyGenParams.privateKeyAttributes.keyUsage = 00 00 00 66 a9 47 2d 80 5a Advanced Pkcs #11For an RSA private key, it would be this Digest CKBYTEPTRseedBuffer, CKULONGseedLen Hardware IssuesRandom Numbers Ckrv rv Rv = Using Cryptographic Hardware Page Non-Cryptographic Operations Example in this section corresponds to the file mdigest.c Message DigestsCreating a Digest Message Digests If status = BDigestInit If status = BDigestUpdate Your call will be the following#define Digestlen BER-Encoding the Digest Remember to destroy all objects when you are done with them Saving the State of a Digest Algorithm Object Saved StateFollowing example BER-encodes the preceeding sample digest Item stateInfo = Null Message Digests Status = Rsademoealloc break 1Code Sample DigestDataSavedState Message Digests Hash-Based Message Authentication Code Hash-Based Message Authentication Code Hmac Hash-Based Message Authentication Code Hmac Generate a random 24-byte key using KI24ByteCreate the key object RandomAlgorithm, keyData, KEYSIZE, Asurrenderctx *NULLPTR != Unsigned char *digestedData unsigned int digestedDataLen Generating Random Numbers Generating Random Numbers with SHA1Generating Random Numbers Setting The Algorithm Object Random Seed Unsigned char *gets char *randomSeed != 0 break Puts Enter a random seed if status = If status = BGenerateRandomBytes Generate Additional seeding Generating Independent Streams of RandomnessThis step is identical to the previous example Typedef struct Steps 4, 5 These steps are identical to the previous exampleItem randomSeed AX931RANDOMPARAMS x931Params Converting Data Between Binary Encoding Binary Data To AsciiConverting Data Between Binary and Ascii If status = BEncodeInit asciiEncoder != 0 break BDestroyAlgorithmObject &asciiEncoder Tfree asciiEncoding Decoding ASCII-Encoded Data If status = binaryDecoding == Nullptr != 0 break If status = BDecodeInit asciiDecoder != 0 break BDestroyAlgorithmObject &asciiDecoder Tfree binaryDecoding Symmetric-Key Operations Example in this section corresponds to the file descbc.c Block CiphersDES with CBC Block Ciphers For new padding schemes Examples include des, rc5RC5 parameters Points at init vector Item Call BGenerateRandomBytes Now set up the Bblkcipherwfeedbackparams structure Format of info supplied to BSetKeyInfo Depends on cipher type, as follows Unsigned int outputBufferSize Decrypting RC2 Cipher Now you can set your algorithm object as follows Init If rc2KeyItem.data != Nullptr Use a random number generator to come up with 24 bytes Update EncryptedData = Nullptr If rc2KeyItem.data != Nullptr RC5 Cipher 0x10 Unsigned int 255 Unsigned intInitialization vector Unsigned char initVector8 ARC5CBCPARAMS rc5Params Use a random number generator to create 10 bytes Item rc5KeyItemIf rc5KeyItem.data != Nullptr Update Final EncryptedData = Nullptr RC6 Cipher #define Blocksize Unsigned char initVectorBLOCKSIZE Setting the Key Data If rc6KeyItem.data != Nullptr Break OutputLenTotal = outputLenUpdate + outputLenFinal Been allocated AES Cipher Unsigned char *aesParams Creating a Key Object If aesKeyItem.data != Nullptr Final Password-Based Encryption Iteration count Unsigned char * salt Init Tmemset pbeKeyItem.data, 0, Maxpwlen Update Final Page Public-Key Operations Performing RSA Operations Generating a Key PairPerforming RSA Operations Where Item is There is no in generating a key pair Destroy Milliseconds Private non-CRT What is MultiPrime?MultiPrime MultiPrime Two-Prime RSA 48.8 17.5 Three-Prime RSA 10.9 How Many Primes? Sample BGetKeyInfo BGenerateInitRsaGen BGenerateKeypair Set the Algorithm Object Generating an RSA MultiPrime Key If status = BGenerateInit keypairGenerator Distributing an RSA Public Key Crypto-C Format BER/DER EncodingIf you looked at the elements of the struct If status = myPublicKeyBER.data == Nullptr != Format of info returned by BGetKeyInfo RSA Public-Key Encryption Send it off Remember to free any memory you allocatedTfree myPublicKeyBER.data Input constraints Reference Manual entry on AIPKCSRSAPublic states #define Blocksize RSA Private-Key Decryption If status = BDecryptInit Raw RSA Encryption and Decryption Optimal Asymetric Encryption Padding Oaep MultiPrime Computing a Digital Signature RSA Digital Signatures Setting The Algorithm Object Entry for the AI in use Surrender context outlined in The Surrender Context on Verifying a Digital Signature If status = BVerifyInit Update Performing DSA Operations Generating DSA ParametersPerforming DSA Operations Bdsaparamgenparams dsaParams DsaParams.primeBits = There is no in generating DSA parameters Generate Generating a DSA Key Pair DSA Signatures Computing a Digital Signature Creating An Algorithm Object Properly cast Nullptr for the surrender context #define Maxsiglen To verify the signature created here, use the same AI Data and you know its length, your call is the following Performing Diffie-Hellman Key Agreement Generating Diffie-Hellman Parameters Adhparamgenparams Adhparamgenparams dhParams There is no in generating Diffie-Hellman parameters Destroy Base generator Distributing Diffie-Hellman Parameters If you look at the elements of the struct BER Format A p t e r 7 P u b l i c K e y O p e r a t i o n s Item dhParametersBER Diffie-Hellman Key Agreement If status = BKeyAgreeInit Phase Other party should send their public value and its length Saving the Object State Performing Elliptic Curve Operations Generating Elliptic Curve ParametersPerforming Elliptic Curve Operations Implementation version Input of 0 defaults to fieldElementBitsInput of 0 defaults to Format of info supplied to BSetAlgorithmInfo Performing Elliptic Curve Operations No Update step is necessary for parameter generation GeneralFlag = Retrieving Elliptic Curve Parameters Elliptic curve coefficient Indicates type of base fieldIt is the prime number Case that fieldType = Ftfp If status = output-base.data == Nullptr != 0 break If status = output-order.data == Nullptr != 0 break Aecparams ecParamInfoFreeECParamInfo&ecParamInfo Sample code, FreeECParamInfo is implemented as follows Generating an Elliptic Curve Key Pair Becparams paramInfo Initialize There is no Update step for key generation Aecparams curveParams Retrieving an Elliptic Curve KeyKIECPublic gives a pointer to an Aecpublickey structure Public component Performing Elliptic Curve Operations Generating Acceleration Tables Generating a Generic Acceleration TableEnd FreeECPubKeyInfo Retrieve the elliptic curve parameters Format the informationAecparams *cryptocECParamInfo Aecparams ecParamInfo For odd prime field There is no Update step for building acceleration tables Allocate memory Build the acceleration tableItem accelTableItem Retrieve the public key information Generating a Public-Key Acceleration Table FreeECPubKeyInfo&publicKeyInfo Put the information retrieved in the proper format Item pubKeyAccelTableItem unsigned int maxTableLen GeneralFlag = If status = BBuildTableFinal Performing EC Diffie-Hellman Key AgreementBuild the public-key acceleration table Item pubKeyAccelTableItem Create Optional Set Acceleration Table Info If status = alicePublicValue == Nullptr != 0 break If status = aliceSecretValue == Nullptr != 0 break Performing Ecdsa in Compliance with Ansi Generating an EC Key Pair Generating EC Parameters Computing a Digital Signature Create Item aTableItem Build an algorithm chooser with the appropriate AMs Now, using BSignUpdate, pass in the data to be signed Aecparams *ecParamInfoIf status = signature == Nullptr != 0 break Unsigned int signatureLen Initialized random algorithm in BSignFinalDestroy all objects that are no longer needed Use the same AI and digestInfo as you did for signing Optional Set Public Key Acceleration Table Info Performing Ecdsa with X9.62-Compliant BER 0x7a Item stockECParamsBERECParamsBER154 = 0x30 0x81 0x52 0xd1 StockECParamsBER.data = ECParamsBER stockECParamsBER.len = 0x79 DataToSign = 0x530x68 0x73 Aecparams *ecParamsInfo Use the same AI as you did for signing Tfreesignature BDestoryAlgorithmObject &ecDSAVerify Using Ecaes Using Elliptic Curve Parameters Using an EC Key PairEcaes Public-Key Encryption Optional Acceleration Table Now, pass this information into your algorithm objectItem accelerationTableItem Break FieldElementLen = ecParamInfo-fieldElementBits + 7 Final Ecaes Private-Key Decryption Steps for decryption are similar to those for encryptionCreate an algorithm object = TmallocmaxDecryptedDataLen BDecryptUpdateOutputLenUpdate MaxDecryptedDataLen = outputLenTotalPage Generating Shares Secret Sharing Example in this section corresponds to the file scrtshar.c Secret Sharing #define Secretsize 16 #define Totalshares Tfree secretSharecount If status = secretSharecount == Nullptr != 0 breakBreak If status != 0 break Unsigned int outputLenFinal If status = BEncryptFinal Use the same AI, AIBSSecretSharing Reconstructing the Secret Asurrenderctx *NULLPTR != 0 break If status != 0 break BDestroyAlgorithmObject &secretReconstructer Page Putting It All Together An X9.31 Example X9.31 Sample Program X9.31 Sample ProgramBkeyobj privateKey = Bkeyobjnullptr Item randomSeed Printf ================================================\n Generating Random BytesStatic unsigned char f4Data = 0x01, 0x00 Unsigned int status To create a random algorithm object and set the parameters Providing the Seed Generating a Key Pair Break Computing a Digital Signature Printf ============================= \nRsaVerifyX931. For signing, use rsaSignX931 AX931PARAMS Break Init Verifying the Signature If status != Return End GeneralSurrenderFunction Surrendering Control Printing the Buffer Contents Appendix a Overview of the Demos Command-Line Demo User’s Guide Command-Line Demo User’s GuideCommand Line mode Input Redirection mode Using Bdemo Specifying User KeysSign a File Create a File Envelope Verify a Signed FileOpen a File Envelope Generate a Key Pair Using Bdemodsa Running BdemodsaEnter any arbitrary string of printable characters Sign a File Running Bdemoec Using Bdemoec File Reference File ReferenceTable A-1Demo Program Source Files BSLite Table A-1Demo Program Source Files BSLite BSLite Page Glossary Application Programming Interface Advanced Encryption StandardSeries of steps used to complete a task American National Standards Institute O s s a r y See XOR Generic security service application program interfaceElectronic business Data Interchange See ECC An algorithm that generates the subkeys in a block cipher Process of having a third party hold onto encryption keysProcess that creates a larger key from the original key Act of creating a key Extra bits concatenated with a key, password, or plaintext Data to be encryptedPrivate key in the RSA public-key cryptosystem Secure Multipurpose Internet Mail Extensions Number extracted from a pseudo- random sequence Trusted Computer System Evaluation Criteria Simple Mail Transfer ProtocolSecure Wide Area Network See secret key XOR Page Index Ecdsa D e A B S a F E C r y p t o C D e v e l o p e r ’s G u i d e D e See also RC4 subprime