# 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 Z_{n} = {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 Z_{n} (see Table 11.1 for notation). A redundancy function *R: M* *—>* Z_{n} 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 = fh*mod^{d}*n.* - (c) A’s signature for m is s.

- (a) Compute m =
- 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 = s*mod^{e}*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 = *fh ^{d}* mod n where

*fh*=

*R(m).*Since

*ed =*1 (mod

*Ф), s*(mod

^{e}= fh^{ed}= fh*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 = Z _{tl }*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'*mod

^{1}*n*= 3 1 22 9 9 78

^{44360237}mod 55465219 = 30729435.

*Signature verification. В*computes

*fh = s*mod

^{e}*n =*30729435

^{5}mod 55465219 = 31229978. Finally,

*В*accepts the signature since

*fh*has the required redundancy (i.e.,

*fh*e Mr), and recovers

*m = R~*31229978. □

^{1}(fh) =