RSA Security Crypto-C User Manual

RSA BSAFE
®
Crypto-C
Cryptographic Components for C
Developer’s Guide
Version 5.2.2
RSA Security Inc. 20 Crosby Drive Bedford, MA 01730 USA Tel (US) 1 877 RSA 4900, +1 781 301 5000 Fax +1 781 301 5170 www.rsasecurity.com
RSA Security Ireland Limited Bay 127, Shannon Free Zone Shannon, County Clare, Ireland Tel +353 61 72 5100 Fax +353 61 72 5110 www.rsasecurity.ie
Trademarks
ACE/Server, BSAFE, Genuine RSA Encryption Engine, Keon, RC2, RC4, RC5, RSA, RSA SecurPC, SecurCare, SecurID, SoftID, and WebID are registered trademarks, and RC6, RSA Security, RSA Secured, SecurSight, and The Most Trusted Name in e-Security are trademarks, of RSA Security Inc.
Other product and company names mentioned herein may be the trademarks of their respective owners.
License agreement
This software and the associated documentation are proprietary and confidential to RSA Security, are furnished under license, and may be used and copied only in accordance with the terms of such license and with the inclusion of the copyright below. This software and any copies thereof may not be provided or otherwise made available to any other person.
Note on encryption technologies
This product may contain encryption technology. Many countries prohibit or restrict the use, import, or export of encryption technologies, and current use, import, and export regulations should be followed when exporting this product.
Distribution
Limit distribution of this document to trusted personnel.
RSA Security notice
The RC5® Block Encryption Algorithm With Data-Dependent Rotations is protected by U.S. Patent #5,724,428 and #5,835,600.
The RC6™ Encryption Algorithm is the subject of pending U.S. and foreign patent applications.
The DES implementation in this product contains code based on the "libdes" package written by Eric A. Young (eay@pobox.com) and is included with his permission.
Compaq MultiPrime™ technology is protected by United States patent 5,848,159 and is the subject of patent applications in other countries.
© 2001 RSA Security Inc. All rights reserved. 001-019003-522-001-000 First printing: May 2001

Contents

