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?


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$.
  • $\begingroup$ So A can only be sure the message was REALLY Form B if he meets B beforehand to exchange $m$ and $r$? $\endgroup$ – 今天春天 May 10 '15 at 11:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.