Shamir sharing and GF(2^n)
- From: "Peter S. May" <psmay@xxxxxxxxxxxx>
- Date: Tue, 03 Oct 2006 13:12:26 -0400
All right, so despite still being a little foggy on the specifics of
GF(2^n), once everything was abstracted out I managed to put together a
nice (t,n) secret sharing mechanism for t < 256 (using GF(2^8)), and it
looks adaptable to GF(2^16), provided I can find an irreducible
polynomial that works. (A doc I found about Reed-Solomon coding
suggested x^8 + x^5 + x^3 + x^2 + 1, rendered as 100101101b = 301, and
it works, but I'm still not sure how to construct an irreducible
polynomial for a given field. Any suggestions?)
In the meantime, I'd like to ask anyone who's messed with such things
before to examine my algorithm for "szt" (Solve for x^Zero Term). It
performs Gaussian elimination but really does it in a rather human
way--so I'm wondering if there's anything more efficient.
The matrix initialization code sets up the (augmented) matrix something
like this:
[ ... x0^3 x0^2 x0 1 | y0 ]
[ ... x1^3 x1^2 x1 1 | y1 ]
[ ... x2^3 x2^2 x2 1 | y2 ]
[ ... ... ... ... ... | ... ]
(This layout is an arbitrary decision with its roots in when I was
working this out mod 65537; in that scheme multiplication was a slightly
cheaper operation than division.)
The algorithm works by dividing the top row by its left column so that
its first element is 1, then the product of the first row and the first
column of a later row is subtracted from that row to make the leftmost
term 0. Then, the top row and the left column are discarded, and the
process is repeated on the smaller matrix. (This makes the matrix upper
triangular, but we only want the x^0 term so we can discard the other
rows.) When the matrix is reduced to one row, the solution is the y
element divided by the x element.
This seems about as good an algorithm as any for solving an arbitrary
augmented matrix, but is it the best way to work out a linear
interpolation problem?
Thanks in advance for any keen insight -- PSM
GF256_DATA gf256_szt_prealloc(GF256_DATA* x, GF256_DATA* y, size_t size, GF256_DATA* work_buffer)
{
size_t i, j, m;
data tmp;
int b;
#define ROWLEN (size+1)
#define NUMROWS (size)
#define LASTCOL (size)
#define BUF(row,col) ( work_buffer[ (ROWLEN * (row)) + (col) ] )
if( size == 0 )
return ~0;
else if( size == 1 ) {
if( x[0] == 0 )
return ~0; /* linear dependence? */
else
return div(y[0],x[0]);
}
/* there are at least three cols. set them up. */
for(i = 0; i < NUMROWS; ++i) {
BUF(i,LASTCOL) = y[i];
BUF(i,LASTCOL-1) = 1;
BUF(i,LASTCOL-2) = x[i];
for(j = 0; j < LASTCOL-2; ++j) {
#define CURINDEX ( (LASTCOL-3) - (j) )
BUF(i,CURINDEX) = mul(x[i],BUF(i,CURINDEX+1));
#undef CURINDEX
}
}
for( m = 0; m < size - 1; ++m ) {
/* first col must be invertible */
if( BUF(m,m) == 0 ) {
/* find a row that's invertible there */
for(i = m+1; i < size; ++i) {
if( BUF(i,m) != 0 ) {
tmp = BUF(m,j);
BUF(m,j) = BUF(i,j);
BUF(i,j) = tmp;
break;
}
}
if( i == size )
return ~0; /* linear dependence? */
}
/* normalize the top row so the first col is 1 */
tmp = BUF(m,m);
for(i = m; i < ROWLEN; ++i)
BUF(m,i) = div(BUF(m,i),tmp);
/* for each following row, drain the first col to 0 by
* subtracting the first row * the first col of this row */
for(i = m+1; i < size; ++i) {
tmp = BUF(i,m);
for(j = m; j < ROWLEN; ++j)
BUF(i,j) = sub(BUF(i,j),mul(tmp,BUF(m,j)));
}
}
if( BUF(size-1,LASTCOL-1) == 0 ) {
return ~0;
}
return div( BUF(size-1,LASTCOL), BUF(size-1,LASTCOL-1) );
}
Attachment:
signature.asc
Description: OpenPGP digital signature
- Follow-Ups:
- Re: Shamir sharing and GF(2^n)
- From: Mark Wooding
- Re: Shamir sharing and GF(2^n)
- From: David Wagner
- Re: Shamir sharing and GF(2^n)
- Prev by Date: How many Prime numbers
- Next by Date: Re: Shamir sharing and GF(2^n)
- Previous by thread: How many Prime numbers
- Next by thread: Re: Shamir sharing and GF(2^n)
- Index(es):
Relevant Pages
|
Loading
