| 1 | #! @PYTHON@ |
| 2 | ### |
| 3 | ### Shamir secret sharing |
| 4 | ### |
| 5 | ### (c) 2011 Mark Wooding |
| 6 | ### |
| 7 | |
| 8 | ###----- Licensing notice --------------------------------------------------- |
| 9 | ### |
| 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 |
| 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 | ### |
| 17 | ### distorted-keys is distributed in the hope that it will be useful, |
| 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 |
| 23 | ### along with distorted-keys; if not, write to the Free Software Foundation, |
| 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 | print |
| 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() |