Public-Key Cryptography - Codes: The Guide to Secrecy from Ancient to Modern Times - page 181

1. If Alice signs a message m with sig k ( m ), it must be computationally infeasi-
ble for an adversary to retrieve the pair ( m, sig k ( m )), called the unforgeable
property .

2. If Bob receives sig k ( m )= c from Alice, then Bob must be able to verify
that this is Alice's signature using ver k ( c ), called the authentic property .
3. After being transmitted, neither Bob nor Mallory can alter m , called the
not alterable property ;

4. Bob must be able to instantly detect if an m is being resent, called the not
reusable property .

DSS Types

1. A DSS with message recovery means that the message being sent is not
required as input to the verification algorithm.

2. A DSS with appendix means that the message is required as input for the
verification algorithm.

A significant benefit of RSA is that it can be used for both enciphering
plaintext and signing messages. Thus, our first DSS is naturally derived from
the RSA cipher, and it is an example of the first type of scheme, one with
message recovery (see [206]). Before explaining it in formal terms, we give a
brief introductory explanation.
The executions for encryption and signing involve the same RSA calculations
modulo the given RSA modulus n . For instance, if Alice wants to sign a message
m , she easily computes c m d A (mod n ) using her private RSA key, d A , and

sends ( c, m ) to Bob. Bob, or anyone in possession of her public key e A , uses
it to verify the signature via c e A

≡

≡ m (mod n ). Formally, this is presented as

follows.

RSA Signature Scheme
Setup Stage : Alice wishes to send a message m

to
Bob. She selects an RSA modulus n = pq and an RSA key pair ( e, d ) obtained
via the RSA key generation algorithm given on page 173. The keyspace is
K

∈ M = Z /n Z = C

= { k =( n, p, q, e, d ): ed ≡ 1 (mod φ ( n )) } , where n, e are public and p, q, d

are private.
Signing Stage : Alice's private digital signature sig k is given by
sig k ( m ) m d ≡ ≡ c (mod n ) ,

c e (mod n ) is her public verification algorithm. She sends ( m, c )to

and ver k ≡

Bob.
Verification Stage : Bob obtains Alice's public ( e, ver k ), and computes
ver k ( m, c ) which is 1 precisely when m c e (mod n ), in which case he accepts ≡

the signature, and rejects it otherwise.