Challenge Problems

1.) Letting Space=00, A=01, B=02, ..., Z=26, encode the following message using the public key (42173,23).

I DO NOT LIKE OVALTINE BUT I DO LIKE CAPTAIN MIDNIGHT

To do the encoding, block the letters in groups of two. So, for example, DO = 0415. To test your solution, send your message to our "encryptor."

2.) As in (1), the following message was encoded using the same scheme and public key. See if you can properly decode it using the decryption exponent D= 5447.

24018 24784 23890 27866 4286 21586 24719 14460

Click here for the answer or use our decryptor.

3.) Digital Signatures:

The other aspect of the RSA algorithms, that was not discussed above, is its ability to verify the sender of the message. This is done using a digital signature. To be of any use this signature must be easy to generate and easy for the receiver to verify, but difficult to decode otherwise. There are various methods for generating such digital signatures, but one of the easiest exploits the inverse relation of the public enciphering and secret deciphering keys by reversing their roles.

To generate a digital signature, the sender "encodes" each plaintext block P_i using their own decryption exponent. Call the result S_i that is S_iP_i ^D mod(n). For a secure transmission, each of these signature blocks is encoded using the receiver public key, but this has nothing to do with the signature itself, so we may skip this step for the purpose of our exercise. When the receiver obtains the message, it is decoded using the receiver's public key (remember, in this exercise, we are skipping this step) giving the message and the encoded blocks S_i. The receiver then looks up the sender's public key (n,E) and uses it to decipher the signature blocks since

If this text matches the message text, the receiver may be assured that the message indeed came from the proper sender. Note that in practice, a "compressed" version of the original message text is used for the signature verification to save computation time.

As an exercise, use the decoding exponent in exercise (2) to generate a digital signature for the message in exercise (1), then use the public key in (1) to verify the signature is correct.

Click here for the answer