A one-time pad, used properly, provides a simple and unbreakable method of encryption. The "pad" is a random block of data equal in length to the message to be encoded. Two copies of the pad are needed, one for the message sender and one for the message receiver. The message to be encrypted is combined with the data in the pad by, for example, an exclusive OR; transmitted to the recipient, and decoded by the inverse operation. To be unbreakable, the pad must consist of truly random data, and it must be used only once.

Of course, you still need to securely exchange a one-time pad for each message to be encrypted. Let’s imagine that this is too much trouble, so what we are going to do instead is to use some common text as the basis for our one-time pad. We’ll select the "random" block as an offset from the first character in that text. And we’ll reuse our "one time" over and over again for different messages, with different offsets. Since the text isn’t random, and the one-time pad is used multiple times, we may have compromised security somewhat. This is a Good Thing, because your Challenge is to crack a sequence of messages encrypted with this scheme.

The prototype for the code you should write is:

Your InitOneTimePad routine will be called each time our Intelligence Service captures a new one-time pad being used by our adversary. You will also be given a sorted dictionary of words in the vocabulary of our adversary. You can allocate memory and do whatever analysis might be appropriate.

For each intercepted message, your DecryptMessage routine will be called with the encrypted text. Fortunately, we know that our encrypting adversary uses the oneTimePad in a consistent manner. S/he uses a section of the pad starting at an offset known to the sender and receiver, but unknown to us. The section of the pad used is as long as the encrypted message, ignoring any characters in the pad (beyond the offset) outside the range of printable ASCII characters (0x20-0x7E). The n^th character x of the clear text is encrypted as x+y-0x20, modulo the legal range of the character set, where y is the n^th legal character of the oneTimePad beyond the offset value. So, if the oneTimePad [offset] starts with "When in the Course<CR> of human events", and your clear text is "The British are coming.", the encrypted text would be ",QKnB\Xt^\N<SP>%b[rWUmYUgv", where <CR> denotes a nonprintable (and ignored) carriage return and <SP> denotes a space character that you might not otherwise notice. Note that nonprintable characters are counted in determining the starting position (offset) within the pad.

You should determine the section of the one-time pad that was used for encryption, decrypt the message, store the oneTimePad offset used for this message, and return a NULL-terminated string containing the clear text.

Your TermOneTimePad routine should return any dynamically allocated memory.

The winner of this Challenge will be the entry that correctly solves all test cases while incuring the lowest cost. Solutions will incur a cost of 10 points per millisecond of execution time, including the time incurred for initialization, decryption, and termination. You can earn a bonus of up to 25% reduction of incurred cost based on a subjective evaluation of the clarity of your code and commentary.

This will be a native PowerPC Carbon Challenge, using the Metrowerks CodeWarrior Pro 7.0 development environment. Please be certain that your code is carbonized, as I may evaluate this Challenge using Mac OS X.

Test code for this Challenge is available.

You can get a head start on the Challenge by reading the Programmer's Challenge mailing list. It will be posted to the list on or before the 12th of the preceding month. To join, send an email to listserv@listmail.xplain.com with the subject "subscribe challenge-A". You can also join the discussion list by sending a message with the subject "subscribe challenge-D".