Shamir Secret Sharing Implementation Query



Hi,

Say my secret is an n-bit number, under Shamir's scheme I need a
prime, the first prime larger than the secret, then I work in GF(p).
(Think that's correct)

Now in terms of a practical implementation, lets say im secret sharing
arbitrarily long data in 64-bit blocks. I have to assume my secret
could be all 64 bits, which means I will need a 65-bit prime.

What im trying to understand is what is the most efficient way to
share arbitrarily long data in small broken down blocks. i.e if I use
64-bit blocks then how big should my prime be to avoid bit-wasting.

Will 64-bit blocks with a 65-bit prime work ok? Or should I use 63-bit
blocks with a 64-bit prime. Because im working with 8-bit ASCII
secrets, it's obviously easier to work with 64-bit data blocks.

Please could someone give me some pointers on how to do this
correctly, ideally I want to hardcode a prime for my application
rather than searching for one bigger than the secret on each block.

Additionally how complex is it to compute shares in GF(p) from a
programming perspective? Will I have to use lookup tables? Any help
here is much appreciated, I'm not a mathematician and don't have
access to any field-calculation libraries for this project, so have to
do the calculations manually from the ground up.

Thanks for any help.
.



Relevant Pages

  • Re: Efficient Exponentiation of a Shared Secret
    ... shared among a number of parties. ... Shamir's scheme this is the case). ... Is there a scheme in which the secret s can be expressed as a product ... using any k out of n shares the secret x can be reconstructed, ...
    (sci.crypt)
  • Re: Shamir Secret Sharing - Finite Fields
    ... That scheme, and its security properties, are fine in any field, ... In Shamir's scheme, a random polynomial R is selected, where Ris ... If the secret is large then you can split it and perform sharing on each ... use any finite field with the scheme without reducing security? ...
    (sci.crypt)
  • Questions about Shamir secret sharing
    ... polynomial scheme from "How to Share a Secret", ... ss10001 is an experiment in implementing secret sharing as proposed by ... me whether OC mode provides sufficient security, ...
    (sci.crypt)
  • Re: A new public key algorithm based on avalanche properties
    ... I do not understand how the OP's scheme cant work. ... (addition by a secret integer modulo a public number). ... - Has the various commutive properties that the protocol needs for this to ... Is computationally easier to compute than known believed-secure DH groups ...
    (sci.crypt)
  • Re: Joint encryption?
    ... > Google for secret sharing or secret splitting. ... Looking at Shamir's scheme, I'm surprised I didn't come up with this ... I've been reading up on secret sharing since I posted this ...
    (Bugtraq)