FOR PUBLIC-KEY CRYPTOSYSTEMS

Frank Rubin

August 6, 1997

Suppose that a group of people wish to send a message so that the receiver knows for certain that the message came from those specific people, and can later prove this to an impartial third party. For example, the message might be a contract requiring the signatures of several corporate officers, or a legal document requiring witnesses and notarization. The procedure for producing the signature should guarantee that nobody else can forge the signature or modify the signed message, and that no signer can later deny signing. Even if another, possibly larger, group of corporate officers wanted to change the message, or masquerade as the actual signers, they should be unable to do that unless the group included all of the actual signers.

One possible way to achieve this would be to have each party append a separate digital signature to the message. This means a message requiring n signatures would be increased in length by about n times as much as for one signature. For economy, it would be preferable to have a joint signature about the same length as a single signature, provided that it does not take significantly more execution time to produce it than n separate signatures.

This paper will show a method to achieve this goal in two common public-key cryptosystems. It is an extension of a method I described in an earlier paper [8] for single digital signatures. The method consists of two steps: first construct a secure hashing or digest of the message, then build a signature from that hash value. I will describe this for both of the leading public-key cryptosystems, the RSA system, and the Quadratic Residue system.

In the RSA cryptosystem, it takes slightly less time to produce the joint signature than the n separate signatures. In the Quadratic Residue cryptosystem it may take longer to produce the joint signature than n separate signatures, depending on the relative sizes of the signers' public keys.

There are many other signature methods, such as Schnorr's scheme [9] (which is based on the ElGamal cryptosystem [4]), the Lamport scheme [3], and its modified version by Bos and Chaum [2]. Meijer and Akl [5] presented 4 signature schemes. This paper is not intended as a survey of signature methods, and it will not try to extend any of these others to handle multiple signers.

In an RSA (Rivest-Shamir-Adleman) cryptosystem [6], each user of the system has a public key that anyone can use for encrypting messages to that user, and a private key for reading those messages. The public key consists of two numbers, N and E. N is the user's modulus, and E is the user's enciphering exponent. A message is divided into blocks, each block being an integer in the range 0 to N-1. To encipher a block B the sender raises B to the E-th power modulo N. The receiver can recover B by raising B

In a quadratic residue public-key cryptosystem [1], each user has a public key which is an integer N. This integer is again the product of two large primes. A message to a receiver R is enciphered by choosing a random initial value and successively squaring it modulo N. A low-order portion of each successive square, or quadratic residue, is exclusive-ored to the next block of the message. The quadratic residue following the last block of the message is appended to the message. If the prime factors of N have been chosen in a particular way, this allows the receiver to reconstruct the initial value, and thence the entire sequence of quadratic residues.

The basis for the digital signature is a secure hashing function, or message digest. This means a hash function where any change to the message almost certainly changes the hash value, and nobody can modify a message in such a way that the hash value remains unchanged. A suitable hash function is described in [8]. Let the message M consist of the blocks B

H

H

H = H

where Q is some fixed large number used as a seed, D is a fixed multiplier, and J

J

J

Since N is odd, B

Changing any block of the message will almost certainly change the value of the hash. If the prime factors p and q of N are chosen so that either p or q or both are

In the previous paper [8], the hashing modulus N was the sender's modulus. This choice meant that nobody except the sender could create a message which has the same hash value as the genuine message. That was perfectly secure in a single-sender single-signature situation. However, here we have multiple signatories, each of whom is responsible for the contents of the message. We can use neither a sender's modulus, nor the receiver's modulus, for this would allow that person to substitute another message for the genuine message.

I propose that the cryptosystem have an additional public modulus specifically for the purpose of constructing this hash. The factorization of this modulus would be known only to some trusted central authority, or perhaps to nobody at all. This could be arranged by using a computer program that generated two large primes and reported their product, but not the primes themselves. The choice of these primes could depend on physical events that could never be replicated, such as the exact timing of keystrokes from several mutually isolated keyboards.

Since this master modulus or

Suppose that the signers are S

Consider the RSA case first. The first signer constructs a signature by deciphering the hash value H using the modulus N

The receiver can then verify the joint signature by reversing these steps. First the signature is enciphered using S

This process assumes that the receiver knows who has signed the message. The text of the message may specify this, but we must be prepared for messages that do not specify. If the sending organization has d authorized signers, and n signatures are required, then the receiver could conceivably try all P(d,n) = d!/(d-n)! permutations, potentially a large number. This can be avoided by appending a d-bit tag following the signature, with a 1 for each signer. The tag also determines the length of the signature, making it easy to separate the message from the signature, which must be done before the receiver can compute the hash value.

