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
See our Web Site for regional Customer Service telephone and fax numbers.
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.
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
correspondent’s authenticity, and confirm data integrity. RSA Security’s generalpurpose 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 Security’s 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, you’ll be able to use RSA BSAFE CryptoC’s algorithms at unprecedented levels of speed and throughput across a wide range
of hardware platforms. RSA BSAFE Crypto-C’s support for the Intel Itanium™ and
Pentium™4 processors will allow developers the ability to take advantage of benefits
of these powerful processors. Also, RSA Security’s 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 CryptoC.
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
xviRSA BSAFE Crypto-C Developer’s 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.
xviiiRSA BSAFE Crypto-C Developer’s 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 AbbreviationDefinition
Crypto-CRSA 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.
PKIThe 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 APIThe default application programming interface between PKI services and the
developer's application.
SPIService provider interfaces that enable customized implementation to
augment or replace the default Cert-J functionality.
User InterfaceAny 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.
2.Frequently Asked Questions (FAQ) About Today’s 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.
xxRSA BSAFE Crypto-C Developer’s 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 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
xxiiRSA BSAFE Crypto-C Developer’s 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
2RSA BSAFE Crypto-C Developer’s 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)
In addition to the cryptographic algorithms listed here, Crypto-C offers a hardware
interface that allows vendors of cryptographic hardware to support the Crypto-C
API. One such vendor is Intel®, whose Intel hardware security primitives include the
Intel Random Number Generator.
For information on using the Intel hardware (when present) with Crypto-C, see the
Intel Security Hardware User’s Guide, included on the Crypto-C CD-ROM. For
information about using Crypto-C with other cryptographic hardware, contact the
specific hardware vendor.
RSA BSAFE Crypto-C products include PKCS #11 hardware support to allow
communication with hardware like smart cards (for secure key storage) and
cryptographic accelerator cards (for performance improvements). PKCS #11 support
is in addition to the BHAPI hardware support offered in previous versions of CryptoC.
Chapter 1 Introduction3
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 Security’s 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:
4RSA BSAFE Crypto-C Developer’s 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 Introduction5
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.
6RSA BSAFE Crypto-C Developer’s 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
8RSA BSAFE Crypto-C Developer’s Guide
Introductory Example
Introductory Example
The CD containing the Crypto-C library distribution also includes sample source code
to accompany this Developer’s 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 algorithm’s 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 Start9
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
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
:
10RSA BSAFE Crypto-C Developer’s 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 function’s 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 Start11
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 haven’t 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.
12RSA BSAFE Crypto-C Developer’s Guide
rc4Encrypter
, it is ready to
Introductory Example
See the description and prototype in Chapter 4 of the Reference Manual for
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 Start13
Introductory Example
object as an RC4 key, we need to use B_SetKeyInfo. See Chapter 4 of the Reference
Manual for this function’s 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:
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:
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 Start15
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
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
16RSA BSAFE Crypto-C Developer’s 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 Start17
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
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
18RSA BSAFE Crypto-C Developer’s 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:
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 function’s
description and prototype:
Chapter 2 Quick Start19
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.
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
20RSA BSAFE Crypto-C Developer’s 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:
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.
/* 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
};
22RSA BSAFE Crypto-C Developer’s 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;
/* 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;
}
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 hexASCII 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 Start25
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
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;
26RSA BSAFE Crypto-C Developer’s 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:
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:
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 Start29
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:
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 */
30RSA BSAFE Crypto-C Developer’s 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 Start31
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.
32RSA BSAFE Crypto-C Developer’s 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 Start33
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
36RSA BSAFE Crypto-C Developer’s 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 Cryptography37
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;
38RSA BSAFE Crypto-C Developer’s 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 cipher’s 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. CryptoC 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 Cryptography39
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
40RSA BSAFE Crypto-C Developer’s 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
Schneier’s Applied Cryptography [15], provide full descriptions of the various modes.
Chapter 3 Cryptography41
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
42RSA BSAFE Crypto-C Developer’s 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 Cryptography43
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.
44RSA BSAFE Crypto-C Developer’s 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 Cryptography45
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 pseudorandom 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
46RSA BSAFE Crypto-C Developer’s 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 fixedlength 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 Cryptography47
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.
48RSA BSAFE Crypto-C Developer’s 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 Cryptography49
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
50RSA BSAFE Crypto-C Developer’s 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 Bob’s 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 Cryptography51
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
52RSA BSAFE Crypto-C Developer’s 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?
Aren’t 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 Euler’s phifunction.
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.
Apply the RSA algorithm with these parameters to the “plaintext message” m = 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 Cryptography53
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 = 99 mod 55
81 – 55 = 26 26 mod 55
84 · 84 = 26 · 26 = 676676 – (12 · 55) = 16
88 · 88 = 16 · 16 = 256256 – (4 · 55) = 36
8 · 9 = 72
72 – 55 = 17
17 · 16 = 272272 – (4 · 55) = 52
52 · 36 = 18721872 – (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.
54RSA BSAFE Crypto-C Developer’s Guide
Cryptography Overview
However, for very large numbers, factoring is very difficult. The RSA Laboratories
publication, Frequently Asked Questions About Today’s 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 publickey 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
recipient’s 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
server’s 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 Cryptography55
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
56RSA BSAFE Crypto-C Developer’s 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 Alice’s. One of them has altered their copy of the contract, but who? Or
maybe the dispute centers on Bob’s 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 Bob’s and Alice’s copies with
the third party’s 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 Cryptography57
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 Alice’s private key, the other using Bob’s 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 Alice’s. To discover which copy has been altered:
1.Digest the new copy.
2.Decrypt each party’s 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 Bob’s private key, to which only Bob has
access. Therefore, it is unlikely that Alice forged Bob’s 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 sender’s 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.
58RSA BSAFE Crypto-C Developer’s 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 file’s digest encrypted with the RSA private key associated with the public
key you used. It would have been computationally infeasible to produce that 96byte 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 Bob’s private key will be able to generate a digital signature
from the message she generated in such a way that Bob’s public key will verify it
properly. In this way, Alice authenticates Bob’s 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 Cryptography59
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
60RSA BSAFE Crypto-C Developer’s 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 Cryptography61
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 person’s public key, they
look up the certificate associated with that person’s 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 CA’s 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 individual’s public key, the CA sends the certificate and signs it
with the digest of the certificate encrypted with the CA’s private key. To verify that
the certificate is genuine, you must digest the certificate and decrypt the signature
using the CA’s 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
62RSA BSAFE Crypto-C Developer’s 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 Cryptography63
,
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 party’s private value
1
: 2nd party’s private value
x
2
: 1st party’s public value
y
1
: 2nd party’s 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
64RSA BSAFE Crypto-C Developer’s 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 Today’s 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:
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. Menezes’s 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
66RSA BSAFE Crypto-C Developer’s 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 fieldFp 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 don’t 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 Cryptography67
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
can’t 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
68RSA BSAFE Crypto-C Developer’s 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 can’t 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 Fpoint 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 Cryptography69
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 = r’ mod n if and only if rP = r’P
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
70RSA BSAFE Crypto-C Developer’s 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
NotationNameDescription
F
q
a, bcoefficients of the curvea and b are elements of F
Ppoint of prime order
norder of PThe smallest nonzero number such that P added
hcofactorThe order of the curve divided by the order of P:
base fieldEither:
: {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 Cryptography71
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 (000…01). 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
“normal”arithmetic 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.
72RSA BSAFE Crypto-C Developer’s 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 Cryptography73
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 signer’s 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= r’c 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 = r’P.
(See “The Point P and its Order” on page 69.)
74RSA BSAFE Crypto-C Developer’s 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.
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 Cryptography75
), 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.
76RSA BSAFE Crypto-C Developer’s 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 xotp’ = 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 DiffieHellman 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 Cryptography77
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 other’s 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
78RSA BSAFE Crypto-C Developer’s Guide
Loading...
+ hidden pages
You need points to download manuals.
1 point = 1 manual.
You can buy points or you can get point for every manual you upload.