A one-time pad (OTP) is a coding system that cannot be cracked. The system uses a set of random characters (the OTP) to encode a message by a sender. The receiver, who also has the OTP, decodes the message. The rules for keeping the OTP secure are:
1. Only the sender and receiver have the OTP. That is, the key is truly secret.
2. The OTP is only used once.
3. The OTP must be at least the same length as the message. If it isn't, then part of the OTP would be used over and that would violate Rule 2 above.
4. The OTP must be truly random.
The term one-time pad is used because the original system used two identical pads of sheets containing random characters. The users would each use one sheet from their pads for a message then destroy the sheets used.
It has been proven that the OTP provides perfect secrecy. This seems like a bold statement given the ever-increasing power of computers. One would think the code could be cracked by use of the brute force method - using a super-computer to try every possible key to decrypt the encoded message. While a super-computer could try every possible key, in doing so it would also produce every possible message of the given length of the OTP.
Here's an example, I used the Boxentriq Code-Breaking site to encode the ten-character message "KISS POTUS" using the OTP key of "JIHGFEDCBA" to produce the result "TQSRTRVVS". My key doesn't follow Rule 4 but it I'm using it just for demonstration purposes. The supercomputer would eventually get to the key "JIHGFEDCBA" and produce the result "KISS POTUS"; however, it would also produce every other possible ten-character combination, including "KICK POTUS", "I LIKE YOU", "GO HOME NOW" and millions of other possible messages and many more millions of just random, scrambled letters. While the supercomputer "cracked" the code, one would not know which of the millions of results was the intended message.
There are weaknesses of the OTP system. Keeping the key secret is a human weakness. Producing truly random characters is system weakness.
A Proposal for Improvement
Instead of the sender and receiver having long, identical pads, they agree on the digits of a single irrational number to be used as the key for the OTP. Irrational numbers, such as the square root of 2, can be expressed succinctly (and have the advantage that their digital expansion continues infinitely without any recognizable pattern - square root of 2 = 1.414213562373095048801688724210...).
The users of the code would agree on what irrational number to be the key for their initial message. The sender would reserve the last few characters of the message to indicate the key for the next message - another irrational number. There is an unlimited supply of such numbers. One could also have a program to randomly produce each subsequent key to use.
I'm new to this subject, so it is very possible someone has already suggested this method.
A site with resources for many code systems: Boxentriq Code-Breaking
Wikipedia entry: One-time pad
An example of a ten million digit pad based on the digits of pi. Digits of pi are discussed in these other posts.
8/6/2021 update: also review Vigenere cipher
6/21/2024 updated: I've made a Mathematica routine to encode and decode messages using the strategy noted in this blog post. Leave a comment with your email and I'll share with you.
No comments:
Post a Comment