The RSA scheme taught in lecture is sometimes called "textbook RSA," since it is the simplest possible implementation and it ignores some real-world issues. In this problem, we will investigate one possible extension of textbook RSA called "padding." For this problem, Alice has the public key (n, e) and private key d. Bob attempts to send the message m to Alice by transmitting c=m^e mod n. Each encryption and decryption takes 1 second. Furthermore, you may assume that n has more than 376 bits.

(a) It happens that Bob is trying to tell Alice the three-digit passcode to his garage so she can borrow his bike pump. Mallory, an evil eavesdropping neighbor, wants to know the passcode as well. She knows that Bob will send only the three-digit passcode (that is, his message will look like "577", "628", or something else similar). Assuming Alice and Bob are using textbook RSA, and assuming Mallory can read all communications between Alice and Bob, how can Mallory determine Bob's passcode?

(b) Bob, being always mindful of Mallory's malevolence, changes his garage's passcode every day at 8 a. m. for extra security. Assuming he had texted Alice at 10 a. m., will Mallory be able to break into the garage before 8 a. m. the next day? How much time would it take for her to determine the passcode?

(c) The next day, Bob decides to send Alice the passcode a second time, just in case she wants to borrow the bike pump again. This time, however, they use a slightly different communication protocol. Rather than just sending the passcode, Bob first encodes the passcode into a 10-digit binary string. He then appends 366 random bits to the end of that string (this is called "padding"). This final bitstring of length 376 is m. When Alice receives c, she decodes it as usual, and then just ignores the last 366 bits. Adapt your strategy from part (a) to allow Mallory to determine Bob's new passcode.

(d) With the protocol from part (c), will Mallory now be able to break into the garage before 8 a. m. the next day (again assuming Bob sent Alice the encrypted message at 10 a. m.)? How much time would it take for her to determine the passcode?