Public-Key Algorithms, Digital Signatures | RSA Security 5.2.2

The Crypto-C Toolkit

Public-Key Algorithms

•RSA Public Key Cryptosystem

•Diffie-Hellman Key Agreement

Digital Signatures

•DSA

•RSA Digital Signatures

Elliptic Curve Public-Key Algorithms

•Elliptic Curve Digital Signature Algorithm (ECDSA)

•Elliptic Curve Diffie-Hellman Key Agreement

•Elliptic Curve Authenticated Encryption Scheme (ECAES)

Secret Sharing

•Bloom-Shamir Secret Sharing

Hardware Support

In addition to the cryptographic algorithms listed here, Crypto-C offers a hardware interface that allows vendors of cryptographic hardware to support the Crypto-C API. One such vendor is Intel®, whose Intel hardware security primitives include the Intel Random Number Generator.

For information on using the Intel hardware (when present) with Crypto-C, see the Intel Security Hardware User’s Guide, included on the Crypto-C CD-ROM. For information about using Crypto-C with other cryptographic hardware, contact the specific hardware vendor.

RSA BSAFE Crypto-C products include PKCS #11 hardware support to allow communication with hardware like smart cards (for secure key storage) and cryptographic accelerator cards (for performance improvements). PKCS #11 support is in addition to the BHAPI hardware support offered in previous versions of Crypto- C.

C h a p t e r 1 I n t r o d u c t i o n

3

Image 25

RSA Security 5.2.2 manual Digital Signatures, Elliptic Curve Public-Key Algorithms, Secret Sharing

Contents

