# Shamir Secret Sharing

Kasparov Patel

Ranch Hand

Posts: 40

Ulf Dittmer

Rancher

Posts: 42968

73

posted 2 years ago

One approach might be to apply the algorithm to each character in the text (the "S" in the description on the Wikipedia page). The problem with that is that each character would be encrypted with the same number, thus making it amenable to character analysis. You could combine every two characters into one number to alleviate that to some degree, although not completely.

posted 2 years ago

The 'secret' in Shamir's secret sharing is normally a key for use in some encryption algorithm such as AES. Having generated a key and created the shares one then encrypts the text using the key and passes out the shared key pieces together with the encrypted text.

Now one could actually directly share the cleartext treating it as one big number but to do that for for arbitrary length text would be computationally very expensive so for arbitrary length text one would break the text into a number of chunks and share each chunk. A few years ago someone published an implementation of this approach in the old Sun Java forum using a polynomial over GF256 allowing each chunk to be just 1 byte; this would seem to be what Ulf is alluding to and in it's minimal form is susceptible to frequency analysis.

The steps I use in my standard example for a K from N system to just share the key are -

1) Generate a random key (SecureRandom is good for this).

2) Encrypt the cleartext and generate the ciphertext using the random key (I use the AES).

3) Create a random prime number 'P' at least as big as the random key (BigInteger.probablePrime() is good for this).

4) Create a K-1 th order Lagrange polynomial over P taking (0, key) as one of the points and K-1 other random (x,y) points.

5) Create the N shares each as the triple (P, a random point over P, the Lagrange polynomial evaluated at the random point).

The N shares are then passed out to the N people who need to be able decrypt the ciphertext.

To recover the clear text, K of the N people who hold shares must get together and then

1) Regenerate the K-1 th order Lagrange polynomial from the K shares.

2) Evaluate the polynomial at zero to get the key.

3) Decrypt the ciphertext using the key.

Kasparov Patel wrote:

I am trying to do shamir secret sharing of a given text regardless of text length. It could be 20, 50 or 100 words long. Can any one explain me, how to supply text to shamir's secret?

The 'secret' in Shamir's secret sharing is normally a key for use in some encryption algorithm such as AES. Having generated a key and created the shares one then encrypts the text using the key and passes out the shared key pieces together with the encrypted text.

Now one could actually directly share the cleartext treating it as one big number but to do that for for arbitrary length text would be computationally very expensive so for arbitrary length text one would break the text into a number of chunks and share each chunk. A few years ago someone published an implementation of this approach in the old Sun Java forum using a polynomial over GF256 allowing each chunk to be just 1 byte; this would seem to be what Ulf is alluding to and in it's minimal form is susceptible to frequency analysis.

The steps I use in my standard example for a K from N system to just share the key are -

1) Generate a random key (SecureRandom is good for this).

2) Encrypt the cleartext and generate the ciphertext using the random key (I use the AES).

3) Create a random prime number 'P' at least as big as the random key (BigInteger.probablePrime() is good for this).

4) Create a K-1 th order Lagrange polynomial over P taking (0, key) as one of the points and K-1 other random (x,y) points.

5) Create the N shares each as the triple (P, a random point over P, the Lagrange polynomial evaluated at the random point).

The N shares are then passed out to the N people who need to be able decrypt the ciphertext.

To recover the clear text, K of the N people who hold shares must get together and then

1) Regenerate the K-1 th order Lagrange polynomial from the K shares.

2) Evaluate the polynomial at zero to get the key.

3) Decrypt the ciphertext using the key.

Kasparov Patel

Ranch Hand

Posts: 40

posted 2 years ago

Hello Friends,

Thanks for your reply. I do have some questions. I know I can convert string into byte array and using that value I can create share. But I am not getting how can I convert back from byte array to string to show original string?

Please help me.

Thanking You

Thanks for your reply. I do have some questions. I know I can convert string into byte array and using that value I can create share. But I am not getting how can I convert back from byte array to string to show original string?

Please help me.

Thanking You

Kasparov Patel

Ranch Hand

Posts: 40

posted 2 years ago

I have taken references from may places. Some of them are as follow:

1) http://www.youtube.com/watch?v=v6IvxnJHD-o

2) http://en.wikipedia.org/wiki/Shamir's_Secret_Sharing

3) http://www.cap-lore.com/code/shamir.c

It is up to you, whether you want to answer or not.

Thanking You,

1) http://www.youtube.com/watch?v=v6IvxnJHD-o

2) http://en.wikipedia.org/wiki/Shamir's_Secret_Sharing

