Shamir Secret Sharing Implementation Query


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, ...
  • 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? ...
  • 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, ...
  • 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 ...
  • 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 ...