Cryptographic Components for C Crypto-C License agreement TrademarksDistribution Limit distribution of this document to trusted personnel 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 Improved performance What’s New in Version 5.2.2?Hardware support MultiPrime RSA Advanced Encryption Standard AES Organization of This ManualOrganization of This Manual 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 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 RSA Security Web Site Getting Support and Service How to Contact RSA SecurityHow to Contact RSA Security You can get technical support as follows Introduction Algorithms Crypto-C Toolkit Digital Signatures Public-Key AlgorithmsElliptic Curve Public-Key Algorithms Secret Sharing Pkcs Standards and Crypto-C Cryptographic Standards and Crypto-CNist Standards and Crypto-C Nist Approval and Windows 32-bit Platforms Nist Approval and Windows NT Platforms Pkcs Compared with Nist Ansi X9 Standards and Crypto-C Quick Start Six-Step Sequence Six-Step Sequence Include Files Introductory ExampleCreating an Algorithm Object Introductory Example Nullptr is also defined in aglobal.h Where Pointer is defined in aglobal.hTypedef unsigned char *POINTER #define Nullptr POINTER0 Balgorithmobj algorithmObject Algorithm object Setting the Algorithm ObjectAlgorithm information Break Init Creating a Key Object Setting a Key ObjectFor our example, we use Key information Int BSetKeyInfo Now we can complete the call to BSetKeyInfo Selecting an Algorithm Chooser Saving the Object State optional UpdateSurrender Context We can now complete our call to BEncryptInit Unsigned int Output data bufferLength of output data Input data For now, we declare Unsigned int outputLenUpdateUnsigned char *encryptedData = Nullptr Final If status = BEncryptUpdate Asurrenderctx *surrenderContext Surrender context Destroy Pointer to key object For our example, we use the followingBalgorithmobj * algorithmObject Pointer block For this example, call Tfree as follows Putting It All TogetherTfree encryptedData If rc4KeyItem.data != Nullptr Init If status = BEncryptInit Introductory Example EncryptedData = Nullptr End main If encryptedData != Nullptr Creating the Key Object Decrypting the Introductory ExampleDecrypting the Introductory Example First create the algorithm object 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 Include Summary of the Six StepsCreate Set Final Page Cryptography Symmetric-Key Cryptography Cryptography OverviewCiphers Cryptography Overview Padding Block CiphersCiphers in Crypto-C Crypto-C implements the following block ciphers 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 Prime Numbers Modular MathMultiPrime Numbers RSA Algorithm Cryptography Overview Security SummaryCalculation is shown in Table 1Calculation of 827 mod 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 Point P and its Order Coefficients Over a Field of Even CharacteristicPoints of an Elliptic Curve Elliptic curve parameters Order of a Point Order of an Elliptic CurvePoint of Prime Order Is written EFq Cofactor Summary of Elliptic Curve TerminologyOrder n of P Is sometimes called the base point 2Elliptic Curve Parameters Elliptic Curve Key Pair Generation Representing Fields of Even Characteristic Creating the Key Pair Ecdsa Signature SchemeSigning a Message Math Verifying a Signature Recall that Q = dP, so Elliptic Curve Authenticated Encryption Scheme EcaesNow 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 Ascii Encoding and Decoding Applications of CryptographyLocal Applications Applications of Cryptography Point-to-Point Applications Client/Server Applications Peer-to-Peer Applications Public-Key vs. Symmetric-Key Cryptography Choosing AlgorithmsStream vs. Block Symmetric-Key Algorithms Choosing Algorithms Key Agreement vs. Digital Envelopes Block Symmetric-Key Algorithms Elliptic Curve Algorithms Secret Sharing and Key Escrow Interoperability Handling Private Keys Security ConsiderationsElliptic Curve Standards Security Considerations Pseudo-Random Numbers and Seed Generation Temporary Buffers Choosing Passwords DES Weak Keys Initialization Vectors and Salts3DES 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 RC2 Effective Key Bits Diffie-Hellman Parameters and DSA KeysRC4 Key Bits RC5 Key Bits and Rounds Elliptic Curve Keys Algorithms in Crypto-C Using Crypto-C Basic Algorithm Info Types Information Formats Provided by Crypto-CBER-Based Algorithm Info Types Algorithms in Crypto-C PEM-Based Algorithm Info Types Summary of AIsBSAFE1 Algorithm Info Types 1Message Digests 3ASCII Encoding Algorithms in Crypto-C 2Message Authentication4Pseudo-Random Number Generation 5Symmetric Stream Ciphers 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 11Bloom-Shamir Secret Sharing 10 Elliptic Curve Public-Key Cryptography12Hardware Interface Algorithm Info Type Algorithms in Crypto-C 13Advanced Encryption Standard AES Summary of KIs Keys In Crypto-CKeys In Crypto-C 15Block Cipher Keys 16RSA Public and Private Keys Keys In Crypto-C 15Block Cipher Keys17DSA Public and Private Keys Keys In Crypto-C 18Elliptic Curve Keys Algorithm Choosers System Considerations In Crypto-CAn Encryption Algorithm Chooser System Considerations In Crypto-C An RSA Algorithm Chooser Description of AIX962RandomV0 instead of AISHA1Random Surrender Context Also gives the form that a surrender function must have Sample Surrender FunctionReserved for future use Int *Surrender Pointer handle Saving State When to Allocate Memory Memory-Management Routines and Standard C Libraries Memory-Management RoutinesCrypto-C uses the following memory-management routines Tmalloc Trealloc Tfree Tmemset Tmemcpy Tmemmove Tmemcmp Memory Allocation BER/DER EncodingBinary Data Typedef struct unsigned char *data unsigned int len System Considerations In Crypto-C Symmetric Block Algorithms Input and OutputInput constraints Output considerations 20Input Limits for RSA Pkcs Encryption General Considerations DES Keys Key SizePublic 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 = For an RSA private key, it would be this Advanced Pkcs #11Digest 00 00 00 66 a9 47 2d 80 5a Random Numbers Hardware IssuesCkrv rv Rv = CKBYTEPTRseedBuffer, CKULONGseedLen Using Cryptographic Hardware Page Non-Cryptographic Operations Creating a Digest Message DigestsMessage Digests Example in this section corresponds to the file mdigest.c If status = BDigestInit Your call will be the following If status = BDigestUpdate#define Digestlen BER-Encoding the Digest Remember to destroy all objects when you are done with them Saved State Saving the State of a Digest Algorithm ObjectFollowing 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 Generate a random 24-byte key using KI24Byte Hash-Based Message Authentication Code HmacCreate the key object RandomAlgorithm, keyData, KEYSIZE, Asurrenderctx *NULLPTR != Unsigned char *digestedData unsigned int digestedDataLen Generating Random Numbers with SHA1 Generating Random NumbersGenerating 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 This step is identical to the previous example Generating Independent Streams of RandomnessTypedef struct Additional seeding These steps are identical to the previous example Steps 4, 5Item randomSeed AX931RANDOMPARAMS x931Params Encoding Binary Data To Ascii Converting Data Between BinaryConverting 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 DES with CBC Block CiphersBlock Ciphers Example in this section corresponds to the file descbc.c RC5 parameters Examples include des, rc5Points at init vector Item For new padding schemes 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 255 Unsigned int 0x10 Unsigned intInitialization vector Unsigned char initVector8 ARC5CBCPARAMS rc5Params Item rc5KeyItem Use a random number generator to create 10 bytesIf 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 Generating a Key Pair Performing RSA OperationsPerforming RSA Operations Where Item is There is no in generating a key pair Destroy MultiPrime What is MultiPrime?MultiPrime Milliseconds Private non-CRT Two-Prime RSA 48.8 17.5 Three-Prime RSA 10.9 How Many Primes? Sample RsaGen BGenerateInitBGenerateKeypair BGetKeyInfo Set the Algorithm Object Generating an RSA MultiPrime Key If status = BGenerateInit keypairGenerator Distributing an RSA Public Key BER/DER Encoding Crypto-C FormatIf you looked at the elements of the struct If status = myPublicKeyBER.data == Nullptr != Format of info returned by BGetKeyInfo Send it off Remember to free any memory you allocated RSA Public-Key EncryptionTfree 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 Generating DSA Parameters Performing DSA OperationsPerforming 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 Generating Elliptic Curve Parameters Performing Elliptic Curve OperationsPerforming Elliptic Curve Operations Input of 0 defaults to Input of 0 defaults to fieldElementBitsFormat of info supplied to BSetAlgorithmInfo Implementation version Performing Elliptic Curve Operations No Update step is necessary for parameter generation GeneralFlag = Retrieving Elliptic Curve Parameters It is the prime number Indicates type of base fieldCase that fieldType = Ftfp Elliptic curve coefficient If status = output-base.data == Nullptr != 0 break Aecparams ecParamInfo If status = output-order.data == Nullptr != 0 breakFreeECParamInfo&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 KIECPublic gives a pointer to an Aecpublickey structure Retrieving an Elliptic Curve KeyPublic component Aecparams curveParams Performing Elliptic Curve Operations Generating a Generic Acceleration Table Generating Acceleration TablesEnd FreeECPubKeyInfo Format the information Retrieve the elliptic curve parametersAecparams *cryptocECParamInfo Aecparams ecParamInfo For odd prime field There is no Update step for building acceleration tables Build the acceleration table Allocate memoryItem 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 Build the public-key acceleration table Performing EC Diffie-Hellman Key AgreementItem pubKeyAccelTableItem GeneralFlag = If status = BBuildTableFinal 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 Aecparams *ecParamInfo Now, using BSignUpdate, pass in the data to be signedIf status = signature == Nullptr != 0 break Destroy all objects that are no longer needed Initialized random algorithm in BSignFinalUse the same AI and digestInfo as you did for signing Unsigned int signatureLen Optional Set Public Key Acceleration Table Info Performing Ecdsa with X9.62-Compliant BER ECParamsBER154 = 0x30 0x81 Item stockECParamsBER0x52 0xd1 0x7a StockECParamsBER.data = ECParamsBER stockECParamsBER.len = 0x68 DataToSign = 0x530x73 0x79 Aecparams *ecParamsInfo Use the same AI as you did for signing Tfreesignature BDestoryAlgorithmObject &ecDSAVerify Using Ecaes Using an EC Key Pair Using Elliptic Curve ParametersEcaes Public-Key Encryption Now, pass this information into your algorithm object Optional Acceleration TableItem accelerationTableItem Break FieldElementLen = ecParamInfo-fieldElementBits + 7 Final Steps for decryption are similar to those for encryption Ecaes Private-Key DecryptionCreate an algorithm object OutputLenUpdate BDecryptUpdateMaxDecryptedDataLen = outputLenTotal = TmallocmaxDecryptedDataLenPage Generating Shares Secret Sharing Example in this section corresponds to the file scrtshar.c Secret Sharing #define Secretsize 16 #define Totalshares Break If status != 0 break If status = secretSharecount == Nullptr != 0 breakUnsigned int outputLenFinal If status = BEncryptFinal Tfree secretSharecount 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 Static unsigned char f4Data = 0x01, 0x00 Generating Random BytesUnsigned int status Printf ================================================\n To create a random algorithm object and set the parameters Providing the Seed Generating a Key Pair Break Printf ============================= \n Computing a Digital SignatureRsaVerifyX931. 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 mode Command-Line Demo User’s GuideInput Redirection mode Command-Line Demo User’s Guide Specifying User Keys Using BdemoSign a File Verify a Signed File Create a File EnvelopeOpen a File Envelope Generate a Key Pair Running Bdemodsa Using 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 Series of steps used to complete a task Advanced Encryption StandardAmerican National Standards Institute Application Programming Interface O s s a r y Electronic business Data Interchange Generic security service application program interfaceSee ECC See XOR Process that creates a larger key from the original key Process of having a third party hold onto encryption keysAct of creating a key An algorithm that generates the subkeys in a block cipher Data to be encrypted Extra bits concatenated with a key, password, or plaintextPrivate key in the RSA public-key cryptosystem Secure Multipurpose Internet Mail Extensions Number extracted from a pseudo- random sequence Secure Wide Area Network Simple Mail Transfer ProtocolSee secret key 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