Digital Signatures using RSA

Question

RSA can be used for digital signatures this way:

1. B creates $m$ (product of two primes), $r$ (a number for what gcd($r$, $\Phi(m)$ equals 1) and tells $m$ and $r$ A.
2. B chooses $s$ which is the inverse of $r$.
3. B sends the unencrypted message $x_1x_2x_3$ together with the message he encrypted using $s$: $y_1 y_2 y_3 = g(x_1)g(x_2)g(x_3)$.

But how does A know that the message $x_1x_2x_3$ reached him unadulterated? How does A know that the message was really from $B$? If I was an attacker, what do I have to do to fake a message?

An example $(m=667, r=5, s=493)$:

$x_1x_2x_3 = (111,112,113)$ and $y_1y_2y_3 = (194,603,201)$ To check if this message is real I would have to calculate $194^5 \text{ mod }667$ and check if it equals $111$. The next: $603^5 \text{ mod } 667$ equals 112 and so on. Is this true?

Answer 1

While your observation is right, i.e., the recipient can be confident that the private key $(s,m)$ was used to encrypt $x_i\to y_i$ by using the public key to decrypt $y_i\to z_i$ and check whether $x_i=z_i$, the actual procedure is somewhat different.

First of all, the "signature" of the message won't be an encrypted version of the full message (which woul dessentially make a signe dmessage twice as long as the cleartext). Instead, one encrpyts only a hash of the message. (This adds a little uncertainty as it might be possible for an attacker to alter the cleartext in such a way that a hash collision occurs).

The major problem is in step 1. The public key ($m$ and $r$) cannot simply be "told" the recipient as that would raise the question how to be sure that this information can be transferred authentically. There are ways to circumvent this problem:

• $A$ and $B$ meet ahead of the message transfer and hand out their public keys in person
• $B$ meets "in person" (i.e., exchanges his public key securely) with a trusted third party, who can then sign that the public key in question really belongs to $B$. This requires a hierarchy of trusted signers (Certifficate Authorities), where ultimately some of these CAs must have "well-known" public keys. Part of the trust in $B$s public key then is in fact trust in the CAs doing their job right ...
• Everybody meets a few friends of theirs in person who as in the first variant acknowledge each other's identity and public key. For a sufficiently wide-spread web of trust, there will be a chain that makes $A$ the friend of a friend of a friend ... and under the assumption that everybody in the chain was honest, $A$ can trust the fact that $B$'s public key was really issued by $B$.