CS 4953 -- Cryptography
Final Exam
Wednesday, 8 May 2002, 8 am - 10:15 am

Please try to give your answers on the lines provided below. In each case you should show your work for full credit. (An incorrect answer with proper work might get full credit.)

Part I: Preliminaries

  1. In the field consisting of the integers mod 37, what is the definition of the multiplicative inverse of 14?

  2. In the integers mod 37, state how you would use the Extended Euclidean Algorithm to find the multiplicative inverse of 14. (Don't actually find the inverse, just say how you would do the calculations. There is no credit for just writing down the inverse.)

  3. State Fermat's Theorem and verify that it is true for a = 3 and p = 7. (Show your work.)

  4. By any method, find 21024 mod 7? (But you must show your method, and not just write down an answer.)

Part II: Coding and Information Theory

  1. Contrast the two kinds of coding: source coding (compression) and channel coding (coding for errors).

  2. What does the entropy of a message say about compression? (In the absense of noise.)

  3. What special property does Verhoeff's Decimal Error Detection scheme have that the other simple decimal error detection schemes do not have (those using a single decimal check digit)?

 

Part III: Introduction to Cryptography

  1. A question about the One-time Pad:
    1. What is the major disadvantage of the one-time pad?

    2. Why might one want to use the one-time pad anyway?

Part IV: Public Key Cryptography

  1. (This question is somewhat similar to Rabin's public key cryptosystem.) Bob wants to flip a coin with Alice, where there should be only two possible outcomes: Bob "wins the toss" or Bob "loses the toss", each with probability 0.5. Unfortunately, Alice and Bob are connected only by a communications line, they have no friend to flip for them, and they don't trust each other. Use the following protocol:
    1. Alice selects large primes p and q, each with remainder 3 when divided by 4. Alice calculates n = p*q and sends n to Bob.
    2. Bob picks a random number a (between 1 and n), and sends x = a2 mod n to Alice.
    3. Alice uses Rabin's formulas to find the 4 square roots of x, and picks one of them at random (call it y), and sends y to Bob.
    4. If y is either the original a or is n - a, then Bob knows he has lost the toss. He asks Alice to send him the two factors of n, and Alice wins once Bob can verify that they are indeed the factors and that she has not cheated.
    5. Otherwise, Bob calculates gcd(x + y, n). This will be a factor of n, and so Bob can determine both p and q, and he sends the factors of n to Alice, winning the toss.

    Consider the "toy" specific case of p = 7, and q = 11.
    1. Do these values meet the criteria above? What does Alice send to Bob in this case?

    2. Suppose Bob chooses a = 31. What value x does Bob send to Alice?

    3. It turns out that the four square roots of x are 24, 31, 46, and 53. What might Alice send back to Bob?

    4. Which two cases are the ones listed above in which Bob loses the toss?

    5. Show that in the two remaining cases, Bob can calculate a factor of n using the method above, and so in these cases he will win the toss.

Part V: Random Number Generation

  1. What is the general form of a linear congruence generator? (Just show what it looks like, without specific numbers.)

Part VI: The Advanced Encryption Standard

  1. This question concerns the AES key.
    1. Explain briefly how the key is used during AES encryption. (You should include the terms key expansion and round in your explanation.)

    2. How is the action in part a. reversed during decryption?

Part IX: Identification and Key Distribution

  1. Suppose that H is a one-way function, and that Pi is a collection of passwords for 1 <= i <= n.
    1. In a typical Unix setting, explain what is stored in the password file.

    2. Explain how to search efficiently for passwords that match entries in an online dictionary.

    3. Explain what a salt is and how to use it to make the search for passwords much harder.

  2. Your company has its own new proprietary block cipher SLAM with characteristics similar to the AES: 128-bit blocks and keys. You say you're worried about SLAM's security, but they say they have to use SLAM to justify the expense of developing it (the developer of SLAM is the nephew of the CEO). They propose the following: they will use ECB mode and encrypt the first block of a message with SLAM, the second with AES, and so on alternating, using the same key for both ciphers.

     

    1. There are at least three major things wrong with this idea. Give as many as you can, and explain why each aspect is bad.

    2. What should they do instead, assuming they have to use SLAM (to keep the CEO happy)?

  3. Suppose A ("Alice") has registered her public RSA key with a public trusted server T. A then wants to prove to B ("Bob") that she really is A.
    1. Exactly what will A be leaving with T ?

    2. What is the simplest thing A could do to prove to B that she is really A?

    3. What is a replay attack in this setting?

    4. What can A and B do to protect against replay attacks?

  4. This question is concerned with threshold schemes.
    1. Explain in complete detail how a user A can use a threshold scheme to maintain two shares of a secret password "aragorn" on two separate systems, where both shares are needed to recover the password.

    2. Assuming an opponent cannot obtain both shares, how secure is the password?