CIS 3319 Lab: Key Recovery and Key Escrow

CIS 3319 Lab: Key Recovery and Key Escrow
 

First, find a lab partner. 

 

One of the problems with any type of encryption system – public-key or secret-key – is key management.  Decryption keys and moduli are usually very long numbers (100- or 200-digit key) that are hard for human beings to remember.  The solution is to store these numbers on a secondary memory device that’s not easily accessible by unauthorized party (perhaps on a diskette that one keeps in a secure place).  There are two possible problems:

Ÿ  Even a key that is kept in a secure location can be compromised – discovered or stolen by an unauthorized party.  Anyone who suspects that his/her key has been compromised should get a new key. 

Ÿ  The storage device on which the key is stored could be destroyed or corrupted.  In either case, the key is lost.  One possible solution is to ask a “trusted third party” to maintain a copy of the key.  This assumes that one can find such a trusted third party.  An individual may be willing to trust a close friend, but this is not possible for a business.

 

A second solution is to split the key into two or more parts, and ask a different third party to store each part.  The purpose of this laboratory exercise is to explore one method for doing this.  This method is based on a famous mathematical theorem called the Chinese Remainder Theorem.  To make things easy, you will be using three-digit keys.

 

This is also the basic idea behind the various “key-escrow” proposals from the United States government.   All keys would be split into two or more parts, with each part entrusted to a different public or private agency.  The idea is that the police could recover the key without the individual’s knowledge by obtaining warrants against each of the escrowing agencies.  This would permit the police to “listen in” on encrypted communications or to read encrypted files without the key holder’s knowledge.   

 

The steps of the lab exercises are given below:

1.      Launch Excel and open the file: Lab2_keyshare.xls;

2.      Choose Add-Ins from the Tools menu, and be sure that the Analysis ToolPak is checked.

3.      Click on the tab for labeled Key Splitting.  This reveals a worksheet for splitting a three-digit key into three parts.

4.      Use a prime number closest to the last three-digit of your Temple student ID as the three-digit key value.  Enter this value in cell B6.  Record this value below: ______059______

                                                                                   Your student ID: 915552057

5.      Select three moduli[1] and enter the values in cells A14, A15 and A16, respectively.  These values are three numbers between 10 and 31, (i.e., the cube root of 1000 – 10 – and the square root of 1000 – approximately 31) – such that no pair of moduli has any common factor larger than 1.  Record your three moduli below:

_____11____                    ____12____                ____13____



6.      Split your key into three pieces by dividing the key by each of the moduli and taking the remainder.  Record three pieces of your key in cells B14, B15 and B16.  Also record the values of these pieces below:  ___4___                  ___11_____                ____7_____    
In reality, one would ask three different parties to each store one piece.  Instead, write down your three moduli and the corresponding three pieces on a sheet of paper and exchange it with your partner.

 

7.      Click on the tab labeled Key Recovery.  This reveals a worksheet for recovering a key from its three parts.



8.      Enter your partner’s moduli in cells A7, A8 and A9.  Enter your partner’s corresponding key pieces in cells B7, B8 and B9.  Record all six of these values below:


       Modulus               Corresponding  Key Piece

 

       __11___               ___________1__________

       ___23___             ___________14__________

 

       ___31___             ___________14__________

 

10.  The key recovery calculation takes place in cells C7:E9 and cell E11.  It works as follows: 



Ÿ  In each row of column C, compute the products of the moduli in the other two rows.  For example, if the moduli in column A are 11, 13 and 16, the corresponding cells in column C will contain 13*16 = 208, 11*16 = 176, and 11*13 = 143, respectively

Ÿ  Calculate the inverse (stored in column D) of the value in column C with respect to the modulus in column A. I.e., C7*D7 Mod (A7) = 1.  Record the values in column D below:

D7:_____16_______               D8: ______17______                         D9: _____25________




Ÿ  The “magic numbers” in column E are just the product of the inverse and the other moduli.  Thus, the magic number in cell E7 is just C7*D7.  Note that this is just the product of the number in cell C7 and its inverse. Record the values appear in cells E7, E8 and E9.

E7:____ 11408____               E8: ___ 5797____                        E9: ____ 6325____




Ÿ  To recover the key, multiply each key piece by the corresponding “magic number”, i.e., B7*E7, B8*E8, & B9*E9, and then do the following computation: 

(B7*E7 + B8*E8 + B9*E9) Mod (A7*A8*A9)

Because of the special way we have constructed the magic numbers, this calculation produces the original key. Record the recovered key value in cell E11.  Also record this value below.  Check with your partner to see that you have correctly recovered her/his key.

The recovered key is ___ 727___ 


 
[1] Moduli is the plural of modulus, a term you encountered in the first encryption exercise, i.e., n = p*q.  These moduli are not really the same as the modulus in the RSA public-key encryption method.  However, they are both applications of the same basic mathematical concept.