Page 324 - Discrete Mathematics and Its Applications

4.6 Cryptography 303

k 1
k 2
because the adversary would need to find k 1 and k 2 from a mod p and a mod p, respec-
tively. Furthermore, no other method is known for finding the shared key using just the public
information. We have remarked that this is thought to be computationally infeasible when p
and a are sufficiently large. With the computing power available now, this system is considered
unbreakable when p has more than 300 decimal digits and k 1 and k 2 have more than 100 decimal
digits each.

DIGITAL SIGNATURES Not only can cryptography be used to secure the confidentiality of
a message, but it also can be used so that the recipient of the message knows that it came from
the person they think it came from. We first show how a message can be sent so that a recipient
of the message will be sure that the message came from the purported sender of the message.
In particular, we can show how this can be accomplished using the RSA cryptosystem to apply
a digital signature to a message.
Suppose thatAlice’s RSA public key is (n, e) and her private key is d.Alice encrypts a plain-
e
text message x using the encryption function E (n,e) (x) = x mod n. She decrypts a ciphertext
d
message y using the decryption function D (n,e) = x mod n. Alice wants to send the message
M so that everyone who receives the message knows that it came from her. Just as in RSA en-
cryption, she translates the letters into their numerical equivalents and splits the resulting string
into blocks m 1 , m 2 ,...,m k such that each block is the same size which is as large as possible
so that 0 ≤ m i ≤ n for i = 1, 2, ..., k. She then applies her decryption function D (n,e) to each
block, obtaining D n,e (m i ), i = 1, 2,...,k. She sends the result to all intended recipients of the
message.
When a recipient receives her message, they applyAlice’s encryption function E (n,e) to each
block, which everyone has available because Alice’s key (n, e) is public information. The result
is the original plaintext block because E (n,e) (D (n,e) (x)) = x. So, Alice can send her message
to as many people as she wants and by signing it in this way, every recipient can be sure it came
from Alice. Example 10 illustrates this protocol.

EXAMPLE 10 Suppose Alice’s public RSA cryptosystem key is the same as in Example 8. That is, n =
43 · 59 = 2537 and e = 13. Her decryption key is d = 937, as described in Example 9. She
wants to send the message “MEET AT NOON” to her friends so that they are sure it came from
her. What should she send?

Solution: Alice first translates the message into blocks of digits, obtaining 1204 0419 0019
1314 1413 (as the reader should verify). She then applies her decryption transformation
D (2537,13) (x) = x 937 mod 2537 to each block. Using fast modular exponentiation (with the
help of a computational aid), she finds that 1204 937 mod 2537 = 817, 419 937 mod 2537 = 555,
19 937 mod 2537 = 1310, 1314 937 mod 2537 = 2173, and 1413 937 mod 2537 = 1026.
So, the message she sends, split into blocks, is 0817 0555 1310 2173 1026. When one of
her friends gets this message, they apply her encryption transformation E (2537,13) to each block.
When they do this, they obtain the blocks of digits of the original message which they translate
back to English letters. ▲

WehaveshownthatsignedmessagescanbesentusingtheRSAcryptosystem.Wecanextend
this by sending signed secret messages. To do this, the sender applies RSA encryption using
the publicly known encryption key of an intended recipient to each block that was encrypted
using sender’s decryption transformation. The recipient then first applies his private decryption
transformation and then the sender’s public encryption transformation. (Exercise 32 asks for
this protocol to be carried out.)