The recent postings about crypto sharing/spliting programs
renewed my interest, so I dusted off cryptosplit (a Shamir
secret sharing program I wrote around November of last year)
and fixed up the bugs which made it unusable. Here it is,
less bugged, about 10 times faster than before, but still ugly.
# This is a shell archive. Save it in a file, remove anything before
# this line, and then unpack it by entering "sh file". Note, it may
# create directories; files and directories will be owned by you and
# have default permissions.
#
# This archive contains:
#
# README
# Makefile
# cryptosplit.c
# gf.h
#
echo x - README
sed 's/^X//' >README << 'END-of-README'
X
XHow to use
X----------
XTo encode:
X
Xcsplit -g <number of pieces> -q <minimum number required for decode> [filename]
X
Xtake filename and split it into the number of pieces given by -g. Each
Xpiece is "filename.0", "filename.1", ..., "filename.(n-1)" if
Xfilename isn't supplied, it operates like kinda like a filter taking the
Xincoming data and spliting it into files "piece.0", "piece.1", ...
X
Xto decode:
X
Xprovide atleast the number of pieces specified by -q when you encoded.
XIf you specify less than the minimum number, it will not decode.
X
Xexample:
X
Xcsplit -g 5 -q 3 file
X[split file into 5 pieces, any 3 of which will reconstruct it]
X
Xcsplit file.0 file.1 file.2
X[put them together in the decoded file and output to stdout]
X
Xif you want to put it into a file, redirect it using the shell, or
Xuse "-o filename"
X
X-Ray
X
X
END-of-README
echo x - Makefile
sed 's/^X//' >Makefile << 'END-of-Makefile'
X
XCFLAGS=-O
X
X
Xcsplit: cryptosplit.c gf.h
X cc $(CFLAGS) cryptosplit.c -o csplit
X
END-of-Makefile
echo x - cryptosplit.c
sed 's/^X//' >cryptosplit.c << 'END-of-cryptosplit.c'
X/*
X * Cryptosplit 2.03 An implementation of Shamir secret sharing over GF(2^8)
X *
X * written by Ray Cromwell <rjc(a)gnu.ai.mit.edu> Version 2.01 - fixed bug and
X * make it generate a different polynomial for each byte
X */
X
X/* Pay no attention to the sloppy code, this is only a first draft */
X
X#include "gf.h"
X#include <sys/types.h>
X#include <sys/stat.h>
X#include <ctype.h>
X#include <stdio.h>
X
Xwrite_pieces(char **, char **, int);
Xwrite_key(char *, char *, int);
Xint read_key(char *, int);
Xint read_pieces(char **, int);
Xgenerate_key(char *);
X
Xint quorum = 2;
Xint pieces = 3;
X
Xint generate = 0;
Xchar *key = 0;
Xchar *tmpkey = 0;
Xchar **keypieces;
Xchar *keyfiles[256];
Xchar *outputfile = (char *) 0;
X
X#define CHUNKSIZE 8192
X#define RANDINIT(x) srand(time(0))
X#define RAND rand
X
Xmain(int argc, char *argv[])
X{
X int c = 1, k = 0;
X
X RANDINIT(0);
X
X if (argc == 1)
X print_help();
X keyfiles[0] = (char *) 0;
X
X while (c < argc) {
X if (argv[c][0] == '-') {
X if (argv[c][1] == 'g') {
X generate = 1;
X c++;
X if (c >= argc)
X print_help();
X pieces = atoi(argv[c++]);
X } else if (argv[c][1] == 'q') {
X c++;
X if (c >= argc)
X print_help();
X quorum = atoi(argv[c++]);
X } else if (argv[c][1] == 'o') {
X c++;
X if (c >= argc)
X print_help();
X outputfile = argv[c++];
X }
X } else {
X keyfiles[k++] = argv[c++];
X }
X }
X if (generate) {
X if (k > 0) {
X init_buffers();
X if(quorum > pieces) pieces=quorum;
X generate_keys(keyfiles[0]);
X }
X } else {
X if (k < 2) {
X fprintf(stderr, "You didn't supply enough pieces.\n");
X exit(1);
X }
X quorum = pieces = k;
X init_buffers();
X rebuild_key(k);
X }
X}
X
Xinit_buffers()
X{
X int i;
X keypieces = (char **) malloc(sizeof(char *) * pieces);
X for (i = 0; i < pieces; i++)
X keypieces[i] = (char *) malloc(CHUNKSIZE);
X key = (char *) malloc(CHUNKSIZE);
X tmpkey = (char *) malloc(CHUNKSIZE);
X}
X
Xint
Xread_pieces(char **files, int offset)
X{
X int i, s;
X FILE *f;
X for (i = 0; i < quorum; i++) {
X if (!(f = fopen(files[i], "r"))) {
X perror("Cryptosplit");
X exit(1);
X }
X fseek(f, offset, SEEK_SET);
X if (feof(f)) {
X fclose(f);
X return 0;
X }
X s = fread(keypieces[i], 1, CHUNKSIZE, f);
X fclose(f);
X }
X return s;
X}
X
Xrebuild_key(int ksize)
X{
X unsigned char **coeffs;
X unsigned char *consts;
X int i, j, k, p, t, sr, ip, klen, off = 0;
X unsigned char x, y, z, r;
X coeffs = (unsigned char **) malloc(sizeof(char *) * quorum);
X t = 1;
X x = 0;
X for (i = 0; i < quorum; i++) {
X coeffs[i] = (char *) malloc(quorum);
X }
X consts = (char *) malloc(quorum);
X while (klen = read_pieces(keyfiles, off)) {
X off += klen;
X t = 1;
X while (t < klen) {
X for (i = 0; i < quorum; i++) {
X x = keypieces[i][0];
X y = keypieces[i][t];
X consts[i] = y;
X coeffs[i][quorum - 1] = 1;
X z = x;
X for (j = quorum - 2; j >= 0; j--) {
X coeffs[i][j] = z;
X z = GFMUL(z, x);
X }
X }
X sr = 0;
X ip = 0;
X/* Invert quorum x quorum matrix to obtain the constant factor */
X/* We can use lagrange interpolation or something better later.
X Shamir says there is an O(n^2 log n) method, I'll code it when
X I see it. */
X
X for (i = sr; i < quorum; i++) {
X/* print_matrix(coeffs, consts); */
X r = GFINV(coeffs[i][i]);
X consts[i] = GFMUL(consts[i], r);
X coeffs[i][i] = 1;
X for (j = sr + 1; j < quorum; j++) {
X coeffs[i][j] = GFMUL(coeffs[i][j], r);
X }
X for (ip = i + 1; ip < quorum; ip++) {
X r = coeffs[ip][sr];
X for (j = sr; j < quorum; j++) {
X z = GFMUL(coeffs[i][j], r);
X coeffs[ip][j] = GFADD(coeffs[ip][j], GFMUL(coeffs[i][j], r));
X }
X consts[ip] = GFADD(consts[ip], GFMUL(consts[i], r));
X }
X sr = sr + 1;
X }
X/* print_matrix(coeffs, consts); */
X key[t - 1] = consts[quorum - 1];
X t++;
X }
X write_key(outputfile, key, klen - 1);
X }
X}
X
Xint
Xread_key(char *file, int offset)
X{
X int size;
X FILE *f;
X if (file)
X f = fopen(file, "r");
X else
X f = stdin;
X fseek(f, offset, SEEK_SET);
X if (feof(f)) {
X fclose(f);
X return 0;
X }
X size = fread(key, 1, CHUNKSIZE - 1, f);
X fclose(f);
X return size;
X}
X
Xint
Xfilesize(char *file)
X{
X struct stat s;
X if (stat(file, &s)) {
X perror("Cryptosplit");
X exit(0);
X }
X return s.st_size;
X}
X
Xgenerate_keys(char *keyfilename)
X{
X int i, j, k, o, keylength, off;
X unsigned char *coeffs;
X unsigned char x, y, z;
X char tmpname[256];
X coeffs = (char *) malloc(sizeof(char *) * quorum);
X off = 0;
X if (!keyfilename)
X keyfilename = "piece";
X
X for (i = 0; i < pieces; i++) {
X keyfiles[i] = (char *) malloc(256);
X sprintf(keyfiles[i], "%s.%d", keyfilename, i);
X unlink(keyfiles[i]);
X }
X while (keylength = read_key(keyfilename, off)) {
X off += keylength;
X for (j = 0; j < keylength; j++) {
X /* Generate a random quorum-1'th degree polynomial */
X for (o = 1; o < quorum; o++) {
X coeffs[o] = GF(RAND() % 256);
X }
X for (i = 0; i < pieces; i++) {
X y = key[j];
X x = GF(i + 1);
X keypieces[i][0] = x;
X z = x;
X for (k = 1; k < quorum; k++) {
X y = GFADD(y, GFMUL(coeffs[k], x));
X x = GFMUL(x, z);
X }
X keypieces[i][j + 1] = y;
X }
X }
X write_pieces(keyfiles, keypieces, keylength + 1);
X }
X}
X
Xwrite_pieces(char **files, char **data, int ks)
X{
X FILE *f;
X int i;
X for (i = 0; i < pieces; i++) {
X f = fopen(files[i], "a");
X fwrite(data[i], ks, 1, f);
X fclose(f);
X }
X}
X
Xwrite_key(char *file, char *t, int k)
X{
X FILE *f;
X if (file)
X f = fopen(file, "a");
X else
X f = stdout;
X fwrite(t, k, 1, f);
X fclose(f);
X}
X
Xprint_help()
X{
X fprintf(stderr, "To generate 'pieces' of a 'key'\n");
X fprintf(stderr, "Usage: cryptosplit -g <# of pieces> -q <quorum required to rebuild> keyfile\n\n");
X fprintf(stderr, "To reconstruct the original file from n 'pieces'\n");
X fprintf(stderr, "Usage: cryptosplit piece_1 piece_2 ... piece_n [-o output filename]\n");
X exit(0);
X}
X
Xprint_matrix(char **co, char *c)
X{
X int i, j;
X for (i = 0; i < quorum; i++) {
X for (j = 0; j < quorum; j++) {
X printf("%3u ", ((unsigned long) co[i][j] & 0xFF));
X }
X printf("= %3u\n", ((unsigned long) c[i] & 0xFF));
X }
X printf("\n");
X}
END-of-cryptosplit.c
echo x - gf.h
sed 's/^X//' >gf.h << 'END-of-gf.h'
X/* Cryptosplit
X * An implementation of Shamir secret sharing over GF(2^8)
X *
X * written by Ray Cromwell <rjc(a)gnu.ai.mit.edu>
X */
X
X/* Pay no attention to the sloppy code, this is only a first draft */
X
X/* g is a primitive element, this table represents g^k for 0 <= k <= 255 */
Xint G[]={
X1, 103, 129, 227, 78, 81, 222, 46, 50, 20, 176, 94, 170, 253, 166, 32,
X33, 70, 199, 36, 106, 59, 229, 203, 249, 237, 93, 3, 169, 84, 242, 210,
X243, 181, 114, 86, 60, 7, 226, 41, 208, 61, 96, 99, 202, 158, 108, 190,
X77, 248, 138, 220, 224, 231, 5, 44, 252, 193, 161, 194, 8, 150, 250, 68,
X9, 241, 123, 167, 71, 160, 165, 137, 117, 180, 21, 215, 223, 73, 179, 247,
X254, 15, 116, 211, 148, 52, 145, 24, 109, 217, 204, 27, 196, 141, 62, 201,
X55, 56, 76, 159, 11, 63, 174, 182, 219, 2, 206, 213, 17, 156, 162, 107,
X92, 100, 40, 183, 188, 131, 45, 155, 64, 66, 140, 89, 72, 212, 118, 29,
X65, 37, 13, 186, 6, 133, 168, 51, 115, 49, 189, 228, 172, 120, 14, 19,
X82, 119, 122, 192, 198, 67, 235, 216, 171, 154, 39, 195, 111, 23, 25, 10,
X88, 47, 85, 149, 83, 16, 251, 35, 136, 18, 53, 246, 153, 142, 151, 157,
X197, 234, 191, 42, 121, 105, 146, 177, 57, 43, 30, 232, 113, 255, 104, 245,
X48, 218, 101, 79, 54, 95, 205, 124, 69, 110, 112, 152, 233, 22, 126, 139,
X187, 97, 4, 75, 125, 34, 239, 147, 214, 184, 200, 80, 185, 175, 209, 90,
X225, 128, 132, 207, 178, 144, 127, 236, 58, 130, 74, 26, 163, 12, 221, 135,
X102, 230, 98, 173, 31, 143, 240, 28, 38, 164, 238, 244, 87, 91, 134, 1,
X};
X
X/* if n=g^k, this table returns k=lg n */
Xint I[]={
X0, 255, 105, 27, 210, 54, 132, 37, 60, 64, 159, 100, 237, 130, 142, 81,
X165, 108, 169, 143, 9, 74, 205, 157, 87, 158, 235, 91, 247, 127, 186, 244,
X15, 16, 213, 167, 19, 129, 248, 154, 114, 39, 179, 185, 55, 118, 7, 161,
X192, 137, 8, 135, 85, 170, 196, 96, 97, 184, 232, 21, 36, 41, 94, 101,
X120, 128, 121, 149, 63, 200, 17, 68, 124, 77, 234, 211, 98, 48, 4, 195,
X219, 5, 144, 164, 29, 162, 35, 252, 160, 123, 223, 253, 112, 26, 11, 197,
X42, 209, 242, 43, 113, 194, 240, 1, 190, 181, 20, 111, 46, 88, 201, 156,
X202, 188, 34, 136, 82, 72, 126, 145, 141, 180, 146, 66, 199, 212, 206, 230,
X225, 2, 233, 117, 226, 133, 254, 239, 168, 71, 50, 207, 122, 93, 173, 245,
X229, 86, 182, 215, 84, 163, 61, 174, 203, 172, 153, 119, 109, 175, 45, 99,
X69, 58, 110, 236, 249, 70, 14, 67, 134, 28, 12, 152, 140, 243, 102, 221,
X10, 183, 228, 78, 73, 33, 103, 115, 217, 220, 131, 208, 116, 138, 47, 178,
X147, 57, 59, 155, 92, 176, 148, 18, 218, 95, 44, 23, 90, 198, 106, 227,
X40, 222, 31, 83, 125, 107, 216, 75, 151, 89, 193, 104, 51, 238, 6, 76,
X52, 224, 38, 3, 139, 22, 241, 53, 187, 204, 177, 150, 231, 25, 250, 214,
X246, 65, 30, 32, 251, 191, 171, 79, 49, 24, 62, 166, 56, 13, 80, 189,
X};
X
X#define GFADD(a,b) ((a) ^ (b))
X#define GFMUL(a,b) (((a)==0 || (b)==0) ? 0 : G[(I[(a)] + I[(b)]) % 255])
X#define GFINV(a) ((a)==0 ? 0 : G[255-I[(a)]])
X#define GF(a) (G[(a) % 255])
X#define LOGGF(a) (I[(a)%255])
X
END-of-gf.h
exit
