# RSA signatures in practice

(i) Reblocking problem

One suggested use of RSA is to sign a message and then encrypt the resulting signature. One must be concerned about the relative sizes of the moduli involved when implementing this procedure. Suppose that A wishes to sign and then encrypt a message for B. Suppose that (па, ед) and (np, ев) are A's and B’s public keys, respectively. If nA > пв, then there is a chance that the message cannot be recovered by B, as illustrated in Example 11.22.

• 11.22 Example (reblocking problem) Let nA = 8387 x 7499 = 62894113, eA = 5, and dA = 37726937;andпв = 55465219,ев = 5,dB = 44360237. Noticethatn.4 > пв■ Suppose m = 1368797 is a message with redundancy to be signed under A’s private key and then encrypted using J5’s public key. A computes the following:
• 1. s = mdA mod nA = 136 8 7 9737726037 mod 62894113 = 59847900.
• 2. c = mod nB = 59847900s mod 55465219 = 38842235.

To recover the message and verify the signature, В computes the following:

• 1. s = cd mod nB = 38 8 4 2 2 3544360237 mod 55465219 = 4382681.
• 2. m = seA mod nA = 4382681s mod 62894113 = 54383568.

Observe that m ф in. The reason for this is that .s is larger than the modulus nB. Here, the probability of this problem occurring is (nA - nB)/nA к 0.12. □

There are various ways to overcome the reblocking problem.

• 1. reordering. The problem of incorrect decryption will never occur if the operation using the smaller modulus is performed first. That is, if nA > nB, then entity A should first encrypt the message using B’s public key, and then sign the resulting cipher- text using ^4’s private key. The preferred order of operations, however, is always to sign the message first and then encrypt the signature; for if A encrypts first and then signs, an adversary could remove the signature and replace it with its own signature. Even though the adversary will not know what is being signed, there may be situations where this is advantageous to the adversary. Thus, reordering is not a prudent solution.
• 2. two moduli per entity'. Have each entity generate separate moduli for encrypting and for signing. If each user’s signing modulus is smaller than all of the possible encrypting moduli, then incorrect decryption never occurs. This can be guaranteed by requiring encrypting moduli to be (t + l)-bit numbers and signing moduli f-bit numbers.
• 3. prescribing the form of the modulus, hr this method, one selects the primes p and q so that the modulus n has a special form: the highest-orderbit is a 1 and the k following bits are all 0’s. A f-bit modulus n of this form can be found as follows. For n to have the required form, 2*~1 < n < 2/_1 + 2,~k~1. Select a random [t/2]-bit prune p, and search for a prime q in the interval between [2t-1/pl and |_(2*_1 + 2t~k~1)/p then n = pq is a modulus of the required type (see Example 11.23). This choice for the modulus n does not completely prevent the incorrect decryption problem, but it can reduce the probability of its occurrence to a negligibly small number. Suppose that nA is such a modulus and s = md-A mod nA is a signature on in. Suppose further that s has aim one of the high-order k + 1 bit positions, other than the highest. Then s, since it is smaller than nA, must have a 0 in the highest-order bit position and so is necessarily smaller than any other modulus of a similar form. The probability that s does not have any l’s in the high-order k + 1 bit positions, other than the highest, is less than (|)fc, which is negligibly small if k is selected to be around 100.
• 11.23 Example (prescribing the form of the modulus) Suppose one wants to construct a 12-bit

modulus n such that the high order bit is a 1 and the next k = 3 bits are 0’s. Begin by selecting a 6-bit prune p = 37. Select a prune q in the interval between [211 fp = 56 and [(211 + 28)/pJ = 62. The possibilities for q are 59 and 61. If q = 59 is selected, then n = 37 x 59 = 2183, having binary representation 100010000111. If q = 61 is selected, then n = 37 x 61 = 2257, having binary' representation 100011010001. □

(ii) Redundancy functions

In order to avoid an existential forgery attack (see §11.2.4) on the RSA signature scheme, a suitable redundancy function R is required. §11.3.5 describes one such function which has been accepted as an international standard. Judicious choice of a redundancy function is crucial to the security of the system (see §11.3.2(ii)).

(iii) The RSA digital signature scheme with appendix

Note 11.14 describes how any digital signature scheme with message recovery can be modified to give a digital signature scheme with appendix. For example, if MD5 (Algorithm 9.51) is used to hash messages of arbitrary bitlengths to bitstrings of length 128, then Algorithm 11.9 could be used to sign these hash values. If n is a k-bit RSA modulus, then a suitable redundancy function R is required to assign 128-bit integers to A:-bit integers. §11.3.6 describes a method for doing this which is often used in practice.

(iv) Performance characteristics of signature generation and verification

Let n = pq be a 2A-bit RSA modulus where p and q are each А-bit primes. Computing a signature s = md mod n for a message m requires 0(A3) bit operations (regarding modular multiplication, see §14.3; and for modular exponentiation, §14.6). Since the signer typically knows p and q, she can compute si = md mod p, s2 = md mod q, and determine s by using the Chinese remainder theorem (see Note 14.75). Although the complexity of this procedure remains О (A3), it is considerably more efficient in some situations.

Verification of signatures is significantly faster than signing if the public exponent is chosen to be a small number. If this is done, verification requires 0(A[1]) bit operations. Suggested values for e in practice are 3 or 216 + l;[1] of course, p and q must be chosen so that gcd(e, (p - l)(g - 1)) = 1.

The RSA signature scheme is thus ideally suited to situations where signature verification is the predominant operation being performed. For example, when a trusted third party creates a public-key certificate for an entity A, this requires only one signature generation, and this signature may be verified many times by various other entities (see §13.4.2).

(v) Parameter selection

As of 1996, a minimum of 768 bits is recommended for RSA signature moduli. A modulus of at least 1024 bits is recommended for signatures which require much longer lifetimes or which are critical to the overall security of a large network. It is prudent to remain aware of progress in integer factorization, and to be prepared to adjust parameters accordingly.

No weaknesses hi the RSA signature scheme have been reported when the public exponent e is chosen to be a small number such as 3 or 216 + 1. It is not recommended to restrict the size of the private exponent d in order to improve the efficiency of signature generation (cf. §8.2.2(iv)).

(vi) Bandwidth efficiency

Bandwidth efficiency for digital signatures with message recover)' refers to the ratio of the logarithm (base 2) of the size of the signing space Ms to the logarithm (base 2) of the size of Mr, the image space of the redundancy function. Hence, the bandwidth efficiency is determined by the redundancy R. For RSA (and the Rabin digital signature scheme, § 11.3.4), the redundancy function specified by ISO/IEC 9796 (§ 11.3.5) takes А-bit messages and encodes them to 2A-bit elements in Ms from which a 2A-bit signature is formed. The bandwidth efficiency in this case is For example, with a modulus of size 1024 bits, the maximum size of a message which can be signed is 512 bits.

(vii) System-wide parameters

Each entity must have a distinct RSA modulus; it is insecure to use a system-wide modulus (see §8.2.2(vi)). The public exponent e can be a system-wide parameter, and is in many applications (see Note 8.9(h)).

(viii) Short vs. long messages

Suppose n is a 2/e-bit RSA modulus which is used in Algorithm 11.19 to sign /.--bit messages (i.e., the bandwidth efficiency is i). Suppose entity A wishes to sign a kt-bit message m. One approach is to partition m into fc-bit blocks such that m = mi||m2|| ■ • • ||mt and sign each block individually (but see Note 11.6 regarding why this is not recommended). The bandwidth requirement for tins is 2kt bits. Alternatively, A could hash message m to a bitstring of length l < к and sign the hash value. The bandwidth requirement for this signature is kt + 2k, where the term kt comes from sending the message m. Since kt + 2к < 2kt whenever t > 2, it follows that the most bandwidth efficient method is to use RSA digital signatures with appendix. For a message of size at most /г-bits, RSA with message recovery is preferred.

• [1] -’The choice of e = 216 + 1 is based on the fact that e is a prime number, and fhe mod n can be computedwith only 16 modular squarings and one modular multiplication (see §14.6.1).
• [2] -’The choice of e = 216 + 1 is based on the fact that e is a prime number, and fhe mod n can be computedwith only 16 modular squarings and one modular multiplication (see §14.6.1).