16.3 Digital RSA Signatures

Team-Fly

"Please, your Majesty," said the Knave, "I didn't write it, and they can't prove that I did: there's no name signed at the end."

—Lewis Carroll, Alice's Adventures in Wonderland

To clarify how the RSA algorithm is used for generating digital signatures we consider the following process, by which a participant A sends a message M with her digital signature to a participant B, upon which B checks the validity of the signature.

A generates her RSA key with components n_A, d_A, and e_A. She then transmits her public key <e_A, n_A> to B.
A would now like to send a message M with her signature to B. To this end A generates the redundancy R = μ(M) with R < n_A using a redundancy function μ (see below). Then A calculates the signature

and sends (M, S) to B.
B possesses the public key <e_A, n_A> of A. After B has received the message M and the signature S from A, then B calculates

with the public key >e_A, n_A> of A.
B now checks whether R′ = R. If this is the case, then B accepts the digital signature of A . Otherwise, B rejects it.

Digital signatures that must be checked by a separate transmittal of the signed message M are called digital signatures with appendix.

The signature procedures with appendix are used primarily for signing messages of variable lengths whose numerical representation exceeds the modulus, so that M ≥ n. In principle, one could, as we did above, divide the message into blocks M₁, M₂, M₃, . . . of suitable lengths M_i < n and encrypt and sign each block separately. However, leaving aside the fact that in such a case a counterfeiting problem arises consisting in the possibility of mixing up the order of the blocks and the signatures belonging to the blocks, there are two further compelling reasons to employ, instead of construction of blocks, the function μ that we named the redundancy function in the paragraph above in which we discussed calculating a digital signature.

The first is that a redundancy function μ : maps arbitrary messages M from a message space into the residue class ring whereby messages typically are reduced by the application of hash functions (cf. page 337) to values z 2¹⁶⁰, which then are linked with predefined sequences of characters. Since the image of M under μ is signed in a single RSA step and hash functions can be calculated quickly by design, the use of such a procedure represents great savings in time over the number of RSA steps required for the individual blocks of M.

The second reason is that the RSA algorithm has an undesirable property for creating signatures: For two messages M₁ and M₂ the multiplicative relation

(16.4)

holds, which supports the counterfeiting of signatures if no measures are taken against it.

On account of this property, called homomorphism, of the RSA function it would be possible without the inclusion of redundancy R to have messages digitally signed with a "hidden" signature. To do this one could select a secret message M and a harmless message M₁, from which a further message M₂ := M M₁ mod n_A is formed. If one succeeded in getting a person or authority A to digitally sign the messages M₁ and M₂, then one would obtain the signatures S₁ = mod n_A, and S₂ = mod n_A, from which one can create the signature to M by calculating S₂ mod n_A, which was probably not what A had in mind, though nonetheless A may not have noticed this when generating the signatures S₁ and S₂: The message M would in this case be said to have a hidden signature.

To be sure, one could counter that with high probability M₂ does not represent a meaningful text and that anyway, A would not be well advised to sign M₁ or M₂ at a stranger's request and without examining the contents with care. Yet one should not rely on such assumptions of reasonableness when it comes to human behavior in order to justify the weaknesses of a cryptographic protocol, especially when such weaknesses can be eliminated, such as in this case by including redundancy. In order to achieve this redundancy, the redundancy function μ must satisfy the property

(16.5)

for all M₁, M₂ Î and thus ensure that the signature function itself does not possess the undesirable homomorphism property.

Supplementary to the signature procedures with appendix there are additional methods known that make it possible to extract the signed message from the signature itself, the so-called digital signatures with message recovery (cf. [MOV], Chapter 11, [ISO2], and [ISO3]). Digital signatures with message recovery based on the RSA algorithm are particularly suited for short messages with a binary length less than one-half the binary length of the modulus.

However, in every case the security properties of redundancy functions should be carefully examined, such as is demonstrated by the procedure published in 1999 by Coron, Naccache, and Stern for attacking such schemes. The procedure is based on an attacker having access to a large number of RSA signatures attached to messages whose representation as an integer is divisible exclusively by small primes. Based on such a makeup of the messages it is possible under favorable conditions, without knowledge of the signature key, to construct additional signatures to additional messages, which would amount to counterfeiting these signatures (cf. [Coro]). The ISO has reacted to this development: In October 1999 the workgroup SC 27 removed the standard [ISO2] from circulation and published the following announcement:

Based on various attacks on RSA digital signature schemes . . . , it is the consensus of ISO/IEC JTC 1/SC 27 that IS 9796:1991 no longer provides sufficient security for application-independent digital signatures and is recommended to be withdrawn.^[8]

The withdrawn standard refers to digital signatures for which the RSA function is applied directly to a short message. Signatures with appendix, which arise by way of a hash function, are not included.

A widely distributed redundancy scheme for which the attack of Coron, Naccache, and Stern has at best a theoretical significance and represents no real threat is set by the PKCS #1 format of RSA laboratories (cf. [RDS1], [Coro], pages 11–13, and [RDS2]). The PKCS #1 format specifies how a so-called encryption block EB should appear as input value to an encryption or signing operation:

At the head is a byte BT that describes the block type (01 for private key operations, that is, signatures; 02 for public key operations, that is, encryption) and then at least eight filler bytes PS₁ . . . PS_ℓ, ℓ ≥ 8, with the value FF (hex) in the case of signing and nonzero random values in the case of encryption. There follows 00 as separator byte, and then come finally the data bytes D₁ . . . D_n: the payload, so to speak. The number ℓ of filler bytes PS_i depends on the size of the modulus m and the number n of data bytes: If k is defined by

(16.6)

then

(16.7)

The minimum number 8 ≤ ℓ of filler bytes is required for encryption for reasons of security. Even with a small message this prevents an attacker from encrypting all possible values and comparing the result with a given encrypted text to determine the plain text without knowing the associated secret key. However, it is important that the PS_i be random numbers that are determined anew for each encryption operation. For consistency the minimum number of filler bytes is retained in signing operations, from which it follows that for the number n of data bytes we have

(16.8)

In the signing case the data bytes D_i are typically constructed from an identifier for a hash function H and the value H(M) of this hash function (called the hash value), which represents the text M to be signed. The resulting data structure is called the DigestInfo. The number of data bytes depends in this case on the constant length of the hash value, independent of the length of the text. This is particularly advantageous when M is much longer than H(M). We shall not go into the precise process for the construction of the data structure DigestInfo, but simply assume that the data bytes correspond to the value H(M)(but see in this connection [RDS1]).

From the cryptographic point of view there are several fundamental requirements to place on hash functions so as not to diminish the security of a redundancy scheme based on such a function and thereby call the entire signing procedure into question. When we consider the use of hash and redundancy functions in connection with digital signatures and the possibilities for manipulating them that might arise, we observe the following:

In accordance with our considerations thus far, we start with the assumption that a digital signature with appendix relates to a redundancy R = μ(M) whose principal component is the hash value of the text to be signed. Two texts M and M′ for which H(M) = H(M′), and consequently μ(M) = μ(M′), possess the same signature S = R^d = μ(M)^d = μ(M′)^d mod n. The recipient of a signature to the text M could now conclude that the signature actually refers to the text M′, which in general would be contrary to the intent of the sender. Likewise, the sender could assume actually to have signed the text M′. The point here is that texts M ≠ M′ with H(M) = H(M′) always exist, due to the fact that infinitely many texts are mapped to finitely many hash values. This is the price to be paid for the convenience of hash values of fixed length.^[9]

Since we must also assume the existence of texts that possess identical signatures in relation to a particular hash or redundancy function (where we assume that the same signature key has been used), then it is crucial that such texts not be easy to find or to construct.

In sum, a hash function should be easy to compute, but this should not be the case for the inverse mapping. That is, given a value H of a hash function it should not be easy to find a preimage that is mapped to H. Functions with this property are called one-way functions. Furthermore, a hash function must be collision-free, meaning that it must not be easy to find two different preimages of a given hash value. At present, these properties are satisfied by such strong hash functions as the widely used functions RIPEMD-160 (cf. [DoBP]) and the Secure Hash Algorithm SHA-1 (cf. [ISO1]).

