Shamir Secret Sharing

[Kasparov Patel]

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]

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]

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]

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?

import java.math.BigInteger;
import java.util.Random;


public class Main {
    public static void main(String[] args){

        //INIT
        int N = 5;
        int K = 3;
        try
        {
          String str = new String("Shamir Secret Sharing");
          byte[] a0 = str.getBytes("US-ASCII");
          BigInteger secret = new BigInteger(a0);
          modLength = secret.bitLength() + 1;
          BigInteger primeNum = genPrime();
          BigInteger[] coeff = new BigInteger[K-1];
          BigInteger[] partecipants = new BigInteger[K];
          for (int i=0;i<K;i++)
            partecipants[i] = new BigInteger(Integer.toString(i+1));
          System.out.println("Prime Number: "+primeNum);
          for (int i=0;i<K-1;i++){
            coeff[i] = randomZp(primeNum);
            System.out.println("a"+(i+1)+": "+coeff[i]);
          }
          
          //SHARES
          BigInteger[] shares = new BigInteger[N];
          for(int i=0;i<N;i++){
            BigInteger toAdd= secret;
            for(int j=0;j<K-1;j++){
              BigInteger power = new BigInteger(Integer.toString((int)(Math.pow((i+1),(j+1)))));
              toAdd=toAdd.add(coeff[j].multiply(power));  
            }
            shares[i] = toAdd.mod(primeNum);
            System.out.println("Share n."+(i+1)+": "+shares[i]);
          }
          //INTERPOLAZIONE
          BigInteger secret2= new BigInteger("0");
          double term;
          for (int i=0;i<K;i++){
            term = 1;
            BigInteger sharePartecipanteNow = shares[(partecipants[i].intValue())-1];
            for (int j=0;j<K;j++){
              if (partecipants[i].intValue()!=partecipants[j].intValue()){
                
                BigInteger num = new BigInteger(Integer.toString(partecipants[j].intValue()*(-1)));
                BigInteger den = new BigInteger(Integer.toString(partecipants[i].intValue()-partecipants[j].intValue()));
                term = term*(num.doubleValue())/(den.doubleValue());
              }
              
            }
            term = term*sharePartecipanteNow.intValue();
            secret2 = secret2.add(new BigInteger(Integer.toString((int)term)));
          }
          while(secret2.intValue()<0)
            secret2 = secret2.add(primeNum);
          BigInteger bi = secret2.mod(primeNum);
          a0 = bi.getBytes();
          String str2 = new String(a0);
          System.out.println("The secret is: "+str2);
        }
        catch(Exception e){
          System.out.println(e);
        }
    }

    /*private static String convert(byte[] data) 
    {
      StringBuilder sb = new StringBuilder(data.length);
      for (int i = 0; i < data.length; ++ i) {
        if (data[i] < 0) throw new IllegalArgumentException();
        sb.append((char) data[i]);
      }    
      return sb.toString();
    }*/
    private static BigInteger genPrime() { 
        BigInteger p=null; 
        boolean ok=false; 
        do{
            p=BigInteger.probablePrime(modLength, new Random()); 
            if(p.isProbablePrime(CERTAINTY)) 
                ok=true; 
        }while(ok==false); 
        return p; 
    }

    private static BigInteger randomZp(BigInteger p) { 
        BigInteger r; 
        do{
            r = new BigInteger(modLength, new Random()); 
        } while (r.compareTo(BigInteger.ZERO) < 0 || r.compareTo(p) >= 0); 
         return r; 
    }

    private static final int CERTAINTY = 50; 
    private static int modLength; 
}

Please help me.

Thanking You

[Richard Tookey]

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]

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]

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]

Ok thanks.

[Kasparov Patel]

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]

Hello Richard,

I have changed my code which is as follow:

          
          //Share code
          
          for(int i=0; i<a0.length; i++)
          {
            int toAdd= a0[i];
            for(int j=0; j<N; j++)
            {
              for(int k=0; k<K-1; k++)
              {                              
                toAdd = (int)(toAdd + (coeff[k] * (Math.pow(j,k) % primeNum) % primeNum)) % primeNum; // Modular math 
              }
              char c = (char)toAdd;
              System.out.println("Share n"+(j+1)+": "+c);
            }
          }
        }
        catch(Exception e){
          System.out.println(e);
        }
    }
}

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]

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]

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]

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]

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]

Richar, i have the same problema but i cant resolve it can you post your last code

[Richard Tookey]

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.