of them can be used to reassemble the original secret.
It must be the case that
.ie t $1 <= "thresh" <= "count" <= 255$.
-.el \{\
-1
-\(<=
-.I thresh
-\(<=
-.I count
-\(<=
-255.
-.\}
+.el .RI "1\~\(<= " thresh "\~\(<= " count "\~\(<= 255."
.PP
The first line contains secret-sharing parameters,
which will be required in any recovery operation.
The share's index,
as a decimal integer;
.ie t $0 <= i < "count"$.
-.el \{\
-0 \(<=
-.I i
-<
-.IR count .
-.\}
+.el .RI "0\~\(<= " i "\~< " count .
.TP
.B y
The share data, Base64 encoded.
be a field.
Suppose we are given a secret
.ie t $s member k$
-.el \{\
-.I s
-\*(mo
-.I k
-.\}
+.el .IR s \~\*(mo\~ k
which we want to split into shares
such that any $t$ of them can be used to recover
.IR s .
Choose coefficients
.ie t $a sub i member k$
-.el \{\
-.IR a _ i
-\*(mo
-.I k
-.\}
+.el .IR a _ i \~\*(mo\~ k
for
.ie t $1 <= i < t$
-.el \{\
-1 \(<=
-.I i
-<
-.I t
-.\}
+.el .RI "1\~\(<= " i \~<\~ t
at random.
Let
.ie t $p(x) = s + a sub 1 x + ... + a sub {t-1} x sup {t-1}$.
.el \{\
-.IR p ( x )
-=
-.I s
-+
-.IR a _1
-.I x
-+ ... +
-.IR a _( t \-1)
-.IR x ^( t \-1).
+.IR p ( x ")\~= " s "\~+ " a "_1\~+ ...\~+"
+.IR a _( t \-1)\~ x ^( t \-1).
.\}
Note that
.ie t $p(0) = s$.
-.el \{\
-.IR p (0)
-=
-.IR s .
-.\}
+.el .IR p "(0)\~= " s .
We can evaluate
.I p
to obtain shares
.ie t $y sub i = p( x sub i )$
-.el \{\
-.IR y _ i
-=
-.IR p ( x _ i )
-.\}
+.el .IR y _ i "\~= " p ( x _ i )
for various
.ie t $x sub i member k - lbrace ~ 0 ~ rbrace$.
-.el \{\
-.IR x _ i
-\*(mo
-.I k
-\-
-{ 0 }.
-.\}
+.el .IR x _ i "\~\*(mo " k "\~\- {\~0\~}."
.PP
How do we recover the secret?
Suppose we are given
.ie t $y sub i = p( x sub i )$
-.el \{\
-.IR y _ i
-=
-.IR p ( x _ i )
-.\}
+.el .IR y _ i "\~= " p ( x _ i )
for
.ie t $0 <= i < t$,
-.el \{\
-0 \(<=
-.I i
-<
-.IR t .
-.\}
+.el .RI "0\~\(<= " i "\~< " t ,
where the
.ie t $x sub i$
.el .IR x _ i
.el .RI \*(*l_ i
is a
.ie t degree-$(t - 1)$
-.el \{\
-.RI degree-( t
-\- 1)
-.\}
+.el .RI degree-( t \~\-\~1)
polynomial
such that
.ie t $lambda sub i ( x sub i ) = 1$,
-.el \{\
-.RI \*(*l_ i ( x _ i )
-= 1,
-.\}
+.el .RI \*(*l_ i ( x _ i )\~=\~1,
and
.ie t $lambda sub i ( x sub j ) = 0$
-.el \{\
-.RI \*(*l_ i ( x _ j )
-= 0
-.\}
+.el .RI \*(*l_ i ( x _ j )\~=\~0
if
.ie t $j != i$.
-.el \{\
-.I j
-\(!=
-.IR i .
-.\}
+.el .IR j \~\(!=\~ i .
Define
.ie t \{\
.EQ
.I q
has degree
.ie t $t - 1$,
-.el \{\
-.I t
-\- 1,
-.\}
+.el .IR t "\~\- 1"
and
.ie t $q( x sub i ) = y sub i = p( x sub i )$
-.el \{\
-.IR q ( x _ i )
-=
-.IR y _ i
-=
-.IR p ( x _ i )
-.\}
+.el .IR q ( x _ i ")\~= " y _ i "\~= " p ( x _ i )
for all
.ie t $0 <= i < t$.
-.el \{\
-0 \(<=
-.I i
-<
-.IR t .
-.\}
+.el .RI "0\~\(<= " i \~<\~ t .
Hence
.ie t $p - q$
-.el \{\
-.I p
-\-
-.I q
-.\}
+.el .IR p \~\-\~ q
is a polynomial with degree at most
.ie t $t - 1$
-.el \{\
-.I t
-\- 1
-.\}
+.el .IR t \~\-\~1
but with at least
.I t
distinct zeros;
therefore
.ie t $q - p$
-.el \{\
-.I p
-\-
-.I q
-.\}
+.el .IR q \~\-\~ p
must be identically zero
and hence
.ie t $q == p$
-.el \{\
-.I q
-\(==
-.I p
-.\}
+.el .IR q \~\(==\~ p
and
.ie t $s = q(0)$.
-.el \{\
-.I s
-=
-.IR q (0).
-.\}
+.el .IR s "\~= " q (0).
.PP
Suppose we are given
.ie t $t - 1$
-.el \{\
-.I t
-\- 1
-.\}
+.el .IR t \~\-\~1
shares.
Then,
for any putative secret
represented as the quotient ring
.ie t $FIELD sub 2 [u]/( u sup 8 + u sup 4 + u sup 3 + u sup 2 + 1 )$.
.el \{\
-.RI GF(2)[ u ]/( u ^8
-+
-.IR u ^4
-+
-.IR u ^3
-+
-.IR u ^2
-+
-1).
+.RI GF(2)[ u ]/( u ^8\~+
+.IR u ^4\~+
+.IR u ^3\~+
+.IR u ^2\~+\~1).
.\}
Hence, a field element fits exactly into a single byte:
specifically, the field element
.ie t $x = a sub 0 + a sub 1 u + ... + a sub 7 u sup 7$
.el \{\
-.I x
-=
-.IR a _0
-+
-.IR a _1
-.I u
-+ ... +
-.IR a _7
-.IR u ^7
+.IR x \~=
+.IR a _0\~+
+.IR a _1\~ u \~+
+\&...\~+
+.IR a _7\~ u ^7
.\}
corresponds to the byte
.ie t $B(x) = a sub 0 + 2 a sub 1 + ... + 2 sup 7 a sub 7$.
.el \{\
-.IR B ( x )
-=
-.IR a _0
-+
-2
-.IR a _1
-+ ... +
-2^7
-.IR a _7.
+.IR B ( x )\~=
+.IR a _0\~+
+.RI 2\~ a _1\~+
+\&... +
+.RI 2^7\~ a _7.
.\}
Secrets longer than a single byte are shared bytewise independently,
which is why the shares leak information about the secret size.
.PP
The program represents share indices as small integers
.ie t $0 <= i < n$;
-.el \{\
-0 \(<=
-.I i
-<
-.IR n ;
-.\}
+.el .RI "0\~\(<= " i \~<\~ n ;
specifically, the share with index
.I i
is generated by
.el .IR p ( x )
where
.ie t $i = B(x) - 1$.
-.el \{\
-.I i
-=
-.IR B ( x )
-\- 1.
-.\}
+.el .IR i "\~= " B ( x )\~\-\~1.
.SH AUTHOR
Mark Wooding, <mdw@distorted.org.uk>
.SH SEE ALSO