We shall not go into further detail on this topic, which is very important to cryptography. The interested reader is referred to [Pren] or [MOV], Chapter 9, as well as the literature cited therein. Algorithms for transforming texts or hash values into natural numbers can be found in [IEEE], Chapter 12: "Encoding Methods" (we already have available the corresponding functions clint2byte_l() and byte2clint_l(); cf. page 150). An implementation of RIPEMD-160 can be found in ripemd.c on the accompanying CD-ROM.

In thinking about the signature protocol described above we are immediately confronted with the following question: How can B know whether he is in possession of the authentic public key of A? Without such certainty B cannot trust the signature, even if it can be verified as described above. This becomes critical when A and B do not know each other personally or when there has been no personal exchange of public keys, which is the normal case in communication over the Internet.

To make it possible for B nonetheless to trust in the authenticity of A's digital signature, A can present her communication partner a certificate from a certification authority that attests to the authenticity of A's public key. An informal "receipt," which one may believe or not, is, of course, inadequate. A certificate is rather a data set that has been formatted according to some standard^[10] that among other things speaks to the identity of A as well as her public key and that itself has been digitally signed by the certification authority.

The genuineness of a participant's key can be verified with the help of the information contained in the certificate. Applications that support such verification in software already exist. The future multiplicity of such applications, whose technical and organizational basis will be based on so-called public key infrastructures (PKI), can today only be guessed at. Concrete uses are emerging in the digital signing of e-mail, the validation of commercial transactions, e-commerce and m-commerce, electronic banking, document management, and administrative procedures (see Figure 16.1).

click to expand
Figure 16.1: Example of the construction of a certificate

On the assumption that B knows the public key of the certification authority, B can now verify the certificate presented by A and thereafter A's signature to become convinced of the authenticity of the information.

The example presented in Figure 16.2, which shows a client's digitally signed bank statement together with the certificate of the bank presented by a certification authority, demonstrates this process.

Such a bank statement has the advantage that it can reach the client over any electronic transmittal path, such as e-mail, in which it would be further encrypted to protect the confidentiality of the information.

click to expand
Figure 16.2: Certification of a digital signature

However, the problem of trust has not been hereby miraculously cleared up, but merely shifted: Now B need no longer believe directly in the validity of A's key (in the above example that of the bank), but in exchange must check the genuineness of the certificate presented by A. For certainty to be attained, the validity of certificates must be verified anew for every occurrence, either from the source that issued the certificate or an authority that represents it. Such a procedure can succeed only if the following conditions are met:

the public key of the certification authority is known;
the certification authority takes the greatest care in the identification of the receivers of certificates and in the protection of their private certification keys.

To achieve the first of these desiderata the public key of the certification authority can be certified by an additional, higher, authority, and so forth, resulting in a hierarchy of certification authorities and certificates. However, verification along such a hierarchy assumes that the public key of the highest certification authority, the root certification authority, is known and can be accepted as authentic. Trust in this key must thus be established by other means through suitable technical or organizational measures.

The second condition holds, of course, for all authorities of a certification hierarchy. A certification authority, in the sense of granting legal force to a signature, must establish the organizational and technical processes for which detailed requirements have been set in law or associated implementing orders.

At the end of 1999 a European Union directive was adopted that will set a framework for the use of digital signatures in Europe (cf. [EU99]). There will also be an implementing order for the European Union that encompasses the various national approaches and creates a European standard, which of course must be incorporated into national law. A corresponding revision of the German signature law is supposed to take effect in 2001 (cf. [SigG]). In the United States the Electronic Signatures Act has been in effect since October 2000. These regulations lead one to believe that in the near future digital signatures that adhere to the statutes of the individual countries will be exchanged to set the seal on legal transactions throughout Europe and—one day perhaps—between Europe and the United States, and that those digital signatures will be valid within each of the different legal systems.

We now leave this interesting topic, which can pursued further in [Bies], [Glad], [Adam], [Mied], and [Fegh], and turn our attention, finally, to the implementation of C++ classes that provide for encryption and the generation of digital signatures.

^[8]ISO/IEC JTC 1/SC27: Recommendation on the withdrawal of IS 9796:1991, 6 October 1991.

^[9]In the language of mathematics we would say that hash functions H : → that map texts of arbitrary length to values in are not injective.

^[10]Widely used is ISO 9594-8, which is equivalent to the ITU-T (formerly CCITT) recommendation X.509v3.

Team-Fly