 RSA and related signature schemes

This section describes the RSA signature scheme and other closely related methods. The security of the schemes presented here relies to a large degree on the intractability of the integer factorization problem (see §3.2). The schemes presented include both digital signatures with message recovery and appendix (see Note 11.14).

The RSA signature scheme

The message space and ciphertext space for the RSA public-key encryption scheme (§8.2) are both Zn = {0,1,2,... , n — 1} where n = pq is the product of two randomly chosen distinct prime numbers. Since the encryption transformation is a bijection, digital signatures can be created by reversing the roles of encryption and decryption. The RSA signature scheme is a deterministic digital signature scheme which provides message recovery (see Definition 11.7). The signing space Ms and signature space S are both Zn (see Table 11.1 for notation). A redundancy function R: M —> Zn is chosen and is public knowledge.

11.18 Algorithm Key generation for the RSA signature scheme

SUMMARY: each entity creates an RSA public key and a corresponding private key. Each entity A should do the following:

• 1. Generate two large distinct random primes p and q, each roughly the same size (see §11.3.2).
• 2. Compute n = pq and 6 = (p — l)(q - 1).
• 3. Select a random integer e, 1 < e < Ф, such that gcd(e, ф) = 1.
• 4. Use the extended Euclidean algorithm (Algorithm 2.107) to compute the unique integer d, 1 < d < ф, such that ed = 1 (mod Ф).
• 5. A’s public key is (n, e); A’s private key is d.
• 11.19 Algorithm RSA signature generation and verification

SUMMARY: entity A signs a message m € M. Any entity В can verify A’s signature and recover the message m from the signature.

• 1. Signature generation. Entity A should do the folio whig:
• (a) Compute m = R(m), an mteger in the range [0, n — 1].
• (b) Compute s = fhd mod n.
• (c) A’s signature for m is s.
• 2. Verification. To verify A’s signature s and recover the message m, В should:
• (a) Obtain A’s authentic public key (?г, e).
• (b) Compute fh = se mod n.
• (c) Verify that fh e Mr; if not, reject the signature.
• (d) Recover m = R^1(fh).

Proof that signature verification works. If s is a signature for a message m, then s = fhd mod n where fh = R(m). Since ed = 1 (mod Ф), se = fhed = fh (mod n). Finally, R~1(fh) = R_1 (R(m)) = m.

11.20 Example (RSA signature generation with artificially small parameters)

Key generation. Entity A selects primes p = 7927, q = 6997, and computes n = pq = 55465219 and ф = 7926 x 6996 = 55450296. A chooses e = 5 and solves ed=bd=l (mod 55450296), yielding d = 44360237. A’s public key is (n = 55465219, e = 5); A’s piivate key is d = 44360237.

Signature generation. For the sake of simplicity (but see § 11,3.3(ii)), assume that M = Ztl and that the redundancy function R: M —> Z„ is the identity map R(m) = m for all m e M. To sign a message m = 31229978, A computes fh = R(m) = 31229978, and computes the signature s = hi'1 mod n = 3 1 22 9 9 7844360237 mod 55465219 = 30729435. Signature verification. В computes fh = se mod n = 307294355 mod 55465219 = 31229978. Finally, В accepts the signature since fh has the required redundancy (i.e., fh e Mr), and recovers m = R~1(fh) = 31229978. □