## Introduction

RSA Digital Signatures are one of the most common Signatures encountered in the Digital Security world. RSA is the work of Ron Rivest, Adi Shamir, and Leonard Adleman. The system was developed in 1977 and patented by the Massachusetts Institute of Technology. Though Rivest, Shamir, and Adleman are generally credited with the discovery, Clifford c***s (Chief Mathematician at GCHQ - the British equivalent of the NSA) described the system in 1973. However, c***s did not publish (the work was considered classified), so the credit lay with Rivest, Shamir, and Adleman.

This example of RSA Digital Signature is a Digital Signature Scheme with Appendix, meaning the original message must be presented to the Verify function to perform the verification.

This is in contrast to a Digital Signature Scheme with Recovery, in which the original message is concatenated or interleaved into the signature. Digital Signature Schemes with Recovery do not require the original message for verification since it is available in the signature. Part Two of this example will focus on the code to generate a Signature with Recovery.

## Digital Signatures

Digital Signatures are the electronic world's equivalent to a handwritten signature. A Digital Signature provides the following to the cryptographer:

Note that a MAC, though similar to a Digital Signature, does not provide Non-Repudiation since both the Signer and Verifier use the same key.

## Compiling and Integrating Crypto++

The sample provided uses Crypto++ RSA algorthms. For those who are interested in other C++ Cryptographic libraries, please see Peter Gutmann's Cryptlib or Victor Shoup's NTL.

Crypto++ can be downloaded from Wei Dai's Crypto++ page. For compilation and integration issues, see Compiling and Integrating Crypto++ into the Microsoft Visual C++ Environment. This article is based upon basic assumptions presented in the previously mentioned article.

## Signature Process

The signature process is a bit counter intuitive. This is because the 'public result' is derived from the Private Key rather than the Public Key. The 'public result' is the digital signature. Layman generally refer to signatures as 'Encrypt with the Public Key'. However, purely encrypting with the Public Key is not a valid cryptographic operation.

### Signing Process

When one signs a document using an Appendix scheme, two steps occur:

- Hash the document
**Decrypt** the hash of the document **as if** it were an instance of ciphertext using the **Private Key**

At step two, the document (hash) was not previously encrypted, even though a decryption occurs immediately. As the layman requests, this is the first stage of 'Encrypt with the Private Key'.

### Verification Process

To verify a signature, one performs the following steps. Note that since this is an Appendix system, one has the original document to present to the verification process:

- Hash the document
**Encrypt** the previously generated document hash (from step 2 of the Signing Process) using the **Public Key**
- Verify the recovered hash from Step 2 of the Verifcation Process matches the calculated hash from Step 1 of the Verifcation Process

Step one of the Verification process states to hash the document. Since this is a Signature Scheme with Appendix, the document is required for the verification process. If using the Recovery counterpart, one would recover the embedded document from the signature.

## PKCS #1, Version 1.5

PKCS defines three signing schemes for RSA using MD2, MD5, and SHA. One may also consult RFC 3447 for additional guidance. The schemes are `typedef'`

d in the Crypto++ `RSAFunction`

class for convenience. MD2 and MD5 are no longer considered cryptographically secure. One should use SHA as the digest function.

typedef RSASS<PKCS1v15, SHA>::Signer RSASSA_PKCS1v15_SHA_Signer;
typedef RSASS<PKCS1v15, SHA>::Verifier RSASSA_PKCS1v15_SHA_Verifier;
typedef RSASS<PKCS1v15, MD5>::Signer RSASSA_PKCS1v15_MD5_Signer;
typedef RSASS<PKCS1v15, MD5>::Verifier RSASSA_PKCS1v15_MD5_Verifier;
typedef RSASS<PKCS1v15, MD2>::Signer RSASSA_PKCS1v15_MD2_Signer;
typedef RSASS<PKCS1v15, MD2>::Verifier RSASSA_PKCS1v15_MD2_Verifier;

This article will forgo they `typedef`

, and use `RSASS<PKCS1v15, SHA>`

directly. Since the signature declaration uses templates, readers in Eurpoe could use Whirpool as the hashing function by creating `RSASS`

object using `RSASS<PKCS1v15, Whirlpool>`

.

`PKCS1v15`

