sharing secret
It is a known problem: I have a secret and want to share it with for example 5 friends in such a way that any for example 3 of them may find out the full secret (and any 2 can not).
The problem is known as "k-treshold system for sharing secret", and there is a solution based on the Chinese Remainder Theorem. It sound simple and good in theory, but I don't trust it a lot - I know it's quite easy to get something very wrong when dealing with security. So is there any available implementation of this solution, or another solution?
[548 byte] By [
Maaartina] at [2007-10-2 21:32:49]
Shamir's 'k' from 'n' is very easy to implement in Java using BigInteger and Lagrange Polynomials.
Thanks! That's really simple - and even WITHOUT BigInteger: http://szabo.best.vwh.net/secret.html
> Thanks! That's really simple - and even WITHOUT
> BigInteger:
> http://szabo.best.vwh.net/secret.html
BigInteger allows you to
1) convert a secret key in the form of bytes to a BigInteger
2) generate a probable prime larger than your secret key
3) perform the required modulo arithmetic
4) generate the modulo inverse needed in computing the Lagrange interpolation
etc etc etc
Sure, it does. BigInteger is fine, but Shamir writes:
If the number D is long, it is advisable to break it into shorter blocks of bits (which are handled separately) in order to avoid multiprecision arithmetic operations. The blocks cannot be arbitrarily short, since the smallest usable value of p is n + 1 (there must be at least n + 1 distinct arguments in [0, p) to evaluate q(x) at). However, this is not a severe limitation since sixteen bit modulus (which can be handled by a cheap sixteen bit arithmetic unit) suffices for applications with up to 64,000 Di pieces.
Yes, the partition of the secret into a set of short blocks is one way of handling the precision problem. There is a unix utility (which I can't find a reference to right now) which splits a whole file this way. I thought it was part of a freshmeat project called ssss but I have just checked and it des not seem to operate the way I remember!
Out of interest only, I was looing at dealing with keys so that a key could be split and the component parts stored on a smart card. On one contract I had worked on a system like this and I was interested in seeing how it could be done. I was suprised how easy it was to do in Java.
In my system, each share consists of 3 basic parts - the x value, the y value and the modulus. In addition to this I distribute a hash of the secret, the x value, the y value and the modulus. Once a ley has been recovercd, the hash allows me to check that enough shares have been presented to recover the secret and that all the shares presented are valid.
I found I could handle share generation of a 256 byte key with any 10 from 20 is a very short time (much less than a second) but a 4096 byte key with any 50 from a 100 the process is very slow (20 or so seconds). As Shamir suggests, splitting the secret into short segments might be the way to improve on this. I shall add this to my ever growing list of 'things to look at '.
There is a unix utility (which I can't find a reference to right now) which splits a whole file this way.
You mean split?
http://www.hmug.org/man/1/split.php
Once a ley has been recovercd, the hash allows me to check that enough shares have been presented to recover the secret and that all the shares presented are valid.
Nice and simply, I think about somthing similar.
As Shamir suggests, splitting the secret into short segments might be the way to improve on this. I shall add this to my ever growing list of 'things to look at '.
It's VERY simple: You don't need to seek any "meaningfull" way to split it. Just split your 4096 byte key into 2048 pieces, 2 byte each and use the Shamirs algorithm on each of them. Then concatenate the corresponding parts and distibute it. The time for a 4096 byte key will be exatle the time for the 2 byte key times 2048, i.e. a couple of milliseconds.
> There is a unix utility (which I can't find a
> reference to right now) which splits a whole file
> this way.
>
> You mean split?
> http://www.hmug.org/man/1/split.php
No not 'split'! 'split' just breaks the file; it does not do k from n.
I've just finished a simple implementation of the alg based on computing with modulus of 251. It's quite stupid, but takes only about 2 seconds for processing a 4096 byte secret with any 50 from 100. I'm quite sure, I can speed it up at least twice.
Reconstruction of the key is nearly 100 times faster, for whatever reason.
> I've just finished a simple implementation of the alg
> based on computing with modulus of 251. It's quite
> stupid, but takes only about 2 seconds for processing
> a 4096 byte secret with any 50 from 100. I'm quite
> sure, I can speed it up at least twice.
>
> Reconstruction of the key is nearly 100 times faster,
> for whatever reason.
Looks to be a lot faster than my BigInteger version. Just out of interest, I shall have a go at it sometime.
I've expected it to be even faster. The most time consuming part is the computation of the values of the polynomials.
Using modulus 251 arithmetic I would need sligtly more than 4096 polynomials (log(251)/log(256)*4096 = 4082), with a simple coding (base128) it would be 4096*8/7=4682, but using my current stupid version it is 8192.
Each polynomial of degree 49 is to be computed on for 100 different x values, so about 20e5 modulus operations are to be carried out. Using a table lookup would make it dramatically faster.
Instead of GF(251) I should use GF(256), this way no bits would be wasted, and the computation using lookup tables for division and multiplication would be as simple as it is now. I'm going to seek the tables now.
I can send the code to you, if you wish.
I've got the multiplication table for GF(256), so I expect a major speed up, maybe tomorow I'll do it. One simple lookup in a table of 256*256 bytes instead of multiplication and modulus....
I'm not sure you can use GF(256) (Grant may know). My understanding is that it is best (required?) if it is prime. I have been working with 65537.
For this you need polynomials. Polynomials are defined over a field. A simplest finite field is GF(p) for a prime p. The're also GF(p**n) for any prime p and n>0, which are harder to understand but otherwise as good as GF(p). I'm going to test in just now.
> For this you need polynomials. Polynomials are
> defined over a field. A simplest finite field is
> GF(p) for a prime p. The're also GF(p**n) for any
> prime p and n>0, which are harder to understand but
> otherwise as good as GF(p). I'm going to test in just
> now.
I didn't know that one could use p**n!
I have just tried my modular inverse routine on 16 and it fails. My implementation is based on that given by Ferguson and Schneier in 'Practical Cryptography'.How does one take the inverse for 2**n?
It works.... for our example it takes 56 seconds for 100 repetions on my 3GHz computer. Because of using GF(256) it's limited to 255 shares, that's the only limitation.
Sorry for all missing comments.
package de.grajcar.util;
public class GF256 {
private GF256() {
}
public static int mul(int a, int b) {
a &= 0xFF;
b &= 0xFF;
return mul[(a<<8) + b] & 0xFF;
}
public static int inv(int a) {
a &= 0xFF;
return a==0 ? 1/0 : inv[a] & 0xFF;
}
public static int div(int a, int b) {
return mul(a, inv(b));
}
private static int privateMul(int a, int b) {
int result = 0;
for(int counter=0; counter<8; ++counter) {
if((b&1) != 0) result ^= a;
boolean carry = (a&0x80) != 0;
a <<= 1;
a &= 0xFF;
if(carry) a ^= 0x1b;
b >>= 1;
}
return result & 0xFF;
}
private final static byte[] mul = new byte[1<<16];
private final static byte[] inv = new byte[1<<8];
static {
for (int a=0; a<256; ++a) {
for (int b=0; b<256; ++b) {
final int c = privateMul(a, b);
mul[(a<<8)+b] = (byte) c;
if (c==1) inv[a] = (byte) b;
}
}
}
}
package de.grajcar.util;
import java.security.SecureRandom;
import java.util.Random;
public final class Shamir {
public static byte[][] encode(byte[] data, int needed, int total) {
if (needed<=0) throw new IllegalArgumentException("needed must be > 0");
if (total>255) throw new IllegalArgumentException("total must be <= 255");
if (needed>total) throw new IllegalArgumentException("needed must be <= total");
final Random random = new SecureRandom();
final byte[][] polynomial = new byte[data.length][needed];
for (int i=0; i<polynomial.length; ++i) {
final byte[] p = polynomial[i];
for (int j=0; j><p.length; ++j) {
p[j] = (byte) random.nextInt(256);
}
p[p.length-1] = data[i];
}
byte[][] result = new byte[total][data.length+1];
for (int i=0; i><result.length; ++i) {
final byte[] r = result[i];
r[r.length-1] = (byte) (i+1);
for (int j=0; j><polynomial.length; ++j) {
final byte[] p = polynomial[j];
int n = 0;
for (int k=0; k><p.length; ++k) {
n = GF256.mul(n, i+1);
n ^= p[k];
}
r[j] = (byte) n;
}
}
return result;
}
public static byte[] decode(byte[][] shares) {
final byte[] result = new byte[shares[0].length-1];
final byte[] x = new byte[shares.length];
for (int i=0; i><x.length; ++i) x[i] = shares[i][shares[i].length-1];
final byte[] lagr = new byte[x.length];
for (int i=0; i><x.length; ++i) {
int p = 1, q = 1;
for (int j=0; j><x.length; ++j) {
if (i==j) continue;
p = GF256.mul(p, x[j]);
q = GF256.mul(q, x[j]^x[i]);
}
lagr[i] = (byte) GF256.div(p, q);
}
for (int i=0; i><result.length; ++i) {
int n = 0;
for (int j=0; j><x.length; ++j) n ^= GF256.mul(shares[j][i], lagr[j]);
result[i] = (byte) n;
}
return result;
}
}
>
I have just tried my modular inverse routine on 16 and it fails..
It MUST fail! Modular arithmetics is field only for primes, otherwise there's no division possible.GF(16) and modular arithmetics for modulus 16 are two very different things.
See my posted class GF256. The formula in privateMul I took from
http://www.samiam.org/galois.html
the rest is my own simple optimization.
> I have just tried my modular inverse routine on 16
> and it fails..
>
> It MUST fail! Modular arithmetics is field only for
> primes, otherwise there's no division possible.GF(16)
> and modular arithmetics for modulus 16 are two very
> different things.
:-) This just shows my ignorance! I was not aware of the distinction.
>
> See my posted class GF256. The formula in privateMul
> I took from
> http://www.samiam.org/galois.html
> the rest is my own simple optimization.
Very very interesting. I can follow the concepts but not (yet) the detail.
a test case....
package de.grajcar.util;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import junit.framework.TestCase;
public class ShamirTest extends TestCase {
public void test0() {
for (int i=0; i<10; ++i) {
final byte[] secret = new byte[(1<<i)-1];
random.nextBytes(secret);
final int total = 2 + random.nextInt(100);
final int needed = 1 + random.nextInt(total);
final byte[][] shares = Shamir.encode(secret, needed, total);
//Report.a(i, secret.length, total, needed);
for (int j=0; j><100; ++j) {
final byte[][] sh = new byte[needed][];
final int[] sel = nextSelection(total, needed);
for (int k=0; k<needed; ++k) sh[k] = shares[sel[k]];
final byte[] restored = Shamir.decode(sh);
assertTrue(Arrays.equals(secret, restored));
// Report.a(i, total, needed, Arrays.toString(sel));
}
}
}
private int[] nextSelection(int range, int length) {
if (length>range) throw new IllegalArgumentException();
int[] result = new int[length];
if (range>2*length) {
HashSet<Integer> set = new HashSet<Integer>(length);
for (int i=0; i<length; ) {
int r = random.nextInt(range);
boolean b = set.add(new Integer(r));
if (b) result[i++] = r;
}
} else {
int[] a = range==length ? result : new int[range];
for (int i=0; i><range; ++i) a[i] = i;
for (int i=1; i><range; ++i) {
int ix = random.nextInt(i);
int tmp = a[i]; a[i] = a[ix]; a[ix] = tmp;
}
if (range!=length) {
for (int i=0; i><length; ++i) result[i] = a[i];
}
}
return result;
}
private final Random random = new Random(0);
}
>
> I've got the multiplication table for GF(256), so I
> expect a major speed up, maybe tomorow I'll do it.
> One simple lookup in a table of 256*256 bytes instead
> of multiplication and modulus....
Hi;
I was searching the internet to find addition and multiplication tables for GF(256); when i found this discussion in the forum, wherein you have said that you have them.
Can you please provide me with the tables. It will be of great help.
Thanks in advance
Aka
Akaa at 2007-7-21 8:05:52 >
I have the tables no more, but I have a class doing all the work. Addition is the usual XOR, so it's not included.
The operands are byte (declared as ints for convenience).
public class GF256 {
private GF256() {
}
public static int mul(int a, int b) {
a &= 0xFF;
b &= 0xFF;
return mul[256*a+b] & 0xFF;
}
public static int inv(int a) {
a &= 0xFF;
return a==0 ? 1/0 : inv[a] & 0xFF;
}
public static int div(int a, int b) {
return mul(a, inv(b));
}
private static int privateMul(int a, int b) {
int result = 0;
for (int i=0; i<8; ++i) {
if ((b&1) != 0) result ^= a;
boolean carry = (a&0x80) != 0;
a <<= 1;
a &= 0xFF;
if (carry) a ^= 0x1b;
b >>= 1;
}
return result & 0xFF;
}
private final static byte[] mul = new byte[1<<16];
private final static byte[] inv = new byte[1<<8];
static {
for (int a=0; a<256; ++a) {
for (int b=0; b<256; ++b) {
final int c = privateMul(a, b);
mul[256*a+b] = (byte) c;
if (c==1) inv[a] = (byte) b;
}
}
}
}
