CS 4363 -- Cryptography
Final Exam: Answers
(Answers finished 2003-05-16 12:15:28)

Part I: RSA Cryptosystem

  1. In detail, give the steps needed to create an instance of RSA, assuming encryption exponent 3. At the end, explain what the following are: the encryption function, the decryption function, the public key, and the private key.

    1. Choose ``large'' prime integers p and q of roughly the same size, but not too close together.
    2. Calculate the product n = p*q (ordinary integer multiplication).
    3. Choose an encryption exponent e less than n that has no factors in common with either p - 1 or q - 1. (The exponent e can be 3 or it could be chosen at random.)
    4. Calculate the (unique) decryption exponent satisfying e*d mod (p - 1)*(q - 1) = 1.
    5. The encryption function is E(m) = me mod n, for any message m.
    6. The decryption function is D(c) = cd mod n, for any ciphertext c.
    7. The public key (published): This is the pair of integers (n, e).
    8. The private key (kept secret): This is the triple of integers (p, q, d).

    Assume that Alice and Bob have RSA key pairs (EA, DA), and (EB, DB), where E is the encryption key (= algorithm) and D is the decryption key.

  2. Explain how Alice makes a message m secret and sends it to Bob and how Bob recovers the message.

    Alice gets Bob's public key EB from a distribution authority. Alice calculates EB(m) = c and sends c to Bob. Only Bob knows the decryption key, so only Bob can compute DB(c) = DB(EB(m)) = m. Unless there is some failure in the system, no one intercepting the transmission of c will be able to recover the message m. However, anyone might have sent him this message, and even Alice might have leaked the message to others.

  3. Explain how Alice sends Bob a signed message m and how Bob verifies the signature.

    Alice uses her secret key to calculate DA(m) = s. At the other end, Bob can retrieve Alice's public key EA from the key authority and use it to recover the message, by calculating EA(s) = EA(DA(m)) = m. Anyone can fetch Alice's public key and do this calculation, so there is no secrecy here, but assuming the system does not break down (that the key authority works and that the cryptosystem is not leaked or stolen or broken), only Alice can have signed this message, so it must have originated with her.

  4. Explain how Alice could use a secure one-way hash function to quickly sign an arbitrarily long message.

    Suppose h is a public secure one-way hash function, that is, for m of any length, h(m) will be a fixed length, say perhaps 128 bits long, and given the value h(m), it is an intractable computation to find m or to find any m' such that h(m) = h(m'). Then Alice can sign the hash h(m) by using her secret key to calculate DA(h(m)) = s. Next Alice sends the following to Bob: the message m in the clear, and the signature s. At the other end, Bob can fetch Alice's public key EA, and then can calculate EA(s) = EA(DA(h(m))) = h(m). Finally Bob can use the public h to verify that h(m) is the value he just calculated from Alice's transmission.

Part II: Advanced Encryption Standard

Here is a table of "exponentials" with base 03. The entry E(rs) is the field element given by 03rs, where these are hex numbers, and the initial ``0x'' is left off for simplicity.

Table of ``exponentials'': E(rs) = 03^rs
E(rs)s
0123456789abcdef
r
 0  01  03  05  0f  11  33  55  ff  1a  2e  72  96  a1  f8  13  35 
 1  5f  e1  38  48  d8  73  95  a4  f7  02  06  0a  1e  22  66  aa 
 2  e5  34  5c  e4  37  59  eb  26  6a  be  d9  70  90  ab  e6  31 
 3  53  f5  04  0c  14  3c  44  cc  4f  d1  68  b8  d3  6e  b2  cd 
 4  4c  d4  67  a9  e0  3b  4d  d7  62  a6  f1  08  18  28  78  88 
 5  83  9e  b9  d0  6b  bd  dc  7f  81  98  b3  ce  49  db  76  9a 
 6  b5  c4  57  f9  10  30  50  f0  0b  1d  27  69  bb  d6  61  a3 
 7  fe  19  2b  7d  87  92  ad  ec  2f  71  93  ae  e9  20  60  a0 
 8  fb  16  3a  4e  d2  6d  b7  c2  5d  e7  32  56  fa  15  3f  41 
 9  c3  5e  e2  3d  47  c9  40  c0  5b  ed  2c  74  9c  bf  da  75 
 a  9f  ba  d5  64  ac  ef  2a  7e  82  9d  bc  df  7a  8e  89  80 
 b  9b  b6  c1  58  e8  23  65  af  ea  25  6f  b1  c8  43  c5  54 
 c  fc  1f  21  63  a5  f4  07  09  1b  2d  77  99  b0  cb  46  ca 
 d  45  cf  4a  de  79  8b  86  91  a8  e3  3e  42  c6  51  f3  0e 
 e  12  36  5a  ee  29  7b  8d  8c  8f  8a  85  94  a7  f2  0d  17 
 f  39  4b  dd  7c  84  97  a2  fd  1c  24  6c  b4  c7  52  f6  01 

