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 Cocks (Chief Mathematician at GCHQ - the British equivalent of the NSA) described the system in 1973. However, Cocks 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