The situation is more complex in a Quadratic Residue or Double Quadratic Residue [7] public key cryptosystem. A signer in a QR system produces a signature by taking the square root of the hash value modulo the sender's public modulus. However, not all values have square roots. Only quadratic residues have square roots, and only about 1/4 of all residues are quadratic residues. Thus it would appear that there is only a 1/4 chance of being able to produce a signature for each signer.

With a single signer, this problem is solved by appending an extra byte to the hash value. This byte is initially set to 0, and the signer tries to obtain a square root. If this value is not a quadratic residue, then the byte is stepped to 1, then 2, and so forth. The extra byte allows 256 tries, making success 99.999999% certain.

With multiple signers, the first signer would pass the signature, that is, the square root of the hash value, to the second signer, who would calculate the square root modulo N

Fortunately, the situation is not really this bad. The public moduli N

If the potential signers can arrange so that each successive modulus is at least 3 bits longer than the preceding one, then each signer will have at least 8 tries, so there will be at most a 10% chance of needing to backtrack after each signature attempt.

If this cannot be arranged, then there is a more general procedure that will solve the problem. Instead of appending a fixed number of bits to the hash value, append a variable number of bits depending on the number of signers and the relative sizes of their public moduli. A rule of thumb might be 6 bits for the first signer, plus 2 additional bits for each additional signer, reduced by the extra bits allowed by their moduli.

Let e

b

b

The number of bits that must be added is

max (b

With this number of bits, the chance of obtaining a joint signature is at least 99.9999887%, regardless of the number of signers. In the worst case all e

Actually, since the master key is probably a good deal larger than any of the signers' public keys, the entire hash value would not be used in any case, so these added bits do not increase the size of the hash value (which could potentially mean the signature would have to be done as two or more blocks). Instead, the hash value would be truncated to the length of the first signer's public key, less one bit, less the number of added bits determined above. Then the added bits would restore the length to one less than the length of first signer's key.

The amount of work required to produce the joint signature depends on whether each signer finds a square root, or whether it is necessary to backtrack. This, in turn, depends on the values of e

If a group of people frequently sign digital documents together, excessive backtracking can be avoided by choosing the public moduli so that e

In both the RSA and Quadratic Residue signature schemes it is possible for a signer to claim that a signature was forged by publishing the factorization of the public modulus. It is required that each signer uses the same modulus for signatures as for encrypted messages. Thus publishing the factorization would potentially reveal the contents of all encrypted messages the signer had ever received. It is assumed that this is sufficient to deter such publication. (If not, then the document may be protected by registering its time of receipt with a trusted authority.)

A message can be signed by n signatories by hashing the message, and then successively decrypting the hash value with the public keys of the signers. For the RSA cryptosystem, the amount of work is actually less than the work needed to produce n separate signatures. For the Quadratic Residue cryptosystem, several tries at producing a joint signature may be needed, so the work may be slightly to substantially greater than the work to produce n signatures. Substantial extra work may be prevented by choosing public moduli of sufficiently different lengths. For both systems, the length of the joint signature is only slightly greater than the length of a single signature.

The joint signature is secure in the sense that no party or parties can fake the signature, nor can any signers deny that they signed. The signature can be proved to a third party, such as a court of law.

1 | L. Blum, M. Blum and M. Shub 1986. A Simple Unpredictable Pseudorandom Number Generator. SIAM J. Compu. 15: 364-383. | ||||||||||||||

2 | J. N. E. Bos and D. Chaum 1993. Provably Unforgeable Signatures. Lect. Notes in Compu. Sci. 740: 1-14. | ||||||||||||||

3 | W. Diffie and M. E. Hellman 1976. Multiuser Cryptographic Techniques. AFIPS Conf. Proc. 45: 109-112. | ||||||||||||||

4 | T. ElGamal 1985. A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Trans. on Info. Theory 31: 469-472. | ||||||||||||||

5 | H. Meijer and S. Akl 1982. Digital Signature Schemes. Cryptologia 6: 329-338. | ||||||||||||||

6 | R. L. Rivest, A. Shamir and L. Adleman 1978. A Method for Obtaining Digital Signatures and Public Key Cryptosystems. Comm. ACM 21: 120-126. | ||||||||||||||

7 | F. Rubin 1995. The Quadratic and Double Quadratic Residue Ciphers. Cryptologia 19: 275-283. | ||||||||||||||

8 | F. Rubin 1995. Message Authentication Using Quadratic Residues. Cryptologia 19: 397-404. | ||||||||||||||

9 | C. P. Schnorr 1991. Efficient Signature Generation by Smart Cards. J. Cryptology 3: 161-174. |