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

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.

    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.

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

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

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).

  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.

  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)?

  4. What is a secure one-way hash function? How can the AES be used to provide such a function? (Unless the AES gets broken somehow.)

Part III: Threshold Schemes

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

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

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

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

  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).

Part IV: Verification Protocol

  1. What is a one-way function?

  2. Why not have A send h(K) to B and then have B send h(h(K)) 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)?

Part V: Zero Knowledge Scheme

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

  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.

  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?

    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.