Bob has a document $m$ that Alice agrees to sign. They do the following:

1. Alice generates two large primes $p$, $q$, and computes $n=pq$. She chooses $e_A$ such that $1<e_A<\varphi (n)$ with $\gcd \left(e_A\text{,}\varphi \left(n\right)\right)=1\text{,}$ and calculates $d_A$ such that $e_A{d}_A\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}\varphi (n))$. Alice publishes $(e_A\text{,}n)$ and keeps private $d_A$, $p$, $q$.

2. Alice’s signature is

   $s\equiv m^{d_A}(\text{mod}n)\text{.}$

3. The pair $(m\text{,}s)$ is then made public.

Bob can then verify that Alice really signed the message by doing the following:

1. Download Alice’s $(e_A\text{,}n)$.

2. Calculate $z\equiv s^{e_A}(\mathrm{m}\mathrm{o}\mathrm{d}n)$. If $z=m$, then Bob accepts the signature as valid; otherwise the signature is not valid.

Suppose Eve wants to attach Alice’s signature to another message $m_1$. She cannot simply use the pair $(m_1\text{,}s)$, since $s^{e_A}\cancel{\equiv }{m}_1(\text{mod}n)$. Therefore, she needs $s_1$ with $s_1^{e_A}\equiv m_1(\mathrm{m}\mathrm{o}\mathrm{d}n)$. This is the same problem as decrypting an RSA “ciphertext” $m_1$ to obtain the “plaintext” $s_1$. This is believed to be hard to do.

Another possibility is that Eve chooses $s_1$ first, then lets the message be $m_1\equiv s_1^{e_A}(\mathrm{m}\mathrm{o}\mathrm{d}n)$. It does not appear that Alice can deny having signed the message $m_1$ under the present scheme. However, it is very unlikely that $m_1$ will be a meaningful message. It will probably be a random sequence of characters, and not a message committing her to give Eve millions of dollars. Therefore, Alice’s claim that it has been forged will be believable.

There is a variation on this procedure that allows Alice to sign a document without knowing its contents. Suppose Bob has made an important discovery. He wants to record publicly what he has done (so he will have priority when it comes time to award Nobel prizes), but he does not want anyone else to know the details (so he can make a lot of money from his invention). Bob and Alice do the following. The message to be signed is $m$.

1. Alice chooses an RSA modulus $n$ ($n=pq$, the product of two large primes), an encryption exponent $e$, and decryption exponent $d$. She makes $n$ and $e$ public while keeping $p\text{,}q\text{,}d$ private. In fact, she can erase $p\text{,}q\text{,}d$ from her computer’s memory at the end of the signing procedure.

2. Bob chooses a random integer $k(\mathrm{m}\mathrm{o}\mathrm{d}n)$ with $gcd(k\text{,}n)=1$ and computes $t\equiv k^{e}m(\mathrm{m}\mathrm{o}\mathrm{d}n)$. He sends $t$ to Alice.

3. Alice signs $t$ by computing $s\equiv t^d(\mathrm{m}\mathrm{o}\mathrm{d}n)$. She returns $s$ to Bob.

4. Bob computes $s/k(\mathrm{m}\mathrm{o}\mathrm{d}n)$. This is the signed message $m^d$.

Let’s show that $s/k$ is the signed message: Note that $k^{ed}\equiv (k^e{)}^d\equiv k(\mathrm{m}\mathrm{o}\mathrm{d}n)$, since this is simply the encryption, then decryption, of $k$ in the RSA scheme. Therefore,

which is the signed message.

The choice of $k$ is random, so $k^e(\mathrm{m}\mathrm{o}\mathrm{d}n)$ is the RSA encryption of a random number, and hence random. Therefore, $k^{e}m(\mathrm{m}\mathrm{o}\mathrm{d}n)$ gives essentially no information about $m$ (however, it would not hide a message such as $m=0$). In this way, Alice knows nothing about the message she is signing.

Once the signing procedure is finished, Bob has the same signed message as he would have obtained via the standard signing procedure.

There are several potential dangers with this protocol. For example, Bob could have Alice sign a promise to pay him a million dollars. Safeguards are needed to prevent such problems. We will not discuss these here.

Schemes such as these, called blind signatures, have been developed by David Chaum, who has several patents on them.