They say that the formula for Coca-Cola is split among the company’s executives, so that a certain number of them have to get together in order to reconstruct it. The same is true of the nuclear launch codes, which require several persons to agree. I just ran into a clever way to do this with pencil and paper, and couldn’t resist improving on it.
This post by “fgrieu” on the Information Security Stack Exchange describes a way to do a paper and pencil secret-splitting scheme where three shares are made but only two are needed to reconstruct the secret. It is based on a clever property of base 3 numbers that I explain below. But before that a description on an even simpler scheme.
To split a string that we’ll call a “secret” into two parts, both of which are needed for reconstructing the secret, you only need to do this: (1) generate a random string of length equal to that of your secret, which will be part 1; (2) add, subtract, or do any other reversible operation using the random string and the secret, which gives part 2. What you are doing is a one-time-pad encryption of the secret, using part 1 as pad, which results in part 2 as ciphertext. Once you get the pad and the ciphertext together (parts 1 and 2), you can undo the operation and retrieve the secret. The process is theoretically impossible to break, no matter how many billions of years of computer time you throw at it.
But we often need some redundancy, when we don’t want to be forever unable to recover the secret in case one of the parts is lost. Let’s say we have three people but we need only two to retrieve the message. One way to do it is to repeat the encryption process described above three times, resulting in three sets of shares that retrieve the same message: (A1,A2), (B1,B2), and (C1,C2). Then we give shares A1 and B2 to the first person, B1 and C2 to the second, and C1 and A2 to the third. You can check that they can always make a complete set of two shares whenever two persons get together. If there are more people, the splitting process needs to be repeated more times, and each person gets a bigger set of shares.
The problem with the above scheme, without getting into how they are going to identify the shares that belong to the same set, is that the amount of data each person is given grows exponentially with the number of people and gets out of hand easily. But there are cleverer schemes that need a lot less data. The most popular among them is the “Shamir Secret Splitting Scheme,” or SSSS for short, which uses the properties of polynomials to do the math.
Unfortunately, SSSS involves a fair amount of computation, which is onerous to do by hand even for a simple 2 out of 3 split. Here’s where fgrieu’s method comes in. You make three shares, only two of which are needed for reconstruction. The first and second shares are made in the conventional way: one is a random string, and the other is the result of encrypting the secret with the first. We already know how to reconstruct the secret from those. So if the secret is K and the random string is E, and the second part R is obtained by subtraction so that R = E – K, then K = E – R is the reconstructed secret. This works with subtraction in any base, but if we use base 3 we get a very interesting result.
Let’s now make a third share S = R – K. We can retrieve the secret from shares 2 and 3 by doing K = S – R, but the clever thing is that we can get it also from the difference of shares 1 and 3, since S = R – K = E – K – K = E – 2K. If we subtract shares 1 and 3 we get: S – E = -2K. Now, in base 3, K = -2K, since then 3K = 0. But this is always true when we use modulo 3 operations (keep only the remainder of dividing by 3), since 3K is always a multiple of 3, and therefore 3K mod 3 = 0 always.
So the trick is to use as operation a subtraction modulo 3. This implies writing everything in base 3, which can get tedious easily when done by hand, but fgrieu gives us a clever shortcut: use letters, plus an extra symbol (27 symbols in total) to represent three base 3 digits each. This allows us to skip the encoding/decoding to and from base 3, plus gives us a simple way to handle spaces and punctuation. Then fgrieu gives us a table to aid in subtraction, used the normal way, that is, looking up one operand on one edge of the table, and the other on a perpendicular edge. And here is my improvement: use an addition table rather than a subtraction table, which ends up simpler-looking and symmetric, but do the operations by starting on one edge and then going down that column (or across that row) until you find the other operand, then perpendicularly to read the result at the edge. This is equivalent to a subtraction, and easier to do with the help of a pointer or just visually.
Here’s the table I came up with. It is made of a number of 3 by 3 blocks, and this is why I call the algorithm “Sudoku”:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z .
-----------------------------------------------------
A | A B C D E F G H I J K L M N O P Q R S T U V W X Y Z . | A
B | B C A E F D H I G K L J N O M Q R P T U S W X V Z . Y | B
C | C A B F D E I G H L J K O M N R P Q U S T X V W . Y Z | C
D | D E F G H I A B C M N O P Q R J K L V W X Y Z . S T U | D
E | E F D H I G B C A N O M Q R P K L J W X V Z . Y T U S | E
F | F D E I G H C A B O M N R P Q L J K X V W . Y Z U S T | F
G | G H I A B C D E F P Q R J K L M N O Y Z . S T U V W X | G
H | H I G B C A E F D Q R P K L J N O M Z . Y T U S W X V | H
I | I G H C A B F D E R P Q L J K O M N . Y Z U S T X V W | I
J | J K L M N O P Q R S T U V W X Y Z . A B C D E F G H I | J
K | K L J N O M Q R P T U S W X V Z . Y B C A E F D H I G | K
L | L J K O M N R P Q U S T X V W . Y Z C A B F D E I G H | L
M | M N O P Q R J K L V W X Y Z . S T U D E F G H I A B C | M
N | N O M Q R P K L J W X V Z . Y T U S E F D H I G B C A | N
O | O M N R P Q L J K X V W . Y Z U S T F D E I G H C A B | O
P | P Q R J K L M N O Y Z . S T U V W X G H I A B C D E F | P
Q | Q R P K L J N O M Z . Y T U S W X V H I G B C A E F D | Q
R | R P Q L J K O M N . Y Z U S T X V W I G H C A B F D E | R
S | S T U V W X Y Z . A B C D E F G H I J K L M N O P Q R | S
T | T U S W X V Z . Y B C A E F D H I G K L J N O M Q R P | T
U | U S T X V W . Y Z C A B F D E I G H L J K O M N R P Q | U
V | V W X Y Z . S T U D E F G H I A B C M N O P Q R J K L | V
W | W X V Z . Y T U S E F D H I G B C A N O M Q R P K L J | W
X | X V W . Y Z U S T F D E I G H C A B O M N R P Q L J K | X
Y | Y Z . S T U V W X G H I A B C D E F P Q R J K L M N O | Y
Z | Z . Y T U S W X V H I G B C A E F D Q R P K L J N O M | Z
. | . Y Z U S T X V W I G H C A B F D E R P Q L J K O M N | .
-----------------------------------------------------
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z .And here is how to use it. In addition to the instructions that follow, I’ve written a JavaScript program that does the calculations for you. First to split a secret:
- Process the secret so it is made of the characters A-Z, plus periods. All letters are converted to upper case, diacritics are removed, spaces, dashes, and commas are turned into periods, and all other punctuation into double periods. Numbers are encoded as 0=A. 1=B, and so forth. Let’s say your secret becomes “BIG.SECRET” which encodes the space as a period.
Count the number of characters in the processed secret and generate a string containing the same number of random characters in the same set (A to Z, plus period). This is the draft first part, which is written in a row right below the processed secret. In our example, there are 10 characters so I generate this 10-character random string: “WRYBLIROXO”
Now do this for each pair of letters forming a column: look up the 1st row letter at the top or bottom of the Tableau shown below and go down or up that column until you encounter the 2nd row letter, then go left or right to read a letter on the side headers, which is written below the other two. Alternatively, you can start on the side and follow the row to find the second letter, then up or down. When finished, this constitutes the draft second part. In our example, the first letter is found by looking up B at the top, then down until we find W, and then horizontally to the edge: V. Doing this for each pair of secret and random letters gives: “VJSOUEPGTW”
Repeat the process in step 3 with the letters in first and third rows (not the 2nd), this time starting with the 1st row letter as before and then finding the 3rd row letter on that column. Read the resulting letter at left or right and write it below the other three. The fourth row thus formed is the draft third part. In our example, this becomes: “XNVYCAQTYD”. The complete work table looks like this:
BIG.SECRET WRYBLIROXO VJSOUEPGTW XNVYCAQTYD
- To obtain the final first, second, and third shares, prepend “E” to the first part, “R” to the second, and “S” to the third. This is so they can be arranged in the proper order when retrieving the secret. The result is this: 1st share “EWRYBLIROXO”, 2nd share “RVJSOUEPGTW”, third share “SXNVYCAQTYD”.
The steps to retrieve the secret from any two shares:
- Write the two parts forming two rows. If one part begins with “E” and the other with “R”, write the one starting with “E” at the bottom. If one begins with “R” and the other with “S”, write the one starting with “R” at the bottom. If one begins with “E” and the other with “S”, write the one starting with “E” at the top. Say we have shares three and one from the example above, so we write the one beginning with E at the top, and the one beginning with S below it.
For each pair of letters forming a column: look up the 1st row letter at the top or bottom of the Tableau shown below, and then go down or up that column until you find the 2nd row letter, then left or right to read the result on a side header. As when splitting, you can also start on the side and follow a row until the second letter is found, then up or down. The string made from all the resulting letters is the secret. This is the work table we come up with:
EWRYBLIROXO SXNVYCAQTYD .BIG.SECRET
You will know that you wrote the parts in the correct order because the first character of the result is a period, which can then be discarded. Not all punctuation can be recovered, but at least you can identify periods or major punctuation as double periods.
And that’s it. Since the algorithm is ultimately based on a one-time pad, having a single share does not give you any information on what the secret is, but any two gives you the whole thing. I hope you like it.