# 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. □