1. Without using a computer or any electronic devices, i.e., manually, calculate

28^65,000,000,019 (mod 65). Hint: You may need to use Chinese Remainder Theorem and Fermats Little Theorem.

2. Besides being used for message authentication and efficient signature of long message, cryptographic hash functions have many other usages such as user authentication between two users (e.g., Alice and Bob) having a shared secret key K, committing a value first and then disclosing the value later, and many security and key management protocols . One scenario works as follows (hash function H is public, as normally assumed):

Alice wants to authenticate Bob, Alice selects a random r1 and sends r1 to Bob.

Bob selects a random r2, computes z = H(r1 + K + r2), and sends (r2,z) back to Alice.

Alice can recompute H(r1 + K + r2) and check whether it equals to z. If yes, Bob is authenticated.

Such a user authentication protocol works but is complicated, or to say, not efficient. Can you design a more efficient user authentication protocol

between two users by simply using the shared secret key K and the public hash function H?