specifies additional parameters to the signature scheme such as optional padding. If 128 or 192 bit hashes are too large (and data integrity is not required but basic error detection is desired), one could instantiate a `RSASS`

object using a CRC: `RSASS<PKCS1v15, CRC32>`

. These changes obviously diverge from RFC 3447.

The latest version of PKCS is version 2.1. Crypto++ does not implement version 2.0 and above. This is because at version 2.0, Multi-prime RSA was introduced. Crypto++ does not support multi-prime RSA. Multi-prime RSA uses a modulus which may have more than two prime factors. The additional prime factors affect private-key operations and has a lower computational cost for the decryption and signature primitives.

## Crypto++ Implementation

The Crypto++ implementation is based on Wei Dai's code located in validate2.cpp. The function of interest is `ValidateRSA()`

. The code that follows is the abridged version of the sample accompanying this article. The full version includes the program code for printing the Public and Private Keys, and Hex Encoding of the Signature. Points to remember when using the code below are:

`AutoSeededRandomPool`

constructs a Pseudo Random Number Generator
`InvertibleRSAFunction`

simply houses the Keys with some additional information to expedite inverting
`RSASS< PKCS1v15, SHA >`

creates an RSA object using SHA-1
`byte*`

`signature`

will receive the Signature (it is inconvenient that one cannot retrieve the length at compile time so the `new`

and `delete`

can be omitted)

std::string message(
"I think computer viruses should count as life. I think it\n" \
" says something about human nature that the only form of\n" \
" life we have created so far is purely destructive. We've\n" \
" created life in our own image."
);
AutoSeededRandomPool rng;
CryptoPP::InvertibleRSAFunction keys;
keys.GenerateRandomWithKeySize( rng, 384 );
RSASS< PKCS1v15, SHA >::Signer signer( keys );
byte* signature = new byte[ signer.MaxSignatureLength() ];
if( NULL == signature ) { return -1; }
size_t length = signer.SignMessage( rng, (const byte*) message.c_str(),
message.length(), signature );
RSASS< PKCS1v15, SHA >::Verifier verifier( signer );
bool result = verifier.VerifyMessage( (const byte*)message.c_str(),
message.length(), signature, length );
if( true == result )
{
cout << "Message Verified" << endl;
}
else
{
cout << "Message Verification Failed" << endl;
}
if( NULL != signature ) { delete[] signature; }

### RSA Parameters

Should the reader desire to load p, q, n, d, and e individually, use `SetPrime1()`

, `SetPrime2()`

, `SetModulus()`

, and `SetPublicExponent()`

, and `SetPrivateExponent() `

of class `InvertibleRSAFunction`

.

### SignatureStandard

Unlike ESIGN, the RSA Signer and Verifier object require the addition of a SignatureStandard. The SignatureStandard specifies the protocol the Signer and Verifier object will use. Since this article is using RSA with an Appendix, PKCS1v15 is selected.

### Signature Length

A final detail on Signature lengths. The `signature`

buffer is allocated using `MaxSignatureLength()`

. Later, the Signature is passed to the Verifier using `length`

to specify the size of the generated signature. `length`

was returned from `Signer::SignMessage()`

method.

ESIGN - a Signature Scheme with Appendix, both values are the same. In a system which uses Signatures with Recovery, this may be different. In this case, one would use the use the result returned from `SignMessage()`

as the actual signature length.

## Mathematics

The mathematics of Key Generation, Signing, and Verification are described in detail in many texts. The reader is referred to Wikipedia's RSA entry, the PKCS #1 specification, or RFC 3447.

## Acknowledgements

- Wei Dai for Crypto++ and his invaluable help on the Crypto++ mailing list
- Dr. A. Brooke Stephens who laid my Cryptographic foundations

## Revisions

- 11.26.2007 Added Multi-prime Information
- 11.25.2007 Updated Crypto++ Information
- 09.19.2007 Added Signature Process
- 09.19.2007 Added note on PKCS #1
- 09.19.2007 Added note on RFC 3447
- 09.13.2007 General Updates
- 06.19.2007 Initial Release

## Checksums

Sample.zip

MD5: 61ED4B512816BF4751D56446DE99D585

SHA-1: EB0791DD23C8FF656EE1383F7550C0E89D01A768