Not an official ACM page
[1996 East-Central problem set | My ACM problem archive | my home page]

ACM East Central Region
1996 Regional Programming Contest

Problem 7 - Enigmatic Encryption

One Saturday morning, Valentine McKee attempted to log into, the new BIT supercomputer, to work on her new MPI implementation. After a few failed login attempts, Valentine put her head in her hands. "I can't believe it! I've forgotten my password!"

Valentine thought for a few minutes. She remembered choosing her password as a combination of two words from the body of her thesis. The password program on kevin had required her to make the password between 5 and 8 characters long with at least one "special" character (non-alpha), so Valentine had also incorporated a numeral into the password. "Either 0, 2, 4, or 8, between the two words," she recalled. Also, to save typing effort, the she had used only lowercase for the letters. She could not recall, however, whether or not the original words had been all lowercase. She did recall that both words were longer than just a single character.

Valentine started to read through the most recent printout of her thesis, trying to jog her memory of the password, but to no avail. Finally, she said, "My thesis is on line in my lab and I have a record there of my encrypted password. I never thought I would have to use it, though."

She sighed as she invoked man crypt to determine how crypt() processes passwords.

crypt(3C)                      C Library Functions                       crypt(3C)

        crypt -- generate encryption 

        char *crypt(const char *key, const char *salt); 

        crypt() is the password encryption function. It is based on a one-way
        encryption algorithm with variations intended (among other things) to
        frustrate use of hardware implementations of a key search.

        key is the input string to encrypt, for instance, a user's typed password.
        Only the first eight characters are used; the rest are ignored.  salt is
        a two-character string chosen from the set [a-zA-Z0-9./]; this string is
        used to perturb the hashing algorithm in one of 4096 different ways,
        after which the input string is used as the key to repeatedly encrypt a
        constant string.  The returned value points to the encrypted input string.
        The first two characters of the return value are the salt itself.

        The return value for crypt() points to static data that are overwritten by
        each call.

        The crypt() function is provided for you. You do not have to write it

ApollOS 1.3                      Last change: 17 Apr 1970 1                       1


The first line of input is the encrypted password. The next lines of input are the contents of Valentine's thesis. Each input line will consist of 80 or fewer characters of printable ASCII text and will be terminated by a newline. No lines will be empty. Words are assumed to be any contiguous set of alphabetic characters (upper or lower case), separated by whitespace or punctuation.


The output of the program is Valentine's original password.

Note from Ed.: This problem requires the system function crypt(). If your system does not have a compatible implementation, try using this. It is from the BSD sources. It worked on my IRIX 6.3 box, but had slight problems when compiled with Borland C++ 3.1 under MS-DOS.

Sample Input

The parallel algorithms were executed on the Connection Machine model 
CM-2 --- a single-instruction multiple data (SIMD) parallel computer 
which, in its largest configuration, contains 65,536 bit-serial 
processors and 2048 Weitek floating-point units (FPU's). 
The bit-serial processors are clustered together into groups of 16 
within a single integrated circuit, and these IC's are connected 
together in a 12-dimensional hypercube. Two IC's, or 32 processors, 
share a single Weitek FPU. Note that a fully configured CM-2 contains 
2048 times as much floating point hardware as a conventional computer 
containing a single Weitek FPU (e.g., a SUN-4). 

Output for the Sample Input


Judge's Data

Set 1 input, output
Set 2 input, output

This page maintained by Ed Karrels.
Last updated November 25, 1997