One-time pad
Introduction
There are many forms of encryption. The strength of these varies enormously. One that is universally acknowledged as being uncrackable by cryptoanalysis is the one-time pad. This will remain true regardless of any future advances in mathematics or increases in computer speed.
The one-time pad works like this. Two people, A and B, wish to communicate securely. They each have a copy of a pad holding a series of randon numbers. A uses his copy of the pad to encrypt a message. This example is slightly simplified to aid the explanation, but the full implementation will be covered later.
The message begins "SECRET" and the one-time pad begins 13 4 8 13 20 7. A advances each letter in the message through the alphabet by the number of letters on the pad. If this goes past Z then it loops back to the start of the alphabet.
- S + 13 becomes F
- E + 4 becomes I
- C + 8 becomes K
- R + 13 becomes E
- E + 20 becomes Y
- T + 7 becomes A
A then immediately destroys the part of the one-time pad used for the message.
A sends B "FIKEYA".
B reverses the process by subtracting the numbers on the one-time pad.
- F - 13 becomes S
- I - 4 becomes E
- K - 8 becomes C
- E - 13 becomes R
- Y - 20 becomes E
- A - 7 becomes T
B then immediately destroys the part of the one-time pad used for the message.
The strengths of this system are:
The message can ONLY be decrypted using the part of the one-time pad which has been destroyed.
The part of the pad used is effectively a randomly generated encryption key that is the length of the message and is only ever used for one message. Some countries have legislation that requires an indiviual to surrender any encryption keys they have to allow encrypted messages to be decrypted, but since the key has been destroyed there is nothing to surrender and the message remains secret.
The weakness is that there must be a secure way of A and B exchanging the one-time pad to start with.
The method can be applied to any computer file with these changes:
- Computer files consist of a series of numbers (bytes) from 0 to 255
- The numbers on the one-time pad should be 0 to 255
- Each byte in the message file will be XORed with the a byte from the one-time pad to encrypt. XOR the encrypted byte again with the same byte from the one-time pad results in the original value from the message. This is simpler and quicker for the computer to do than adding and subtracting numbers and keeping the numbers in the 0 to 255 range.
Since computer files can be millions of bytes long:
- A very large one-time pad is needed to encrypt it.
- A computer program is the only practical method for encrypting a large file
Neither of these are problems because:
- A large one-time pad can easily be created using a computer program.
- Even a one-time pad that is several GB in size can be exchanged on something as small as a microSD card which is about the sizeof a fingernail.
Programs to do the encryption and decryption are quite simple and will be described later.
A Perl version of a one-time pad system
I have written a set of Perl programs to implement a one-time pad system. Although there are many other computer languages that I could have used that would run much faster, I have selected Perl because:
- Trust
- Portability
Trust
Anyone who is security conscious enough to use encryption, will be very wary of running a program from an unfamiliar source, because of the risk of it being a Trojan i.e. the program does a lot more than it admits to.
Most programming languages generate compiled code, so its true actions can not be readily checked and must simply be trusted.
Perl is an interpreted scripting language, so the actions of the code are still readable. A small, well written and commented script can be easily examined by someone with a little computer knowledge to verify that that it is not doing anthing malicious.
Portability
The Perl interpreter is installed as standard on many computers and is available to install for free on most others.
One-time pad format
Since the one-time pad is used multiple times for different messages, we need to track where the next unused part of the pad begins. I store a number at the start of the file (before the random data begins) to hold this location and refer to it as the "bookmark".
Encrypted message format
At the start of the encrypted message will be a the value of the bookmark used when the file was encrypted. The rest of the file is the encrypted message.
The set of programs are:
- createpad.pl
- encrypt.pl
- decrypt.pl
- getbookmark.pl
- setbookmark.pl
createpad.pl
Syntax: perl createpad.pl onetimepad_file pad_size
This creates a file with pad_size bytes of random data prefixed with a bookmark that points to the first byte of random data.
encrypt.pl
Syntax: perl encrypt.pl message_file onetimepad_file encrypted_file
This:
- encrypts message_file to encrypted_file using onetimepad_file
- deletes the part of onetimepad_file used for the encryption
- updates the bookmark in onetimepad_file
- deletes the message_file
decrypt.pl
Syntax: perl decrypt.pl encrypted_file onetimepad_file message_file
This:
- decrypts encrypted_file to message_file using onetimepad_file
- deletes the part of onetimepad_file used for the decryption
- updates the bookmark in onetimepad_file
- deletes the encrypted_file
getbookmark.pl
Syntax: perl getbookmark.pl onetimepad_file
This displays the value of the bookmark from the given one-time pad.
setbookmark.pl
Syntax: perl setbookmark.pl onetimepad_file new_bookmark
This sets the value of the bookmark in the given one-time pad and erases the data between the old bookmark and the bookmark.