Scribd
Upload
60 views3 pages

Key Recovery and Escrow in Encryption

This document describes a laboratory exercise on key splitting and recovery using the Chinese Remainder Theorem. Students will split a 3-digit key into 3 pieces by dividing the key modulo 3 different moduli and exchanging pieces with another student. They will then enter the received pieces and moduli to recover the original key through calculations using the moduli, pieces, and their inverses.

Uploaded by

lakshmisudarshan
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
60 views3 pages

Key Recovery and Escrow in Encryption

This document describes a laboratory exercise on key splitting and recovery using the Chinese Remainder Theorem. Students will split a 3-digit key into 3 pieces by dividing the key modulo 3 different moduli and exchanging pieces with another student. They will then enter the received pieces and moduli to recover the original key through calculations using the moduli, pieces, and their inverses.

Uploaded by

lakshmisudarshan
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd

CPSC 6126 – Computer Security Name: ________________________

Spring, 2003

LABORATORY EXERCISE 2b
Second Encryption Exercise:
Key Recovery and Key Escrow

This is an experiential lab exercise. You must complete this exercise with one of your
classmates.

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 that are
impossible for most human beings to remember. Face it: many people have trouble
remembering their passwords or PINs, much less a 100- or 200-digit key. The solution is
to store these numbers on a secondary memory device that’s not easily accessible by
unauthorized “third parties”1 (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 third 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”
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. We will
be discussing these proposals in class.

1
The sender and receiver of the encrypted message – usually called Alice and Bob – are the first and
second party.
CMPT 109 Spring, 1998
Lab Exercise XIV page 2

1. Launch Excel and open the file

[Link]

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

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

3. Use the last three digits of your SSN as the three-digit key value. Enter this value in
cell B6. Record this value below:

________________

4. If they’re not already there, enter the values 11, 13 and 16 in cells B14, B15 and B16,
respectively. These values are your moduli.2 (It is not absolutely necessary to use
the three moduli above. You could choose any three numbers between 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. For example, you could choose 14, 15
and 23.)

Record your three moduli below:

__________ __________ __________

5. The spreadsheet will split your key into three pieces by dividing by each of the
moduli and taking the remainder. The three pieces of your key will appear in cells
C14, C15 and C16. Record the values of these pieces below:

__________ __________ ___________

6. 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 sheet of paper and
exchange pieces with a student at another computer.

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

2
Moduli is the plural of modulus, a term you encountered in the first encryption exercise. 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.
CMPT 109 Spring, 1998
Lab Exercise XIV page 3

8. Enter the other student’s moduli in cells B7, B8 and B9. Enter her/his corresponding
key pieces in cells C7, C8 and C9. Record all six of these values below:

Modulus Corresponding piece

________ _________

________ _________

________ _________

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 B are 11, 13 and 16, the
corresponding cells in column C will contain 13*16 = 208, 11*16 = 176, and
11*13 = 143, respectively
 Each row in column D contains the inverse of the value in column C with respect
to the modulus in column B. To see this, enter the following formula in cell F7:

= MOD (C7*D7,A7)

MOD is a built-in function that divides its first argument by its second and takes
the remainder. What value appears in cell when you enter this formula?

______________

Select the range F7:F9 and fill down. What values appear in cells F8 and F9?

F8: ___________ F9: _____________

All of these values should be 1. This illustrates the concept of an inverse.

 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.
 To recover the key, multiply each piece by the corresponding “magic number.”
Divide the result by the product of the moduli and take the remainder. Because of
the special way we have constructed the magic numbers, this calculation produces
the original key.

The recovered key value should appear in cell E11. Record this value below. Check
with the other student to see that you have correctly recovered her/his key.

Common questions

Powered by AI

The Chinese Remainder Theorem is utilized in key splitting by dividing a key into parts using different moduli, whereby each part is the remainder of the key divided by different moduli . By storing each part with different parties, this method improves security because no single party has access to the complete key, aiding in secure key recovery without compromising the entire key .

Key escrow systems that permit governments to recover encryption keys without an individual's knowledge raise significant ethical concerns. This approach could infringe on privacy and autonomy as it allows authorities to access private communications potentially without user consent . It creates a possibility for misuse by authorities if the process lacks transparency and accountability. Balancing security and privacy is crucial, and obtaining warrants for such access presents both legal and ethical challenges .

The assumption that storing key parts with different third parties inherently enhances security can be flawed. While it reduces the risk of a single point of failure, it assumes perfect trustworthiness and coordination among parties. If any party is compromised, it could expose a portion of the key. Additionally, if the third parties do not have stringent security measures or could potentially be coerced or hacked, the key parts remain vulnerable. Furthermore, coordination to retrieve keys might introduce logistical challenges and vulnerabilities .

Selecting moduli with no common factors larger than 1 is crucial in the key splitting process to ensure the mathematical integrity of the Chinese Remainder Theorem's application. It prevents any overlap or duplication in divisor results, which is necessary to uniquely define each part of the key. This ensures that no two parts can recreate another, which safeguards against unauthorized synthesis of the original key if only a subset of the parts is revealed .

Using common memory devices such as diskettes for key management presents challenges due to modern security threats. These devices can be easily compromised if physical and logical security measures are not robust. Damage or corruption of such devices results in key loss, highlighting the importance of redundancy and secure backups . With the increase in sophisticated attacks, relying solely on such devices is impractical without additional layers of encryption and access control to protect against unauthorized access or data corruption .

In key splitting, moduli are used to divide a key into parts by taking remainders, facilitating secure storage across multiple parties . In contrast, the RSA method uses moduli as a core part of public-key encryption, where a modulus is formed from two large prime numbers and used for encrypting and decrypting messages. While both utilize the concept of remainders, their applications are distinct: one for key fragmentation and recovery, and the other for data protection and encryption .

The requirement of warrants for law enforcement to access keys in escrow systems aims to align with privacy laws by legitimizing access through legal channels . However, this system challenges privacy norms by potentially allowing invasions on personal data without the key holder's knowledge, depending on the transparency and regulation of the warranting process. If not properly regulated, it risks overreach and abuse, contravening core principles of user privacy and potentially undermining trust in legal and encryption frameworks .

Key recovery involves using the split parts, each associated with moduli, to reconstruct the original key. The "magic numbers" are calculated using products of moduli and their inverses . Each piece of the key is multiplied by its corresponding magic number. The result is divided by the product of the moduli, taking the remainder to recover the original key. This process ensures that even with partial knowledge of parts, one can reconstruct the entire key systematically .

The 'Analysis ToolPak' in Excel is necessary to perform functions required for the key splitting and recovery processes, such as modulus calculations. The spreadsheet features enable input of key values, moduli, and the division of keys into parts. Functions like multiplication and calculating remainders automate the process of key splitting and recovery, easing the understanding and application of complex mathematical principles .

The two primary problems in key management for encryption systems are: (1) compromising a securely stored key, which could be discovered or stolen by an unauthorized party, and (2) loss of the key due to destruction or corruption of the storage device where it is stored . Potential solutions include using a trusted third party to keep a copy of the key or splitting the key into parts and having different third parties store each part .

You might also like