src/ShamirsSecret.java

   1 import java.security.InvalidParameterException;
   2 import java.util.Random;
   3 import java.util.Vector;
   4
   5 public class ShamirsSecret {
   6         private static Random rand = new Random();
   7         private static int prime = 257;
   8
   9         public static int ggT(int a, int b){
  10                 if (b<0) b=-b;
  11                 if (a==0) return b;
  12                 if (a<0) a=-a;
  13                 while (b != 0) if (a>b) a-=b; else b-=a;
  14                 return a;
  15         }
  16
  17
  18         public static class Quotient{
  19                 int divident;
  20                 int divisor;
  21
  22                 public Quotient(int i) {
  23                         this.divident=i;
  24                         this.divisor=1;
  25                 }
  26
  27                 public Quotient(int divident,int divisor) throws InvalidParameterException{
  28                         if (divisor == 0) throw new InvalidParameterException("Divisor of quotient must not be zero!");
  29                         int ggt = ggT(divident,divisor);
  30                         if (divisor<0) ggt = -ggt;
  31                         this.divident=divident/ggt;
  32                         this.divisor=divisor/ggt;
  33                 }
  34
  35                 public Quotient times(Quotient q) throws InvalidParameterException{
  36                         return new Quotient(divident * q.divident,divisor * q.divisor);
  37                 }
  38
  39                 public Quotient times(int f) throws InvalidParameterException{
  40                         return new Quotient(f*divident,divisor);
  41                 }
  42
  43                 @Override
  44                 public String toString() {
  45                         return (divisor == 1) ? ""+divident : "["+divident+"/"+divisor+"]";
  46                 }
  47
  48                 public int val() throws InvalidParameterException {
  49                         if (divisor != 1) throw new InvalidParameterException("Divisor should not be "+divisor);
  50                         return divident;
  51                 }
  52
  53                 public Quotient add(int i) throws InvalidParameterException{
  54                         return add(new Quotient(i));
  55                 }
  56
  57                 public Quotient add(Quotient q) throws InvalidParameterException {
  58                         return new Quotient(divident*q.divisor + divisor*q.divident,divisor*q.divisor);
  59                 }
  60
  61                 public int mod(int q) throws InvalidParameterException {
  62                         int inv = 1;
  63                         while ((divisor*inv)%q !=1)inv++; // search the inverse of the divisor
  64                         return (divident*inv)%q;
  65                 }
  66         }
  67
  68         public static class Share{
  69                 private int x,y;
  70
  71                 public Share(int x, int[] coefficients) {
  72                         this.x=x;
  73                         int sum=0;
  74                         for (int i=0; i<coefficients.length; i++) sum+=coefficients[i]*pow(x,i);
  75                         this.y=sum % prime;
  76                 }
  77
  78                 @Override
  79                 public String toString() {
  80                         return "Secret(x = "+x+", y = "+y+")";
  81                 }
  82         }
  83
  84         private static int pow(int x,int e){
  85                 return (e==0) ? 1 : x*pow(x,e-1);
  86         }
  87
  88         private static Vector<Share> createSecrets(int secret, int count, int requires) {
  89                 Vector<Share> result = new Vector<Share>();
  90
  91                 int [] coefficients = new int[requires];
  92                 coefficients[0] = secret;
  93                 for (int i=1; i<requires; i++) coefficients[i]=rand.nextInt(256);
  94                 for (int x=1; x<=count; x++) result.add(new Share(x, coefficients));
  95                 return result;
  96         }
  97
  98         private static int reconstruct(Vector<Share> shares) throws InvalidParameterException{
  99                 Quotient sum = new Quotient(0);
 100                 for (Share share_j:shares){
 101                         Quotient prod = new Quotient(1);
 102                         for (Share share_m:shares){
 103                                 if (share_j == share_m) continue;
 104                                 prod = prod.times(new Quotient(share_m.x,share_m.x-share_j.x));
 105                         }
 106                         sum = sum.add(prod.times(share_j.y));
 107                 }
 108                 return sum.mod(prime);
 109         }
 110
 111         public static void main(String[] args) throws InvalidParameterException {
 112                 int secret = rand.nextInt(255);
 113                 System.out.println(secret);
 114                 Vector<Share> shares = createSecrets(secret,5,3);
 115                 System.out.println(shares);
 116
 117                 shares.remove(0);
 118                 shares.remove(0);
 119                 System.out.println(shares);
 120
 121                 secret=reconstruct(shares);
 122                 System.out.println(secret);
 123         }
 124 }