Win a copy of Kotlin in Action this week in the Kotlin forum!
programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Shamir Secret Sharing

Kasparov Patel
Ranch Hand
Posts: 40
Hello Friends,

I am trying to do shamir secret sharing of a given text regardless of text length. Can any one explain me, how to supply text to shamir's secret?

Thanking You,

Ulf Dittmer
Rancher
Posts: 42972
73
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.

Richard Tookey
Bartender
Posts: 1166
17
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
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?

Thanking You

Richard Tookey
Bartender
Posts: 1166
17
Sorry but the vast majority of this this code is obviously 'borrowed' and until you indicate where you obtained it from and give appropriate credit I am unable to help any further.

Kasparov Patel
Ranch Hand
Posts: 40
I have taken references from may places. Some of them are as follow:

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,

Richard Tookey
Bartender
Posts: 1166
17
Kasparov Patel wrote:I have taken references from may places. Some of them are as follow:

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
Ok thanks.

Kasparov Patel
Ranch Hand
Posts: 40
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?

Thanking You

Kasparov Patel
Ranch Hand
Posts: 40
Hello Richard,

I have changed my code which is as follow:

I hope now it should not be any problem. I would appreciate if you could tell me that how can I generate string instead of each characters.

Thanking You,

Richard Tookey
Bartender
Posts: 1166
17
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.

Kasparov Patel
Ranch Hand
Posts: 40
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.!

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
Bartender
Posts: 1166
17
Since you seem to have ignored the part of my previous post about encoding the integer values as 4 hex characters I don't think I can help you (You cannot fit a 32 bit int value into a 16 bit char!)

P.S. I still don't understand your code in relation to Shamir's secret sharing.

Kasparov Patel
Ranch Hand
Posts: 40
• 1
Hello Richard,

Thanks for your reply. I got the solution by self. All I need to do is to create a loop where I am creating string.

Thanking You,

fernando moreno
Greenhorn
Posts: 1
Richar, i have the same problema but i cant resolve it can you post your last code

Richard Tookey
Bartender
Posts: 1166
17
fernando moreno wrote:Richar, i have the same problema but i cant resolve it can you post your last code

Sorry that is not how this forum works. You should post your code and we will try to help you fix any problems.

 With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.