Encrypting a Message Using the Public Key | RSA Security 5.2.2

Cryptography Overview

Encrypting a Message Using the Public Key

Anyone who wishes to send Bob an encrypted message can do so using the elliptic curve parameters and Q. To encrypt a message M, where the length (in bytes) of the message is f, another party follows these steps:

1.Compute a random value, k1, between 1 and n – 1.

2.Compute the elliptic curve point Q1 = k1P. This will be transmitted along with the encrypted message.

3.Compute the elliptic curve point S1 = k1Q. S1 is a pair (x1,y1). This is the secret information the sender uses to encode the message.

4.Compute a one time pad, otp, of length f, from x1 using a key derivation function (KDF). otp is a concatenation of a series of hashes; it is constructed using f, x1, and SHA1. otp is described below. The description uses the following notation: (1) denotes the concatenation of two numbers, (2) for a number a, [a] denotes the integer part of a. In particular, [f/160] denotes the integer part of f/160.

a.Initiate a 32-bit, big-endian bit string counter. In hex, counter is initialized to 0000000116.

b.For i = 1 to [f/160], create a series of hashes, as follows:

Compute Hashi = SHA1(x1 counter), that is, the SHA1 hash of the concatenation of x1 and counter.

Increment counter. Increment i.

c.We want the length of the pad to be exactly the same as the length, f, of the message M. If f/160 is not an integer, we need to truncate the last hash to make the lengths equal. Therefore, we define Hash’[f/160] as follows:

Hash’[f/160] = {	Hash[f/160]	if f/160 is an integer
Hash’[f/160] = {	the [f/160] – (160 ⋅ [f/160])	if f/160 is not an integer
	leftmost bits of Hash[f/160]

d.Set otp to be the concatenation of the series of hashes: otp = Hash1 Hash2 …Hash[f/160]-1Hash’[f/160]

5.Compute M’ = otp XOR M.

7 6	R S 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

Image 98

RSA Security 5.2.2 manual Encrypting a Message Using the Public Key

Contents

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