10 More Discussions You Might Find Interesting
1. Shell Programming and Scripting
Input file:
bv|111259484|pir||T49736_real_data
bv|159484|pir||T9736_data_figure
bv|113584|prf|T4736|truth
bv|113584|pir||T4736_truth
Desired output:
bv|111259484|pir|T49736|real_data
bv|159484|pir|T9736|data_figure
bv|113584|prf|T4736|truth
bv|113584|pir|T4736|truth
Once the... (8 Replies)
Discussion started by: perl_beginner
8 Replies
2. Shell Programming and Scripting
I am working with an undocumented feature of a software product (BladeLogic). It is returning the below string in response to a query. It is enclosed with square brackets, "records" are separated with commas and "fields" separated with semicolons. My thought was that this might be some basic... (1 Reply)
Discussion started by: dshcs
1 Replies
3. Programming
Hello,
Over the past few years, I've conducted some rather thorough R&D in the field of lexicon-data-structure optimization.
A Trie is a good place to start, followed by a traditional DAWG.
Smaller means faster, but a traditional DAWG encoding operates as a Boolean-graph, unable to index... (1 Reply)
Discussion started by: HeavyJ
1 Replies
4. Shell Programming and Scripting
Hi All,
I want to create a data structure like this
$VAR1 = {
'testsuite' => {
'DHCP' => {
'failures' => '0',
'errors' => '0',
'time' =>... (3 Replies)
Discussion started by: Damon_Qu
3 Replies
5. Shell Programming and Scripting
I have the perl data structure and what i need to do is find all values in
@{$extractColumns{'2'}{'D'}} which are not there in @{$extractColumns{'2'}{'M'}} but seems like i need to put a flag somewhere and i messed up
foreach my $order (keys %extractColumns)
{
foreach my $value... (2 Replies)
Discussion started by: dinjo_jo
2 Replies
6. Programming
Dear All,
I would appreciate if some one could please post a few examples using GDSL library. The library provides general data structure operations.
I am having confusion using list data structure regarding arguments.
Would appreciate your kind response.
with regards,
Usman (2 Replies)
Discussion started by: usman_minhas
2 Replies
7. Programming
hello guys,
i'm required to modify the process scheduling part of the freebsd kernel as part of our homework.
the homework needs us add a new variable to the process data structure, and the priority of the process will be having something to do with the variable.
to adjust the variable... (2 Replies)
Discussion started by: billconan
2 Replies
8. Shell Programming and Scripting
Hello,
I have a file of the following information ( first field parent item, second field child item)
PM01 PM02
PM01 PM1A
PM02 PM03
PM03 PM04
PM03 PM05
PM03 PM06
PM05 PM10
PM1A PM2A
PM2A PM3B
PM2A PM3C
The output should be like this :
PM01 PM02 PM03 PM04
... (2 Replies)
Discussion started by: ThobiasVakayil
2 Replies
9. Programming
I have heard about on-disk data structures, but I am trying to understand how to implement it.
I want to write a program which is going to make use of a B-Tree which is so huge that whole of it cannot sit in memory.
Lets take a simple case of a linked list. Suppose I want to have a linked... (1 Reply)
Discussion started by: the_learner
1 Replies
10. Filesystems, Disks and Memory
the superblock has the offset for inode table.
My question is
1) whether it starts relative to the start of the first cylinder group
or is it relative to the start of filesystem???
2)and also which entry corresponds to the root(/) inode?? is it second or third entry???
My questions are... (4 Replies)
Discussion started by: anwerreyaz
4 Replies
GFSHARE(7) Shamir Secret Sharing in gf(2**8) GFSHARE(7)
NAME
gfshare - explanation of Shamir Secret Sharing in gf(2**8)
SYNOPSIS
In simple terms, this package provides a library for implementing the sharing of secrets and two tools for simple use-cases of the algo-
rithm. The library implements what is known as Shamir's method for secret sharing in the Galois Field 2**8. In slightly simpler words,
this is N-of-M secret-sharing byte-by-byte. Essentially this allows us to split a secret S into any M shares S(1) to S(M) such that any N
of those shares can be used to reconstruct S but any less than N shares yields no information whatsoever.
EXAMPLE USE CASE
Alice has a GPG secret key on a usb keyring. If she loses that keyring, she will have to revoke the key. This sucks because she go to con-
ferences lots and is scared that she will, eventually, lose the key somewhere. So, if, instead she needed both her laptop and the usb
keyring in order to have her secret key, losing one or the other does not compromise her gpg key. Now, if she splits the key into a 3-of-5
share, put one share on her desktop, one on the laptop, one on her server at home, and two on the keyring, then the keyring-plus-any-
machine will yield the secret gpg key, but if she loses the keyring, She can reconstruct the gpg key (and thus make a new share, rendering
the shares on the lost usb keyring worthless) with her three machines at home.
THE PRINCIPLES BEHIND SHAMIR'S METHOD
What Shamir's method relies on is the creation of a random polynomial, the sampling of various coordinates along the curve of the polyno-
mial and then the interpolation of those points in order to re-calculate the y-intercept of the polynomial in order to reconstruct the
secret. Consider the formula for a straight line: Y = Mx + C. This formula (given values for M and C) uniquely defines a line in two dimen-
sions and such a formula is a polynomial of order 1. Any line in two dimensions can also be uniquely defined by stating any two points
along the line. The number of points required to uniquely define a polynomial is thus one higher than the order of the polynomial. So a
line needs two points where a quadratic curve needs three, a cubic curve four, etc.
When we create a N-of-M share, we encode the secret as the y-intercept of a polynomial of order N-1 since such a polynomial needs N points
to uniquely define it. Let us consider the situation where N is 2: We need a polynomial of order 1 (a straight line). Let us also consider
the secret to be 9, giving the formula for our polynomial as: Y = Ax + 9. We now pick a random coefficient for the graph, we'll use 3 in
this example. This yields the final polynomial: Sx = 3x + 9. Thus the share of the secret at point x is easily calculated. We want some
number of shares to give out to our secret-keepers; let's choose three as this number. We now need to select three points on the graph for
our shares. For simplicity's sake, let us choose 1, 2 and 3. This makes our shares have the values 12, 15 and 18. No single share gives
away any information whatsoever about the value of the coefficient A and thus no single share can be used to reconstruct the secret.
Now, consider the shares as coordinates (1, 12) (2, 15) and (3, 18) - again, no single share is of any use, but any two of the shares
uniquely define a line in two-dimensional space. Let us consider the use of the second and third shares. They give us the pair of simula-
neous equations: 15 = 2M + S and 18 = 3M + S. We can trivially solve these equations for A and S and thus recover our secret of 9.
Solving simultaneous equations isn't ideal for our use due to its complexity, so we use something called a 'Lagrange Interpolating Polyno-
mial'. Such a polynomial is defined as being the polynomial P(x) of degree n-1 which passes through the n points (x1, y1 = f(x1)) ... (xn,
yn = f(xn)). There is a long and complex formula which can then be used to interpolate the y-intercept of P(x) given the n sets of coordi-
nates. There is a good explanation of this at http://mathworld.wolfram.com/LagrangeInterpolatingPolynomial.html.
OKAY, SO WHAT IS A GALOIS FIELD THEN?
A Galois Field is essentially a finite set of values. In particular, the field we are using in this library is gf(2**8) or gf(256) which is
the values 0 to 255. This is, cunningly enough, exactly the field of a byte and is thus rather convenient for use in manipulating arbi-
trary amounts of data. In particular, performing the share in gf(256) has the property of yielding shares of exactly the same size as the
secret. Mathematics within this field has various properties which we can use to great effect. In particular, addition in any Galois Field
of the form gf(2**n) is directly equivalent to bitwise exclusive-or (an operation computers are quite fast at indeed). Also, given that (X
op Y) mod F == ((X mod F) op (Y mod F)) mod F we can perform maths on values inside the field and keep them within the field trivially by
truncating them to the relevant number of bits (eight).
OKAY, SO WHY IS THERE NO MULTIPLICATION IN THIS IMPLEMENTATION?
For speed reasons, this implementation uses log and exp as lookup tables to perform multiplication in the field. Since exp( log(X) + log(Y)
) == X * Y and since table lookups are much faster than multiplication and then truncation to fit in a byte, this is a faster but still
100% correct way to do the maths.
AUTHOR
Written by Daniel Silverstone.
REPORTING BUGS
Report bugs against the libgfshare product on www.launchpad.net.
COPYRIGHT
libgfshare is copyright (C) 2006 Daniel Silverstone.
This is free software. You may redistribute copies of it under the terms of the MIT licence (the COPYRIGHT file in the source distribu-
tion). There is NO WARRANTY, to the extent permitted by law.
SEE ALSO
gfsplit(1), gfcombine(1), libgfshare(3)
1.0.5 February 2006 GFSHARE(7)