Commit | Line | Data |
---|---|---|
53263601 MW |
1 | #! @PYTHON@ |
2 | ### | |
3 | ### Shamir secret sharing | |
4 | ### | |
5 | ### (c) 2011 Mark Wooding | |
6 | ### | |
7 | ||
8 | ###----- Licensing notice --------------------------------------------------- | |
9 | ### | |
599c8f75 MW |
10 | ### This file is part of the distorted.org.uk key management suite. |
11 | ### | |
12 | ### distorted-keys is free software; you can redistribute it and/or modify | |
53263601 MW |
13 | ### it under the terms of the GNU General Public License as published by |
14 | ### the Free Software Foundation; either version 2 of the License, or | |
15 | ### (at your option) any later version. | |
16 | ### | |
599c8f75 | 17 | ### distorted-keys is distributed in the hope that it will be useful, |
53263601 MW |
18 | ### but WITHOUT ANY WARRANTY; without even the implied warranty of |
19 | ### MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
20 | ### GNU General Public License for more details. | |
21 | ### | |
22 | ### You should have received a copy of the GNU General Public License | |
599c8f75 | 23 | ### along with distorted-keys; if not, write to the Free Software Foundation, |
53263601 MW |
24 | ### Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. |
25 | ||
26 | from __future__ import with_statement | |
27 | ||
28 | import sys as SYS | |
29 | import os as OS | |
30 | import hashlib as H | |
31 | import base64 as B | |
32 | from cStringIO import StringIO | |
33 | import optparse as OPT | |
34 | ||
35 | ###-------------------------------------------------------------------------- | |
36 | ### Arithmetic in GF(2^8). | |
37 | ### | |
38 | ### These functions implement arithmetic in a field containing exactly 256 | |
39 | ### elements. This is convenient, because there's exactly one field element | |
40 | ### for each one-byte value. | |
41 | ### | |
42 | ### Actually, we only implement multiplication and division, because addition | |
43 | ### and subtraction are trivial -- they're the XOR operation that Python | |
44 | ### already has. Multiplication and (especially) division are fiddly if you | |
45 | ### do them directly, but the field is easily small enough that log tables | |
46 | ### are a feasible alternative. | |
47 | ### | |
48 | ### There are many (isomorphic) representations of the field GF(2^8). The | |
49 | ### one we use here is a field of residue classes of binary polynomials: | |
50 | ### GF(2)[x]/(x^8 + x^4 + x^3 + x^2 + 1). Usefully, the element [x] (i.e., | |
51 | ### the residue class containing x) generates the multiplicative group of the | |
52 | ### field: every nonzero element can be written in the form x^k for some | |
53 | ### integer 0 <= k < 255. Multiplication by x is especially easy, so this is | |
54 | ### a good choice as a base of logarithms. | |
55 | ### | |
56 | ### More precisely, we use an integer encoding of the residue classes. Each | |
57 | ### class contains exactly one polynomial of degree less than 8, called the | |
58 | ### principal representative. If the principal representative of a residue | |
59 | ### class is a_7 x^7 + ... + a_1 x + a_0, with each a_i either 0 or 1, then | |
60 | ### the encoding of the representative is 2^7 a_7 + ... + 2 a_1 + a_0. It is | |
61 | ### easily verified that this mapping is invertible. | |
62 | ||
63 | def gf28_log_tables(): | |
64 | """Build the log tables used to implement GF(2^8) arithmetic.""" | |
65 | global GF28_LOG, GF28_EXP | |
66 | log = [0] * 256 | |
67 | exp = [0] * 256 | |
68 | x = 1 | |
69 | for i in xrange(255): | |
70 | exp[i] = x | |
71 | log[x] = i | |
72 | x <<= 1 | |
73 | if x & 0x100: | |
74 | x ^= 0x11d | |
75 | GF28_LOG = log | |
76 | GF28_EXP = exp[:255] * 2 | |
77 | gf28_log_tables() | |
78 | ||
79 | def gf28_mul(x, y): | |
80 | """Multiply two elements X and Y of GF(2^8), retturning their product.""" | |
81 | if x == 0 or y == 0: return 0 | |
82 | else: return GF28_EXP[GF28_LOG[x] + GF28_LOG[y]] | |
83 | ||
84 | def gf28_div(x, y): | |
85 | """ | |
86 | Divide element X by Y in GF(2^8), returning the quotient. | |
87 | ||
88 | Raise `ZeroDivisionError' if Y is zero. | |
89 | """ | |
90 | if y == 0: raise ZeroDivisionError | |
91 | elif x == 0: return 0 | |
92 | else: return GF28_EXP[GF28_LOG[x] + 255 - GF28_LOG[y]] | |
93 | ||
94 | ###-------------------------------------------------------------------------- | |
95 | ### Secret sharing machinery. | |
96 | ### | |
97 | ### Shamir's secret sharing scheme uses polynomial interpolation. Let K be a | |
98 | ### finite field, and let s -- the `secret' -- be an element of K. Let t -- | |
99 | ### the `threshold' -- be a positive integer. A degree-(t - 1) polynomial | |
100 | ### p(x) over K has the general form a_{t-1} x^{t-1} + ... + a_1 x + a_0; we | |
101 | ### then have p(0) = a_0. If we choose a_0 = s, and the other a_i uniformly | |
102 | ### at random from K, then we have chosen a degree-(t - 1) polynomial | |
103 | ### uniformly at random, subject to the restrictiion that it evaluates to s | |
104 | ### at 0. We can issue shares of the form (x, p(x)) for 0 < x < #K. | |
105 | ### | |
106 | ### Any collection of t shares can be used to reconstruct the polynomial. We | |
107 | ### can use Lagrange interpolation to do this. Suppose that we're given t | |
108 | ### different shares (x_i, y_i) for 0 <= i < t. Firstly, set | |
109 | ### | |
110 | ### ------- x - x_j | |
111 | ### l_i(x) = | | --------- | |
112 | ### | | x_i - x_j | |
113 | ### 0 <= j < t | |
114 | ### j /= i | |
115 | ### | |
116 | ### Now notice that l_i(x_i) = 1 and l_i(x_j) = 0 if j /= i. Then | |
117 | ### | |
118 | ### ---- | |
119 | ### p(x) = > l_i(x) y_i | |
120 | ### ---- | |
121 | ### 0 <= i < t | |
122 | ### | |
123 | ### To see this, it suffices to note that (a) l_i(x) (and therefore the sum) | |
124 | ### is a degree-(t - 1) polynomial, and (b) it agrees with p(x) at t distinct | |
125 | ### points, namely each of the x_i. So, with t shares, we can recover the | |
126 | ### original polynomial, and hence p(0) = s. With t - 1 shares, we can add a | |
127 | ### fake `share' (0, s') for any guessed s' in K and interpolate | |
128 | ### corresponding values for the remaining shares; we therefore have perfect | |
129 | ### secrecy. | |
130 | ### | |
131 | ### We use K = GF(2^8), as implemented above. Each byte of a long secret is | |
132 | ### shared independently. | |
133 | ### | |
134 | ### All of this machinery is the same as in my Catacomb library and Daniel | |
135 | ### Silverstone's `gfshare' package. | |
136 | ||
137 | class SecretSplit (object): | |
138 | """ | |
139 | Create shares of a secret. | |
140 | ||
141 | Initialize with a secret S and a threshold T; then issue shares with the | |
142 | `issue' method. | |
143 | """ | |
144 | ||
145 | def __init__(me, s, t): | |
146 | """ | |
147 | Initialize secret sharing. | |
148 | ||
149 | S is a string containing the secret; T is the threshold, i.e., the number | |
150 | of shares requierd to recover the secret. | |
151 | """ | |
152 | ||
153 | ## The number of bytes in the secret is a useful thing to store. | |
154 | me._n = len(s) | |
155 | ||
156 | ## Build an array of coefficients chosen at random. | |
157 | me._coeffs = [OS.urandom(me._n) for i in xrange(t - 1)] + [s] | |
158 | ||
159 | def issue(me, x): | |
160 | """ | |
161 | Issue the share with index X, returning it as a string. | |
162 | ||
163 | The share will be binary, even if the original secret is plain text. The | |
164 | index must be in the range 1 <= X <= 255. | |
165 | """ | |
166 | ||
167 | ## Check that the index is in range. | |
168 | if x < 1 or x > 255: | |
169 | raise ValueError, 'share index out of range' | |
170 | ||
171 | ## Evaluate the polynomial at the chosen index. | |
172 | o = StringIO() | |
173 | for i in xrange(me._n): | |
174 | y = 0 | |
175 | for j in me._coeffs: | |
176 | y = gf28_mul(x, y) ^ ord(j[i]) | |
177 | o.write(chr(y)) | |
178 | return o.getvalue() | |
179 | ||
180 | class SecretJoin (object): | |
181 | """ | |
182 | Recover a secret given a number of shares. | |
183 | """ | |
184 | def __init__(me): | |
185 | me._n = None | |
186 | me._m = {} | |
187 | ||
188 | def insert(me, x, p): | |
189 | """ | |
190 | Insert a share P with index X. | |
191 | ||
192 | All the shares must have the same length. It doesn't matter what the | |
193 | length of the first share is, but the others have to match it. | |
194 | """ | |
195 | ||
196 | ## Check that the share index is in range. | |
197 | if x < 1 or x > 255: | |
198 | raise ValueError, 'share index out of range' | |
199 | ||
200 | ## Make sure that we haven't been given this one already. | |
201 | if x in me._m: | |
202 | raise ValueError, 'duplicate share index' | |
203 | ||
204 | ## Check the length of the share. Store the length if this is the first | |
205 | ## share. | |
206 | if me._n is None: | |
207 | me._n = len(p) | |
208 | elif len(p) != me._n: | |
209 | raise ValueError, 'bad share length' | |
210 | ||
211 | ## Store the share. | |
212 | me._m[x] = p | |
213 | ||
214 | def recover(me): | |
215 | """ | |
216 | Recover the secret from the shares provided, and return it as a string. | |
217 | ||
218 | It's assumed that the caller provided the correct number of shares. | |
219 | """ | |
220 | ||
221 | ## Iniitialize a map of l_i(0) values. These depend only on the share | |
222 | ## indices provided, and are therefore independent of the secret length. | |
223 | ll = {} | |
224 | kk = me._m.keys() | |
225 | for xi in kk: | |
226 | l = 1 | |
227 | for xj in kk: | |
228 | if xi != xj: | |
229 | l = gf28_mul(l, gf28_div(xj, xi ^ xj)) | |
230 | ll[xi] = l | |
231 | ||
232 | ## Now do the interpolation. | |
233 | o = StringIO() | |
234 | for i in xrange(me._n): | |
235 | y = 0 | |
236 | for xi in kk: | |
237 | y = y ^ gf28_mul(ll[xi], ord(me._m[xi][i])) | |
238 | o.write(chr(y)) | |
239 | return o.getvalue() | |
240 | ||
241 | ###-------------------------------------------------------------------------- | |
242 | ### Key/value encoding. | |
243 | ### | |
244 | ### We use a simple encoding for the data structures we handle. The encoding | |
245 | ### looks like this: | |
246 | ### | |
247 | ### LABEL:KEY=VALUE;KEY=VALUE;... | |
248 | ### | |
249 | ### The LABEL just says what kind of structure this is meant to be. The KEYs | |
250 | ### are short strings which identify the structure slots. We're doing this | |
251 | ### on the cheap, so order is significant, and there are no creature comforts | |
252 | ### like optional slots. The VALUEs are encodings of the slot values; the | |
253 | ### details of the encoding depend on the VALUE type, which is statically | |
254 | ### determined by the structure. | |
255 | ||
256 | class StructureSlot (object): | |
257 | """ | |
258 | Base class for structure slot types. | |
259 | ||
260 | Subclasses must implement `encode' and `decode' methods. | |
261 | """ | |
262 | def __init__(me, name): | |
263 | """Initialize a structure slot, remembering its name.""" | |
264 | me._name = name | |
265 | ||
266 | class IntegerSlot (StructureSlot): | |
267 | """ | |
268 | An integer slot. | |
269 | """ | |
270 | TYPE = 'integer' | |
271 | def encode(me, value): | |
272 | return '%d' % value | |
273 | def decode(me, string): | |
274 | return int(string) | |
275 | ||
276 | class StringSlot (StructureSlot): | |
277 | """ | |
278 | A string slot, unencoded. Be careful. | |
279 | """ | |
280 | TYPE = 'string' | |
281 | def encode(me, value): | |
282 | return value | |
283 | def decode(me, string): | |
284 | return string | |
285 | ||
286 | class BinarySlot (StructureSlot): | |
287 | """ | |
288 | A binary slot, encoded as Base64. | |
289 | """ | |
290 | TYPE = 'base64' | |
291 | def encode(me, value): | |
292 | return B.b64encode(value) | |
293 | def decode(me, string): | |
294 | return B.b64decode(string) | |
295 | ||
296 | class StructureType (object): | |
297 | """ | |
298 | Base class for classes which can encode and decode their slots. | |
299 | """ | |
300 | ||
301 | def __init__(me, *args, **kw): | |
302 | """ | |
303 | Initialize a structure object. | |
304 | ||
305 | The arguments correspond to slots. Positional arguments are read first, | |
306 | and stored in the appropriate attributes. Keywords arguments are used to | |
307 | set arbitrary attributes, but it is an error to set an attribute which | |
308 | already has a value. | |
309 | ||
310 | The `decoded' method is called after argument processing. | |
311 | """ | |
312 | ||
313 | _magic = False | |
314 | ||
315 | ## Decode the arguments. | |
316 | if len(args) > len(me.SLOTS): | |
317 | raise ValueError, 'too many positional arguments' | |
318 | for i in xrange(len(args)): | |
319 | slotdef, attr = me.SLOTS[i] | |
320 | setattr(me, attr, args[i]) | |
321 | for k, v in kw.iteritems(): | |
322 | if k == '_magic': | |
323 | _magic = v | |
324 | continue | |
325 | if hasattr(me, k): | |
326 | raise ValueError, 'already set attribute' | |
327 | setattr(me, k, v) | |
328 | ||
329 | ## Initialize the object. (There's a hack here for the `decode' method.) | |
330 | if not _magic: | |
331 | me.decoded() | |
332 | ||
333 | def encode(me): | |
334 | """ | |
335 | Encode an object as a string. | |
336 | """ | |
337 | o = StringIO() | |
338 | o.write(me.LABEL) | |
339 | o.write(':') | |
340 | sep = '' | |
341 | for slotdef, attr in me.SLOTS: | |
342 | o.write(sep) | |
343 | o.write('%s=%s' % (slotdef._name, slotdef.encode(getattr(me, attr)))) | |
344 | sep = ';' | |
345 | return o.getvalue() | |
346 | ||
347 | def save(me, path): | |
348 | """ | |
349 | Write an encoded description of the object to PATH. | |
350 | """ | |
351 | with open(path + '.new', 'w') as f: | |
352 | f.write(me.encode()) | |
353 | f.write('\n') | |
354 | OS.rename(path + '.new', path) | |
355 | ||
356 | @classmethod | |
357 | def decode(cls, string): | |
358 | """ | |
359 | Decode a STRING, returning a new object. | |
360 | ||
361 | The `decoded' method is called on the new object. | |
362 | """ | |
363 | if not string.startswith(cls.LABEL + ':'): | |
364 | raise SyntaxError, 'incorrect label' | |
365 | slots = string[len(cls.LABEL) + 1:].split(';') | |
366 | if len(slots) != len(cls.SLOTS): | |
367 | raise SyntaxError, 'wrong number of slots' | |
368 | obj = cls(_magic = True) | |
369 | for i in xrange(len(slots)): | |
370 | slot = slots[i] | |
371 | slotdef, attr = cls.SLOTS[i] | |
372 | if not slot.startswith(slotdef._name + '='): | |
373 | raise SyntaxError, 'incorrect slot name' | |
374 | try: | |
375 | val = slotdef.decode(slot[len(slotdef._name) + 1:]) | |
376 | except (ValueError, SyntaxError): | |
377 | raise SyntaxError, 'invalid %s value' % slotdef.TYPE | |
378 | setattr(obj, attr, val) | |
379 | obj.decoded() | |
380 | return obj | |
381 | ||
382 | @classmethod | |
383 | def load(cls, path): | |
384 | """ | |
385 | Read an encoded description of a structure and return the decoded object. | |
386 | """ | |
387 | with open(path, 'r') as f: | |
388 | cont = f.read() | |
389 | if cont and cont[-1] == '\n': | |
390 | cont = cont[:-1] | |
391 | if '\n' in cont: | |
392 | raise SyntaxError, 'encoding must be a single line' | |
393 | return cls.decode(cont) | |
394 | ||
395 | def decoded(me): | |
396 | """ | |
397 | Hook for object initialization. | |
398 | ||
399 | This is called by `__init__' and `decode'. | |
400 | """ | |
401 | pass | |
402 | ||
403 | ###-------------------------------------------------------------------------- | |
404 | ### Higher-level share management. | |
405 | ### | |
406 | ### We store shares together with a bunch of metadata about the sharing | |
407 | ### parameters, and a hash of all of that together with the final secret. | |
408 | ### Theoretically, storing a hash weakens the whole scheme from providing | |
409 | ### unconditional security to merely providing computational security (based | |
410 | ### on the assupmption that the hash function is one-way). In practice, the | |
411 | ### secret will be used as a symmetric encryption key or similar, so it's | |
412 | ### already only secure against computationally bounded adversaries. | |
413 | ||
414 | class Secret (StructureType): | |
415 | """ | |
416 | Represents a secret, either about to be shared or recently recovered. | |
417 | """ | |
418 | LABEL = 'shamir-secret' | |
419 | SLOTS = [(IntegerSlot('n'), 'count'), | |
420 | (IntegerSlot('t'), 'thresh'), | |
421 | (BinarySlot('s'), 'secret')] | |
422 | ||
423 | def hash(me, hashfn): | |
424 | """ | |
425 | Hash the secret and its parameters using the hash function HASHFN. | |
426 | ||
427 | The hash is returned as a raw binary string. The HASHFN must be one of | |
428 | the hash functions known to Python's `hashlib' module (essentially, hash | |
429 | functions known to OpenSSL). | |
430 | """ | |
431 | h = H.new(hashfn) | |
432 | h.update(me.encode()) | |
433 | return h.digest() | |
434 | ||
435 | class Params (StructureType): | |
436 | """ | |
437 | Represents secret sharing parameters. | |
438 | """ | |
439 | LABEL = 'shamir-params' | |
440 | SLOTS = [(IntegerSlot('n'), 'count'), | |
441 | (IntegerSlot('t'), 'thresh'), | |
442 | (StringSlot('f'), 'hashfn'), | |
443 | (BinarySlot('h'), 'hash')] | |
444 | ||
445 | class Share (StructureType): | |
446 | """ | |
447 | Represents a share of a secret. | |
448 | """ | |
449 | LABEL = 'shamir-share' | |
450 | SLOTS = [(IntegerSlot('i'), 'index'), | |
451 | (BinarySlot('y'), 'share')] | |
452 | ||
453 | ###-------------------------------------------------------------------------- | |
454 | ### Utilities. | |
455 | ||
456 | QUIS = OS.path.basename(SYS.argv[0]) | |
457 | ||
458 | def moan(message): | |
459 | SYS.stderr.write('%s: %s\n' % (QUIS, message)) | |
460 | ||
461 | def die(message, rc = 1): | |
462 | moan(message) | |
463 | SYS.exit(rc) | |
464 | ||
465 | class struct (object): | |
466 | def __init__(me, **kw): | |
467 | me.__dict__.update(kw) | |
468 | ||
469 | class Subcommand (struct): | |
470 | pass | |
471 | ||
472 | class SubcommandOptionParser (OPT.OptionParser, object): | |
473 | ||
474 | def __init__(me, usage = '%prog [-OPTIONS] COMMAND [ARGS ...]', | |
475 | *args, **kw): | |
476 | super(SubcommandOptionParser, me).__init__(usage = usage, *args, **kw) | |
477 | me.subcommands = [ | |
478 | Subcommand(name = 'help', usage = '[COMMAND ...]', opts = [], | |
479 | func = me.cmd_help, | |
480 | desc = 'Show help for %prog, or for the COMMANDs.') | |
481 | ] | |
482 | me.disable_interspersed_args() | |
483 | ||
484 | def add_subcommand(me, name, func, usage, desc = None, opts = []): | |
485 | subcmd = Subcommand(name = name, func = func, usage = usage, | |
486 | desc = desc, opts = opts) | |
487 | me.subcommands.append(subcmd) | |
488 | ||
489 | def lookup_subcommand(me, name): | |
490 | match = [] | |
491 | for sub in me.subcommands: | |
492 | if sub.name == name: | |
493 | return sub | |
494 | elif sub.name.startswith(name): | |
495 | match.append(sub) | |
496 | if len(match) == 1: | |
497 | return match[0] | |
498 | elif len(match) == 0: | |
499 | me.error("unknown command `%s'"% name) | |
500 | else: | |
501 | me.error("ambiguous command `%s': could be any of %s" | |
502 | % (name, ', '.join(["`%s'" % sub.name for sub in match]))) | |
503 | ||
504 | def subcmd_usage(me, sub): | |
505 | if sub.usage: | |
506 | return '%s %s' % (sub.name, sub.usage) | |
507 | else: | |
508 | return sub.name | |
509 | ||
510 | def print_help(me): | |
511 | super(SubcommandOptionParser, me).print_help() | |
512 | ||
513 | print 'Commands:' | |
514 | for sub in me.subcommands: | |
515 | if sub.usage is None: | |
516 | continue | |
517 | print ' ' + me.subcmd_usage(sub) | |
518 | ||
519 | def make_subcommand_optparser(me, sub): | |
520 | op = OPT.OptionParser(usage = 'usage: %%prog %s' % me.subcmd_usage(sub), | |
521 | description = sub.desc) | |
522 | for opt in sub.opts: | |
523 | op.add_option(opt) | |
524 | return op | |
525 | ||
526 | def cmd_help(me, gopts, opts, args): | |
527 | if not args: | |
528 | me.print_help() | |
529 | else: | |
530 | for name in args: | |
531 | sub = me.lookup_subcommand(name) | |
532 | op = me.make_subcommand_optparser(sub) | |
533 | op.print_help() | |
534 | ||
535 | def dispatch(me, args = None): | |
536 | if args is None: | |
537 | args = SYS.argv[1:] | |
538 | gopts, args = me.parse_args(args) | |
539 | if not args: | |
540 | me.error('missing command') | |
541 | sub = me.lookup_subcommand(args[0]) | |
542 | op = me.make_subcommand_optparser(sub) | |
543 | opts, args = op.parse_args(args[1:]) | |
544 | sub.func(gopts, opts, args) | |
545 | ||
546 | OPTPARSE = SubcommandOptionParser(description = """\ | |
547 | Split and recombine secrets using Shamir's secret sharing system. | |
548 | """) | |
549 | ||
550 | ###-------------------------------------------------------------------------- | |
551 | ### Issue shares given a secret. | |
552 | ||
553 | def parse_sharing(string): | |
554 | slash = string.find('/') | |
555 | if slash == -1: | |
556 | raise ValueError, "no `/'" | |
557 | return int(string[slash + 1:]), int(string[:slash]) | |
558 | ||
559 | def cmd_issue(gopts, opts, args): | |
560 | ||
561 | if len(args) < 1 or len(args) > 2: | |
562 | OPTPARSE.error('bad arguments') | |
563 | ||
564 | try: | |
565 | count, thresh = parse_sharing(args[0]) | |
566 | except ValueError, err: | |
567 | OPTPARSE.error("bad sharing parameters `%s': %s" | |
568 | % (args[0], err.message)) | |
569 | ||
570 | if len(args) < 2 or args[1] == '-': | |
571 | sec = SYS.stdin.read() | |
572 | else: | |
573 | with open(args[1], 'rb') as f: | |
574 | sec = f.read() | |
575 | ||
576 | secret = Secret(count, thresh, sec) | |
577 | h = secret.hash(opts.hashfn) | |
578 | params = Params(count, thresh, opts.hashfn, h) | |
579 | print params.encode() | |
580 | ||
581 | ss = SecretSplit(sec, thresh) | |
582 | for i in xrange(count): | |
583 | share = Share(i, ss.issue(i + 1)) | |
584 | print share.encode() | |
585 | ||
586 | OPTPARSE.add_subcommand( | |
587 | 'issue', cmd_issue, | |
588 | '[-H HASHFN] THRESH/COUNT [SECRET-FILE]', | |
589 | """\ | |
590 | Issue shares of a secret. The secret (as a binary lump) is read from | |
591 | SECRET-FILE, or standard input if SECRET-FILE is omitted. COUNT + 1 lines | |
592 | are written to standard output: the first line contains the sharing | |
593 | parameters, and does not need to be kept especially secret (though it | |
594 | contains a hash of the secret, so it compromises the unconditional security | |
595 | of the secret sharing scheme); the remaining lines are the shares, one per | |
596 | line. All of the lines are plain text.""", | |
597 | [OPT.make_option('-H', '--hash-function', type = 'string', | |
598 | action = 'store', dest = 'hashfn', default = 'sha256', | |
599 | help = 'Hash function for verifying the share.')]) | |
600 | ||
601 | ###-------------------------------------------------------------------------- | |
602 | ### Recover a secret from shares. | |
603 | ||
604 | def cmd_recover(gopts, opts, args): | |
605 | ||
606 | ## Keep track of how well we've done so far. Report all of the things | |
607 | ## which go wrong. | |
608 | lose = False | |
609 | lineno = 1 | |
610 | ||
611 | ## Read the system parameters. | |
612 | line = SYS.stdin.readline() | |
613 | if line.endswith('\n'): | |
614 | line = line[:-1] | |
615 | try: | |
616 | params = Params.decode(line) | |
617 | except ValueError, err: | |
618 | moan("parameters (line %d) invalid: %s" % (lineno, err.message)) | |
619 | lose = True | |
620 | ||
621 | ## Now read the shares. Pay attention to syntax errors, but not to much | |
622 | ## else. Build the maps for the sharing parameters. | |
623 | sj = SecretJoin() | |
624 | shmap = {} | |
625 | for line in SYS.stdin: | |
626 | lineno += 1 | |
627 | if line.endswith('\n'): | |
628 | line = line[:-1] | |
629 | try: | |
630 | share = Share.decode(line) | |
631 | except ValueError, err: | |
632 | moan("share invalid (line %d): %s" % (lineno, err.message)) | |
633 | lose = True | |
634 | continue | |
635 | share.lineno = lineno | |
636 | if share.index in shmap: | |
637 | moan("duplicate share index " | |
638 | "(line %d, index %d previously on line %d)" % | |
639 | (lineno, share.index, shmap[share.index].lineno)) | |
640 | lose = True | |
641 | elif share.index < 0 or share.index >= params.count: | |
642 | moan("share index %d out of range (line %d)" % (share.index, lineno)) | |
643 | lose = True | |
644 | elif len(shmap) >= params.thresh: | |
645 | moan("enough shares already (line %d)" % lineno) | |
646 | lose = True | |
647 | else: | |
648 | sj.insert(share.index + 1, share.share) | |
649 | shmap[share.index] = share | |
650 | ||
651 | if len(shmap) < params.thresh: | |
652 | moan("not enough shares") | |
653 | lose = True | |
654 | ||
655 | if lose: | |
656 | SYS.exit(1) | |
657 | ||
658 | ## Reassemble the secret. | |
659 | secret = Secret(params.count, params.thresh, sj.recover()) | |
660 | ||
661 | if params.hash != secret.hash(params.hashfn): | |
662 | die('secret doesn\'t match hash') | |
663 | ||
664 | if opts.file == '-': | |
665 | SYS.stdout.write(secret.secret) | |
666 | else: | |
667 | with open(opts.file, 'wb') as f: | |
668 | f.write(secret.secret) | |
669 | ||
670 | OPTPARSE.add_subcommand( | |
671 | 'recover', cmd_recover, | |
672 | '', | |
673 | """\ | |
674 | Standard input should contain a number of lines. The first line should | |
675 | contain the secret sharing parameters (the first line output by `issue'); | |
676 | the remaining lines should contain shares. The shares may be supplied in | |
677 | any order. The secret is written to the OUTPUT file, or standard output.""", | |
678 | [OPT.make_option('-o', '--output', action = 'store', type = 'string', | |
679 | dest = 'file', default = '-', | |
680 | help = 'Write the secret to FILE.')]) | |
681 | ||
682 | ###----- That's all, folks -------------------------------------------------- | |
683 | ||
684 | if __name__ == '__main__': | |
685 | OPTPARSE.dispatch() |