9 . ie '\*(.T'utf8' .ds mo ∈
11 . ie '\*(.T'utf8' .ds *l \(*l
16 \h'-\w'\fB\\$1\ \fP'u'\fB\\$1\ \fP\c
33 tdefine member 'type "relation" \(mo'
34 define lbrace 'roman "{"'
35 define rbrace 'roman "}"'
38 .TH shamir 1 "3 May 2015" "distorted.org.uk key management"
47 shamir \- split a secret into shares, and recombine them
69 program implements a simple secret sharing scheme.
74 into a number of shares
84 can be used to reconstruct it, but
87 shares provide no information at all
89 (other than its length).
90 .SH COMMAND-LINE OPTIONS
91 The following options are recognized.
95 of the options and commands
97 and exit successfully.
100 Print the version number
105 and exit successfully.
106 .SH COMMAND REFERENCE
110 command prints information to standard output
122 command reads a secret from
124 (or from standard input,
129 and writes a number of lines to standard output.
133 is the total number of shares issued;
136 of them can be used to reassemble the original secret.
137 It must be the case that
138 .ie t $1 <= "thresh" <= "count" <= 255$.
139 .el .RI "1\~\(<= " thresh "\~\(<= " count "\~\(<= 255."
141 The first line contains secret-sharing parameters,
142 which will be required in any recovery operation.
143 These do not usually need to be kept secret
144 (though they contain a cryptographic hash of the original input)
145 but it's a good idea to ensure their integrity.
146 This can be done by storing the parameters in a safe place,
147 possibly protected by a digital signature,
148 or by issuing each share holder with a copy of the parameters
149 and checking that they match at recovery time.
151 The remaining lines contain share data, one per line, for
154 Each share holder should be given one of these lines.
156 The following options are accepted.
158 .BI "\-H, \-\-hash-function=" hashfn
159 The hash function to use when hashing the secret.
160 This may be any hash function name known to OpenSSL.
164 \*(pr shamir issue 3/5 secret
166 shamir-params:n=5;t=3;f=sha256;h=lbcQW/lmV4z0ZKORE5Y0/g+thgWFKr4Kv3i1vEfNkUQ=
167 shamir-share:i=0;y=Ft3jhDQgTdMgEJ3Og3+OZ98NTSRGEWFjIN6mAQmzvHc=
168 shamir-share:i=1;y=zHpbi0h+mFVVv0vAo0djMK296b5XRCAYRV6yMsy74Rs=
169 shamir-share:i=2;y=FbSHVSqoXLVbxkuVZweLXacXmqAnWMEgLOP3qlSvfPc=
170 shamir-share:i=3;y=Q0bUOCUfgSlZSFPOSwhr2YjCSfXKRjwRDmwK8PZPB48=
171 shamir-share:i=4;y=mogI5kfJRclXMVObj0iDtIJoOuu6Wt0pZ9FPaG5bmmM=
176 command reads parameters and shares from standard input,
177 computes the original secret,
178 and writes it to standard output.
180 There are no command-line options.
182 The first line of standard input must contain the sharing parameters.
183 Subsequent lines contain shares,
185 The shares may be in any order.
188 number of shares must be provided.
189 The shares are checked for various kinds of errors
190 (e.g., duplicate shares, out-of-range indices),
191 and the secret is computed
192 and checked against the hash stored with the parameters.
193 If everything is correct,
194 the secret is written to standard output;
195 otherwise errors are reported to standard error,
196 and the program exits with a nonzero status
197 having written nothing to standard output.
203 shamir-params:n=5;t=3;f=sha256;h=lbcQW/lmV4z0ZKORE5Y0/g+thgWFKr4Kv3i1vEfNkUQ=
204 shamir-share:i=2;y=FbSHVSqoXLVbxkuVZweLXacXmqAnWMEgLOP3qlSvfPc=
205 shamir-share:i=1;y=zHpbi0h+mFVVv0vAo0djMK296b5XRCAYRV6yMsy74Rs=
206 shamir-share:i=4;y=mogI5kfJRclXMVObj0iDtIJoOuu6Wt0pZ9FPaG5bmmM=
208 \*(pr shamir recover <shares >secret2
209 \*(pr cmp secret secret2
214 program applies a simple encoding
215 to the various kinds of structured data it deals with,
222 An encoded object has the form
228 Encodings do not contain whitespace characters.
232 is a token which identifies the kind of object encoded.
235 is named with a token
236 (usually a single letter),
237 and supplied with its
239 in a suitable encoding,
242 The syntax is very picky.
243 The order of the slots is significant,
244 and all slots must be defined.
248 object describes a secret and its sharing parameters.
249 Secret objects are not input or output directly,
250 but are hashed when constructing parameters objects (described below).
252 The label for a secret object is
254 Its slots are as follows.
257 The total number of shares issued,
262 as a decimal integer.
265 The threshold required for recovery,
270 as a decimal integer.
273 The secret itself, Base64-encoded,
278 object describes how a secret has been split into shares
279 and provides information about how it can be reassembled.
281 The label for a parameters object is
283 Its slots are as follows.
286 The total number of shares issued,
291 as a decimal integer.
294 The threshold required for recovery,
299 as a decimal integer.
302 The name of the hash function
306 This may be any of the hash functions known to OpenSSL.
309 The hash of a secret object,
310 made using the hash function named by the
314 No trailing newline is included when hashing the secret object.
318 object describes a single share.
319 The label for a parameters object is
321 Its slots are as follows.
325 as a decimal integer;
326 .ie t $0 <= i < "count"$.
327 .el .RI "0\~\(<= " i "\~< " count .
330 The share data, Base64 encoded.
332 .SH MATHEMATICAL BACKGROUND
333 (This section has lots of mathematical notation
334 and doesn't look especially good in a terminal.)
339 Suppose we are given a secret
341 .el .IR s \~\*(mo\~ k
342 which we want to split into shares
343 such that any $t$ of them can be used to recover
346 .ie t $a sub i member k$
347 .el .IR a _ i \~\*(mo\~ k
350 .el .RI "1\~\(<= " i \~<\~ t
353 .ie t $p(x) = s + a sub 1 x + ... + a sub {t-1} x sup {t-1}$.
355 .IR p ( x ")\~= " s "\~+ " a "_1\~+ ...\~+"
356 .IR a _( t \-1)\~ x ^( t \-1).
360 .el .IR p "(0)\~= " s .
364 .ie t $y sub i = p( x sub i )$
365 .el .IR y _ i "\~= " p ( x _ i )
367 .ie t $x sub i member k - lbrace ~ 0 ~ rbrace$.
368 .el .IR x _ i "\~\*(mo " k "\~\- {\~0\~}."
370 How do we recover the secret?
372 .ie t $y sub i = p( x sub i )$
373 .el .IR y _ i "\~= " p ( x _ i )
376 .el .RI "0\~\(<= " i "\~< " t ,
385 sum from {pile {0 <= j < t above j != i}}
386 {x - x sub j} over {x sub i - x sub j}.
393 .\" L_i(x) = > ---------.
397 --- \fIx\fP \- \fIx\fP_\fIj\fP
398 \*(*l_\fIi\fP(\fIx\fP) = > ---------.
399 --- \fIx\fP_\fIi\fP - \fIx\fP_\fIj\fP
409 .ie t degree-$(t - 1)$
410 .el .RI degree-( t \~\-\~1)
413 .ie t $lambda sub i ( x sub i ) = 1$,
414 .el .RI \*(*l_ i ( x _ i )\~=\~1,
416 .ie t $lambda sub i ( x sub j ) = 0$
417 .el .RI \*(*l_ i ( x _ j )\~=\~0
420 .el .IR j \~\(!=\~ i .
424 q(x) = sum from {0 <= i < t} lambda sub i (x) y sub i .
431 .\" q(x) = > L_i(x) y_i.
435 \fIq\fP(\fIx\fP) = > \*(*l_\fIi\fP(\fIx\fP) \fIy\fP_\fIi\fP.
447 .ie t $q( x sub i ) = y sub i = p( x sub i )$
448 .el .IR q ( x _ i ")\~= " y _ i "\~= " p ( x _ i )
451 .el .RI "0\~\(<= " i \~<\~ t .
455 is a polynomial with degree at most
464 must be identically zero
470 .el .IR s "\~= " q (0).
477 for any putative secret
480 there exists a distinct possible value for each of the remaining shares
481 which can be determined using the above interpolation,
482 each of which is equally likely.
484 The polynomial interpolation technique is due to Lagrange;
485 its use as a secret-sharing scheme is due to Adi Shamir.
488 this secret-sharing scheme is
489 .IR "information-theoretically secure" ;
491 there's a cryptographic hash of the secret in the sharing parameters,
492 so security is limited to the computational difficulty
493 of inverting this hash.
494 Knowledge of fewer than
496 shares doesn't make this any easier;
497 and there's a security benefit to
498 knowing that a dishonest share holder
499 can't introduce errors into the recovered secret.
501 All of the above works in any field
503 Computation is easiest in a small finite field
504 (rather than, say, the rationals).
505 This program uses the field
506 .ie t $FIELD sub {2 sup 8}$
508 represented as the quotient ring
509 .ie t $FIELD sub 2 [u]/( u sup 8 + u sup 4 + u sup 3 + u sup 2 + 1 )$.
511 .RI GF(2)[ u ]/( u ^8\~+
516 Hence, a field element fits exactly into a single byte:
517 specifically, the field element
518 .ie t $x = a sub 0 + a sub 1 u + ... + a sub 7 u sup 7$
526 corresponds to the byte
527 .ie t $B(x) = a sub 0 + 2 a sub 1 + ... + 2 sup 7 a sub 7$.
535 Secrets longer than a single byte are shared bytewise independently,
536 which is why the shares leak information about the secret size.
538 The program represents share indices as small integers
540 .el .RI "0\~\(<= " i \~<\~ n ;
541 specifically, the share with index
544 evaluating the polynomial
548 .ie t $i = B(x) - 1$.
549 .el .IR i "\~= " B ( x )\~\-\~1.
551 Mark Wooding, <mdw@distorted.org.uk>
553 .BR distorted-keys (7),