July 2002 Programmer's Challenge
One Time Pad
Mail solutions to:
progchallenge@mactech.com
Due Date: 11:59pm ET, Saturday, 6 July 2002
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:
void InitOneTimePad(
const char *oneTimePad,
/* NULL terminated text to be used for the one-time pad */
/* You should ignore (skip) any characters not in the range 0x20-0x7E, inclusive */
const char *dictionary[],
/* list of NULL-terminated words in the vocabulary, sorted in ASCII order */
long numDictionaryWords
);
void DecryptMessage(
const char *encryptedMessage,
/* NULL terminated text to decode */
/* Guaranteed to contain only characters in the range 0x20-0x7E, inclusive */
char *decryptedMessage,
/* Return decrypted message, same size as encryptedMessage*/
long *offset
/* offset into the oneTimePad that you determine to be the basis for encryption */
);
void TermOneTimePad(void);
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 nth character x of the clear text is encrypted as x+y-0x20, modulo the legal range of the character set, where y is the nth 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".
|