Understanding the RSA Digital Signature Algorithm

The latest FIPS186-2 now lists the RSA digital signature (RSA ds) as one of the three recommended algorithms for digital signatures. The FIPS186-2 simply says to see the ANSI x9.31 for documentation. The RFC 2437 ( http://www.ietf.org/rfc/rfc2437.txt ) also describes the RSA digital signature, the RSA key exchange, and more, and is freely available. Those who need to understand any differences between the RFC 2437 and the ANSI X9.31 can reference the paper "Differences between ANSI X9.31 and RSA PKCS#1" ( http://www.corsec.com/copy/pdf/X931_PKCS1.pdf ).

Recall from the key agreement algorithm in Chapter 4 that RSA had three public variables called p , q , and the modulus n . The public key is represented by {n,e} and the private key is {n,d} . If the private key {n,d} is not available, it will have to be computed from the p , q , dP , dQ , and qInv variables with the Chinese Remainder Theorem (CRT) key.

Cross-Reference

The Chinese Remainder Theorem was introduced in Chapter 4.

If the CRT key is used, the variable s can be generated from the following equations:

s2 = m ^dQ mod q .
h = qInv (s1 - s2) mod q .
s = s2 + h q .

When the signature is generated, a digest is computed for the data and returned as the variable m . The signature s is computed from the following equation:

s = m ^d mod n

To verify the message, the algorithm will need the public key {n,e} , the capability to recompute the same digest from the data as m , and the signature s . The message digest is recomputed as the test variable a . The b variable will be generated using the following equation from the signature and the public key:

b = s ^e mod n

The variables a and b match if the signature, keys, and data are valid. The a value is computed as the integer returned as the message digest. Unlike the DSS algorithm, the RSA algorithm may use the MD2, MD4, MD5, or SHA-1 digest. In order to account for the possibility of different message digests, the message digest algorithm identifier is returned as part of the signature information block.

Cross-Reference

Chapter 9 introduced MD2, MD4, MD5, and SHA-1.

Other variables that are included in the format of the signature are block type, encryption-block formatting, and a padding block. RSA not only has a key algorithm and signature algorithm, but also an encryption algorithm. Since RSA includes an encryption algorithm, the signature block may also be encrypted with the RSA cipher.

Tip	In order to format the signature block, the PKCS#1 includes a padding string and algorithm to ensure the correct format size when hashing and using the RSA encryption.

Table of content

Java Security Solutions

ISBN: 0764549286
EAN: 2147483647

Year: 2001
Pages: 222

Authors: Rich Helton, Johennie Helton

BUY ON AMAZON

A Practitioners Guide to Software Test Design

Practical Intrusion Analysis: Prevention and Detection for the Twenty-First Century: Prevention and Detection for the Twenty-First Century

Mastering Delphi 7

Microsoft WSH and VBScript Programming for the Absolute Beginner

Comparing, Designing, and Deploying VPNs

FileMaker 8 Functions and Scripts Desk Reference