shamiralgorithms.java

用java实现Shamir门限算法

//Test the ShamirAlgorithms from the 'How to Share a Secret'
import java.io.*;
import java.math.*;
import java.util.*;

public class ShamirAlgorithms
{  
        BigInteger iResult=new BigInteger(0,new Random());
	    static BigInteger numOfPlainData=new BigInteger(1023,new Random());
       static int numOfDataDivideInto;
  	   static	int numOfDataRecoverRequestLess; 
  	static int [] indexCompare=new int[numOfDataRecoverRequestLess];
        BigInteger [] ai=new BigInteger[numOfDataRecoverRequestLess];
        static BigInteger [] iData=new BigInteger[numOfDataDivideInto];
        BigInteger [] iKey=new BigInteger [numOfDataDivideInto];
        BigInteger [] resumeDataPieces=new BigInteger [numOfDataRecoverRequestLess];
        BigInteger [] resumeKeyPieces=new BigInteger [numOfDataRecoverRequestLess];
  		static BigInteger randomPrime=BigInteger.probablePrime(1024,new Random());   
            
  public static void main(String[] args)
	{   
	    //Date time1=new Date();
	    
	    //long test1;
	    //long test2;
	    
  		
        System.out.println("请输入分割秘密的碎片数量：");
        numOfDataDivideInto=MyInput.readInt();
	 	System.out.println("请输入恢复秘密的最少碎片数量：");
        numOfDataRecoverRequestLess=MyInput.readInt();
        System.out.println();
        System.out.println();
        
        System.out.println("所要保密的秘密明文数是 :"+ numOfPlainData);
        System.out.println();	
        System.out.println("秘密分割的碎片数量:"+ numOfDataDivideInto);
        System.out.println();	
        System.out.println("恢复秘密的最少碎片数量 :"+ numOfDataRecoverRequestLess);
        System.out.println();	
        System.out.println("随机产生的1024位大素数 :"+ randomPrime);
        System.out.println();
        System.out.println();
        
        ShamirAlgorithms  P1=new ShamirAlgorithms();
        P1.SetPieces();
        P1.Lagelas();
   }
        //Shamir算法中把一份明文分为n份
        void SetPieces()
        {
        ai[0]=numOfPlainData;
  	    for(int i=1;i<numOfDataRecoverRequestLess;i++)
  	      {
  	  	     ai[i]=new BigInteger(128,new Random());
  	      }
  	    /*for(int i=0;i<numOfDataRecoverRequestLess;i++)
  	      {
  	  	     System.out.println("The "+ i +"of ai is :"+ ai[i]);
  	      }       
   	    System.out.println();
        System.out.println();*/
   	    for(int i=0;i<numOfDataDivideInto;i++)
  	      {
  	      	iData[i]=new BigInteger(0,new Random());
  	      } 
  	      
  	    for(int i=0;i<numOfDataDivideInto;i++)
  	      {  
  	         BigInteger temp=new BigInteger(32,new Random());
  	         iKey[i]=temp;
  	         for(int j=1;j<numOfDataRecoverRequestLess;j++)
  	        {    
  	      	   iData[i]=iData[i].add(ai[j].multiply((temp.pow(j))));
   	         }
   	           iData[i]=iData[i].add(ai[0]);
   	           iData[i]=iData[i].mod(randomPrime);
          }
   	    for(int i=0;i<numOfDataDivideInto;i++)
   	    { int temp=i+1;
   	      System.out.println("第 "+ temp +"  份X是:"+ iKey[i]);
   	      System.out.println("第 "+ temp +"  份Y 是:"+ iData[i]);
   	      System.out.println();	
   	    } 
   	   
   	   
  	    for(int i=0;i<numOfDataRecoverRequestLess;i++)
  	      {
  	      	indexCompare[i]=0;
  	      } 

   	     for (int i=0; i<numOfDataRecoverRequestLess; ++i)
   	    { 
   	    	Random ran1=new Random();
   	    	int index=ran1.nextInt(numOfDataDivideInto);
   	    	indexCompare[i]=index;
   	    	for(int j=0;j<i;j++)
   	    	 {
   	    	 	if(index==indexCompare[j])
   	    	 	  i--;
   	    	 }
   	    	
         }
      
   	    for (int i=0; i<numOfDataRecoverRequestLess; ++i)
   	    {
   	        int index=indexCompare[i];
   	    	resumeDataPieces[i]=iData[index];
   	    	resumeKeyPieces[i]=iKey[index];
   	    	
   	    }
   	  }
       //拉格朗日插值法 
        void Lagelas()
        {
            BigInteger iTotalX =new BigInteger(0,new Random());
            BigInteger iMinusX =new BigInteger(0,new Random()); 
            iTotalX=iTotalX.valueOf(1);   
     
        for (int i=0; i<numOfDataRecoverRequestLess; ++i)
	               {
		            iTotalX = iTotalX.multiply(resumeKeyPieces[i]);
		            iTotalX=iTotalX.mod(randomPrime);
	               }
            
   	    for(int i=0;i<numOfDataRecoverRequestLess;i++)   
          {
           BigInteger iTotalMinusX=new BigInteger(1,new Random());
           iTotalMinusX=iTotalMinusX.valueOf(1) ; 
           for(int j=0;j<numOfDataRecoverRequestLess;j++)   
             {     
                    if(i!=j)
                    {
                    	iMinusX = resumeKeyPieces[j].subtract(resumeKeyPieces[i]);
                    	if(resumeKeyPieces[i].compareTo(resumeKeyPieces[j])<0)
				          {
					           iMinusX = randomPrime.add(iMinusX);		
				          }
				        iTotalMinusX = (iTotalMinusX.multiply(iMinusX)).mod(randomPrime);       
                     
                    }
              
             }       
       
           iTotalMinusX = (iTotalMinusX.multiply(resumeKeyPieces[i]));
           iTotalMinusX=iTotalMinusX.modInverse(randomPrime);
		   iResult =iResult.add(((resumeDataPieces[i].multiply(iTotalX)).mod(randomPrime)).multiply(iTotalMinusX)).mod(randomPrime); 
		   iResult =iResult.mod(randomPrime);
          }
       System.out.println("由"+numOfDataRecoverRequestLess+"份碎片恢复的秘密明文是 :"+ iResult); 
       
      
       System.out.println();
       
        for (int i=0; i<numOfDataRecoverRequestLess-1; ++i)
	               {
		            iTotalX = iTotalX.multiply(resumeKeyPieces[i]);
		            iTotalX=iTotalX.mod(randomPrime);
	               }
            
   	    for(int i=0;i<numOfDataRecoverRequestLess-1;i++)   
          {
           BigInteger iTotalMinusX=new BigInteger(1,new Random());
           iTotalMinusX=iTotalMinusX.valueOf(1) ; 
           for(int j=0;j<numOfDataRecoverRequestLess-1;j++)   
             {     
                    if(i!=j)
                    {
                    	iMinusX = resumeKeyPieces[j].subtract(resumeKeyPieces[i]);
                    	if(resumeKeyPieces[i].compareTo(resumeKeyPieces[j])<0)
				          {
					           iMinusX = randomPrime.add(iMinusX);		
				          }
				        iTotalMinusX = (iTotalMinusX.multiply(iMinusX)).mod(randomPrime);       
                     
                    }
              
             }       
       
           iTotalMinusX = (iTotalMinusX.multiply(resumeKeyPieces[i]));
           iTotalMinusX=iTotalMinusX.modInverse(randomPrime);
		   iResult =iResult.add(((resumeDataPieces[i].multiply(iTotalX)).mod(randomPrime)).multiply(iTotalMinusX)).mod(randomPrime); 
		   iResult =iResult.mod(randomPrime);
          }
       System.out.println("由少于"+numOfDataRecoverRequestLess+"份碎片产生的不确定的一个大数:"+ iResult); 
      }
 
}