In the public key encryption scheme described earlier, anyone can send you encrypted messages without you knowing who they are. Consider Crowley on his island trying to arrange a transfer of pineapples with Satoshi on another island. If Crowley receives two messages with contradictory information both claiming to come from Satoshi (for example, "Send pineapples to the north island. —Your friend, Satoshi" and "Send pineapples to the south island. —Your friend, Satoshi"), how does Crowley know which message really came from Satoshi?
Fortunately, Satoshi can use a trick to prove his identity and the authenticity of his messages: He can encrypt messages not only with his public key but also with his private key. This backward encryption method reverses the mathematics of encryption, just as you'd expect: Although it's very difficult to encrypt a message (only the person with access to the private key can accomplish this), it's very easy to decrypt a message (anyone with the public key can do so).
Therefore, if Satoshi uses this backward method to encrypt the message: "My name is Satoshi, I live on the south island, and I double-pinky-swear to pay you for some pineapples," anyone, including Crowley, can decrypt this message using Satoshi's public key (which, let's assume, was previously established to be 100 percent authentic). Crowley can then say, "I know Satoshi is the only person on Earth who has access to his private key, and this message was written by someone who must have access to this private key; therefore, these words are Satoshi's words."
When you use this method to prove your identity, the functions of the public and private key are reversed. Satoshi can use his private key to encrypt a message, and everyone else can decrypt it using his public key. Because others have Satoshi's public key, the contents of the message wouldn't be secret, but the fact that it was encrypted using Satoshi's private key proves that it could not have been sent by anyone else.
This Is It Called a Digital Signature?
The term digital signature is used because the most convenient way to send a reverse encryption is to send two separate bits of information: a message and a message signature.
Think about it: Satoshi has nothing to hide in the message he is sending (in fact, he explicitly wants everyone to be able to read his message); therefore, it is arguably more convenient for Satoshi to send the message in an unencrypted form and then a duplicate it in encrypted form. Crowley can easily read the message and only bother using Satoshi's public key to decrypt the duplicate if he is suspicious of whether Satoshi actually wrote it.
However, it seems inefficient to send a message twice. Clearly, Satoshi must send the entire unencrypted message to get the message out to the world. But could the encrypted message be shortened? In fact it can, by using cryptographic hash functions. Remember that if anyone tries to tamper with a message, the hash of that message will be different as a result. Satoshi can therefore simply calculate the hash output of his message and then encrypt only that hash using his private key. Then anyone who reads the message can decrypt Satoshi's hash output (using his public key) and also calculate the hash of the unencrypted message, checking whether the two agree.
Keep in mind that a hash of a message, no matter how long the original message, is a short piece of data. Therefore, by only encrypting the hash of the original message, you can create a short digital signature of a much longer message. More important, even the slightest alteration to the unencrypted message would cause the cryptographic hash to be completely different, thus preventing any interceptor from modifying the signed message. As a result, not only does a digital signature prove that the real Satoshi signed the message, but it also proves that he signed a very specific message. In this regard, digital signatures are even better than analog handwritten signatures.
Using Digital Signatures
Using the RSA encryption scheme, implementing digital signatures is straightforward. Let's assume that we are using the same encoding scheme as in Table 7-2 and we want to send the message "fade" unencrypted but signed. Table 7-4 shows how to use a digital signature to prove authorship of the message.
Now we can send the message "fade" and sign it with ifda. The recipient doesn't need any additional information to read the message, because it can be read plainly. But to verify the identity of the sender, the recipient needs to know the hash function used (in this case MD5), the prime product n, and the public key of the sender, e. The recipient then decrypts the signature with the public key to obtain the hash value, in this case 8808, and checks to see whether it matches the MD5 hash of the message "fade." If a match is made, the recipient knows who the message came from and that the message was not altered in transit.
Table 7-4: Signing the Message "Fade" Using RSA Encryption
This is how digital signatures work. Of course, in this example, the prime product chosen was a low number so the examples were easy to follow. In practice, RSA cryptography uses 512-bit or 1024-bit prime products (or even higher for military communications), which looks something like this:
Other small details differ in practice to further increase the security of the procedure.