File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Security and the fly likes Shamir Secret Sharing Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Java 8 in Action this week in the Java 8 forum!
JavaRanch » Java Forums » Engineering » Security
Bookmark "Shamir Secret Sharing" Watch "Shamir Secret Sharing" New topic
Author

Shamir Secret Sharing

Kasparov Patel
Ranch Hand

Joined: Jan 23, 2012
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
Marshal

Joined: Mar 22, 2005
Posts: 39578
    
  27
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.


Ping & DNS - updated with new look and Ping home screen widget
Richard Tookey
Ranch Hand

Joined: Aug 27, 2012
Posts: 971
    
  10

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

Joined: Jan 23, 2012
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?



Please help me.

Thanking You
Richard Tookey
Ranch Hand

Joined: Aug 27, 2012
Posts: 971
    
  10

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

Joined: Jan 23, 2012
Posts: 40
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,
Richard Tookey
Ranch Hand

Joined: Aug 27, 2012
Posts: 971
    
  10

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

Joined: Jan 23, 2012
Posts: 40
Ok thanks.
Kasparov Patel
Ranch Hand

Joined: Jan 23, 2012
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?


Please help me.

Thanking You
Kasparov Patel
Ranch Hand

Joined: Jan 23, 2012
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
Ranch Hand

Joined: Aug 27, 2012
Posts: 971
    
  10

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

Joined: Jan 23, 2012
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.!


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
Ranch Hand

Joined: Aug 27, 2012
Posts: 971
    
  10

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

Joined: Jan 23, 2012
Posts: 40
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,

 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Shamir Secret Sharing
 
Similar Threads
SCWCD - 91%
Passed SCWCD with 97%
Passed parts II and III with 91%
Which superhero are you?
I bet, it would never occur to you...