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 `kevin.bit.edu`, 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)

NAME
crypt -- generate encryption

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

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

NOTES
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
yourself.

ApollOS 1.3                      Last change: 17 Apr 1970 1                       1
```

### Input

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.

### Output

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

```h8E6dqt5lkL9o
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

```bit0note
```

### Judge's Data

Set 1 input, output
Set 2 input, output