3873d30a0c710749c645683a6938068247f6a7b8
[shamirs_secret_web_implementation.git] / 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(this.divident * q.divident,this.divisor * q.divisor);
37                 }
38                 
39                 public Quotient times(int m) throws InvalidParameterException{
40                         return new Quotient(this.divident * m,this.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 = 0;
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(256);
113                 System.out.println(secret);
114                 Vector<Share> shares = createSecrets(secret,6,3);               
115                 System.out.println(shares);
116                 
117                 shares.remove(1);
118                 shares.remove(2);
119                 shares.remove(3);
120                 System.out.println(shares);
121                 
122                 secret=reconstruct(shares);
123                 System.out.println(secret);
124         }
125 }