Sudoku Secret Sharing

© Francisco Ruiz, 2018

This document demonstrates a method to split a secret into three parts, so it can be reconstructed with any two of them. It is an improvement on a method presented by "fgrieu" at this web address, where the subtraction table has been replaced with a simpler addition table, and the operations on the table have been made more ergonomical, for an overall improvement in speed and accuracy.

In essence, the method consists of subtracting the secret from a random string (first part), so that when the result (second part) is subtracted again from the random string the secret is recovered. The third part is obtained by subtracting the secret again from the second part. Thus when the third part is subtracted from the second the secret is once again recovered. What is not so obvious is how the secret is also recovered by subtracting the first part from the third. Let K be the secret and E the random string, which is also the first part. Then the second part is R = E - K, so that K = E - R. And then the third part is S = R - K = E - 2K. If we now compute S - E = -2K, this works out to be the same as K if all the operations are mod 3. Indeed, saying K = -2K is the same as saying K + 2K = 3K = 0, but 3K mod 3 = 0 always, since 3K is always divisible by 3.

The mod 3 operations can be performed by converting the letters into base 3 codes (A=000, B=001, C=002, D=010, and so forth) and then using a base 3 table or, more conveniently, a base 27 table comprising three base 3 figures at a time, and then there is no need to convert the letters into something else, but only to add a character to the set (a period, in this example), so there are 27 of them.

The steps to make the parts in more detail:

1. Process the secret so it is made of the characters A-Z, plus periods. In this example, 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.

2. 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.

3. 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.

4. 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.

5. To obtain the final first, second, and third parts, 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 steps to retrieve the secret from any two parts:

1. 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.

2. 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. 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.

Tableau

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 .

Since the process is different for splitting and joining, we have to tell the program what we want to do via the radio buttons below. When splitting, a different set of matched parts is made each time you click the Run button.

     Split     Join   

 

Step 1. Secret

Secret

When splitting, it is converted to the following after everything is turned into uppercase, diacritics are removed and spaces and other punctuation are replaced by one or two periods. When joining, the process is reversed so the boxes at the bottom are the inputs and the box above is filled last.

Processed Secret

 

Step 2. Splitting/Joining

In order to obtain the draft parts we generate the table below, following the instructions at the top of this page. The top row is the processed secret, the 2nd row is the random part 1, the 3rd row is part 2, the 4th and last row is part 3. When joining, there will be only three rows, with the result at the bottom.

Work table

 

Step 3. Final Parts

The draft parts are converted into final parts by prepending a letter as described above. When joining, this is where you write the parts, in any order; they will be rearranged for the work table.

Part 1

Part 2

Part 3