This week's book giveaway is in the Clojure forum.
We're giving away four copies of Clojure in Action and have Amit Rathore and Francis Avila on-line!
See this thread for details.
Win a copy of Clojure in Action this week in the Clojure forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Shamir Secret Sharing

 
Kasparov Patel
Ranch Hand
Posts: 40
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 42966
73
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 1166
17
Java Linux Netbeans IDE
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Bartender
Pie
Posts: 1166
17
Java Linux Netbeans IDE
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Bartender
Pie
Posts: 1166
17
Java Linux Netbeans IDE
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ok thanks.
 
Kasparov Patel
Ranch Hand
Posts: 40
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 1166
17
Java Linux Netbeans IDE
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Bartender
Pie
Posts: 1166
17
Java Linux Netbeans IDE
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Richar, i have the same problema but i cant resolve it can you post your last code
 
Richard Tookey
Bartender
Pie
Posts: 1166
17
Java Linux Netbeans IDE
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
I agree. Here's the link: http://aspose.com/file-tools
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic