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$.
149 The first line contains secret-sharing parameters,
150 which will be required in any recovery operation.
151 These do not usually need to be kept secret
152 (though they contain a cryptographic hash of the original input)
153 but it's a good idea to ensure their integrity.
154 This can be done by storing the parameters in a safe place,
155 possibly protected by a digital signature,
156 or by issuing each share holder with a copy of the parameters
157 and checking that they match at recovery time.
159 The remaining lines contain share data, one per line, for
162 Each share holder should be given one of these lines.
164 The following options are accepted.
166 .BI "\-H, \-\-hash-function=" hashfn
167 The hash function to use when hashing the secret.
168 This may be any hash function name known to OpenSSL.
172 \*(pr shamir issue 3/5 secret
174 shamir-params:n=5;t=3;f=sha256;h=lbcQW/lmV4z0ZKORE5Y0/g+thgWFKr4Kv3i1vEfNkUQ=
175 shamir-share:i=0;y=Ft3jhDQgTdMgEJ3Og3+OZ98NTSRGEWFjIN6mAQmzvHc=
176 shamir-share:i=1;y=zHpbi0h+mFVVv0vAo0djMK296b5XRCAYRV6yMsy74Rs=
177 shamir-share:i=2;y=FbSHVSqoXLVbxkuVZweLXacXmqAnWMEgLOP3qlSvfPc=
178 shamir-share:i=3;y=Q0bUOCUfgSlZSFPOSwhr2YjCSfXKRjwRDmwK8PZPB48=
179 shamir-share:i=4;y=mogI5kfJRclXMVObj0iDtIJoOuu6Wt0pZ9FPaG5bmmM=
184 command reads parameters and shares from standard input,
185 computes the original secret,
186 and writes it to standard output.
188 There are no command-line options.
190 The first line of standard input must contain the sharing parameters.
191 Subsequent lines contain shares,
193 The shares may be in any order.
196 number of shares must be provided.
197 The shares are checked for various kinds of errors
198 (e.g., duplicate shares, out-of-range indices),
199 and the secret is computed
200 and checked against the hash stored with the parameters.
201 If everything is correct,
202 the secret is written to standard output;
203 otherwise errors are reported to standard error,
204 and the program exits with a nonzero status
205 having written nothing to standard output.
211 shamir-params:n=5;t=3;f=sha256;h=lbcQW/lmV4z0ZKORE5Y0/g+thgWFKr4Kv3i1vEfNkUQ=
212 shamir-share:i=2;y=FbSHVSqoXLVbxkuVZweLXacXmqAnWMEgLOP3qlSvfPc=
213 shamir-share:i=1;y=zHpbi0h+mFVVv0vAo0djMK296b5XRCAYRV6yMsy74Rs=
214 shamir-share:i=4;y=mogI5kfJRclXMVObj0iDtIJoOuu6Wt0pZ9FPaG5bmmM=
216 \*(pr shamir recover <shares >secret2
217 \*(pr cmp secret secret2
222 program applies a simple encoding
223 to the various kinds of structured data it deals with,
230 An encoded object has the form
236 Encodings do not contain whitespace characters.
240 is a token which identifies the kind of object encoded.
243 is named with a token
244 (usually a single letter),
245 and supplied with its
247 in a suitable encoding,
250 The syntax is very picky.
251 The order of the slots is significant,
252 and all slots must be defined.
256 object describes a secret and its sharing parameters.
257 Secret objects are not input or output directly,
258 but are hashed when constructing parameters objects (described below).
260 The label for a secret object is
262 Its slots are as follows.
265 The total number of shares issued,
270 as a decimal integer.
273 The threshold required for recovery,
278 as a decimal integer.
281 The secret itself, Base64-encoded,
286 object describes how a secret has been split into shares
287 and provides information about how it can be reassembled.
289 The label for a parameters object is
291 Its slots are as follows.
294 The total number of shares issued,
299 as a decimal integer.
302 The threshold required for recovery,
307 as a decimal integer.
310 The name of the hash function
314 This may be any of the hash functions known to OpenSSL.
317 The hash of a secret object,
318 made using the hash function named by the
322 No trailing newline is included when hashing the secret object.
326 object describes a single share.
327 The label for a parameters object is
329 Its slots are as follows.
333 as a decimal integer;
334 .ie t $0 <= i < "count"$.
343 The share data, Base64 encoded.
345 .SH MATHEMATICAL BACKGROUND
346 (This section has lots of mathematical notation
347 and doesn't look especially good in a terminal.)
352 Suppose we are given a secret
359 which we want to split into shares
360 such that any $t$ of them can be used to recover
363 .ie t $a sub i member k$
379 .ie t $p(x) = s + a sub 1 x + ... + a sub {t-1} x sup {t-1}$.
401 .ie t $y sub i = p( x sub i )$
408 .ie t $x sub i member k - lbrace ~ 0 ~ rbrace$.
417 How do we recover the secret?
419 .ie t $y sub i = p( x sub i )$
441 sum from {pile {0 <= j < t above j != i}}
442 {x - x sub j} over {x sub i - x sub j}.
449 .\" L_i(x) = > ---------.
453 --- \fIx\fP \- \fIx\fP_\fIj\fP
454 \*(*l_\fIi\fP(\fIx\fP) = > ---------.
455 --- \fIx\fP_\fIi\fP - \fIx\fP_\fIj\fP
465 .ie t degree-$(t - 1)$
472 .ie t $lambda sub i ( x sub i ) = 1$,
474 .RI \*(*l_ i ( x _ i )
478 .ie t $lambda sub i ( x sub j ) = 0$
480 .RI \*(*l_ i ( x _ j )
493 q(x) = sum from {0 <= i < t} lambda sub i (x) y sub i .
500 .\" q(x) = > L_i(x) y_i.
504 \fIq\fP(\fIx\fP) = > \*(*l_\fIi\fP(\fIx\fP) \fIy\fP_\fIi\fP.
519 .ie t $q( x sub i ) = y sub i = p( x sub i )$
542 is a polynomial with degree at most
558 must be identically zero
582 for any putative secret
585 there exists a distinct possible value for each of the remaining shares
586 which can be determined using the above interpolation,
587 each of which is equally likely.
589 The polynomial interpolation technique is due to Lagrange;
590 its use as a secret-sharing scheme is due to Adi Shamir.
593 this secret-sharing scheme is
594 .IR "information-theoretically secure" ;
596 there's a cryptographic hash of the secret in the sharing parameters,
597 so security is limited to the computational difficulty
598 of inverting this hash.
599 Knowledge of fewer than
601 shares doesn't make this any easier;
602 and there's a security benefit to
603 knowing that a dishonest share holder
604 can't introduce errors into the recovered secret.
606 All of the above works in any field
608 Computation is easiest in a small finite field
609 (rather than, say, the rationals).
610 This program uses the field
611 .ie t $FIELD sub {2 sup 8}$
613 represented as the quotient ring
614 .ie t $FIELD sub 2 [u]/( u sup 8 + u sup 4 + u sup 3 + u sup 2 + 1 )$.
616 .RI GF(2)[ u ]/( u ^8
626 Hence, a field element fits exactly into a single byte:
627 specifically, the field element
628 .ie t $x = a sub 0 + a sub 1 u + ... + a sub 7 u sup 7$
640 corresponds to the byte
641 .ie t $B(x) = a sub 0 + 2 a sub 1 + ... + 2 sup 7 a sub 7$.
653 Secrets longer than a single byte are shared bytewise independently,
654 which is why the shares leak information about the secret size.
656 The program represents share indices as small integers
664 specifically, the share with index
667 evaluating the polynomial
671 .ie t $i = B(x) - 1$.
679 Mark Wooding, <mdw@distorted.org.uk>
681 .BR distorted-keys (7),