Using RSA for Signing Messages
A nice property of RSA is that if we swap the role of the encryption and decryption keys, it's still possible to transmit messages. That's because the computation (Me)d mod n is the same as (Md)e mod n. Typically, messages are encrypted with your public key, which means that only a person with your private key can read the message. Anyone can pick up your public key and send you a message. Turning that around, you're the only person that can send someone else a message using your private key. However, anyone can pick up your public key and decrypt that message. This allows us to prove who the sender of the message is to the same accuracy as protecting the contents of the message.
To save space, it's not necessary to sign the entire message with your private key. Instead, you can take a hash function for which it is difficult to find collisions and sign the hashed version of your message. This allows you to create a fixed-length signature for use with arbitrarily long messages.
Signing is not compatible with the algorithm presented yesterday for chunking messages. Each chunked message for encryption contains randomly-generated padding bytes. This means that the signature would unpredictably change every time we tried to recompute the message. Signing uses a padding block where every byte of padding has the value 0xff. To make sure that you know which type of padding is being used, the block type for signing is 0x01 instead of the block typeof 0x02 for encryption. The contents of a block look like
0x00 0x01 0xff ... 0xff 0x00 hash
The same private key should not be used for both signing and encrypting messages. Generate multiple key pairs in that situation to prevent information attacks where an attacker has access to messages signed by both the public and private keys.
Next time: Attacks on RSA