Similarly, here is a table of ``logarithms'', where the entry L(rs) is the field element that satisfies rs = 03L(rs), where these are hex numbers, and again the initial ``0x'' is left off.

Table of ``logarithms'': rs = 03^L(rs)
L(rs)s
0123456789abcdef
r
 0    00  19  01  32  02  1a  c6  4b  c7  1b  68  33  ee  df  03 
 1  64  04  e0  0e  34  8d  81  ef  4c  71  08  c8  f8  69  1c  c1 
 2  7d  c2  1d  b5  f9  b9  27  6a  4d  e4  a6  72  9a  c9  09  78 
 3  65  2f  8a  05  21  0f  e1  24  12  f0  82  45  35  93  da  8e 
 4  96  8f  db  bd  36  d0  ce  94  13  5c  d2  f1  40  46  83  38 
 5  66  dd  fd  30  bf  06  8b  62  b3  25  e2  98  22  88  91  10 
 6  7e  6e  48  c3  a3  b6  1e  42  3a  6b  28  54  fa  85  3d  ba 
 7  2b  79  0a  15  9b  9f  5e  ca  4e  d4  ac  e5  f3  73  a7  57 
 8  af  58  a8  50  f4  ea  d6  74  4f  ae  e9  d5  e7  e6  ad  e8 
 9  2c  d7  75  7a  eb  16  0b  f5  59  cb  5f  b0  9c  a9  51  a0 
 a  7f  0c  f6  6f  17  c4  49  ec  d8  43  1f  2d  a4  76  7b  b7 
 b  cc  bb  3e  5a  fb  60  b1  86  3b  52  a1  6c  aa  55  29  9d 
 c  97  b2  87  90  61  be  dc  fc  bc  95  cf  cd  37  3f  5b  d1 
 d  53  39  84  3c  41  a2  6d  47  14  2a  9e  5d  56  f2  d3  ab 
 e  44  11  92  d9  23  20  2e  89  b4  7c  b8  26  77  99  e3  a5 
 f  67  4a  ed  de  c5  31  fe  18  0d  63  8c  80  c0  f7  70  07 

  1. Use the above tables to calculate (22)*(7e).

    To calculate the product 22 * 7e, use the L table above to look up 22 and 7e: L(22) = 1d and L(7e) = a7. This means that

    If the sum above were bigger than ff, then one would need to subtract 255 but this is not necessary in this case. Now use the E table to look up (03)(c4), which is the answer: (a5).

  2. Show how 22 and 7e are represented as polynomials. Show the steps necessary to multiply them as field elements, using the "magic" polynomial m(x) = x8 + x4 + x3 + x + 1, without actually carrying out the operations.

    So we want (22) * (a7) in the field.
    First (22) = 0010 00102 = x5 + x = (in my special notation) 5 1.

    Similarly, (7e) = 0111 11102 = x6 + x5 +x4 +x3 +x2 + x = (in my special notation) 6 5 4 3 2 1.

    First do the multiplication, remembering that in the sum below only an odd number of like powered terms results in a final term: 

    
 (6 5 4 3 2 1) * (5 1)      gives (one term at a time)

 (6 5 4 3 2 1) * (5)    =  (11  10  9  8  7  6)
 (6 5 4 3 2 1) * (1)    =                (7  6  5  4  3  2)
                          ----------------------------------
                           (11  10  9  8        5  4  3  2)

    The final answer requires the remainder on division by m(x), or (8 4 3 1 0). (This is like ordinary polynomial division, though easier because of the simpler arithmetic.

    
                      (11  10  9  8        5  4  3  2)
 (8 4 3 1 0) * (3) =  (11            7  6     4  3)
                      --------------------------------
                          (10  9  8  7  6  5        2)
 (8 4 3 1 0) * (2) =      (10           6  5     3  2)
                      --------------------------------
                              (9  8  7           3)  
 (8 4 3 1 0) * (1) =          (9           5  4     2  1)
                      --------------------------------------
                                 (8  7     5  4  3  2  1)   
 (8 4 3 1 0) * (0) =             (8           4  3     1  0)
                      --------------------------------------
                                    (7     5        2     0)
                                           (the remainder)
    Thus the remainder is
    (in my special notation) (7 5 2 0) = x7 + x5 +x2 +1 = 1010 01012 = a516. (I used A. Talebi's calculations on the exam to help me get the above correct. You only needed to indicate what calculations to carry out, without doing the actual work.)

  3. In the simplest version of the AES, what are the sizes of: the key, the plaintext, and the ciphertext? What are the number of rounds in the AES algorithm (again shortest version)?

    The AES uses 128 bits = 16 bytes = 4 32-bit words for the shortest key size. (Keys can also be 6 and 8 words long.) The plaintext and ciphertext are always 128 bits long, regardless of key size. For the shortest 128-bit key, the number of rounds is 10.

  4. What is a secure one-way hash function? A hash function h has the property that, for x of any size, h(x) is always a fixed size. (Say, h maps any length input to an output of size 128 bits.) For one-way function, given h(x), it is a difficult computation to find x or even to find any x' such that h(x') = h(x). (The word "secure" here doesn't add any extra meaning.)

    How can the AES be used to provide such a function? (Unless the AES gets broken somehow.)

    Use AES in Cipher Block Chaining mode. Break the arbitrarily long input into blocks of length 128 bits each. Use a publicly known key for the AES and use a publicly known value for the initialization vector. Pad the final input block with zeros if necessary. Then the last output block will be a 128-bit result that satisfies the requirements of a one-way hash function.

Part III: Threshold Schemes

  1. Give the definition of a (3, 3)-threshold scheme.

    See part 4 below with n = 3.

  2. What does it mean for such a scheme to be perfect?

    (See 4 below for notation.) For any (k, n)-threshold scheme, fewer than k shares will not allow the secret to be recovered because there is not enough information. However, in some schemes, fewer than k shares does give some information about the secret. With a perfect scheme, fewer than k shares gives no information about the secret, that is, all possible secrets remain just as likely as they were originally.

  3. Show how to use sources of true random bits and exclusive-or to create a perfect (3, 3)-threshold scheme.

    For the (3, 3) case, start with a secret S of bit length m. Choose two true random bit strings of length m: R1 and R2. Set R3 = R1 xor R2 xor S. Given any two shares, there will still be no information about S, but with all three shares, one can calculate R1 xor R2 xor R3 = R1 xor R2 xor R1 xor R2 xor S = (R1 xor R1) xor (R2 xor R2) xor S = 0 xor 0 xor S = S, where 0 is the bit-string with all zeros.

    Some students started with three true random bit strings: R1, R2, and R3. Then they created a sort of ciphertext C = R1 xor R2 xor R3 xor S. This more-or-less works, but you don't have just three isolated shares of the secret and nothing else. Instead you also need the C. (Technically, one could include C in with one of the shares and have a complete system. In this case, say the third user has R3 and C. Then R3 xor C would equal R1 xor R2 xor S, so this system is essentially the same as the above one.)

  4. Give the definition of a (3, n)-threshold scheme. What must be true about the number n?

    For a (3, n)-threshold scheme, where n must be greater than or equal to 3, start with a secret S. It must be possible to create n shares of the secret: Si, for 1 <= i <= n. Then there is an algorithm to recover the secret S from any 3 or more of the shares, but the secret cannot be recovered from fewer than 3 shares. The general (k, n)-threshold schemd (k <= n) just replaces 3 by k.

  5. In Shamir's scheme, if the "secret" is 47 and you want a (3, 10)-threshold scheme, show how you would construct it (but not how your would recover the secret, which is more elaborate).

    In the particular case of a secret S = 47, n = 10 users, and a threshold value k = 3, one first needs to choose a prime p bigger than 47 and 10. Then choose a random polynomial of degree 3-1: f(x) = a2 x2 + a1 x + 47. (This amounts to choosing two random integers a2 and a1 between 1 and p-1 inclusive.) Finally, one can use the points (i, f(i)), for 1 <= i <= 10, on the graph of f as the shares of the secret. Two points on f give no information about S, but 3 points uniquely determine f, and then S = f(0).

Part IV: Verification Protocol

  1. What is a one-way function?

    See part II.4 above.

  2. Why not have A send h(K) to B and then have B send h(h(K)) to A?

    Then C (Carlos) could pretend to be B: since h is public, C could calculate h(h(K)) and send this to A.

  3. What keeps C from intercepting A's transmission of h(h(K)) and then sending h(K) back to A (assuming C doesn't know K)?

    If C doesn't know K, then a knowledge of h(h(K)) does not allow one to calculate h(K), because h is a one-way function.

Part V: Zero Knowledge Scheme

SPEKE below stands for "Simple Password Exponential Key Exchange", (or perhaps "Secure Password Encrypted Key Exchange".) It involves mutual authentication, which proves to each of two parties that the other knows the password.

What is presented here is a much simplified version of the protocol. You can find out more online using "SPEKE".

  1. Steps i. to iv. resemble another protocol that we studied. What is it, and what is it used for?

    The first four steps are almost the same as the Diffie Hellman key distribution scheme. The only difference is that this protocol uses the secret S as the base for exponentiation instead of a fixed public generator a. Instead of A and B agreeing on a random key K, A and B agree on a special K that depends on S. If the S that both A and B use in the same then the two values of K will be the same.

  2. If the S that A uses is the same as the S that B uses, how do you know that the K's calculated by A and B will be the same.

    All the calculations are carried out mod the public p. In both cases, S is raised to the RA and to the RB powers, in the two different orders. Assuming the S is the same, these yield the same result (just as it does for the Diffie-Hellman protocol), namely S raised to the power RA * RB.

  3. Suppose A is a computer user, and suppose B is the computer system that A uses. What could the shared secret S be and how might one use this protocol?

    As mentioned above, the natural application is for A to prove to B that she knows the system password.

    Note: A and B can convince one another that they share the same secret S, but if B doesn't know A's secret, it will not be revealed.