*One Time Pad (OTP) encryption*
By: Toboe
09 April 2005

The One Time Pad, or OTP, is often described as the only provably secure method for encrypting information. Still, it is the one of the simplest to use. The caveat: you have to keep the key safe (as with any properly designed encryption algorithm – the OTP only makes it more difficult than usual), and you must not ever use a key stream that has already been used to encrypt one message, to encrypt another. If you do, breaking the encryption on both messages becomes a trivial textbook excercise in elementary cryptanalysis. If this sounds complicated, believe me, it isn't.

The OTP gets its security from a random key stream, exactly the length of the message to be encrypted. As long as any given key stream is equally likely, any plaintext of the given length is also equally likely and so it can never be proven whether or not the decryption presented is the correct one. This also lends itself well to handling a possible extortion situation: finding a key stream to give a specific plaintext given a ciphertext is trivially easy. If forced to reveal the plaintext, you simply hand out the second key stream. No one can prove that it does not present the intended decryption. If the key stream is chosen carefully and can be chosen in conjunction with the plaintext, it is also possible to disguise the encrypted message as an unencrypted one. Beware, however, that any predictability in the key stream will weaken the cipher, possibly even to the point of making it breakable. Another way to obtain key material is to have an agreed-on set of books, and specify which book is to be used and on what page, row and possibly character the key stream begins, and if any characters are to be skipped. Done right this can be almost as secure as a purely random key stream and at the same time do away with a large part of the key distribution and storage problem.

Mathematically, OTP encryption is defined as simple additions modulo N, where N is the number of possible characters. On computers, it is most often implemented using XOR (the exclusive-or operator, which can be seen as bitwise addition modulo 2). Please note that the scheme outlined below will not be compatible with such a computer implementation. Given a key stream K_n and a plaintext P_n (where n is in the range of 1 to the length of the text to be encrypted), encryption is simply:

C_n = P_n + K_n mod N

Let's look at a practical example. The message we want to encrypt is "returntobase" and the key stream, which has been distributed previously through a known secure channel (this actually is the OTP's biggest drawback) is "ymvowpynwlep". We now have:

	R	E	T	U	R	N
+	Y	M	V	O	W	P
=	Q	R	P	J	O	D
	T	O	B	A	S	E
+	Y	N	W	L	E	P
=	S	C	Y	M	X	U

The ciphertext, thus, is "qrpjodscymxu". Which just happens to also decrypt just fine to "dinnersready" (using the key "uibvjlzktltv"), or for that matter any twelve-letter combination that you can come up with. How do you prove which decryption is the "correct" one? It is impossible if the key streams are equally likely (a property only held by purely random keys).

To do encryption and decryption, I have found that making up a pair of substitution tables ahead of time is the easiest (you could also make the table or tables as the need arises, but be warned that without a computer and appropriate software, it will take a while). It takes some time to set up, but because the tables themselves contain no sensitive information, they can be easily distributed and stored arbitrarily. (You can even use the tables I have made below, if you just need upper case English letters.) Start out by deciding what alphabet you want to use: any letters, numbers, punctuation and so on that you want to be able to encrypt. Throughout this article, I use a simple upper case English letters alphabet, but there is nothing preventing you from using a larger or for that matter smaller one. (For example, if you just need to encrypt geographic positions, the numbers 0-9, a period or some other delimeter, and the letters E, W, N and S will most likely suffice. The resulting ciphertext will look most peculiar...) Then, write the alphabet down in a grid: once along the horizontal axis, and once along the vertical axis. For your convenience, you can also write it down just outside the grid you will be using. You now have something resembling the following:

Now for the boring part. For each row/column combination, shift the plaintext letter to the RIGHT in the alphabet the number of positions given by the key letter's position. For example, for A, shift each plaintext letter right one step (since A is the first letter of this alphabet), and for H, shift right eight steps. If you end up beyond the end of your alphabet just start back at the first character, but keep counting. For example, Y + D mod Z = C (25 + 4 mod 26 = 3). You can also see this as shifting the plaintext alphabet to the left for each key character. In the end, for our 26-letter alphabet, this is what you will get:

Then, do the same thing all over again, but shift the alphabet in the opposite direction this time and use the label "ciphertext" instead of "key". The result will be your decryption table:

When distributing the substitution tables, keep in mind that the tables themselves do not need to be kept secret – only the key and plaintext (which really are just opposite sides of the same coin) have to be. Any determined adversary will be able to determine what alphabet you are using quickly enough anyway.

But how does it work?

To encrypt a message character by character using a table like this, first locate the plaintext character in the leftmost column of the encryption table. Then locate the key character in the top or bottom row (labelled "Key->" here for your convenience). Where the row and column intersect, read the ciphertext character.

To decrypt, find the ciphertext in the top or bottom (C/T) row of the decryption table, the key to the left and read the plaintext at the intersection.

To find the key to get a given plaintext from a given ciphertext, use the decryption table and look up the ciphertext character in the C/T row, locate the desired plaintext character in that column and read the key character to the left.

The key distribution problem

I mentioned above that the key is the OTP's biggest problem. That's not a joke. The OTP's security is completely dependent on the key stream (a) being secure and (b) never being reused. You need some kind of trusted channel to distribute key streams ahead of schedule, and once you are out of key material, you cannot communicate any further without risking exposing previous communications as well as current traffic. Also, the amount of key material required is equal to the length of the message to be encrypted. These drawbacks make the OTP unsuited for anything but short, extremely sensitive messages. But can you decrypt by hand a PGP-encrypted message sent to you? I certainly am not up to the task.

Now. You just received an encrypted transmission from your TL. The ciphertext is UPJR TLZU RQMW HP and the key to be used for this particular transmission is QXAD IYKC MTLC CX. Your team uses the 26-letter alphabet exemplified above. Use the decryption table and find out what is expected from you. If you are feeling competetive, see how long it takes you to do it and then try to get it done faster without sacrificing accuracy. If at all possible, ask someone else (a family member, team member or someone else) to give you the keys and ciphertexts for this excercise, without revealing the plaintext. All you need to know is whether or not you decrypted the message correctly. The correct message is here, reversed: RETA WERO MKNI RD.
Toboe

www.alpharubicon.com
All materials at this site not otherwise credited are Copyright © 1996 - 2005 Trip Williams. All rights reserved. May be reproduced for personal use only. Use of any material contained herein is subject to stated terms or written permission.