It is easy and obvious to see how RSA can be used for digital signatures. The two exponents, e and d, are each related to the other exponent in the same way. Thus, something enciphered with the public exponent d is something anyone could have written, but only the individual knowing e can read; something enciphered with the private exponent e is something anyone can read, but only the individual knowing d could have written.

To execute a digital signature using the Diffie-Hellman key agreement algorithm as the basis requires a different approach.

The basis of digital signature algorithms of this type is as follows: the person knowing x produces a set of two or three numbers that have a relationship to each other such that they can only be generated knowing x, but the presence of the relationship can be verified by those who only know A^x.

Thus, one simplified attempt at a discrete log signature algorithm would be to take a message m, and calculate s such that s = x * m, modulo Q, where P is a Sophie Germain prime such that P-1 = 2Q. Then, someone knowing only A^x could see that A^s = (A^x)^m. However, this wouldn't be effective, because a signed document consists of s and m, and since Q is public, your secret key x could easily be obtained by dividing s by m.

The signature methods actually used, therefore, involve additional parameters, so that the signature s is masked in a way that prevents it from giving away the value of x.

In more detail, these algorithms work like this:

Let us, to simplify matters, assume that the modulus P used for our Diffie-Hellman operations is not only a Sophie Germain prime, and thus

P - 1 = 2 * Q

where Q is also a prime, but in addition, Q is a Sophie Germain prime as well, so that

Q - 1 = 2 * R

for some prime R.

Primes other than Sophie Germain primes can be used; in that case, Q is simply some large prime factor of P-1. R is not used, but Q should also be a prime such that Q-1 has at least one large prime factor, since Q is used as a modulus for carrying out Diffie-Hellman operations as well in the type of algorithm described below.

This means that not only is P suitable as a modulus for securely carrying out Diffie-Hellman key setup, but so is Q, although Q is smaller.

Someone wishing to sign a document, m, has a permanent secret key x, to which A^x modulo Q (rather than A^x modulo P) is the corresponding public key. In addition, a nonce secret key y is generated, for which A^y modulo P, this time, not A^y modulo Q, is the corresponding public key.

A is chosen so that A^Q is equal to 1 modulo P, thus ensuring that A generates a sufficiently large portion of the numbers between 1 and P-1. This is relevant to using it as a base for Diffie-Hellman modulo P.

Also, Y is calculated, where Y equals (A^y modulo P) modulo Q. The message and the signature are both numbers modulo Q.

The signature s is calculated as a function of X and the message m. Various signature schemes are possible; all have in common three numbers, a, b, and c, which are defined in terms of s, Y, and m.

These three numbers satisfy the equation

ax + by = c

modulo Q.

This shows why it's vitally important that a different y is chosen for every signature. a, b, and c are all public information; so if you have two sets of a, b, and c for the same x and y, you can solve for the secret keys x and y.

Given s, m, A^x modulo P, and A^y modulo P (in the DSA, only Y is disclosed, but this makes verifying signatures more difficult; note also that Y can be calculated easily from this value, and Y is used in signature verification), the relationship between a, b, and c can be verified using the equation

(A^x modulo P)^a * (A^y modulo P)^b = A^c

modulo P.

The possible values for a, b, and c (following a different convention from the
one I use here) are given in Bruce Schneier's book *Applied Cryptography* as:

1) a=m, b=Y, c=s 2) a=1, b=Ym, c=s 3) a=1, b=Ym, c=ms 4) a=1, b=Ym, c=Ys 5) a=1, b=ms, c=Ys

and the sign convention may be altered; any of a, b, or c may be replaced by its additive inverse. (All possibilities, of course, can be reached by changing the signs of only two of them.) The Schnorr signature scheme, subject of a patent which still has a considerable time to run, is noted as being related to the fifth of these equations in Applied Cryptography, although elsewhere it is noted that the systems El Gamal and the Digital Signature Algorithm, based on the fourth of these equations, are special cases of Schnorr. The first and second equations, which avoid the need for a division to calculate s, are noted as being related to schemes described in various published papers.

The Handbook of Applied Cryptography, by Menezes, van Oorschot, and Vanstone, gives six possibilities instead, which are simply:

a=m, b=Y, c=s a=Y, b=m, c=s a=s, b=Y, c=m a=Y, b=s, c=m a=m, b=s, c=Y a=s, b=m, c=Y

the three individual elements in every possible order.

[Next] [Up] [Previous] [Index]