3) http://www.cap-lore.com/code/shamir.c

It is up to you, whether you want to answer or not.

Thanking You,

posted 2 years ago

The code you have posted is very close to that posted in http://stackoverflow.com/questions/19327651/java-implementation-of-shamirs-secret-sharing and http://pastebin.com/fctu79Mj . Did you post these?

From my point of view it is actually up to you. I hate plagiarism especially in conjunction with university/college/school assignments.

I will give you a small amount of help at this time. You should junk that possibly plagiarised code because it is rubbish.

Kasparov Patel wrote:I have taken references from may places. Some of them are as follow:

1) http://www.youtube.com/watch?v=v6IvxnJHD-o

2) http://en.wikipedia.org/wiki/Shamir's_Secret_Sharing

3) http://www.cap-lore.com/code/shamir.c

The code you have posted is very close to that posted in http://stackoverflow.com/questions/19327651/java-implementation-of-shamirs-secret-sharing and http://pastebin.com/fctu79Mj . Did you post these?

It is up to you, whether you want to answer or not.

From my point of view it is actually up to you. I hate plagiarism especially in conjunction with university/college/school assignments.

I will give you a small amount of help at this time. You should junk that possibly plagiarised code because it is rubbish.

Kasparov Patel

Ranch Hand

Posts: 40

posted 2 years ago

Kasparov Patel wrote:Hello Friends,

Thanks for your reply. I do have some questions. I know I can convert string into byte array and using that value I can create share. But I am not getting how can I convert back from byte array to string to show original string?

Please help me.

Thanking You

Kasparov Patel

Ranch Hand

Posts: 40

posted 2 years ago

I find it interesting that you are using addition of the previous 'toAdd' ciphertext value to the current cleartext value to create Cipher Block Chaining (CBC) to circumvent frequency analysis. I'm not convinced that your implementation of this will create a decodable set of values from just K shares since all N shares seem to be needed in the same order they were generated in order to invert the CBC. I shall have to think about it.!

As far as creating a single string is concerned, a single 32 bit 'int' value of 'toAdd' cannot be converted (reversibly) to a single 16 bit 'char' value. Assuming that the value of 'primeNum' can be the largest prime value less than 2^31 you will need to represent each integer value of 'toAdd' as a number of characters. If you further require these to be printable then you will need to map the 32 bits a number at a time onto a printable set. One very easy approach to this is to convert the 32 bits in groups of 4 to 8 Hex characters.

As far as creating a single string is concerned, a single 32 bit 'int' value of 'toAdd' cannot be converted (reversibly) to a single 16 bit 'char' value. Assuming that the value of 'primeNum' can be the largest prime value less than 2^31 you will need to represent each integer value of 'toAdd' as a number of characters. If you further require these to be printable then you will need to map the 32 bits a number at a time onto a printable set. One very easy approach to this is to convert the 32 bits in groups of 4 to 8 Hex characters.

Kasparov Patel

Ranch Hand

Posts: 40

posted 2 years ago

Thanks for your quick reply. I think it is not CBC because first iteration of inner loop calculates toAdd = (toAdd + (coeff[0] * Math.power(0,0)) % primeNum ) % primeNum and

second time toAdd = (toAdd + (coeff[1] * Math.power(0,1)) % primeNum ) % primeNum. which is equivalent of F(x) = (a0 + a1x + a2x^2) mod p. Please find my full code as follow:

I have problem to generate 5 shared string. Somehow my code giving me 5 string length of 5 characters only. Could you please tell me how can I get string from an array of characters?

Richard Tookey wrote:I find it interesting that you are using addition of the previous 'toAdd' ciphertext value to the current cleartext value to create Cipher Block Chaining (CBC) to circumvent frequency analysis. I'm not convinced that your implementation of this will create a decodable set of values from just K shares since all N shares seem to be needed in the same order they were generated in order to invert the CBC. I shall have to think about it.!

Thanks for your quick reply. I think it is not CBC because first iteration of inner loop calculates toAdd = (toAdd + (coeff[0] * Math.power(0,0)) % primeNum ) % primeNum and

second time toAdd = (toAdd + (coeff[1] * Math.power(0,1)) % primeNum ) % primeNum. which is equivalent of F(x) = (a0 + a1x + a2x^2) mod p. Please find my full code as follow:

I have problem to generate 5 shared string. Somehow my code giving me 5 string length of 5 characters only. Could you please tell me how can I get string from an array of characters?

Kasparov Patel

Ranch Hand

Posts: 40

fernando moreno

Greenhorn

Posts: 1