Preface xv
What’s New in Version 5.2.2? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvi
Organization of This Manual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .xvii
Conventions Used in This Manual. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xviii
Terms and Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xix
Related Documents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .xx
How to Contact RSA Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .xxii
Improved performance. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .xvi
Hardware support . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .xvi
MultiPrime RSA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .xvi
Serialization for algorithm objects performing RC4, Diffie Hellman key exchange . . . . .xvi
Advanced Encryption Standard (AES) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvii
RSA Security Web Site . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxii
Getting Support and Service . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxii
SecurCare® Online . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxii
Technical Support Telephone Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxii
Call Handling and Escalation Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxii
Chapter 1 Introduction 1
The Crypto-C Toolkit. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Symmetric Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Message Digests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2
Message Authentication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Random-Number Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Public-Key Algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3
Digital Signatures. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3
Elliptic Curve Public-Key Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3
Secret Sharing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3
Hardware Support . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3
iii
Cryptographic Standards and Crypto-C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
PKCS Standards and Crypto-C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
NIST Standards and Crypto-C. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
PKCS Compared with NIST. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
ANSI X9 Standards and Crypto-C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Chapter 2 Quick Start 7
The Six-Step Sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Introductory Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Saving the Object State (optional). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Putting It All Together. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Decrypting the Introductory Example. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Multiple Updates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Summary of the Six Steps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Chapter 3
Cryptography 35
Cryptography Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Symmetric-Key Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Block Ciphers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Padding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Ciphers in Crypto-C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
DES. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Triple DES. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
DESX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
RC2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
RC5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
RC6. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
AES. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
Modes of Operation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
Stream Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Message Digests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
Message Digests and Pseudo-Random Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . 48
Hash-Based Message Authentication Codes (HMAC) . . . . . . . . . . . . . . . . . . . . . . 49
Password-Based Encryption. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
Public-Key Cryptography. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
The RSA Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
Digital Envelopes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
iv RSA BSAFE Crypto-C Developer’s Guide
Optimal Asymmetric Encryption Padding (OAEP). . . . . . . . . . . . . . . . . . . . . . . . . . .55
Authentication and Digital Signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
Digital Signature Algorithm (DSA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .60
Digital Certificates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .61
Diffie-Hellman Public Key Agreement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .62
Elliptic Curve Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .65
Elliptic Curve Parameters. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .66
The Finite Field . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .66
The Point P and its Order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .69
Summary of Elliptic Curve Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .71
Representing Fields of Even Characteristic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .72
Elliptic Curve Key Pair Generation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
Creating the Key Pair . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .73
ECDSA Signature Scheme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .73
Signing a Message. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .73
Verifying a Signature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .74
The Math. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .74
Elliptic Curve Authenticated Encryption Scheme (ECAES) . . . . . . . . . . . . . . . . . . . . . . . . 75
Encrypting a Message Using the Public Key . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .76
Decrypting a Message Using the Private Key . . . . . . . . . . . . . . . . . . . . . . . . . . . . .77
Elliptic Curve Diffie-Hellman Key Agreement. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .77
Phase 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .78
Phase 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .78
The Math. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .79
Secret Sharing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .80
Working with Keys. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .81
Key Generation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .81
Key Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .82
Key Escrow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
ASCII Encoding and Decoding. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .83
Applications of Cryptography. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
Local Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .83
Point-to-Point Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .84
Client/Server Applications. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .85
Peer-to-Peer Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .86
Choosing Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
Public-Key vs. Symmetric-Key Cryptography. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .87
Stream vs. Block Symmetric-Key Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .87
Block Symmetric-Key Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .88
Key Agreement vs. Digital Envelopes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .88
Secret Sharing and Key Escrow. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
Contents v
Elliptic Curve Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
Interoperability. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
Elliptic Curve Standards. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
Security Considerations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
Handling Private Keys. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
Temporary Buffers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
Pseudo-Random Numbers and Seed Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
Choosing Passwords. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
Initialization Vectors and Salts. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
DES Weak Keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
Stream Ciphers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
Timing Attacks and Blinding. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
Choosing Key Sizes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
RSA Keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
Diffie-Hellman Parameters and DSA Keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
RC2 Effective Key Bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
RC4 Key Bits. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
RC5 Key Bits and Rounds. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
Triple DES Keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
Elliptic Curve Keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
Chapter 4 Using Crypto-C 101
Algorithms in Crypto-C. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
Information Formats Provided by Crypto-C. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
Basic Algorithm Info Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
BER-Based Algorithm Info Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
PEM-Based Algorithm Info Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
BSAFE1 Algorithm Info Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
Summary of AIs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
Keys In Crypto-C. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
Summary of KIs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
System Considerations In Crypto-C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
Algorithm Choosers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
An Encryption Algorithm Chooser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
An RSA Algorithm Chooser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
The Surrender Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
A Sample Surrender Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
Saving State. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
When to Allocate Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
vi RSA BSAFE Crypto-C Developers Guide
Memory-Management Routines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
Memory-Management Routines and Standard C Libraries . . . . . . . . . . . . . . . . . .122
Memory Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .123
Binary Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .123
BER/DER Encoding. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .123
Input and Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
Symmetric Block Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .126
The RSA Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .127
General Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .128
Key Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .129
DES Keys. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .129
RSA Keys. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .129
Using Cryptographic Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
Interfacing with a BHAPI Implementation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .132
PKCS #11 Support . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .134
Using a PKCS #11 Device with Crypto-C. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .135
PKCS #11 Support for DSA Key Pair Generation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .144
Advanced PKCS #11. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .147
Random Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
Hardware Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .148
Chapter 5 Non-Cryptographic Operations 151
Message Digests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
Creating a Digest. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .152
BER-Encoding the Digest. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .155
Saving the State of a Digest Algorithm Object. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .156
Saved State. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .156
Hash-Based Message Authentication Code (HMAC) . . . . . . . . . . . . . . . . . . . . . . . 161
Generating Random Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
Generating Random Numbers with SHA1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
Generating Independent Streams of Randomness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
Converting Data Between Binary and ASCII . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
Encoding Binary Data To ASCII . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .172
Decoding ASCII-Encoded Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
Contents vii
Chapter 6 Symmetric-Key Operations 177
Block Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
DES with CBC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
Decrypting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
The RC2 Cipher. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
Decrypting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
The RC5 Cipher. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
Decrypting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
The RC6 Cipher. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
Decrypting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
The AES Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
Password-Based Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
Decrypting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
Chapter 7 Public-Key Operations 213
Performing RSA Operations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
Generating a Key Pair. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
MultiPrime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
What is MultiPrime?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
How Many Primes?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
Sample . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
Generating an RSA MultiPrime Key . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
Distributing an RSA Public Key. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
Crypto-C Format. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
BER/DER Encoding. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
RSA Public-Key Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
RSA Private-Key Decryption. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
Optimal Asymetric Encryption Padding (OAEP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
Raw RSA Encryption and Decryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
RSA Digital Signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
Computing a Digital Signature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
Verifying a Digital Signature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
Performing DSA Operations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
Generating DSA Parameters. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
Generating a DSA Key Pair. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
DSA Signatures. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
Computing a Digital Signature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
Verifying a Digital Signature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
viii RSA BSAFE Crypto-C Developers Guide
Performing Diffie-Hellman Key Agreement. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
Generating Diffie-Hellman Parameters. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .249
Distributing Diffie-Hellman Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .253
Crypto-C Format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .253
BER Format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .254
Diffie-Hellman Key Agreement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .256
Saving the Object State . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .259
Performing Elliptic Curve Operations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
Generating Elliptic Curve Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .260
Retrieving Elliptic Curve Parameters. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .264
Generating an Elliptic Curve Key Pair . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .268
Retrieving an Elliptic Curve Key. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .271
Generating Acceleration Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .273
Generating a Generic Acceleration Table. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .273
Generating a Public-Key Acceleration Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . .277
Performing EC Diffie-Hellman Key Agreement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .280
Performing ECDSA in Compliance with ANSI X9.62. . . . . . . . . . . . . . . . . . . . . . . . . . . .284
Generating EC Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .285
Generating an EC Key Pair . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .285
Computing a Digital Signature. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .286
Verifying a Digital Signature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .289
Performing ECDSA with X9.62-Compliant BER . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .291
Generating EC Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .291
Generating an EC Key Pair . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .293
Computing a Digital Signature. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .293
Verifying a Digital Signature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .296
Using ECAES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .297
Using Elliptic Curve Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .298
Using an EC Key Pair. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .298
ECAES Public-Key Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .298
ECAES Private-Key Decryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .302
Chapter 8 Secret Sharing Operations 305
Secret Sharing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
Generating Shares. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .305
Reconstructing the Secret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .309
Chapter 9 Putting It All Together: An X9.31 Example 313
The X9.31 Sample Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
Contents ix
Appendix A Command-Line Demos 327
Overview of the Demos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
Command-Line Demo User’s Guide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328
BDEMO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328
Starting BDEMO. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328
Specifying User Keys. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
Using BDEMO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
BDEMODSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
Running BDEMODSA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
Using BDEMODSA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
BDEMOEC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
Running BDEMOEC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
Using BDEMOEC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
File Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
BSLite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336
Glossary 339
Index 349
x RSA BSAFE Crypto-C Developers Guide
List of Figures
Figure 3-1 Symmetric-Key Encryption and Decryption . . . . . . . . . . . . . . . . . . . . 36
Figure 3-2 Triple DES Encryption as Implemented in Crypto-C. . . . . . . . . . . . . . 38
Figure 3-3 Electronic Codebook (ECB) Mode . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
Figure 3-4 Cipher-Block Chaining (CBC) Mode . . . . . . . . . . . . . . . . . . . . . . . . . . 43
Figure 3-5 Cipher Feedback (CFB) Mode. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Figure 3-6 Output Feedback Mode (OFB) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Figure 3-7 RC4 Encryption or Decryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
Figure 3-8 DES Key and IV Generation for Password Based Encryption . . . . . . 50
Figure 3-9 Public-Key Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
Figure 3-10 Digital Envelope. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
Figure 3-11 RSA Digital Signature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
Figure 3-12 The Diffie-Hellman Key Agreement Protocol . . . . . . . . . . . . . . . . . . 63
Figure 3-13 Elliptic Curve Diffie-Hellman Key Agreement . . . . . . . . . . . . . . . . . . 79
Figure 3-14 Secret Sharing Key Share Assignment . . . . . . . . . . . . . . . . . . . . 81
Figure 3-15 Secret Sharing Full Key Generation From Shares . . . . . . . . . . . . 81
Figure 4-1 Algorithm Object in a Software Implementation . . . . . . . . . . . . . . 132
Figure 4-2 Algorithm Object in a Hardware Implementation . . . . . . . . . . . . . . 133
xi
xii RSA BSAFE Crypto-C Developers Guide
List of Tables
Table 3-1 Calculation of 827 mod 55. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
Table 3-2 Elliptic Curve Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
Table 3-3 DES Weak and Semi-Weak Keys . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
Table 3-4 Summary of Recommended Key Sizes . . . . . . . . . . . . . . . . . . . . . . . 98
Table 4-1 Message Digests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
Table 4-2 Message Authentication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
Table 4-3 ASCII Encoding. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
Table 4-4 Pseudo-Random Number Generation . . . . . . . . . . . . . . . . . . . . . . . 104
Table 4-5 Symmetric Stream Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
Table 4-6 Symmetric Block Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
Table 4-7 RSA Public-Key Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
Table 4-8 DSA Public-Key Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
Table 4-9 Diffie-Hellman Key Agreement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
Table 4-10 Elliptic Curve Public-Key Cryptography . . . . . . . . . . . . . . . . . . . . . . 110
Table 4-11 Bloom-Shamir Secret Sharing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
Table 4-12 Hardware Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
Table 4-13 Advanced Encryption Standard (AES) . . . . . . . . . . . . . . . . . . . . . . . 112
Table 4-14 Generic Keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
Table 4-15 Block Cipher Keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
Table 4-16 RSA Public and Private Keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
Table 4-17 DSA Public and Private Keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
Table 4-18 Elliptic Curve Keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
Table 4-19 Token Keys. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
Table 4-20 Input Limits for RSA PKCS Encryption . . . . . . . . . . . . . . . . . . . . . . . 127
Table 5-1 Code Sample: DigestDataSavedState() . . . . . . . . . . . . . . . . . . . . . 159
Table A-1 Demo Program Source Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
xiii
xiv RSA BSAFE Crypto-C Developers Guide

Preface

Dear Crypto-C Developer: Congratulations on your purchase of RSA BSAFE®
the-art in cryptographic software toolkits. Crypto-C provides developers with the most important privacy, authentication, and data integrity routines. Crypto-C contains a full palette of popular cryptographic algorithms. This software development kit enables you to develop applications for a wide range of purposes, including electronic commerce, home banking, Webcasting, and enterprise security.
RSA BSAFE® software for enabling applications to share encrypted information, verify the correspondents authenticity, and confirm data integrity. RSA Securitys general­purpose cryptography software has the flexibility to suit a wide variety of security applications or services. This robust, fully supported product is from the most trusted name in e-security: RSA Security.
Crypto-C is written in C and is intended to be completely portable. It is available on a number of platforms and can be ported to most platforms with a minimum of effort. Crypto-C is a toolkit, not an application; it is intended to be integrated into operating systems, communications systems, and other applications. Therefore, you have a modest amount of work ahead of you. We have tried to make this task as clear as possible without limiting your options. This User’s Manual, with its code samples and tutorials, is the best place to start.
Crypto-C 5.2.2 is the latest version of RSA Securitys cryptographic
Crypto-C (Crypto-C), the state-of-
Thanks, and welcome to the RSA Security family. Sincerely, The Crypto-C Development Team
RSA Security
xv

What’s New in Version 5.2.2?

What’s New in Version 5.2.2?
Following is a list of RSA BSAFE Crypto-C features that are new in version 5.2.2:

Improved performance

With the new performance improvements, youll be able to use RSA BSAFE Crypto­Cs algorithms at unprecedented levels of speed and throughput across a wide range of hardware platforms. RSA BSAFE Crypto-Cs support for the Intel Itanium and Pentium4 processors will allow developers the ability to take advantage of benefits of these powerful processors. Also, RSA Securitys implementation of Compaq’s patented MultiPrime technology is designed to process encryption/decryption tasks more than two times faster than previous methods. Typical tasks where customers will experience these performance enhancements are for SSL transactions (signing on the server or client side) and non-repudiation operations (verifying on the client side).

Hardware support

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.

MultiPrime RSA

MultiPrime RSA functionality has been added to Crypto-C v5.2. Use this new function to generate RSA public/private key pairs. RSA MultiPrime key generation follows the same steps as standard RSA key generation with two exceptions: the use of a different AI, AI_RSAMultiPrimeKeyGen, and a different AM must be passed in during the B_GenerateInit call: AM_RSA_MULTI_PRIME_KEY_GEN.

Serialization for algorithm objects performing RC4, Diffie Hellman key exchange

A new algorithm information type, AI_RC4Serialize, has been added to Crypto-C
xvi RSA BSAFE Crypto-C Developers Guide

Organization of This Manual

V5.2. Use this AI to save the internal state of an RC4 encryption or decryption object, or to create a new object from the saved state of a previous RC4 object.

Advanced Encryption Standard (AES)

Crypto-C includes basic AES support for the cutting edge in processor technology: Intel Itanium and Pentium 4.
Organization of This Manual
This manual is organized as follows:
Chapter 1, “Introduction, introduces the Crypto-C toolkit. It lists the algorithms,
cryptographic standards, NIST standards, and ANSI X9 standards used in Crypto-C.
Chapter 2, “Quick Start, uses a code example to describe the basic encryption
and decryption operations in Crypto-C.
Chapter 3, “Cryptography, presents a brief outline of the basic cryptographic
principles and terminology that are used in this manual.
Chapter 4, “Using Crypto-C, presents a brief description of the Crypto-C
algorithm info types and key info types by functionality. It also covers system considerations when using Crypto-C.
Chapters 5-8 present sample code for the major Crypto-C operations.
Chapter 9, Putting it all Together: An X9.31 Example, presents sample code for
the steps involved in creating and verifying RSA digital signatures in accordance with the X9.31 standard.
Appendix A, “Command-Line Demos, describes the three Crypto-C command
line demo applications: BDEMO, BDEMODSA, and BDEMOEC.
Glossary
Index
Preface xvii

Conventions Used in This Manual

Conventions Used in This Manual
The following typographical conventions are used in this manual. Italic is used for:
new terms where they are introduced
the names of manuals and books
Lucida Typewriter Sans is used for:
anything that appears literally in a C program, such as the names of structures
and functions supplied by Crypto-C: for example,
B_DecodeInit
Lucida Typewriter Sans Italic
is used for:
function parameters and placeholders that indicate that an item is replaced by
some actual value in your own program: for example,
Lucida Typewriter Bold
is used for:
randomAlgorithm
text the user types in command line demos and text that is printed to the screen
by the demos (Appendix A only)
Structures and routines defined by Crypto-C are boxed. Direct quotes from the RSA BSAFE Crypto-C Reference Manual are also boxed:
/* Structures defined by Crypto-C */
Crypto-C procedures to use with algorithm object:
B_EncryptInit, B_EncryptUpdate, B_EncryptFinal;
Application code and samples are displayed in a box with a shaded outline:
/* Application code and samples */
Some Crypto-C functions are only available when used with a hardware application that has a BSAFE Hardware API interface (BHAPI). These functions are marked with the icon of a hammer.
xviii RSA BSAFE Crypto-C Developers Guide

Terms and Abbreviations

Terms and Abbreviations
The following table lists terms and abbreviations used in this document. Refer to the Glossary for a list of security and cryptographic terms and abbreviations, along with their definitions, that are used throughout the RSA BSAFE Crypto-C documentation set.
Term or Abbreviation Definition
Crypto-C RSA BSAFE Crypto-C: Cryptographic software development kit developers
use to develop secure applications.
.doc (file) Word for Windows, version 6.x or version 7.x files.
.htm (file) Hypertext Markup Language formatted files used for releasing documents on
the RSA Security internet site.
.pdf (file) Portable Document Format created by Adobe Acrobat Distiller and read by
using Adobe Acrobat Reader.
.rtf (file) Rich Text Format files that are compatable with Microsoft Word for Windows.
.txt (file) Unformatted, cross-platform text files.
PKI The Public Key Infrastructure that combines private key, trust, and certificate
databases for the reserve of needed private keys and certificates for signing or encrypting messages.
Public Client API The default application programming interface between PKI services and the
developer's application.
SPI Service provider interfaces that enable customized implementation to
augment or replace the default Cert-J functionality.
User Interface Any interface that the end user sees or accesses. This includes any HTML
browser-based interfaces
Preface xix

Related Documents

Related Documents
Following is a list of documents referenced in this book and suggested material for further reading.
1. The Public-Key Cryptography Standards (PKCS), RSA Laboratories.
(
http://www.rsasecurity.com/rsalabs/PKCS/)
2. Frequently Asked Questions (FAQ) About Todays Cryptography, RSA Laboratories.
(http://www.rsasecurity.com/rsalabs/faq/)
3. The following Internet Standard documents:
RFCs 1421, 1422, 1423, 1424 on Privacy Enhancement for Internet Electronic Mail.
RFCs 1319 (MD2), 1321 (MD5).
4. The following CCITT Recommendation documents:
X.690: Specifications for the Basic Encoding Rules (BER) for Abstract Notation One (ASN.1).
X.509: The Directory Authentication Framework.
5. Rivest, Shamir, and Adleman, A method for obtaining digital signatures and
public-key cryptosystems. Communications of the ACM, 21(2):120-126, February
1978.
6. A. Shamir, How to share a secret. Communications of the ACM, 22(11):
612-613, November 1979.
7. W. Diffie and M. E. Hellman, New directions in cryptography. IEEE Transactions
on Information Theory, IT-22:644-654, 1976.
8. Data Encryption Standard, FIPS Pub 46-2, National Institute of Standards and
Technology. Available from
9. DES Modes of Operations, FIPS Pub 81, National Institute of Standards and
Technology, 1980.
10. Digital Signature Standard and Secure Hashing Algorithm (DSS and SHA):
FIPS Pub 180-1
X9.30 Part III
11. The following reports from RSA Laboratories (http://www.rsasecurity.com/
rsalabs/technotes
and http://www.rsasecurity.com/rsalabs/bulletins):
Stream Ciphers
MD2, MD4, MD5, SHA and Other Hash Functions
On Pseudo-collisions in MD5
http://www.nist.gov.itl/div897/pubs/index.htm.
xx RSA BSAFE Crypto-C Developers Guide
Related Documents
Results from the RSA Factoring Challenge
Recommendations on Elliptic Curve Cryptosystems
Recent Results for MD2, MD4, and MD5
12. The following OAEP specifications:
SET Secure Electronic Transaction Specification. Book 3: Formal Protocol
Definition, version 1.0. SETCo, 1997. (
http://www.setco.org/)
PKCS#1: RSA Cryptography Specifications. Version 2.0. RSA Security, 1998.
(
http://www.rsasecurity.com/rsalabs/pkcs/)
13. The following ANSI Financial Services Industry documents:
X9.31 (RSA signatures, reversible DSA)
X9.52 Draft (Triple DES)
X9.62 and X9.63 (Elliptic Curves)
14. IEEE Standard Specifications for Public-Key Cryptography on
http://stdsbbs.ieee.org/groups/1363/index.html.
15. B. Schneier, Applied Cryptography, John Wiley & Sons, Inc., New York, 1994.
16. G. Simmons, Contemporary Cryptography, IEEE Press.
17. Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. Handbook of
Applied Cryptography. CRC Press, 1996. Chapter 2 of this book, which covers all aspects of modern cryptography, provides mathematical background on finite fields.
18. A. Menezes, I. Blake, X. Gao, R. Mullin, S. Vanstone, and T. Yaghoobian.
Applications of Finite Fields. Kluwer Academic Publishers, 1993. Provides further reference material on finite fields, including techniques for representing elements.
19. A. Menezes, Elliptic Curve Public Key Cryptosystems, Kluwer Academic Publishers,
1993.
20. Joseph H. Silverman and John Tate, Rational Points on Elliptic Curves, Springer-
Verlag New York, Inc., 1992.
Preface xxi

How to Contact RSA Security

How to Contact RSA Security

RSA Security Web Site

You can visit the RSA Security Web site at http://www.rsasecurity.com. It contains the latest RSA Security news, security bulletins, and information about coming events.
RSA BSAFE product information is available at
products/bsafe http://www.rsasecurity.com/rsalabs/faq.
. RSA Laboratories Cryptography FAQ can also be found at
http://www.rsasecurity.com/

Getting Support and Service

You can get technical support as follows:
SecurCare® Online
www.rsasecurity.com/securcare/index.html
Technical Support Telephone Numbers
www.rsasecurity.com/support/news/tollfree.html
Call Handling and Escalation Process
www.rsasecurity.com/support/news/escproc.html
xxii RSA BSAFE Crypto-C Developers Guide
Chapter 1

Introduction

This chapter introduces the Crypto-C toolkit. It lists the algorithms, cryptographic standards, NIST standards, and ANSI X9 standards used in Crypto-C. This chapter is organized as follows:
The Crypto-C Toolkit
- Algorithms
- Hardware Support
Cryptographic Standards and Crypto-C
- PKCS Standards and Crypto-C
- NIST Standards and Crypto-C
-PKCS Compared with NIST
- ANSI X9 Standards and Crypto-C
1

The Crypto-C Toolkit

The Crypto-C Toolkit
Crypto-C provides developers with a state-of-the-art implementation of the most important privacy, authentication, and data integrity routines.

Algorithms

The following algorithms are implemented in Crypto-C:
Symmetric Ciphers
AES
DES
Triple DES
DESX
RC2® block cipher
RC4® stream cipher
RC5 block cipher
RC6 block cipher
Message Digests
MD
MD2
MD5
SHA1
Message Authentication
HMAC
Random-Number Generation
MD2
MD5
SHA1
X931
2 RSA BSAFE Crypto-C Developers Guide
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
The Crypto-C Toolkit

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 Users 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.
Chapter 1 Introduction 3

Cryptographic Standards and Crypto-C

Cryptographic Standards and Crypto-C

PKCS Standards and Crypto-C

Crypto-C is a general-purpose programming tool that developers can use to write a wide variety of applications. Crypto-C was built to help developers implement the Public-Key Cryptography Standards (PKCS), a series of documents that specify a standard way of performing basic cryptographic operations. Several higher-level standards, such as S/MIME, SET, IPSec, and SSL, require implementation of various PKCS standards. Since Crypto-C complies with PKCS standards, developers should find it fairly easy to integrate Crypto-C into software that implements the PKCS standards.
For copies of the PKCS documents, see the PKCS section of RSA Securitys Web site at
http://www.rsasecurity.com/rsalabs/pkcs, or contact our sales department for a
PKCS diskette.

NIST Standards and Crypto-C

Certain Crypto-C releases may be used to produce applications that are compliant with the Federal Information Processing Standards. Compliance with the FIPS standards is often required by government agencies and contractors. The National Institute of Standards and Technologies (NIST) establishes the FIPS standards, and certifies FIPS-compliant applications.
As changes are made in a new release, RSA Security may need to reapply for NIST certification. If you need to verify whether or not a specific release is compliant with FIPS, contact your sales representative.
NIST Approval and Windows 32-bit Platforms
If you require NIST approval for your Windows 32-bit applications, you may benefit from using the FIPS-compliant Crypto-C algorithms listed following this paragraph. NIST may approve the use of these algorithms in your application without requiring further algorithm-level testing of your application, based on the algorithm certificates issued to Crypto-C. For more information, see the algorithm compliance Web site provided by NIST.
Crypto-C includes the following FIPS-compliant algorithms:
4 RSA BSAFE Crypto-C Developers Guide
Cryptographic Standards and Crypto-C
Secure Hash Algorithm (SHA1), as specified in FIPS PUB 180-1, Secure Hash
Standard (SHS)
RSA Digital Signatures (rDSA), as specified in FIPS PUB 186-2
Digital Signature Algorithm (DSA), as specified in FIPS PUB 186, Digital
Signature Standard (DSS)
Data Encryption Standard (DES), as specified in FIPS PUB 46-2
DES Modes of Operation, as specified in FIPS PUB 81
NIST Approval and Windows NT Platforms
If you require NIST approval for your Windows NT applications, you may benefit from using the Crypto-C Cryptographic Services Module, a DLL that is compliant with the FIPS 140-1 standard. NIST may approve the use of this module in your application without requiring further testing of your application, based on the NIST certification issued to the Crypto-C module. For more information, see the \FIPS140 folder on the Crypto-C CD-ROM for Windows NT.

PKCS Compared with NIST

In some cases, such as the RSA algorithm, the PKCS standards differ from the NIST standards. In such cases, the standard you choose depends primarily on the scope of your application and how it will be deployed.
As mentioned previously, the PKCS standards, many of which have been in place for a long time, have widespread acceptance and are used as the base for many other higher-level standards (for example, S/MIME, SET, IPSec, and SSL). Therefore, if you are implementing one of these higher-level standards, or if you want compatibility with other applications that use the PKCS standards, you should use the PKCS-based implementation.
However, the United States government may have specific standards requirements for certain government agencies and for government contractors. These are usually the standards as defined by NIST. If you are creating applications for U.S. government use, you should ensure that you are in compliance with any required protocols.
Chapter 1 Introduction 5
Cryptographic Standards and Crypto-C

ANSI X9 Standards and Crypto-C

Crypto-C also complies with a number of standards established by the X9 Financial Services Industry committee of the American National Standards Institute (ANSI). If you are writing a financial or government application that must comply with one of the X9 standards, you may benefit by using Crypto-C. This release is fully compliant with the following ANSI X9 standards:
The ANSI X9.31 Standard, which specifies an implementation of RSA Digital
Signatures (rDSA). (Note that this implementation also complies with the NIST standard for rDSA, specified in FIPS PUB 186-2, as mentioned previously.)
The ANSI X9.62 Standard, which specifies an implementation of the Elliptic
Curve Digital Signature Algorithm (ECDSA).
For more information, see the X9 Web site at
http://www.x9.org.
6 RSA BSAFE Crypto-C Developers Guide
Chapter 2

Quick Start

This chapter provides an introduction to using Crypto-C. You are first presented with the Crypto-C model and then you are presented an introductory example. This chapter is organized as follows:
The Six-Step Sequence
Introductory Example
Decrypting the Introductory Example
Multiple Updates
Summary of the Six Steps
7

The Six-Step Sequence

The Six-Step Sequence
The Crypto-C model generally follows a six-step sequence:
1. Create
2. Set
3. Init
4. Update
5. Final
6. Destroy
In addition, for every application, you must include the necessary header files; we will call this Step 0.
The six-step sequence makes it easier to maintain your code. For example, if you have implemented a message digest routine using MD2 and wish to use SHA1 instead, you simply need to make changes in Steps 2 and 3, Set and Init. The rest of your code can be reused. Similarly, if you originally programmed a routine under the assumption that it would get all the data from a single buffer, and you want to modify it to take data from multiple buffers, you can simply change Step 4, Update.
Note: In some cases, an algorithm may not require an Update step. The sections in this chapter show the following:
A six-step encryption example
A six-step decryption example
An example using multiple Updates
A summary of the six-step process
8 RSA BSAFE Crypto-C Developers Guide

Introductory Example

Introductory Example
The CD containing the Crypto-C library distribution also includes sample source code to accompany this Developers Guide. One of the files on that CD, example of converting the Introductory Example into a program. Later in this manual are instructions on writing code for many Crypto-C operations. There are sample programs on the CD to accompany all the topics covered.
With the RSA BSAFE Crypto-C Reference Manual handy, we will encrypt the sentence, Encrypt this sentence. To do this, we will use what is called a stream cipher, that is, an encryption method that encrypts data one character at a time, in a single stream. The cipher we will use is called the RC4 cipher. This cipher can take a key size from 1 to 256 bytes. The RC4 cipher creates a key stream based on the key and XORs the stream of data with the key stream to create ciphertext.
introex.c, is an
The example in this section corresponds to the file
introex.c.
Step 0: Include Files
You must include the following header file and the Crypto-C library in every application you write using Crypto-C:
#include “bsafe.h”
When writing a Crypto-C application, include DEMO_ALGORITHM_CHOOSER, see
15. In addition, you must compile and link in management functions called by the Crypto-C library.
Note: For backward compatibility, the BSAFE 2.x
bsafe2.h, are still valid. If your source code contains the older names, you
should not have any problems.
Selecting an Algorithm Chooser on page
bsafe.h. If you want to use the
tstdlib.c, which contains the memory
include file names, global.h and
Step 1: Creating an Algorithm Object
Whatever operation Crypto-C performs, it does so from an algorithm object. An algorithm object is used to hold information about an algorithms parameters and to keep a context during a cryptographic operation such as encryption or decryption. For our example, we will build an algorithm object that performs encryption.
You build an algorithm object in Steps 1 to 3. As you go through these steps, you
Chapter 2 Quick Start 9
Introductory Example
specify the type of algorithm that is being used, supply any special information or parameters that the algorithm requires, and generate or supply a key for algorithms that need one.
In Step 1, we simply create the object. We do this by declaring a variable to be an algorithm object and calling
B_CreateAlgorithmObject.
In this case, we name our algorithm object
B_ALGORITHM_OBJ rc4Encrypter = (B_ALGORITHM_OBJ)NULL_PTR;
The data type
B_ALGORITHM_OBJ is defined in bsafe.h:
typedef POINTER B_ALGORITHM_OBJ;
rc4Encrypter
and declare it as follows:
where POINTER is defined in aglobal.h:
typedef unsigned char *POINTER;
and NULL_PTR is also defined in aglobal.h:
#define NULL_PTR ((POINTER)0)
So our variable, object is destroyed, it is a good idea to initialize it to
To create an algorithm object, we call
rc4Encrypter
, is a pointer. To prevent problems when the algorithm
NULL_PTR. See Step 6 for details.
B_CreateAlgorithmObject. Chapter 4 of the
Reference Manual gives the function prototypes and descriptions of all the Crypto-C calls. For
int B_CreateAlgorithmObject ( B_ALGORITHM_OBJ *algorithmObject /* new algorithm object */ );
Because argument, we have to pass the address of
B_CreateAlgorithmObject, we find:
B_CreateAlgorithmObject takes a pointer to a B_ALGORITHM_OBJ as its
rc4Encrypter
. The return value is an int. Most Crypto-C calls return either a 0 (zero), which indicates success, or a non-zero error code. After the call, look at the return value: if it is 0, continue; if not, stop. At RSA Security, the tradition is to name the return value
status
:
10 RSA BSAFE Crypto-C Developers Guide
Introductory Example
int status; do { if ((status = B_CreateAlgorithmObject (&rc4Encrypter)) != 0) break;
. . .
} while (0);
Standard RSA Security coding practices use the above do-while construct to make it easy to break out of a sequence when encountering an error. If a Crypto-C function returns a non-zero value,
break will exit the do-while, and further code dependent on
the offending call will not be executed. However, any clean-up code, such as overwriting sensitive memory with zeroes (see Step 6), can follow the
do-while and
will always execute, whether or not there was an error.
Step 2: Setting the Algorithm Object
The variable
rc4Encrypter
is now an algorithm object, but we have not yet determined what type of operations it can perform. In Step 2, we associate the algorithm object with an algorithm and supply any special information or parameters the algorithm requires. We do this with
B_SetAlgorithmInfo. Chapter 4 of the Reference Manual
gives this functions prototype and description:
int B_SetAlgorithmInfo ( B_ALGORITHM_OBJ algorithmObject, /* algorithm object */ B_INFO_TYPE infoType, /* type of algorithm information */ POINTER info /* algorithm information */ );
The first argument is
rc4Encrypter
. The second argument is an algorithm info type, or AI. In Crypto-C, you specify the type of operation an algorithm object performs by setting the object to a particular AI. Chapter 2 of the Reference Manual describes the available AIs. Each AI description also lists the information that must accompany that AI when setting an algorithm object. That accompanying information is the third argument of
B_SetAlgorithmInfo.
For our example, we want to choose a stream cipher AI. A stream cipher processes data in a stream of arbitrary length. This is in contrast to another common type of cipher, the block cipher, which processes data in blocks of a fixed size. In Crypto-C,
Chapter 2 Quick Start 11
Introductory Example
there is a single stream cipher, the RC4 cipher, and a number of AIs that can be used to implement it. For this example we will use argument to
B_SetAlgorithmInfo.
AI_RC4; we pass this as the second
The third argument is information that is specific to the AI we chose. For complex algorithms, this is input that is required by the algorithm, including parameters for algorithms that require them, “salt” and the desired number of iterations for password-based encryption, or an initialization vector for block ciphers. In our example, in Chapter 2 of the Reference Manual states that the format of the
B_SetAlgorithmInfo is NULL_PTR.
AI_RC4 is a simple algorithm that does not require any parameters; its entry
info
supplied to
Thus, we can make the call to B_SetAlgorithmInfo:
if ((status = B_SetAlgorithmInfo (rc4Encrypter, AI_RC4, NULL_PTR)) != 0) break;
Note: Once you have set an algorithm object, do not set it again. If you need an
algorithm object to perform another type of operation, create a new one.
Step 3: Init
Now that we have created and set our algorithm object, encrypt. Actually, since we havent called
B_EncryptInit, it is ready to decrypt as
well. In Step 3, we choose the operations our algorithm object can perform by supplying the desired function pointers to the Crypto-C library; we also create and set a key object that will supply the key data the algorithm needs.
Note: An algorithm object can be used for either encryption or decryption, but not
for both. You should create separate algorithm objects to handle each case.
Look at the entry for
AI_RC4 in Chapter 2 of the Reference Manual:
Crypto-C procedures to use with algorithm object:
B_EncryptInit, B_EncryptUpdate, B_EncryptFinal;
and
B_DecryptInit, B_DecryptUpdate, and B_DecryptFinal.
You may pass
From this, you can see that
(B_ALGORITHM_OBJ)NULL_PTR for all randomAlgorithm arguments.
AI_RC4 can be used with encryption or decryption
procedures; that is, it can be used to encrypt or to decrypt. We want to encrypt, so in Step 3, we will call
B_EncryptInit to initialize our algorithm object to perform
encryption. This call will also associate a key with the algorithm object.
12 RSA BSAFE Crypto-C Developers Guide
rc4Encrypter
, it is ready to
Introductory Example
See the description and prototype in Chapter 4 of the Reference Manual for
B_EncryptInit:
int B_EncryptInit ( B_ALGORITHM_OBJ algorithmObject, /* algorithm object */ B_KEY_OBJ keyObject, /* key object */ B_ALGORITHM_CHOOSER algorithmChooser, /* algorithm chooser */ A_SURRENDER_CTX *surrenderContext /* surrender context */ );
As in Step 2, the first argument is the algorithm object; once again, we use
rc4Encrypter
. The next three arguments are new.
Step 3a: Creating a Key Object
The second argument is a key object, which is used to hold any key-related information, such as the RC4 key, and to supply this information to functions that require it. Before we can pass a key object as an argument, we must create and set it. Creating a key object is similar to creating an algorithm object. We name our key object
rc4Key
and declare it as follows:
B_KEY_OBJ rc4Key = (B_KEY_OBJ)NULL_PTR;
where
B_KEY_OBJ is defined in bsafe.h:
typedef POINTER B_KEY_OBJ;
Chapter 4 of the Reference Manual gives the description and prototype of
B_CreateKeyObject:
int B_CreateKeyObject ( B_KEY_OBJ *keyObject /* new key object */ );
For our example, we use:
if ((status = B_CreateKeyObject (&rc4Key)) != 0) break;
Step 3b: Setting a Key Object
We have a key object, but it is not yet distinguished as an RC4 key. To distinguish the
Chapter 2 Quick Start 13
Introductory Example
object as an RC4 key, we need to use B_SetKeyInfo. See Chapter 4 of the Reference Manual for this functions description and prototype:
int B_SetKeyInfo ( B_KEY_OBJ keyObject, /* key object */ B_INFO_TYPE infoType, /* type of key information */ POINTER info /* key information */ );
This function is similar to just created,
rc4Key
. The second argument is a key info type (KI), and the third
B_SetAlgorithmInfo. The first argument is the key object
argument is information that must accompany the given KI. We want to use a KI compatible with RC4 encryption, so we return to the entry for our AI,
AI_RC4, in
Chapter 2 of the Reference Manual:
Key info types for keyObject in B_EncryptInit or B_DecryptInit:
KI_Item that gives the address and length of the RC4 key.
Key info types are described in Chapter 3 of the Reference Manual. Under the entry for
KI_ITEM we find that the format of ITEM structure:
typedef struct { unsigned char *data; unsigned int len; } ITEM;
len
is the length of the key in bytes. The RC4 cipher takes key sizes of 1 to 256 bytes. A
10-byte key is generally sufficient for most applications.
info
supplied to B_SetKeyInfo is a pointer to an
data
is the key data. A real application would use a random number generator to produce 10 bytes for the key (see Generating Random Numbers on page 165). For this example, we can simply use:
14 RSA BSAFE Crypto-C Developers Guide
Introductory Example
static unsigned char rc4KeyData[] = { 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x10 };
ITEM rc4KeyItem; rc4KeyItem.data = rc4KeyData; rc4KeyItem.len = sizeof(rc4keyData);
Now we can complete the call to B_SetKeyInfo:
if ((status = B_SetKeyInfo (rc4Key, KI_Item, (POINTER)&rc4KeyItem)) != 0) break;
As with algorithm objects, once you have set a key object, you should not set it again. If you need another key object, you should create a new one.
Note: In a real application, for security reasons, you might want to zeroize and free
your key data immediately after setting the key.
Now that we have created and set our key object, argument to
B_EncryptInit.
rc4Key
, we can pass it as the second
Selecting an Algorithm Chooser
The third argument to B_EncryptInit is an algorithm chooser; this is a structure that specifies which algorithm methods to link in. An algorithm method (AM) is the underlying code that actually performs the cryptographic operation. Because many AIs can perform more than one cryptographic function (for example, perform encryption and decryption), an application often has a choice of which underlying algorithm methods need to be linked in.
An algorithm chooser lists all the AMs the application will use; only these AMs will be linked in. Crypto-C comes with a demonstration application containing the algorithm chooser
DEMO_ALGORITHM_CHOOSER. You can use this algorithm chooser in
any Crypto-C application as long as the module which defines it ( compiled and linked in. However,
DEMO_ALGORITHM_CHOOSER will link in all the
algorithm methods available, even though an application might use only two or three. A developer can write an algorithm chooser for the specific application to make the
executable image smaller. See Algorithm Choosers on page 116 in this manual for
Chapter 2 Quick Start 15
AI_RC4 can
choosc.c) is
Introductory Example
instructions on writing an algorithm chooser. For the purposes of our example, we see that the Reference Manual entry for AI_RC4 states that we should use AM_RC4_ENCRYPT in our chooser. Include the following algorithm methods in your chooser:
AM_RC4_ENCRYPT for encryption B_ALGORITHM_METHOD*rc4EncryptChooser[]={ & AM_RC4_ENCRYPT, NULL};
Surrender Context
The fourth argument of B_EncryptInit is a surrender context, which controls when and how the application surrenders control during time-consuming operations. The application developer can put together an surrender function and other information. Crypto-C applications call this surrender function at regular intervals.
The surrender function can simply print out information to the user that indicates that the Crypto-C operation is currently executing, or it can provide the user with a means of halting the operation if it is taking too much time. A surrender context is not required; if none is desired, simply pass a properly cast Context on page 118 for a more detailed description of the structure. For this example, we will use
A_SURRENDER_CTX structure containing a
NULL_PTR. See The Surrender
A_SURRENDER_CTX
(A_SURRENDER_CTX *)NULL_PTR.
We can now complete our call to
if ((status = B_EncryptInit (rc4Encrypter, rc4Key, rc4EncryptChooser, (A_SURRENDER_CTX *)NULL_PTR)) != 0) break;
B_EncryptInit:

Saving the Object State (optional)

This step is optional. Refer to Saving State on page 120 for information on how to receive a buffer that contains all of the data necessary to reconstruct the object, using the call
B_SetAlgorithmState, to the state it was in at the time of calling the Get
routine. This can be done after B_EncryptInit and B_EncryptUpdate, or B_DecryptInit and B_DecryptUpdate.
Step 4: Update
In Steps 1 through 3, we created our algorithm object and initialized it with the
16 RSA BSAFE Crypto-C Developers Guide
Introductory Example
information that it needs to perform RC4 encryption. In Step 4, we can enter the data to encrypt with the
B_EncryptUpdate function. Chapter 4 of the Reference Manual
provides the following description and prototype:
int B_EncryptUpdate ( B_ALGORITHM_OBJ algorithmObject, /* algorithm object */ unsigned char *partOut, /* output data buffer */ unsigned int *partOutLen, /* length of output data */ unsigned int maxPartOutLen, /* size of output data buffer */ unsigned char *partIn, /* input data */ unsigned int partInLen, /* length of input data */ B_ALGORITHM_OBJ randomAlgorithm, /* random byte source */ A_SURRENDER_CTX *surrenderContext /* surrender context */ );
The first argument is our algorithm object,
rc4Encrypter
.
The other arguments call for the plaintext input and encrypted output. Because the output depends on the input, we start with the fifth and sixth arguments, which describe the input.
We name our input
static char dataToEncrypt[] = Encrypt this sentence.;
Crypto-C needs to know how many bytes our input is, so we use
unsigned int dataToEncryptLen; dataToEncryptLen = (unsigned int)strlen (dataToEncrypt) + 1;
If your data is not a string that is, if it does not end with a character do not use
dataToEncrypt
strlen to determine its length.
and declare it as follows:
strlen:
NULL-terminating
The output is described by the second, third, and fourth arguments. The second argument is described in the prototype as
does not mean you simply declare a variable to be
unsigned char *partOut. This
unsigned char * and pass it as the
argument. The output argument that you pass is a pointer to a buffer of allocated memory. This is an important point; see Algorithm Choosers on page 116 for a detailed discussion of this topic.
Chapter 2 Quick Start 17
Introductory Example
For now, we declare:
unsigned char *encryptedData = NULL_PTR;
For a stream cipher, the length of the encrypted (output) data is equal to the length of the input data. So we allocate
encryptedData = T_malloc (dataToEncryptLen); if ((status = (encryptedData == NULL_PTR)) != 0) break;
dataToEncryptLen
bytes with T_malloc:
The previous code sample uses the Crypto-C routine
T_malloc. Crypto-C supplies its
own memory management routines to increase code portability and to meet the special requirements of handling encrypted data. The Crypto-C memory management routines reside in the file
tstdlib.c; make sure this file is compiled and
linked in. These routines are described in Chapter 4 of the Reference Manual and in Memory-Management Routines on page 122 of this manual.
In our example, the
T_malloc routine from tstdlib.c returns a pointer to the
allocated memory. If, for some reason, it cannot allocate memory (for example, when there is not enough memory available), imperative to always check the return value of only a small number of bytes.
T_malloc also sets an unsigned char * variable; it is a
good idea to initialize this variable to
T_malloc will return NULL_PTR. It is
T_malloc, even if you are allocating
NULL_PTR. See Step 6: Destroy on page 20 for
more information. The third argument to
B_EncryptUpdate returns a value indicating how many bytes it placed into the output
buffer. It will place this value at the address specified by the pointer to the
. Make the proper declaration:
int
unsigned int outputLenUpdate;
Crypto-C might not encrypt all the input data during a call to
B_EncryptUpdate is a pointer to an unsigned int.
unsigned
B_EncryptUpdate. Any
unprocessed data will be saved in a buffer inside the algorithm object created by Crypto-C and encrypted during a subsequent call to Update (see Multiple Updates on page 29) or during the call to
B_EncryptFinal (see Step 5: Final” on page 19). This
is why it is important to keep track of how many bytes Crypto-C wrote to the output buffer.
The fourth argument to
18 RSA BSAFE Crypto-C Developers Guide
B_EncryptUpdate is the size of the output buffer. The Update
Introductory Example
function must know the size of the buffer. The Update function will not attempt to place data into unallocated memory; instead, it returns an error if it needs to place more bytes into the buffer than are allocated. In our example, we will use
dataToEncryptLen
as our output data size.
The seventh argument is a random algorithm. Recall that in Chapter 2 of the Reference Manual, the description of
AI_RC4 states:
You may pass
(B_ALGORITHM_OBJ)NULL_PTR for all
randomAlgorithm
arguments.
That is exactly what we will supply in our example. For the eighth argument, once again we pass a properly cast
NULL_PTR as the
surrender context. When we put this all together, our Update call is:
if ((status = B_EncryptUpdate (rc4Encrypter, encryptedData, &outputLenUpdate, dataToEncryptLen, dataToEncrypt, dataToEncryptLen, (B_ALGORITHM_OBJ)NULL_PTR, (A_SURRENDER_CTX *)NULL_PTR)) != 0) break;
encryptedDataLen = outputLenUpdate + outputLenFinal
Note the warning in the Reference Manual Chapter 2 entry for
AI_RC4:
Due to the nature of the RC4 algorithm, security is compromised if multiple data blocks are encrypted with the same RC4 key. Therefore, called after
B_EncryptFinal. This is because after a call to B_EncryptFinal and
B_EncryptUpdate cannot be
B_DecryptFinal, the state of the algorithm object is reset to the state in which it was following the call to B_EncryptInit and B_DecryptInit. To begin an encryption operation for a new data block, you must call
B_EncryptInit and supply a new key.
This simply means that you should not use the same key for two different encryption sessions.
Step 5: Final
B_EncryptFinal finalizes the encryption process by encrypting any data that B_EncryptUpdate could not. See Chapter 4 of the Reference Manual for the functions
description and prototype:
Chapter 2 Quick Start 19
Introductory Example
int B_EncryptFinal ( B_ALGORITHM_OBJ algorithmObject, /* algorithm object */ unsigned char *partOut, /* output data buffer */ unsigned int *partOutLen, /* length of output data */ unsigned int maxPartOutLen, /* size of output data buffer */ B_ALGORITHM_OBJ randomAlgorithm, /* random byte source */ A_SURRENDER_CTX *surrenderContext /* surrender context */ );
For our example, the first argument is
rc4Encrypter
.
The second argument is a pointer to the output buffer that we created for
B_EncryptUpdate. However, B_EncryptUpdate has already placed some data into that
buffer, so we must pass the address of the next byte that is available after the already filled bytes to the number of bytes that
The third argument is a pointer to an
unsigned int to the number of bytes it encrypted.
The fourth argument is the size of the buffer available to
B_EncryptUpdate has already written to part of the buffer, this value will be the total
size of the buffer minus the number of bytes
dataToEncryptLen-outputLenUpdate
B_EncryptFinal. That is the address of the beginning of the buffer plus
B_EncryptUpdate filled, or
unsigned int; B_EncryptFinal will set that
encryptedData
B_EncryptFinal. Because
B_EncryptUpdate has used, or
+
outputLenUpdate
.
Once again, we can pass properly cast null pointers for the fifth and sixth arguments, which are the random algorithm and surrender context.
Then, for our example, we have:
if ((status = B_EncryptFinal (rc4Encrypter, encryptedData + outputLenUpdate, &outputLenFinal, dataToEncryptLen - outputLenUpdate, (B_ALGORITHM_OBJ)NULL_PTR, (A_SURRENDER_CTX *)NULL_PTR)) != 0) break;
.
Step 6: Destroy
When you are done with an algorithm or key object, you must destroy it. The Destroy function frees up any memory that was allocated by Crypto-C and zeroizes any sensitive memory. Because you will always want to destroy the objects, place these
20 RSA BSAFE Crypto-C Developers Guide
Introductory Example
function calls after the do-while construct. That way, even if there is an error somewhere and the program breaks out of the within the
do-while, the Destroy functions will execute. In case the error occurs
before an object has been created, it is a good idea to initialize objects to an object is
NULL_PTR, the Destroy function does nothing.
do-while before executing all the calls
NULL_PTR. If
Chapter 4 of the Reference Manual gives the description and prototype of the Destroy functions:
void B_DestroyKeyObject ( B_KEY_OBJ *keyObject /* pointer to key object */ ); void B_DestroyAlgorithmObject ( B_ALGORITHM_OBJ *algorithmObject /* pointer to algorithm object */ );
For our example, we use the following:
B_DestroyKeyObject (&rc4Key); B_DestroyAlgorithmObject (&rc4Encrypter);
Note: Following these calls, rc4Key and rc4Encrypter will be set to NULL if the
objects were disposed of properly.
In addition to destroying any objects that you created, any memory you allocated must be freed when you are done with it. This means that each corresponding
T_free. Placing the T_free after the do-while guarantees that it will be
T_malloc must have a
called even if there is an error somewhere. However, there is a concern that if there is an error before the memory is allocated, then That is why it is important to initialize the pointer to
T_free is NULL_PTR, the extra call to T_free does nothing.
See Chapter 4 of the Reference Manual for the
void T_free ( POINTER block /* block address */ );
Chapter 2 Quick Start 21
T_malloc and the program breaks out of the do-while before
T_free will be called without a corresponding T_malloc.
NULL_PTR. If the argument to
T_free prototype:
Introductory Example
For this example, call T_free as follows:
T_free (encryptedData);
Note: Using
T_free means you can no longer access the data at that address. Do not
free a buffer until you no longer need the data it contains. If you will need the data later, you might want to save it to a file first.
You may want to zeroize any sensitive data before you free it. To do this, duplicate the following sequence after the
do-while. If there is an error inside the do-while
before you zeroize and free, these important tasks will still be performed:
if (rc4KeyItem.data != NULL_PTR) { T_memset (rc4KeyItem.data, 0, rc4KeyItem.len); T_free (rc4KeyItem.data); rc4KeyItem.data = NULL_PTR; rc4KeyItem.len = 0; }

Putting It All Together

Now we can put Steps 0 through 6 into a program. This program can be found in the file
introex.c:
#include "bsafe.h"
void PrintBuf PROTO_LIST ((unsigned char *, unsigned int));
void main() { B_KEY_OBJ rc4Key = (B_KEY_OBJ)NULL_PTR; B_ALGORITHM_OBJ rc4Encrypter = (B_ALGORITHM_OBJ)NULL_PTR;
/* The RC4 key is hard-coded in this example. In a real application, use a random number generator to produce the key. */ unsigned char rc4KeyData[10] = { 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x10 };
22 RSA BSAFE Crypto-C Developers Guide
Introductory Example
static char dataToEncrypt[] = "Encrypt this sentence."; unsigned char *encryptedData = NULL_PTR; unsigned int dataToEncryptLen, encryptedDataLen; unsigned int outputLenUpdate, outputLenFinal; int status;
do { dataToEncryptLen = strlen (dataToEncrypt) + 1;
/* Step 1: Create an algorithm object. */ if ((status = B_CreateAlgorithmObject (&rc4Encrypter)) != 0) break;
/* Step 2: Set the algorithm to a type that does rc4 encryption. AI_RC4 will do. */ if ((status = B_SetAlgorithmInfo (rc4Encrypter, AI_RC4, NULL_PTR)) != 0) break;
/* Step 3a: Create a key object. */ if ((status = B_CreateKeyObject (&rc4Key)) != 0) break;
/* Step 3b: Set the key object with the 10-byte key. */ rc4KeyItem.data = rc4KeyData; rc4KeyItem.len = rc4KeyDataLen;
if ((status = B_SetKeyInfo (rc4Key, KI_Item, (POINTER)&rc4KeyItem)) != 0) break;
if (rc4KeyItem.data != NULL_PTR) { T_memset (rc4KeyItem.data, 0, rc4KeyItem.len); T_free (rc4KeyItem.data); rc4KeyItem.data = NULL_PTR; rc4KeyItem.len = 0; }
/* Step 3: Init */ if ((status = B_EncryptInit (rc4Encrypter, rc4Key, DEMO_ALGORITHM_CHOOSER, (A_SURRENDER_CTX *)NULL_PTR)) != 0) break;
Chapter 2 Quick Start 23
Introductory Example
/* Step 4: Update */ encryptedData = T_malloc (dataToEncryptLen); if ((status = (encryptedData == NULL_PTR)) != 0) break;
if ((status = B_EncryptUpdate (rc4Encrypter, encryptedData, &outputLenUpdate, dataToEncryptLen, (unsigned char *)dataToEncrypt, dataToEncryptLen, (B_ALGORITHM_OBJ)NULL_PTR, (A_SURRENDER_CTX *)NULL_PTR)) != 0) break;
/* Step 5: Final */ if ((status = B_EncryptFinal (rc4Encrypter, encryptedData + outputLenUpdate, &outputLenFinal, dataToEncryptLen - outputLenUpdate, (B_ALGORITHM_OBJ)NULL_PTR, (A_SURRENDER_CTX *)NULL_PTR)) != 0) break;
encryptedDataLen = outputLenUpdate + outputLenFinal; printf ("Encrypted data (%u bytes):\n", encryptedDataLen); PrintBuf (encryptedData, encryptedDataLen);
} while (0);
/* Done with the key and algorithm objects, so destroy them. */ B_DestroyKeyObject (&rc4Key); B_DestroyAlgorithmObject (&rc4Encrypter);
/* Free up any memory allocated, save it to a file or print it out first if you need to save it. */ if (rc4KeyItem.data != NULL_PTR) { T_memset (rc4KeyItem.data, 0, rc4KeyItem.len); T_free (rc4KeyItem.data); rc4KeyItem.data = NULL_PTR; rc4KeyItem.len = 0; }
24 RSA BSAFE Crypto-C Developers Guide
Introductory Example
if (encryptedData != NULL_PTR){ T_memset (encryptedData, 0, dataToEncryptLen); T_free (encryptedData); encryptedData = NULL_PTR; }
} /* end main */
You may find it a useful exercise to compile and link this program. Also, it could also be instructive to add some print statements. For instance, what are the values of
outputLenUpdate
and
outputLenFinal
?
While it is possible to print the any kind of string, because there is no
encryptedData
NULL-terminating character. The encrypted data
, it will not be an ASCII string it is not
is binary data, so it may be more useful to print out the result byte-by-byte in hex­ASCII strings. For an example of a function that does this, see the RSA_ routine in
samples/common/source/demoutil.c. In addition, note that when writing
PrintBuf()
Crypto-C output to (and reading it from) files, it is usually more useful (in some cases, even necessary) to open the files in binary mode.
To run this exercise, first compile the
samples/make directory. Then link the object files with bsafe.lib or the
introex.c and tstdlib.c. You can find makefiles in
equivalent platform-specific library.
Chapter 2 Quick Start 25

Decrypting the Introductory Example

Decrypting the Introductory Example
Decrypting data is similar to encrypting. The RC4 cipher uses symmetric-key encryption, which means the key that was used to encrypt will be the key needed for decryption.
The example in this section corresponds to the file
dintroex.c.
Step 1: Creating an Algorithm Object
First create the algorithm object.
B_ALGORITHM_OBJ rc4Decrypter = (B_ALGORITHM_OBJ)NULL_PTR;
if ((status = B_CreateAlgorithmObject (&rc4Decrypter)) != 0) break;
Step 2: Setting the Algorithm Object
Use the same AI and parameters as for encryption:
if ((status = B_SetAlgorithmInfo (rc4Decrypter, AI_RC4, NULL_PTR)) != 0) break;
Step 3: Init
Use the same key data as for encryption. Once again, we must create and set the key object.
Step 3a: Creating the Key Object
As before, we name our key object
B_KEY_OBJ rc4Key = (B_KEY_OBJ)NULL_PTR;
Then we allocate space for the key object using
if ((status = B_CreateKeyObject (&rc4Key)) != 0) break;
26 RSA BSAFE Crypto-C Developers Guide
rc4Key
and declare it as follows:
B_CreateKeyObject:
Decrypting the Introductory Example
Step 3b: Setting the Key Object
We need to fill our key with the same 10 bytes of data we used for encryption. We must make sure that we use the same key as we used to encrypt. For our sample application, we can simply re-create the key data we had before:
static unsigned char rc4KeyData[] = { 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x10 };
Now we can complete the call to
if ((status = B_SetKeyInfo (rc4Key, KI_Item, (POINTER)&rc4KeyData)) != 0) break;
B_SetKeyInfo:
Step 4: Update
Here, we must set the buffer that will store the decrypted data; for the RC4 cipher, it should be the same size as the encrypted datas buffer:
unsigned char *decryptedData = NULL_PTR;
decryptedData = T_malloc (encryptedDataLen); if ((status = (decryptedData == NULL_PTR)) != 0) break;
if ((status = B_DecryptUpdate (rc4Decrypter, decryptedData, &decryptedLenUpdate, encryptedDataLenTotal, encryptedData, outputLenTotal, (B_ALGORITHM_OBJ)NULL_PTR, (A_SURRENDER_CTX *)NULL_PTR)) != 0) break;
Chapter 2 Quick Start 27
Decrypting the Introductory Example
Step 5: Final
if ((status = B_DecryptFinal (rc4Decrypter, decryptedData + decryptedLenUpdate, &decryptedLenFinal, encryptedDataLen - decryptedLenUpdate, (B_ALGORITHM_OBJ)NULL_PTR, (A_SURRENDER_CTX *)NULL_PTR)) != 0) break;
In the Introductory Example on page 9, the plaintext was a string. Therefore, we can compute the sum of many characters make up the decryption.
Note: For some algorithms, the decrypted data may not be a string for example,
when the want to print the decrypted data, you will not be able to because the data is in binary form, not ASCII. You could print the binary data using
RSA_PrintBuf(), or you can convert the decrypted data. Crypto-C offers
encoding and decoding functions to convert between binary and ASCII. See Converting Data Between Binary and ASCII on page 172 for more information.
decryptedLenUpdate
NULL-terminating character was not encrypted. In these cases, if you
and
decryptedLenFinal
to determine how
Step 6: Destroy
Always destroy objects when you no longer need them:
B_DestroyAlgorithmObject (&rc4Decrypter);
if (decryptedData != NULL_PTR) { T_memset (decryptedData, 0, encryptedDataLen); T_free (decryptedData); decryptedData = NULL_PTR; }
28 RSA BSAFE Crypto-C Developers Guide

Multiple Updates

Multiple Updates
An application can do multiple updates before the Final call. For example, suppose you have data from three different files that you want to encrypt into a single buffer. You could do this in three steps: read the contents of the first file into a buffer; read the next file, appending the contents to the end of the existing buffer; then append the contents of the third. But that would be clumsy if the contents of the three files are already in three buffers.
You do not have to put data together into a single buffer to encrypt it. Instead, call
B_EncryptUpdate with the first buffer, call it a second time with the second buffer, and
one last time with the third buffer. Then call finished all Updates. Similarly, you can call blocks of encrypted data.
Multiple updates can also be useful for encrypting or decrypting large amounts of data. If you need to process a one-megabyte file, you could allocate a megabyte of memory, put the entire file into that memory buffer, and call Update once. But using such a large amount of memory is impractical or even impossible in some situations. An application is more robust if it allocates a smaller buffer say, 64, 128 or 1024 bytes transfers data from the file in increments, and processes each unit with a separate call to Update. Then it can call Final once for all Updates.
B_EncryptFinal once, after you have
B_DecryptUpdate more than once with
Crypto-C does not always encrypt or decrypt an entire block during an Update call. One reason it might not handle the whole block is because of padding. Padding is used with block ciphers to ensure the data satisfies input restrictions and may add bytes to the original data. See “Padding” on page 37 for more information. Padding and pad operations (encrypting or decrypting the padding, or stripping the pad) take place in Final, so Crypto-C may keep the last few bytes of any input to an Update call in a buffer. If there is another call to Update, then the bytes in that buffer were not the last bytes of input, and Crypto-C continues to encrypt or decrypt. If the next call is to Final, the bytes in the buffer are the last bytes of input, so Crypto-C adds the pad and encrypts it, or decrypts the final bytes and strips the pad.
Note: The output of a particular update may be larger than the input, because
Crypto-C may be processing the current input plus some data in the buffer. Hence, an output buffer of an Update call should always be larger than the input length. For block ciphers, for example, the size of the output buffer may be as large as the length of the input plus the block size.
The following example demonstrates multiple updates. It corresponds to the file
multencr.c; a similar example for decryption is in the file multdecr.c. Assume that
the subroutine
Chapter 2 Quick Start 29
GetDataFromFile
gets, at most, a specified number of bytes from a file,
Multiple Updates
places them into the given buffer, and sets a flag indicating whether the bytes returned are the last ones in the file or not. Assume also that the subroutine
AppendDataToFile
called
B_CreateAlgorithmObject, B_SetAlgorithmInfo, and B_EncryptInit:
#define UPDATE_SIZE 64 #define UPDATE_OUTPUT_SIZE (UPDATE_SIZE + 16)
FILE *inputFile = (FILE *)NULL_PTR; FILE *outputFile = (FILE *)NULL_PTR;
unsigned char dataToEncrypt[UPDATE_SIZE]; unsigned char blockOfEncryptedData[UPDATE_OUTPUT_SIZE]; unsigned int dataToEncryptLen, totalBytesSoFar; unsigned int outputLenUpdate, outputLenFinal; unsigned int sizeToUpdate = UPDATE_SIZE; int endFlag, status;
do {
totalBytesSoFar = 0;
while ((status = GetDataFromFile (inputFile, sizeToUpdate, dataToEncrypt, &dataToEncryptLen, &endFlag)) == 0) { printf ("dataToEncryptLen = %i \n", dataToEncryptLen); PrintBuf (dataToEncrypt, dataToEncryptLen); if ((status = B_EncryptUpdate (encryptionObject, blockOfEncryptedData, &outputLenUpdate, UPDATE_OUTPUT_SIZE, dataToEncrypt, dataToEncryptLen, (B_ALGORITHM_OBJ)NULL_PTR, (A_SURRENDER_CTX *)NULL_PTR)) != 0) break;
appends output data to a file. Finally, assume we have already
/* Save the encrypted data. */ if ((status = AppendDataToFile (outputFile, blockOfEncryptedData, outputLenUpdate)) != 0) break;
totalBytesSoFar += outputLenUpdate; if (endFlag == 1) break; } /* end while */
30 RSA BSAFE Crypto-C Developers Guide
Multiple Updates
/* If there was an error in the above while loop, break out of the do-while construct. */ if (status != 0) break;
/* Call B_EncryptFinal once after all Updates. */ if ((status = B_EncryptFinal (encryptionObject, blockOfEncryptedData, &outputLenFinal, UPDATE_OUTPUT_SIZE, (B_ALGORITHM_OBJ)NULL_PTR, (A_SURRENDER_CTX *)NULL_PTR)) != 0) break;
/* Save the encrypted data. */ if ((status = AppendDataToFile (outputFile, blockOfEncryptedData, outputLenFinal)) != 0) break;
totalBytesSoFar += outputLenFinal;
} while (0);
/* Free up any memory allocated, save it to a file or print it out first if you need to save it. */ T_memset (dataToEncrypt, 0, sizeof (dataToEncrypt));
In the preceeding code example, we took and passed them to be
dataToEncryptLen
B_EncryptUpdate. The number of bytes of output may or may not
; check
outputLenUpdate
dataToEncryptLen
to see. If fewer than
bytes of data to encrypt
dataToEncryptLen
bytes were output, the as-yet-unencrypted input waits in a buffer. Notice that we did not allocate memory but used the stack; we did this by declaring
our buffers to be arrays of
unsigned char. This means that the operating system will
do the allocating and freeing. Also notice the call to
tstdlib.c. The T_memset routine sets all the bytes of a buffer to a particular value; in
this case, it wrote a 0 to every byte in 4 of the Reference Manual. When memory is freed, whether by a call to
T_memset, another memory management routine from
dataToEncrypt
. T_memset is described in Chapter
T_free or
automatically by the operating system, the data still exists at that location; the operating system has simply marked that area as available for use. For security, overwrite any memory that held sensitive data when you are done with it. This prevents attackers from reconstructing secrets by examining your computer’s memory.
Chapter 2 Quick Start 31

Summary of the Six Steps

Summary of the Six Steps
A typical implementation uses the six steps as follows:
Step 0: Include
Include the necessary header files. In addition, make sure that:
Your compiler can locate the Crypto-C header files.
Your compiler can locate and link in the Crypto-C library.
You compile and link in the file containing the definitions for the T_ functions; an
example is provided in
Step 1: Create
Create an algorithm object by declaring a variable to be an algorithm object and calling
B_CreateAlgorithmObject.
Step 2: Set
tstdlib.c.
Use B_SetAlgorithmInfo to associate the algorithm object with an algorithm and to supply any special information or parameters the algorithm requires.
Step 3: Init
Choose the operations the algorithm object can perform by supplying the desired algorithm methods from the Crypto-C library. If the algorithm requires a key, create and set a key object that will supply the key data that the algorithm needs.
Step 4: Update
Initiate an action. The action depends on the algorithm. Update is the only step that can be performed more than once on the same object. For example:
For an encryption or decryption algorithm, an Update step encrypts or decrypts
all or part of the data. You can use multiple Update steps to encrypt or decrypt data.
For a message digest, the Update step is used to enter the data to digest.
For a random number generator, the Update step is used to seed the random
number generation.
32 RSA BSAFE Crypto-C Developers Guide
Summary of the Six Steps
For some algorithms, such as generating a public/private key pair, there is no
Update step.
Step 5: Final
Finalize the action initiated in Step 4. Again, the finalization depends on the algorithm; for some algorithms, Final is replaced by Generate. For example:
For an encryption or decryption algorithm, the Final step encrypts or decrypts the
final portion of the data. For some algorithms, this data may need special handling, such as padding, that is different from the Update step.
For a message digest, the digest action takes place during Final.
For a random number generator, the Final (or Generate) step generates the
random bytes.
For generating a public/private key pair, the key pair generation takes place in
the Generate step.
Step 6: Destroy
Free any memory allocated in the previous steps and overwrite any sensitive memory with zeroes. The Destroy step is crucial to the security of an application.
Chapter 2 Quick Start 33
34
Chapter 3

Cryptography

This chapter contains a brief outline of the basic cryptographic principles and terminology used throughout this manual and documentation set. Refer to
Abbreviations
this documentation set. The publications listed in Related Documents on page xx provide more comprehensive discussions of cryptographic functions and operations. This chapter is organized as follows:
on page xix of the Preface for a list of terms and abbreviations used in
Terms and
Cryptography Overview
Applications of Cryptography
Choosing Algorithms
Security Considerations
35

Cryptography Overview

Cryptography Overview

Symmetric-Key Cryptography

In symmetric-key cryptography, as Figure 3-1 shows, the encrypting key is the same as the decrypting key. Using any other key to decrypt will produce incorrect results. Symmetric-key cryptography is also sometimes called secret-key cryptography, because the key used to both encrypt and decrypt must be kept secret.

Ciphers

There are two categories of symmetric encryption algorithms, block ciphers and stream ciphers. As the name implies, a block cipher processes data in blocks. A stream cipher,
on the other hand, processes a unit of data at a time, where a unit is generally a bit or byte. This allows a stream cipher to take in a variable length stream of data, encrypt it, and output a stream of ciphertext the same length as the input. Crypto-C offers the following block ciphers: DES, Triple DES, DESX, the RC2 cipher, the RC5, the RC6 cipher, and theAES cipher. Crypto-C offers the following stream cipher: the RC4 cipher.
Encryption Operation
Original
Message
Key Data
Encrypted
Message
Figure 3-1 Symmetric-Key Encryption and Decryption
36 RSA BSAFE Crypto-C Developers Guide
Encryption
Algorithm
Key
Key
Decryption
Algorithm
Decryption Operation
Encrypted
Message
Decrypted
Message
Cryptography Overview
Block Ciphers
Block ciphers encrypt data block-by-block. They can encrypt each block separately as in ECB mode, or they can use other modes to make the cipher less vulnerable to attacks based on regular patterns. A mode of operation usually combines the underlying cipher with feedback and other simple operations. The security remains a function of the cipher and not of the mode. See Modes of Operation on page 41 for more information.
Padding
When you encrypt a message using a block cipher, usually your message length will not be a multiple of the block size. Some modes can deal with variable size blocks, but others require the message be a multiple of the block size. For these modes, padding provides a solution to this problem. To pad, you add a regular pattern of bytes to the end of the last block to make it a complete block. With padding, the actual number of bytes encrypted can be as much as one block more than the original data.
Ciphers in Crypto-C
Crypto-C implements the following block ciphers:
DES
Triple DES
DESX
RC2
RC5
RC6
AES
DES
The Digital Encryption Standard, DES, is a commercial encryption US standard that has been available for over 15 years. The federal standard document FIPS PUB 46-2 describes the algorithm.
For DES, the block size is eight bytes. Therefore, the input must be a multiple of eight bytes, or else it must be padded to be a multiple of eight bytes for DES to operate in CBC or ECB modes properly. The key consists of 56 random bits and 8 parity bits, forming a 64-bit, or 8-byte, key.
Chapter 3 Cryptography 37
Cryptography Overview
Tripl e DES
Triple DES executes DES three times, which triples the number of bits in an encryption key. A number of different methods achieve this function. The technique that Crypto-C uses is depicted in Figure 3-2 on page 38.
This technique is known as EDE, or “Encrypt-Decrypt-Encrypt.” The decryption process in the middle stage of Triple DES encryption provides compatibility with DES. If the three keys are the same, the Triple DES operation is equivalent to a single DES encryption. That way, an application that has only DES capabilities can still communicate with applications that use Triple DES. If the three keys are different, the decryption in the middle will scramble the message further; it will not decrypt the first stage. Triple DES decryption is the inverse operation of the previous sequence, that is, DES decryption followed by DES encryption and then another DES decryption.
24 byte Triple DES key (including parity bits)
8 byte
message
block
First 8 bytes
of the key
DES
encryption
Figure 3-2 Triple DES Encryption as Implemented in Crypto-C
Middle 8 bytes
of the key
DES
decryption
Last 8 bytes
of the key
DES
encryption
8 byte
message
block
DESX
DESX is an RSA Security proprietary extension of the DES encryption algorithm that increases the effective number of key bits from 56 to 120 bits. Crypto-C includes DESX for backward compatibility with BSAFE 1.x versions, or as a faster alternative to Triple DES.
RC2
The RC2 cipher was developed by Ronald Rivest as an alternative to DES encryption;
38 RSA BSAFE Crypto-C Developers Guide
Cryptography Overview
it is proprietary to RSA Security. The RC2 cipher has an eight-byte block size. Therefore, the input must be a multiple of eight bytes, or be padded to be a multiple of eight bytes, for the RC2 cipher to operate properly in CBC or ECB modes.
The RC2 input key can be of any length from 1 to 128 bytes. The algorithm uses the input key to generate an effective key that is actually used for encryption purposes. Internally, the algorithm builds a key table based on the bits of the key data; the chosen number of effective key bits limits the number of possible key tables. The effective key size is variable and takes values from one bit up to 1024 bits.
Note: Control over your effective key size benefits you, because you can generate
up to 128 bytes of key data and set the algorithm to use a smaller number of effective bits, such as 80. Then, in the future, if you want to increase the number of effective key bits, you do not have to change the code that generates the key data, only the effective key bit parameter.
RC5
The RC5 cipher was developed by Ronald Rivest as an alternative to DES encryption; it is proprietary to RSA Security. It is a block cipher with the block being either 4 bytes, 8 bytes, or 16 bytes, depending on the word size. The input must be a multiple of the block size, or it must be padded to a multiple of the block size for the RC5 cipher to operate properly. The RC5 ciphers speed and security are dependent on input parameters determined by the user. These parameters are:
word size
rounds
key size (in bytes)
Word size generally refers to the size of a hardware register. For hardware implementations of the RC5 cipher, developers can take advantage of larger registers to increase speed. On chips with smaller registers, the word size can be emulated in software. Version 1.0 of the RC5 cipher accepts word sizes of 16, 32, or 64 bits. Crypto­C accepts a word size of 32 or 64 bits. The block size is twice the word size. For a word size of 32 bits, the block size is 64 bits, or 8 bytes, the same as for DES and the RC2 cipher. For a word size of 64 bits, the block size is 128 bits, or 16 bytes.
The number of rounds is the number of times the operation employs the inner encryption function. Varying the number of rounds allows developers to make a tradeoff between speed and security. The greater the number of rounds, the greater the security, but the slower the execution. The number of rounds can be anywhere from 0 (zero) to 255. For the RC5 cipher with a 32-bit word size, RSA Security recommends at least 16 rounds for applications; while no practical attacks are known
Chapter 3 Cryptography 39
Cryptography Overview
for 12-round RC5-32, recent cryptanalytic work suggests 16 rounds is now a more conservative choice. For the RC5 cipher with a 64-bit word size, RSA Security recommends at least 20 rounds.
The key size can be as little as 0 (zero) and as many as 255 bytes. The RC5 cipher uses the secret key bytes to generate an expanded key table during the Init phase. The key table is then used during encryption or decryption. Therefore, key length will have no appreciable effect on algorithm speed.
The RC5 cipher is more formally described as RC5 w/r/b. For instance, the RC5 cipher with a 32-bit word, 16 rounds, and a 10 byte key would be described as RC5 32/16/10.
RC6
The RC6 cipher was developed by Ronald Rivest and Matthew Robshaw, Ray Sidney, and Lisa Yin of RSA Laboratories West as a candidate for the Advanced Encryption Standard (AES)
The guidelines for the RC6 cipher were aimed at creating a cipher which could take advantage of modern computing power and architecture. These guidelines specify that a submitted algorithm must accept 16-byte blocks (8-byte word). This is in contrast to many previous block ciphers, such as DES and Triple DES, which operate only on 8-byte blocks.
In accordance with these guidelines, RC6 allows a 16-byte block size, which has the following implications:
When you use RC6 with a feedback mode in Crypto-C, your initialization vector
must be 16 bytes.
If you use RC6 with padding, the resulting output might be as many as 16 bytes
more than the input.
The full RC6 algorithm also allows you to specify different levels of security by setting the number of rounds. However, the version submitted for the AES specifies 20 rounds. At 20 rounds, RC6 provides an optimal balance between security and speed. The current implementation of Crypto-C only accepts 20 rounds.
Note: At 20 rounds, the fastest known attack on the cipher is a brute-force attack on
the key, and encryption and decryption operations are faster than with a higher number of rounds. While fewer rounds would still offer good security, there are attacks that would be faster than a brute-force attack on the key. More than 20 rounds might offer more security, but the fastest attack would still be a brute-force attack on the key, and the increased rounds number
40 RSA BSAFE Crypto-C Developers Guide
Cryptography Overview
would slow down the encryption and decryption operations. In addition, if the 20-round version of RC6 is accepted as submitted to the AES, a round count other than 20 rounds might not be AES.
AES
The National Institute of Standards and Technology (NIST) selected an alogorithm (Rijndael) as the replacement for the Data Encryption Standard (DES) in its Advanced Encryption Standard project. Crypto-C includes basic AES support.
Modes of Operation
When you use a block cipher to encrypt a message of arbitrary length, you can also choose a mode of operation.
Modes of operation can use techniques such as feedback or chaining to make identical plaintext blocks encrypt to different ciphertext blocks. Modes are designed so that they do not weaken the security of the underlying cipher, but they may have properties in addition to those inherent in the basic cipher.
Most of the modes of operation in Crypto-C are feedback modes. Feedback modes use the previous block of output to alter the current block of input before encrypting. In this way, encrypting the same block of plaintext twice will virtually never produce the same ciphertext.
A feedback algorithm requires an initialization vector, or IV, to alter the first block. The IV has no cryptographic significance. It is used to alter the first block of data before any encryption takes place; therefore, it does not need to be secret. It should be random, though, so that the first block of encrypted data is not predictable. In order to start the decryption process, it is necessary to use the IV that was employed in the encryption process.
Four Modes
Crypto-C offers the following four block cipher modes:
Electronic Codebook (ECB) mode
Cipher Block Chaining (CBC) mode
Cipher Feedback (CFB) mode
Output Feedback (OFB) mode
A brief description of these modes follows. Most cryptography texts, such as Bruce Schneiers Applied Cryptography [15], provide full descriptions of the various modes.
Chapter 3 Cryptography 41
Cryptography Overview
Electronic Codebook (ECB) Mode
ECB is not a feedback mode; it encrypts each block of input independently of all other blocks. Plaintext patterns are not concealed; instead each identical block of plaintext yields an identical block of ciphertext. This could help an eavesdropper break the code. In addition, the plaintext can be easily manipulated by removing, repeating, or interchanging blocks. The speed of each encryption operation is identical to that of the block cipher. ECB mode is as secure as the underlying block cipher.
1st message
block
2nd message
block
Figure 3-3 Electronic Codebook (ECB) Mode
Block Cipher
Key (K)
Block Cipher
Key (K)
1st cipher
block
2nd cipher
block
42 RSA BSAFE Crypto-C Developers Guide
Cryptography Overview
Cipher Block Chaining (CBC) Mode
With CBC mode, each plaintext block is XORed with the previous ciphertext block, then encrypted. CBC mode is as secure as the underlying block cipher against standard attacks. In addition, any patterns in the plaintext are concealed by the XORing of the previous ciphertext block with the plaintext block.
The decryptor follows the same sequence of steps to decrypt, using the same (secret) key and initialization vector (IV).
Initialization
Vector (IV)
1st message
block
2nd message
block
Figure 3-4 Cipher-Block Chaining (CBC) Mode
XOR
XOR
Block Cipher
Key (K)
Block Cipher
Key (K)
1st cipher
block
2nd cipher
block
An initialization vector is added to the beginning of the plaintext before encryption. This gives you something to XOR the first block with and ensures that identical plaintexts encrypt to different ciphertexts.
Cipher Feedback (CFB) Mode
In cipher feedback (CFB) mode, the cipher object acts as a byte generator. CFB mode encrypts the previous block of ciphertext and XORs the plaintext with this block to produce ciphertext. For the first block, the initialization vector is encrypted. CFB mode is as secure as the underlying cipher against standard attacks. In addition, any patterns in the plaintext are concealed by XORing the previous ciphertext block with the plaintext block.
Chapter 3 Cryptography 43
Cryptography Overview
1st message
block
P
1
Initialization
Vector (IV)
Block Cipher
Block Cipher
Figure 3-5 Cipher Feedback (CFB) Mode
Key (K)
Key (K)
B
1
B
2
XOR
2nd message block
P
2
XOR
To encrypt plaintext using CFB mode:
1. Generate your key and your IV.
2. Encrypt the IV with the key to get a block of output, B
3. XOR B
ciphertext, C
4. Encrypt C
5. XOR B
block of ciphertext, C
6. Repeat Steps 4 and 5 until the entire text is encrypted.
with the first block of your plaintext, P1, to get the first block of
1
.
1
with the key to get the second block of output, B2.
1
with the second block of your plaintext message, P2, to get the second
2
.
2
1st cipher
block
.
1
C
1
2nd cipher block
C
2
To decrypt the ciphertext, the decryptor uses the same (secret) key and initialization vector and follows the same sequence of steps.
CFB mode does not require padding. If your data length is not a multiple of the block size, simply truncate the final block of output to be the same size as the final segment of the data, and then XOR it. You can use CFB mode to encrypt a stream of data.
44 RSA BSAFE Crypto-C Developers Guide
Cryptography Overview
Output Feedback (OFB) Mode
Output feedback mode is similar to CFB mode, except that the quantity XORed with each plaintext block is generated independently of both the plaintext and the ciphertext.
To encrypt a plaintext using OFB, first generate the “output” used for encryption. This is intermediate data that is used in the encryption process. In OFB, the output depends only on the key and the initialization vector.
1. Generate your key and your IV.
2. Encrypt the IV with the key to get a block of output, B
3. Encrypt B
4. Continue encrypting recursively: encrypt B
with the key to get the second block of output, B2.
1
to get B
i
This process gives you an arbitrarily long sequence of pseudo-random blocks that you can use to encrypt the data. To use the output to encrypt:
5. XOR your plaintext with the output, block by block. The result of the XOR is the
ciphertext.
OFB does not require padding. If your data length is not a multiple of the block size, simply truncate the final block of the output to be the same size as the final segment of the data, and then XOR it.
i+1
.
1
.
The decryptor can use the same (secret) key and IV to generate the same sequence of output blocks and XOR the sequence with the ciphertext to recover the plaintext.
Chapter 3 Cryptography 45
Cryptography Overview
1st message
block
Initialization
Vector (IV)
Block Cipher
Key (K)
Block Cipher
Key (K)
Figure 3-6 Output Feedback Mode (OFB)
XOR
2nd message
block
XOR
1st cipher
block
2nd cipher
block
Stream Ciphers
A stream cipher processes the input data one unit at a time. A unit of data is generally a byte, or sometimes even a bit. In this way, encryption or decryption can execute on a variable length of input. The algorithm does not have to wait for a specified amount of data to be input before processing, nor does it have to append and encrypt extra bytes.
RC4
The RC4 cipher is a symmetric stream-encryption algorithm developed by Ronald Rivest and proprietary to RSA Security. It is actually a keyed pseudo-random sequence. It uses the provided key to produce a pseudo-random number sequence which is then XORed with the input data. This means that the encryption and decryption operations are identical.
The number of key bits is variable and ranges from eight to 2048 bits. Using the RC4 cipher with a key size of less than 40 bits is not recommended.
Because RC4 encryption is an XOR between the message bytes and the pseudo­random byte stream generated from the key, the same key should not be used more than once. Otherwise, if some of the bytes of one input message are known (or easy to
46 RSA BSAFE Crypto-C Developers Guide
Cryptography Overview
guess), an attacker would be able to determine some of the original message bytes by XORing two sets of cipher bytes.
Key
Mixing
Pseudo-
random
bytes
XOR
Nth cipher
byte
Nth message
byte
Key
Figure 3-7 RC4 Encryption or Decryption
The RC4 algorithm with MAC
The RC4-with-MAC algorithm is an extension of the RC4 cipher. It provides data integrity by using a Message Authentication Code (MAC) with the RC4 encryption algorithm. The authentication code does not provide cryptographic authentication; rather, it provides the equivalent of a checksum that can be used to determine if any errors were introduced within the cipher bytes. The MAC guards against transmission or retrieval errors, but it may not detect deliberate tampering with the data.

Message Digests

A message digest (also sometimes referred to as a one-way hash function) is a fixed­length computationally unique identifier corresponding to a set of data. That is, each unit of data (for example, a file, a string, or a buffer) will map to a particular short block, called a message digest. It is not random: digesting the same unit of data with the same message digest algorithm will always produce the same short block.
A good message digest algorithm possesses the following qualities:
The algorithm accepts any input data length.
The algorithm produces a fixed length output for any input data.
Chapter 3 Cryptography 47
Cryptography Overview
It is computationally infeasible to produce data that has a specific digest. In other
words, given a particular block of the proper size, it will be virtually impossible to determine a unit of data that will digest to that particular block.
It is computationally infeasible to produce two different units of data that
produce the same digest. In other words, given some data, it is virtually impossible to create different data that will digest to the same block as the first. This quality is also called collision-free.
Message digests have many uses. They can authenticate data, for instance. To create a digest for authentication, digest the data and save the digest. Later, if you need to see if the data has been altered, digest it again and compare the new digest to the old. If the digests are different, the data is different. Although there will exist other sets of data that will digest to the original value, it is virtually impossible to find them. Minor changes in data will produce very different digests.
Crypto-C includes the MD, MD2, MD5, and SHA1 message digest algorithms. MD is included for backward compatibility with BSAFE 1.x. MD, MD2, and MD5 produce a 16-byte digest for any input message; SHA1 produces a 20-byte digest. MD5 is the fastest message digest algorithm implemented in Crypto-C.
Note: Recent cryptanalytic work has discovered a collision in MD2’s internal
compression function, and there is some chance that the attack on MD2 may be extended to the full hash function. The same attack applies to MD. Another attack has been applied to the compression function on MD5, though this has yet to be extended to the full MD5. RSA Security recommends that before you use MD, MD2, or MD5, you should consult the RSA Laboratories Web site at
http://www.rsasecurity.com/rsalabs to be sure that their use is consistent
with the latest information. One bulletin that discusses this issue is Recent Results for MD2, MD4, and MD5; it can be found at
http://www.rsasecurity.com/rsalabs/bulletins/.
Message Digests and Pseudo-Random Numbers
Random number generation (for software implementation, usually pseudo-random number generation) is a key component of cryptographic operations. Random numbers are usually used as cryptographic keys or as a basis for generating keys. Crypto-C uses message digest algorithms with a random seed for generating random numbers. See Pseudo-Random Numbers and Seed Generation on page 92 for a discussion of the security considerations of random number generation.
48 RSA BSAFE Crypto-C Developers Guide
Cryptography Overview
Hash-Based Message Authentication Codes (HMAC)
A hash-based message authentication code (HMAC) combines a secret key with a message digest to create a message authentication code. This method of creating a MAC makes it possible to update the underlying message digest if a new attack makes the original message digest unsecure. Crypto-C provides an HMAC implementation based on SHA1.
Recall that SHA1 produces a 20-byte digest; in addition, we need to know that SHA1 takes input in 64-byte blocks.
Given a message M and a key k, the HMAC of M is computed as follows:
1. Create two different fixed strings that are used in the calculation:
ipad = the byte opad = the byte
2. Extend k to 64 bytes in length by appending zeros to the end of k. For example, if k
is 25 bytes, append 39 copies of the zero byte k’.
3. Compute the following:
SHA1(k XOR opad
where
|| denotes concatenation.
0x36 repeated 64 times
0x5C repeated 64 times
0x00. We will call the extended key
|| SHA1((k’ XOR ipad) || M))
The same key can be used for multiple authentications, but the key should be replaced periodically. For security considerations, the key should be at least as long as the message digest output. For SHA1, this means an HMAC key should be at least 20 bytes. If the key is weakly random”—that is, if knowing some of the key bits might help an attacker generate other key bits, then a longer key should be used.

Password-Based Encryption

Password-based encryption (PBE) generates a symmetric key from a password, and encrypts data using that generated key. Usually, though, a password will not have enough effective random bits to qualify as a candidate for a key or even a random seed to generate a key. For example, each character of an 8-byte alphanumeric password that also allows case-sensitive letters has the equivalent of slightly less than six bits of randomness. For eight-character passwords, this is far less than the required key size of a block cipher such as DES.
Therefore, a good PBE implementation not only uses the password, but mixes in a random number, known as a salt, to create the key (see Figure 3-8 on page 50).
Chapter 3 Cryptography 49
Cryptography Overview
Normally, the mixing is a message digest. This makes the task of getting from password to key very time-consuming for an attacker. Digesting a password with a salt helps thwart dictionary attacks. An attacker could put together a “dictionary” of keys generated from likely passwords, and try out each key on encrypted data. This would greatly reduce the amount of work necessary to find the key and may make it feasible to recover encrypted material. With a salt, the attacker would have to create a dictionary of keys generated from each password, but each password would then have to have a dictionary of each possible salt.
Crypto-C uses the methods described in PKCS v1.5 to implement password-based encryption. The methods use a message digest algorithm with a specific means of padding to increase the search space for dictionary attacks against the key. The applicable Algorithm Information Types (AIs) are: AI_MD2WithDES_*, AI_MD2WithRC2_*, AI_MD5WithDES_*, AI_MD5WithRC2_*, and AI_SHA1WithDES_*.
Password
Pseudo-random
bytes
Figure 3-8 DES Key and IV Generation for Password Based Encryption
Salt
8 bytes
Key
Message digest
I V
8 bytes

Public-Key Cryptography

In 1976, Stanford graduate student Whitfield Diffie and Stanford professor Martin Hellman invented public-key cryptography. In this system, each person owns a pair of keys, called the public key and the private key. The owner of each key pair publishes the public key and keeps the private key secret.
Suppose Alice wants to send a message to Bob. She finds his public key and encrypts
50 RSA BSAFE Crypto-C Developers Guide
Cryptography Overview
her message using that public key. Unlike symmetric-key cryptography, the key used for encryption will not decrypt the message. That is, knowledge of Bobs public key will not help an attacker. To decrypt a message, Bob uses his private key. If Bob wants to respond to Alice, he can encrypt his message using her public key.
To understand this idea, think of taking a number to a power. For instance, given values x and y, compute z=x
1/y
z
. You end up with the original x, because z
y
. To recover x, you would not compute zy, but rather
1/y
=(xy)
1/y
= x
y·1/y
= x1= x. You need two values to perform this exercise: a public key,y, to compute the encrypted value, and the inverse of the public key, or a private key,1/y, to recover the original value.
This example, of course, is not practical because if you made y public, anyone could easily compute 1/y and know your private key. Therefore, a good public-key cryptosystem relies on a key pair for which it is impossible (or at least intractable) to derive the private key from the public key.
Public Key
Input
Message
Encrypted
Message
The decrypted message is equal to the input message
if the public and private keys form a key pair.
Public Key
Cryptosystem
Encryption Operation
Private Key
Public Key
Cryptosystem
Decryption Operation
Encrypted
Message
Decrypted
Message
Figure 3-9 Public-Key Cryptography
In practice, public-key algorithms are slow compared to symmetric-key algorithms. Therefore, they are more often used for shorter messages, such as encrypting the symmetric key for a message encrypted with a symmetric cipher, or for encrypting a digest.
The RSA Algorithm
The RSA algorithm is a public-key cryptosystem for both encryption and
Chapter 3 Cryptography 51
Cryptography Overview
authentication that MIT professors Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman invented in 1977. It is actually similar to the example in the previous section that takes numbers to a power, except that it works in modular math.
Modular Math
Modular math uses a positive integer as a modulus; the only numbers under consideration are the integers from 0 to one less than the modulus. So for mod n, only the integers from 0 to (n–1) are valid operands, and the results of operations will always be numbers from 0 to (n–1). When an operation such as addition or multiplication would give a result that is greater than the modulus, the remainder of the result after division by n is used instead. Therefore, two numbers are equal mod n if and only if their difference is an even multiple of n.
For example, think of military time where the modulus is 2400. For instance, 2200 hours (10:00 P.M.) plus 4 hours is not 2600, but 0200 hours, or 2:00 in the morning. Likewise, if we start at 0, or midnight, 6 times 5 hours (say six 5-hour shifts) is not 3000, but 0600, or 6:00 A.M. the following day.
Another aspect of modular math is the concept of an inverse. Two numbers are the inverse of each other if their product equals 1. For instance, 7·343 = 2401, but if our modulus is 2400, the result is (7·343) mod 2400 ≡ 2401 2400 = 1 mod 2400.
Prime Numbers
The RSA algorithm also employs prime numbers, or primes. A prime number is a number that is evenly divisible by only 1 and itself. For example, 10 is not prime because it is evenly divisible by 1, 2, 5, and 10. But 11 is prime, because its only factors are 1 and 11.
MultiPrime Numbers
MultiPrime RSA functionality was added to Crypto-C V5.1. This new function allows you to generate RSA public/private key pairs. RSA MultiPrime key generation follows the same steps as standard RSA key generation with only a couple of exceptions: the use of a different AI, AI_RSAMultiPrimeKeyGen, and a different AM, AM_RSA_MULTI_PRIME_KEY_GEN, must be passed in during the B_GenerateInit call.
The RSA Algorithm
The RSA algorithm works as follows: take two large primes, p and q, and find their product n = pq; n will be the modulus. Choose a public value, e (also known as the public exponent), that is less than n. There are other constraints on e that are described
52 RSA BSAFE Crypto-C Developers Guide
Cryptography Overview
below. To compute ciphertext c from a plaintext message m, find c = me mod n. To decrypt, determine the private key d, the inverse of e, and compute m = c
d
mod n. The relationship between e and d ensures that the algorithm correctly recovers the original message m, because c
d
= (me)d = med m1 = m mod n. Only the entity that knows d can
decrypt. The security of the system relies on the fact that if you know p, q and e, it is easy to
compute d; but if you know only n and e, it is more difficult to determine d. This is due to the following property of the math: the value d is actually not the inverse of e mod n, but rather the inverse of e mod (p–1)(q–1). The value you pick for e must be relatively prime to (p–1)(q–1), which means e and (p–1)(q–1) share no common factors, so that there exists d such that ed 1 mod (p–1)(q–1). Therefore, you find the private value using a modulus of (p–1)(q–1), but when you apply the RSA algorithm to encryption or decryption, you use a modulus of n = p·q.
Why, if d is the inverse of e mod (p–1)(q–1), does c
d
= (me)d = med = m1 = m mod n? Arent we mixing moduli? That is the quirk of the math; it may seem counterintuitive, but this mixing of moduli is what makes the algorithm work. A complete proof of this fact is beyond the scope of this chapter, so if you want to learn more about the underlying mathematical principle, find a math book that discusses Eulers phi­function.
Incidentally, in practice, you would generally pick e, the public exponent first, then find the primes p and q, which satisfy the requirement that e be relatively prime to (p–
1)(q–1). Consider the following example with small numbers. Choose public exponent e =3.
Then, let p =5 and q = 11, which means n = 55 and (p–1)(q–1) = 40. This is a valid p and q combination because 3 is relatively prime to 40. The inverse of 3 mod 40 is 27.
(3·27) = 81 81 – (2·40) = 81 – 80 = 1 3·27 = 1 mod 40
Apply the RSA algorithm with these parameters to the plaintext messagem = 2.
e=23
c = m
=8 mod 55 This yields an encrypted message of 8. To decrypt, raise the message to the power of the inverse of 3, which is 27.
d=827
c
mod 55
Rather than computing 8
16+8+2+1=816·88·82·81
8
Chapter 3 Cryptography 53
27
directly, a shortcut would be to compute:
= 2 mod 55
Cryptography Overview
The calculation is shown in Table 3-1:
Table 3-1 Calculation of 8
0
8
1
8
2
8
4
8
8
8
16
8
1
2
8
· 8
1
(8
· 82) · 8
1
(8
· 82 · 88) · 8
8
16
27
mod 55
81 · 81 = 8 · 8 = 64
82 · 82 = 9 · 9 = 81
64 – 55 = 9 9 mod 55
81 – 55 = 26 26 mod 55
84 · 84 = 26 · 26 = 676 676 – (12 · 55) = 16
88 · 88 = 16 · 16 = 256 256 – (4 · 55) = 36
8 · 9 = 72
72 – 55 = 17
17 · 16 = 272 272 – (4 · 55) = 52
52 · 36 = 1872 1872 – (34 · 55) = 2
1 mod 55
8 mod 55
16 mod 55
36 mod 55
52 mod 55
2 mod 55
Summary
Take two large primes, p and q, and find their product n = p · q. Set n to be the modulus. Choose a public exponent, e, less than n and relatively prime to (p–1)(q–1). Find d, the inverse of e mod (p–1)(q–1), that is, ed 1 mod (p–1)(q–1). The pair (n,e) is the public key; d is the private key (or the private exponent). The primes p and q must be kept secret or destroyed.
To compute ciphertext c from a plaintext message m, find c = m original message, compute m = c
d
mod n. Only the entity that knows d can decrypt.
e
mod n. To recover the
Note: In public-key cryptography, it is also possible to encrypt using a private key.
In this case, the sender takes the plaintext input and the private key and follows the same steps need to decrypt an encrypted file. This creates a ciphertext that can be read using the public key; to read it, the recipient follows the same steps needed to encrypt with the public key and restores it to the plaintext. This is used in authentication and digital signatures.
Security
The security of the RSA algorithm relies on the difficulty of factoring large numbers. In theory, it is possible to obtain the private key d from the public key (n,e) by factoring n into p and q. To find d, one must know the product (p–1)(q–1). But to find that value, one must know p and q. For example, in the earlier example, an attacker would know that p · q=55, but what is (p–1)(q–1)? Factoring 55 into its component primes is easy: the answer is 5 and 11.
54 RSA BSAFE Crypto-C Developers Guide
Cryptography Overview
However, for very large numbers, factoring is very difficult. The RSA Laboratories publication, Frequently Asked Questions About Todays Cryptography (the FA Q), describes the state of the art in factoring. Factoring numbers takes a certain number of steps, and the number of steps increases exponentially as the size of the number increases. Even on supercomputers, the time to execute all the steps is so great that for large numbers it could take years to compute. Within a short period of time, the current threshold of general numbers that can be factored will probably rise to 155 digits, approximately the size of a 512-bit RSA modulus. Currently, the limit to the size of an RSA modulus in Crypto-C is 2048 bits.
Digital Envelopes
A digital envelope is a way of combining the advantages of symmetric-key and public­key cryptography. In general, public-key algorithms are slower than symmetric-key ciphers, and for some applications may be too slow to be of practical use, while for symmetric-key ciphers, there is the problem of transmitting the key. A digital envelope provides a solution to this dilemma. The sender encrypts the message using a symmetric-key encryption algorithm, then encrypts the symmetric key using the recipients public key. The recipient then decrypts the symmetric key using the appropriate private key and decrypts the message with the symmetric key. In this way, a fast encryption method processes large amounts of data, yet secret information is never transmitted unencrypted.
Optimal Asymmetric Encryption Padding (OAEP)
Optimal Asymmetric Encryption Padding (OAEP) is a general class of methods for constructing digital envelopes from public-key encryption algorithms. OAEP methods have been proposed for the RSA algorithm. OAEP thwarts the Bleichenbacher attack on PKCS #1 digital envelopes.
Recent research by cryptographer Daniel Bleichenbacher of Bell Labs, the research and development arm of Lucent Technologies, indicates that the combination of PKCS #1 and SSL is potentially vulnerable to a class of attacks known as Adaptive Chosen Ciphertext Attacks. Such a potential attack relies on sending a million carefully constructed messages to a target server and observing the variations in the servers response. The potential attack is detectable by network administrators because of the large number of needed messages. The threat is only against digital envelopes; it does not affect digital signatures.
OAEP is a pre-processing step that is applied to data before it is encrypted and after it is decrypted. OAEP prevents a wide range of attacks on the envelope format and ensures that the attacker must break the underlying cryptographic algorithm in order
Chapter 3 Cryptography 55
Cryptography Overview
to reveal the contents of a digital envelope. The main features of OAEP are redundancy and randomization. The redundancy feature
makes it difficult for an attacker to create a new derived message from an existing ciphertext message. The recipient of a derived message checks the redundancy after decrypting the message and rejects redundant messages. The PKCS #1 format has only about 16 bits of redundancy, whereas OAEP formats have 64 to 160 bits of redundancy.
The randomization feature makes each bit of the input to the public key operation dependent on each bit of the message and on 64 to 160 bits of randomness. This makes it difficult for chosen input attacks to work, and it causes ciphertext tampering to change many bits in the decrypted message.
Together, redundancy and randomization create verifiable properties for securing digital envelopes.
Sealing Operation
Envelope Open Operation
Message
Symmetric
Key Data
Recipient’s
Public Key
Digital
Envelope
Encrypted
Message
Symmetric-Key
Encryption
Symmetric Key
Public-Key Encryption
Encrypted
Key
Private-Key
Decryption
Private Key
Figure 3-10 Digital Envelope
Encrypted
Message
Encrypted
Data-Encrypting
Key
Symmetric-Key
Decryption
Key
Digital
Envelope
Message
56 RSA BSAFE Crypto-C Developers Guide
Cryptography Overview
Authentication and Digital Signatures
Suppose Alice and Bob are disputing a contract. Alice says that Bob must uphold certain obligations because he agreed to them in a contract. Bob says that this is not the contract he signed. He offers as evidence his copy of the contract and sure enough, it differs from Alices. One of them has altered their copy of the contract, but who? Or maybe the dispute centers on Bobs assertion that he never signed a contract, that the signature at the bottom is not his. In that case, either Bob is not telling the truth or Alice forged his signature.
If the contract was signed physically, there are ways to determine the truth. Contracts are often filed with government agencies, so comparing Bobs and Alices copies with the third partys copy reveals who made alterations. Witnesses may also sign the contract and later testify that both parties did sign it, and the signatures are not forgeries. For electronic documents, there is also a method to determine if a document has been altered or if someone truly did sign it. This method is the digital signature.
There are two types of signature algorithms. The first is a public-key cryptosystem that can perform block encryption, while the second is only capable of digital signatures. The RSA algorithm is an example of the first type. The Digital Signature Algorithm, DSA, is an example of an algorithm of the second type. Crypto-C includes the RSA and DSA signature methods.
A digital signature uses a public/private key pair to sign a document. First the signer digests the document, as described in Message Digests on page 47, then encrypts it with their private key. A good digital signature algorithm possesses the following properties:
Only the owner of a private/public key pair can generate a signature. Knowledge
of the public key does not enable anyone else to forge a signature.
Knowledge of the public key enables anyone to verify the signature.
The digital signature guarantees the authenticity of the message and its author.
The digital signature is computationally unique for each message and signer. While a normal signature can be imitated, a digital signature is immune to imitation.
Any altering of the message renders the signature invalid.
Note: If a digital signature is invalid, you cannot be sure it was a deliberate forgery.
Transmission errors will also produce errors in a digital signature.
For example, to create a digital signature on a contract:
Chapter 3 Cryptography 57
Cryptography Overview
1. Alice and Bob compose a contract in digital format. The file can be in any form,
such as a word processing file or an ASCII file.
2. Each party digests the file and encrypts the digest with their private key.
3. That encrypted digest is their digital signature.
4. The contract now consists of the file and the two copies of the encrypted digest,
one using Alices private key, the other using Bobs private key. Everyone gets copies of this contract.
The digital signature can be used to verify the data at a later time. Suppose that Bob produces a file that is different from Alices. To discover which copy has been altered:
1. Digest the new copy.
2. Decrypt each partys encrypted digest with the corresponding public key.
3. Compare the new digest to the old one.
4. If one of the new digests does not match the old one, that is the altered file.
If a file has been altered, it will produce a different digest, because it is virtually impossible to produce data that will digest to a given value. Even if someone could manipulate the digest, it would be extremely difficult to produce data that has value to anyone.
The digital signature can also be used to verify that a message came from a given person. What if Bob claims Alice forged his digital signature on the original document? He might say her copy of his encrypted digest is not the true version. However, the digest was encrypted using Bobs private key, to which only Bob has access. Therefore, it is unlikely that Alice forged Bobs signature.
The following example shows how to verify a message and its signature. Suppose you have the following information:
A message
An entity who claims to have sent the message
A block of data 96 bytes long that purports to be the encrypted digest
To verify the message and the sender:
1. Request the possible senders 768-bit (96-byte) RSA public key from a certification
authority.
2. Use that public key to decrypt the 96-byte block of data.
3. If the decryption process results in a 16-byte output, you can say it is a message
digest. There is a message that will digest to those 16 bytes, but you do not yet know what it is.
58 RSA BSAFE Crypto-C Developers Guide
Cryptography Overview
4. Digest the message file.
5. If the digest matches the 16 bytes you obtained from decrypting the original 96-
byte block, the message is verified. That is, you can assume the 96-byte block is the files digest encrypted with the RSA private key associated with the public key you used. It would have been computationally infeasible to produce that 96­byte block any other way.
There are other uses for a digital signature. Suppose that Bob wishes to buy something from Alice over the Internet. He e-mails her a credit card number. Alice can easily find out from the credit card issuer that the number she received is valid and indeed belongs to Bob. But how does she know that it was Bob who sent the number and not someone posing as Bob? She sends the purchaser a randomly generated message and asks him to digitally sign it with his private key. She then retrieves his public key from a certification authority and verifies the signature. Only the person with access to Bobs private key will be able to generate a digital signature from the message she generated in such a way that Bobs public key will verify it properly. In this way, Alice authenticates Bobs identity.
Private Key
Original
Message
Original
Message
Signature
Message
Digest
Signature Operation
Message
Digest
Public Key
RSA Public
Decryption
Verification Operation
Figure 3-11 RSA Digital Signature
RSA Private
Encryption
EQUAL?
YES
NO
Signature
Signature
Valid
Signature
Not Valid
Chapter 3 Cryptography 59
Cryptography Overview
Digital Signature Algorithm (DSA)
The Digital Signature Algorithm (DSA) is part of the Digital Signature Standard (DSS), published by the National Institute of Standards and Technology (NIST), a division of the US Department of Commerce. It is the digital authentication standard of the US government. The DSS specifies the Secure Hash Algorithm (SHA1) as the message digest to use with DSA when generating a digital signature.
To generate a DSA key pair:
1. Find a prime, p, at least 512 bits long.
2. Find a second prime, q, exactly 160 bits long that satisfies the property q|(p–1). q is
called the subprime.
3. Generate a random value, h, the same length as p but less than p.
4. Compute g = h
5. Generate another random value, x, 160 bits long. x is the private value.
6. Compute the public value: y g
Note: The three values p, q, and g (the prime, subprime, and base, respectively) are
called the DSA parameters. The parameters are public and must be generated before you can sign a message.
(p-1)/q
mod p. g is called the base.
x
mod p.
To sign a message using DSA:
1. Digest the message using SHA1. This yields a 20-byte (160-bit) digest.
2. Generate a random value, k, 160 bits long and less than q.
3. Find the following values:
= k–1 mod q
k
inv
k
r = (g
mod p) mod q xr = (x · r) mod q s = [k
4. Output the signature (r,s).
· (digest + xr)] mod q
inv
To verify a message:
1. Digest the message using SHA1.
2. From the signature (r,s), compute:
= s–1 mod q
s
inv
= (digest · s
u
1
= (r · s
u
2
60 RSA BSAFE Crypto-C Developers Guide
inv
) mod q
inv
) mod q
Cryptography Overview
u
a = g
1 mod p
u
2 mod p
b = y v = (a · b mod p) mod q
3. If v = r, the signature is verified. If v r, the signature is invalid.
The Math
To see that this is indeed the signature, consider the following. We have the values:
x
mod p
y = g
and
u
= r · s
2
Make the following algebraic substitutions:
a · b mod p = g
u1 + x·u
= g
digest·s
= g
s
inv
= g
k
= g
mod q
inv
2 mod p
+ x·r·s
inv
(digest + x·r)
mod p
u
1 · g
x·u
inv
mod p
mod p
2 mod p
Recall that:
k
mod p) mod q
r = (g
This means that:
v = (a · b mod p) mod q
k
= (g
mod p) mod q
= r
Digital Certificates
Suppose you own an RSA public/private key pair. You must make your public key public so that others can use it to verify your digital signature or to encrypt session keys when creating an RSA envelope. How do you publicize your key?
Probably the best way is to register public keys with a trusted authority. Then, this trusted authority can certify that a particular public key belongs to a particular entity. Currently, such a public key registration infrastructure exists in the form of digital certificates.
Chapter 3 Cryptography 61
Cryptography Overview
A certificate connects an entity to a public key. For instance, it can list an individual’s name, address, and public key. When people want to use a persons public key, they look up the certificate associated with that persons name and address. A certificate can contain a wide variety of information on its owner, such as the person’s organization or job title. This helps differentiate between people who have the same name. The certificate can also contain information on when it was issued or when the public key expires.
For a certificate system to work, there need to be individuals or organizations that issue and maintain the certificates. These are known as a certificate authorities, or CAs. An individual can request a certificate by presenting a CA with a public key and a name and any other identifying information. It is then the CAs responsibility to verify that the entity making the request is indeed the person identified by the information or is authorized to be associated with that key. The level of trust users place in a CA will depend on the level of verification it performs.
When you ask for an individuals public key, the CA sends the certificate and signs it with the digest of the certificate encrypted with the CAs private key. To verify that the certificate is genuine, you must digest the certificate and decrypt the signature using the CAs public key. Compare the two results: if they are the same, you have a proper certificate.
If the CA you deal with does not have a certificate for the individual in question, that CA can communicate with another CA that might have the right certificate. In fact, to find a particular certificate, a CA may have to go through a chain of CAs until it finds one that possesses the desired certificate.
Names that uniquely distinguish users are necessary for digital certificates to be of real use. The CCITT X.500 series of documents offer more discussion regarding naming conventions and related topics.
Diffie-Hellman Public Key Agreement
The Diffie-Hellman Public Key Agreement, invented by Whitfield Diffie and Martin Hellman in 1976, was the first true public-key algorithm. It provides a method for key agreement; that is, it allows two parties to each compute the same secret key without exchanging secret information. Diffie-Hellman key agreement does not provide encryption or authentication.
The Algorithm
The Diffie-Hellman algorithm is made up of three parts (see Figure 3-12 on page 63):
Parameter Generation
62 RSA BSAFE Crypto-C Developers Guide
Phase 1
Phase 2
Phase 1
Alice
Cryptography Overview
Parameters
Bob
Private value
Public value
Bob
Agreed upon
key
Phase 2
Private value
Public value
Alice
Agreed upon
key
Figure 3-12 The Diffie-Hellman Key Agreement Protocol
=
Parameter Generation
A central authority selects a prime number p of length k bytes, and an integer g greater than 0 but less than p, called the base. The central authority may optionally select an integer l, the private-value length in bits, that satisfies 2
l–1
p.
Phase 1
Each of the two parties executing the Diffie-Hellman protocol does the following:
1. Each party, i, i = 1 or 2, randomly generates a private value, which is a number, x
greater than 0 but less than the prime. If the central authority has specified the
l–1
i
= g
xi < 2l.
x
mod p.
i
length l, the private value shall satisfy 2
2. Each party computes a public value y
Chapter 3 Cryptography 63
,
i
Cryptography Overview
3. The two parties exchange the public values.
These private and public values correspond to the private and public key components of a key pair. The public value is generated in such a way that computing the private value from the public number is computationally infeasible.
Phase 2
Each participant computes the agreed-upon secret key, z, using the other participant’s public value, y', their own private value, x, and the prime, p.
x
z =(y')
mod p
Even with knowledge of the parameters and both public keys, an outside individual will not be able to determine the secret key. You must have one of the private values to determine the secret key. This means secret information is never sent over unsecure lines.
The Math
Even though the two parties involved are making computations using different private values, they will both end up with the same secret key, as illustrated by the following.
p: prime g: base x
: 1st partys private value
1
: 2nd partys private value
x
2
: 1st partys public value
y
1
: 2nd partys public value
y
2
z: secret key
In Phase 1, each party computes a private value, x
x
1
= g
1
= g
2
mod p
x
2
mod p
y
y
, and a public value, yn:
n
In Phase 2, the parties trade public values and compute the same secret key:
x
z = y
z = y
mod p
1
2
x
mod p
2
1
They both compute the same z, because:
x
x
x
x
x
= (g
)
y
1
2
= (g
2
1
1
64 RSA BSAFE Crypto-C Developers Guide
x
)
= y
mod p
2
2
1
Cryptography Overview
Security
The security of Diffie-Hellman key agreement relies on the difficulty of computing nth roots modulo a prime number. It takes very little time to exponentiate a number modulo a prime, but it takes a great deal of time to compute its roots. This problem in modular arithmetic is called the discrete logarithm problem. (Recall that, in the real numbers, if you can compute the logarithm of a number, you can easily compute all of its roots.) The RSA Laboratories publication, Frequently Asked Questions About Todays Cryptography, states, “The best discrete log problems have expected running times similar to that of the best factoring algorithms. That is, the time it takes to compute discrete logs modulo a prime of a certain length is approximately equivalent to the time it takes to factor a number of that same length. See The RSA Algorithm on page 51 for a discussion of factoring.
Multiple-Party Key Agreement
The previous protocol can be extended to more than two parties. For a multiple-party agreement, each individual chooses a private value, then uses the collection of public values from other parties to generate a common secret key.

Elliptic Curve Cryptography

Elliptic curves are mathematical constructs that have been studied by mathematicians for over 100 years. The application of elliptic curves to cryptosystems is more recent; in 1985, Neal Koblitz and Victor Miller independently devised a public-key system using a group of points on an elliptic curve.
The core of elliptic curve cryptosystems rests on the difficulty of a particular type of calculation. For some public-key algorithms, such as Diffie-Hellman key agreement, the security is based in part on the fact that given a modulus n, a number g, and g mod n, it is difficult to determine k. This is called the discrete logarithm problem. Elliptic curve cryptosystems rest on a similar problem: given an elliptic curve E and two points on the curve, P and Q, such that Q = k · P for some number k, it is difficult to determine k. This is called the elliptic curve discrete logarithm problem. (See the next subsection, Elliptic Curve Parameters, for a discussion of these terms.) Many algorithms that are based on the discrete logarithm problem can be translated to analogous algorithms based on the elliptic curve discrete log problem.
Elliptic curves can be used for a variety of public-key cryptosystems. Crypto-C supports the following elliptic curve features:
k
Generation of elliptic curve parameters
Elliptic curve key pair generation
Chapter 3 Cryptography 65
Cryptography Overview
Elliptic Curve Signature Schemes (ECDSA)
Elliptic Curve Authenticated Encryption Scheme (ECAES)
Elliptic Curve Diffie-Hellman key agreement (ECDH)
Crypto-C also allows you to generate precomputed acceleration tables to speed up certain elliptic curve operations. For more information, see the example Generating a Public-Key Acceleration Table on page 277.

Elliptic Curve Parameters

A number of parameters are necessary for elliptic curve cryptosystems. These parameters must be generated before you generate a key pair, create an acceleration table, initiate encryption, or perform key agreement with these systems. You can use the same parameters to generate more than one key. These parameters include:
The finite field, F
Two elements of F
the coefficients of the curve.
, over which the elliptic curve is defined.
q
, a and b, which define the elliptic curve; a and b are also called
q
A point P of prime order on the elliptic curve E .
The order, n, of P .
The cofactor h=#E(F
and #E(F Curve on page 70 for more information.
Note: In all discussions of elliptic curves, the upper case letters P and Q are used to
The next section discusses these terms in detail. We will try to give enough of the math to give you a feel for what the underlying concepts are without going too deeply into the details. A full discussion of elliptic curve cryptography is far beyond the scope of this manual. For background on elliptic curves, see the book by J. Silverman and J. Tate, Rational Points on Elliptic Curves [20]. For more information on elliptic curves in cryptography, see the ANSI X9.62 and X9.63 standards [13], the IEEE
Standard Specifications for Public-Key Cryptography [14], and A. Menezess book, Elliptic Curve Public Key Cryptosystems [19].
) means the number of points in that set. See The Order of an Elliptic
q
denote points on an elliptic curve. The lower case letter p is used to denote a prime.
)/n. Here, E(Fq) means the set of points on the elliptic curve
q
The Finite Field
The elliptic curves used in cryptography are always defined over a finite field, denoted F
. There are two choices for this field:
q
66 RSA BSAFE Crypto-C Developers Guide
Cryptography Overview
An odd prime field, F
A field of even characteristic, F
, where p is an odd prime.
p
m.
2
For more information about finite fields, see the book by A. Menezes, I. Blake, X. Gao, R. Mullin, S. Vanstone, and T. Yaghoobian, Applications of Finite Fields [18] and also Chapter 2 of Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone s book, Handbook of Applied Cryptography [17].
Odd Prime Fields
The odd prime field Fp is simply Zp, the integers mod p. Modular math is described in the section The RSA Algorithm on page 51. Recall that in modular math, we have addition and multiplication, with the additional twist that the numbers loop around, so that, for example, p+1 = 1 mod p.
Although you dont need it to use the cryptosystem, a little background may help. Because p is prime, F have: except for 0, every number in F number c between 1 and p–1, there is another number d in the same range such that cd = 1 mod p. This is the crucial property that distinguishes F math systems and makes it a field.
Not all moduli will give you a field. For instance, our earlier example, arithmetic mod 55, is not a field. You can see this by looking at the number 5 in this system. The first ten multiples of 5 are: 5, 10, 15, 20, 25, 30, 35, 40, 45, and 50. When we multiply 5 by 11, we get 55, which is just 0 mod 55. Now, when we multiply 5 by 12, we just fall back down to 60 = 60–55 = 5 mod 55. In fact, no matter by what we multiply 5, we will just get a multiple of 5, which will reduce back down to the ten numbers listed above. There is no way we can get to 1 as a multiple of 5 in this particular modular system.
has an interesting property that not all modular math systems
p
has a multiplicative inverse. That is, given any
p
from other modular
p
In fact, the only numbers that will give a field in modular arithmetic are the primes. So you can see that fields are fairly special. The crucial thing to remember is:
An odd prime field, F
, is just modular arithmetic, where the modulus p is prime.
p
Fields of Even Characteristic
The fields of even characteristic, also known as characteristic 2, are more complicated. If you were looking for a field of that size, you might start with the integers mod 2 However, it turns out that integers mod 2
m
cannot be a field for any m>1.
Why is this? Remember, we said every element in a field, except 0, has a multiplicative inverse. But, for example, 2
m
2
(except for m = 1). To see this, consider the product 2·2
m–1
cannot be invertible in the integers mod
m–1
= 2m≡ 0 mod 2m. If 2
did have an inverse, I, then we would have:
Chapter 3 Cryptography 67
m
.
m–1
Cryptography Overview
0=0·I
m–1
m–1
)·I mod2
·I)
(2·2 = 2·(2 2·1 mod 2
=2
m
m
Instead, we create the field F the elements of the finite field F
m in a completely abstract manner. We start by letting
2
m be the bit strings of bit-length m. Mathematicians
2
have shown that it is possible to create an addition and a multiplication that make these strings, called m-tuples, into a field.
Addition is easy to define: to add two strings, just XOR them. This is the same as adding them bit by bit, with no carry. Notice that with this field addition rule, for every x in F the integers mod 2
m, we have that x + x = 0. That is already very different from addition in
2
m
.
Note: If you look closely, you will see that we are trying to create a system where 2
can equal 0. In fact, it is because of this property that the number 1 added to itself two times gives us 0 that we say this is a field of characteristic 2 or even characteristic.
Multiplication is even more difficult to define. When you multiply two m-tuples, you cant just multiply them bit-by-bit, or else you would never be able to invert any string that had a 0 in it somewhere. Instead, multiplication in F
m is a complicated
2
operation involving ordinary multiplication and addition of cross terms. The mathematics underlying the construction of F
m is deep, but it is very well-
2
understood by mathematicians. For an in-depth discussion of this field, refer to Related Documents on page xx.
An elliptic curve, E, can be thought of as a particular type of equation. Elliptic curves look slightly different in the two different cases.
Coefficients Over an Odd Prime Field
An elliptic curve E over an odd prime field Fp is all the pairs of points (x,y) that satisfy the equation:
2=x3
y
In this equation, x and y are elements of F evaluated over F that is included as well.
The numbers a and b are called the coefficients of the elliptic curve; they are part of the
68 RSA BSAFE Crypto-C Developers Guide
+ax+b
, and so are a and b. The whole equation is
. For computational reasons, there is also a point at infinity”, Ο,
p
p
elliptic curve parameters.
Coefficients Over a Field of Even Characteristic
An elliptic curve E over a field of even characteristic F that satisfy the equation:
2
+ xy = x3+ax2+b
y
Cryptography Overview
m is all the pairs of points (x,y)
2
In this equation, x and y are elements of F evaluated over F
m. For computational reasons, there is also a “point at infinity, Ο,
2
m, and so are a and b. The whole equation is
2
that is included as well. The numbers a and b are called the coefficients of the elliptic curve; they are part of the
elliptic curve parameters.
Note: Note that the equation over F
F
m there is a quadratic term, ax
2
m is different from the equation over F
2
2
, instead of the linear term ax in the odd
. Over
p
prime case, as well as a new cross-term, xy. The differences in the equation arise because of the differences in arithmetic between the two types of fields.
The Point P and its Order
Obviously, you cant create a cryptosystem out of just any equation. The elliptic curve equation is important because it has special properties. One of these properties is that it is possible to set up an addition system that lets you add one point on the elliptic curve to another. The addition is complex and non-obvious, but it is possible to set up a system of equations that determine the sum of two points. Adding two points on an elliptic curve involves several operations in the underlying field, F multiplications, additions, and the computation of inverses. The complexity of the addition is what makes elliptic curve cryptosystems work if you add a point P to itself k times to get kP, there is no known fast way to get k.
To implement an elliptic curve cryptosystem, we need to specify a point P on our curve that has some special properties. To understand these properties, we need some more concepts: the points on a curve, the order of a curve, and the order of a point on the curve.
, including
q
The Points of an Elliptic Curve
For our field, Fq, and our elliptic curve E, determined by a and b, we can consider all the pairs (x,y) in F point of the elliptic curve. The collection of all the points that satisfy the equation, along with the special point Ο mentioned earlier, is called the points of E over F
Chapter 3 Cryptography 69
that satisfy the elliptic curve equation. Each such pair is called a
q
; this
q
Cryptography Overview
is written E(Fq).
The Order of an Elliptic Curve
The addition system that makes the points on the elliptic curve into what is called a group has a number of properties. First, there can only be a finite number of points on the curve. If every possible pair (x,y) were on the curve, there would be only p
m)2
(2
= 22m possibilities of pairs. The total number of points, including the point Ο, is
called the order of the elliptic curve. The order is written as #E(F
).
q
2
or
The special point Ο plays the role of the additive identity, zero, in the group of the elliptic curve.
The Order of a Point
Given any point on the curve, P, the addition rule lets you add that point to itself. Then you can add your new point to the old point, and so on. When you add a point to itself a number of times, it is called scalar multiplication. Although this is not multiplication in the usual sense it is an iteration of point addition k times it still has the usual math properties like commutativity and associativity over addition. Adding a point P to itself k times gives another point denoted kP.
No matter what P is, there is always some n such that nP = Ο. The smallest n that works for a given P is called the order of P. Not only does n exist, but it is always true that n evenly divides the order of the elliptic curve, #E(F
The order n of P is important because it means that when we use P as the starting point of our calculations, we can apply the rules of arithmetic modulo n. That is, we have the following important fact:
).
q
r = rmod n if and only if rP = rP
A Point of Prime Order
Now that we have those concepts, we can go on to the next parameter. Given our elliptic curve, E, defined over our finite field, F will be used to mask the private key in a public/private key pair. The properties of P are important to the security of our system. Not just any point will do: we need a point P whose order n is prime; the larger the prime, the more secure the cryptosystem.
Remember, P is of the form P =(x,y) where x and y satisfy the elliptic curve equation. To show that x and y are specific to P, we usually write them as x the special point P gives us two parameters:
A point P = (x
70 RSA BSAFE Crypto-C Developers Guide
) of prime order
P,yP
, we want to fix a special point that
q
and yP. Therefore,
P
Cryptography Overview
The order n of P
P is sometimes called the base point.
The Cofactor
We mentioned previously that the prime number n that is the order of P must evenly divide the order of the elliptic curve. That is, we know that the number h =#E(F an integer. We call h the cofactor, and set it as our last parameter:
)/n is
q
The cofactor h =#E(F
q
)/n
Summary of Elliptic Curve Terminology
Table 3-2 lists the elliptic curve parameters and gives a short description of each parameter. For a brief description,refer to the previous sections in this chapter; for a detailed discussion, see [13], [14], and [19] in Related Documents on page xx.
Table 3-2 Elliptic Curve Parameters
Notation Name Description
F
q
a, b coefficients of the curve a and b are elements of F
P point of prime order
n order of P The smallest nonzero number such that P added
h cofactor The order of the curve divided by the order of P:
base field Either:
: {0,1,...,p–1} with arithmetic mod p
F
p
or
m : strings of m bits. Addition is bitwise XOR,
F
2
multiplication exists, but has no quick description
equation, which depends on the base field:
For F
For F
(x or base point
P,yP
The pair x
to itself n times is the zero point, Ο, on the curve.
n is prime.
#E(F
. They determine an
q
:y2=x3+ax+b
p
2
m:y
+ xy = x3+ax2+b
2
)
, yP satisfies the curve equation.
P
)/n
q
Chapter 3 Cryptography 71
Cryptography Overview
Representing Fields of Even Characteristic
For fields of even characteristic (fields of the form F
m), Crypto-C allows you to choose
2
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 F mathematics underlying the construction of F
m, we use the term basis to reflect the original
2
m. From our point of view, it is most
2
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 (00001). 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 normalarithmetic using a hexadecimal or a decimal system, you can represent F
m inmore than one way.
2

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.
72 RSA BSAFE Crypto-C Developers Guide
Cryptography Overview
Creating the Key Pair
To compute a public/private key pair:
1. Generate a random value, d, between 1 and n–1.
2. Compute the elliptic curve point dP, that is, P added to itself d times. Call this
point Q; it is a pair of field elements (x
Q,yQ
).
The key pair is (Q,d): Q is the public key, d is the private key. As previously mentioned, even if you know P and Q, you cannot easily calculate d.

ECDSA Signature Scheme

Once you have generated elliptic curve parameters and created a public/private key pair, you can use this information to create an elliptic curve analogue of the Digital Signature Algorithm (DSA).
Signing a Message
The holder of the private key can sign a message as follows:
1. Digest the outgoing message using SHA1. This yields a 20-byte (160-bit) digest, e.
2. Compute a random value, k, between 1 and n–1.
3. Compute the elliptic curve point kP = (x
4. Currently, the first coordinate, x
, is an element of the finite field. To perform
1
further calculations, we must convert x follows:
For F
, x1 is an integer α in the range 0 to p–1. Let = α. (Essentially, no
p
conversion is required.) For F
m, x
is a bit string of length m bits: s1s2...sm. Because F
2
1
arithmetic, we need a way to think of its elements as integers. To do this, let the integer
be a weighted sum of the bits of x1:
x
1
m
x
=
1
i1=
).
1,y1
to an integer, called . We do this as
1
x
1
mi()
2
si⋅
x
1
m has a very strange
2
In either case, once you have calculated , set r= . If r is zero, go back to step 2.
Note: Although this lets you take a member of the field F
x
1
x
1
m and represent it as an
2
integer, it has some limitations. If you perform any arithmetic operations on
Chapter 3 Cryptography 73
Cryptography Overview
, you will be using regular arithmetic. This is so different from arithmetic in
x
1
F
m that, for example, . However, if you convert two field
2
x1x2+x1x2+
elements and perform operations on them that show they are equal after conversion, then they were equal before conversion.
5. Compute s = k
–1
(e+dr)mod n. Again, you must check that s is nonzero.
The signature for this message is the pair r and s. Notice that, as with DSA, the signature depends on both the message and the private key. This means no one can substitute a different message for the same signature.
Note: The previous equation is merely an outline. For cryptographic purposes, it is
necessary to verify that certain numbers are nonzero, or that they satisfy other conditions. Crypto-C makes the appropriate verifications when it generates your key pair.
Verifying a Signature
When a message is received, the recipient can verify the signature using the received signature values and the signers public key, Q. Because the pair (r,s) that has been received may not actually be a valid signature pair, it is customary to call the received pair (r’,s) instead.
To verify a signature:
1. First verify that r and s are between 1 and n-1. If they are not, the output is
invalid.
2. Digest the received message using SHA1. This yields a 20-byte (160-bit) digest, e.
3. Compute c = (s’)
-1
. Remember, s is an integer mod n, so its inverse is also an
integer mod n.
4. Compute u
5. Compute the elliptic curve point (x
6. Convert x
7. Compute v = mod n
= ec mod n and u2= rc mod n.
1
)=u1P +u2Q.
1,y1
to an integer, . See Step 5 on page 74 for details.
1
x
1
x
1
If v = r, the signature is verified. If they are different, the signature is invalid.
The Math
The ECDSA algorithm depends in part on the fact that if r = r’ mod n, then rP = rP. (See The Point P and its Order on page 69.)
74 RSA BSAFE Crypto-C Developers Guide
Cryptography Overview
The following calculations are really just a series of substitutions that can be made by looking back at the definition. You may find it more convincing to go through the substitution steps yourself, by glancing back at the preceding sections Creating the Key Pair, Signing a Message, and Verifying a Signature.
If the message has been signed correctly, then s = s. Expanding the elliptic curve point (x
Recall that Q =dP, so:
Now recall that s = k
)=u1P +u2Q calculated by the recipient, we see that:
1,y1
P +u2Q =es–1P + rs-1Q
u
1
–1
=s
(eP +rQ)
u
P +u2Q =s–1(eP +rQ)
1
–1
=s
(eP +rdP)
–1
(e + rd)P
=s
–1
=s
(e + dr)P
–1
(e+dr)mod n, so:
P +u2Q =s–1(e + dr)P
u
1
–1
=[k
(e+dr)]-1(e + dr)P
–1)–1
= (k = kP
(e+dr)–1(e+dr)P
This is the point calculated by the recipient. But this is also the point generated by the sender. The recipient then checks that the x-coordinate of the calculated point is in fact the x-coordinate that was received.

Elliptic Curve Authenticated Encryption Scheme (ECAES)

You can use elliptic curves to create an authenticated encryption scheme with a public/private key pair.
As always with elliptic curves, we assume that the elliptic curve parameters have been defined in advance. Suppose Bob has a key pair based on these parameters. The pair is (Q,k elliptic curve parameters. The point Q is the public value and the number k private value.
Chapter 3 Cryptography 75
), where Q = k2P, where P is the base point of prime order specified in the
2
is the
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, k
2. Compute the elliptic curve point Q
, between 1 and n – 1.
1
= k1P. This will be transmitted along with the
1
encrypted message.
3. Compute the elliptic curve point S
= k1Q. S1 is a pair (x1,y1). This is the secret
1
information the sender uses to encode the message.
4. Compute a one time pad, otp, of length f, from x
using a key derivation function
1
(KDF). otp is a concatenation of a series of hashes; it is constructed using f, x 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
00000001
b. For i = 1 to [f/160], create a series of hashes, as follows:
Compute Hash concatenation of x
.
16
= SHA1(x1 || counter), that is, the SHA1 hash of the
i
and counter.
1
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:
, and
1
||
Hash
Hash
d. Set otp to be the concatenation of the series of hashes:
otp = Hash
5. Compute M= otp XOR M.
76 RSA BSAFE Crypto-C Developers Guide
=
[f/160]
{
the [f/160] – (160 × [f/160]) leftmost bits of Hash
|| Hash2 |||| Hash
1
if f/160 is an integer
[f/160]
if f/160 is not an integer
[f/160]
[f/160]-1
|| Hash
[f/160]
Cryptography Overview
6. Compute an authentication tag, tag = SHA1 (x
hash of concatenation of the x-coordinate of the secret point k
|| M). That is, tag is the SHA1
1
Q and the message
1
M. Since tag is an SHA1 hash, tag is 20 bytes long.
7. Transmit the ciphertext c =(Q
,M,tag). The total length of c in bytes is: 21+2 · (the
1
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 =(Q
2. Use the private key k
). If the message was transmitted correctly and encoded with the correct
(x
2,y2
public key, S
3. To v er i fy tha t S
is equal to S1.
2
2
to compute the elliptic curve point S2= k2Q1. S2 is a pair
2
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 x
function outlined in Step 4 on page 76. Use x otp’ = otp.
5. Compute M = otp XOR M’.
,M,tag) into its components, Q1, M, and tag.
1
using the key derivation
2
instead of x1. Since x1 = x2,
2

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.
Chapter 3 Cryptography 77
Cryptography Overview
Phase 1
The first party randomly generates a private value, a number k1, greater than 0 but less than n. Similarly, the second party generates a random private value, k
Each party then computes a public value. To do this, they each compute R each party, this is an elliptic curve point. The two parties exchange their public values.
These private and public values correspond to the private and public key components of a key pair. The public value is generated in such a way that computing the private value from the public value is computationally infeasible.
.
2
= kiP. For
i
Phase 2
Each participant computes the agreed-upon secret key, z, from the others public value, R curve point S. This is a pair, (x secret value.
Even with knowledge of the parameters and both public keys, an outside individual will not be able to determine the secret key. One must have one of the private values to determine the secret key. This means secret information is never sent over unsecure lines.
, and their own private value, ki. The parties compute kiRj to get the elliptic
j
). They then use the first coordinate of S, xS, as their
S,yS
78 RSA BSAFE Crypto-C Developers Guide
Loading...