-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathelGamaImplementationThree.java
More file actions
155 lines (139 loc) · 5.76 KB
/
elGamaImplementationThree.java
File metadata and controls
155 lines (139 loc) · 5.76 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
/**
* Security of the elGamaImplementationThree algorithm depends on the difficulty of computing discrete logs
* in a large prime modulus
*
* - Theorem 1 : a in [Z/Z[p]] then a^(p-1) [p] = 1
* - Theorem 2 : the order of an element split the order group
*/
public final class elGamaImplementationThree { // TODO extends Cryptosystem
public static BigInteger TWO = new BigInteger("2");
/**
* Generate the public key and the secret key for the elGamaImplementationThree encryption.
*
* @param n key size
*/
public static List<List<BigInteger>> KeyGen(int n) {
// (a) take a random prime p with getPrime() function. p = 2 * p' + 1 with prime(p') = true
BigInteger p = getPrime(n, 40, new Random());
// (b) take a random element in [Z/Z[p]]* (p' order)
BigInteger g = randNum(p, new Random());
BigInteger pPrime = p.subtract(BigInteger.ONE).divide(elGamaImplementationThree.TWO);
while (!g.modPow(pPrime, p).equals(BigInteger.ONE)) {
if (g.modPow(pPrime.multiply(elGamaImplementationThree.TWO), p).equals(BigInteger.ONE))
g = g.modPow(TWO, p);
else
g = randNum(p, new Random());
}
// (c) take x random in [0, p' - 1]
BigInteger x = randNum(pPrime.subtract(BigInteger.ONE), new Random());
BigInteger h = g.modPow(x, p);
// secret key is (p, x) and public key is (p, g, h)
List<BigInteger> sk = new ArrayList<>(Arrays.asList(p, x));
List<BigInteger> pk = new ArrayList<>(Arrays.asList(p, g, h));
// [0] = pk, [1] = sk
return new ArrayList<>(Arrays.asList(pk, sk));
}
/**
* Encrypt elGamaImplementationThree
*
* @param (p,g,h) public key
* @param message message
*/
public static List<BigInteger> Encrypt(BigInteger p, BigInteger g, BigInteger h, BigInteger message) {
BigInteger pPrime = p.subtract(BigInteger.ONE).divide(elGamaImplementationThree.TWO);
// TODO [0, N -1] or [1, N-1] ?
BigInteger r = randNum(pPrime, new Random());
// encrypt couple (g^r, m * h^r)
return new ArrayList<>(Arrays.asList(g.modPow(r, p), message.multiply(h.modPow(r, p))));
}
/**
* Encrypt elGamaImplementationThree homomorphe
*
* @param (p,g,h) public key
* @param message message
*/
public static List<BigInteger> Encrypt_Homomorph(BigInteger p, BigInteger g, BigInteger h, BigInteger message) {
BigInteger pPrime = p.subtract(BigInteger.ONE).divide(elGamaImplementationThree.TWO);
// TODO [0, N -1] or [1, N-1] ?
BigInteger r = randNum(pPrime, new Random());
// encrypt couple (g^r, h^r * g^m)
BigInteger hr = h.modPow(r, p);
BigInteger gm = g.modPow(message, p);
return new ArrayList<>(Arrays.asList(g.modPow(r, p), hr.multiply(gm)));
}
/**
* Decrypt elGamaImplementationThree
*
* @param (p,x) secret key
* @param (gr,mhr) (g^r, m * h^r)
* @return the decrypted message
*/
public static BigInteger Decrypt(BigInteger p, BigInteger x, BigInteger gr, BigInteger mhr) {
BigInteger hr = gr.modPow(x, p);
return mhr.multiply(hr.modInverse(p)).mod(p);
}
/**
* Decrypt elGamaImplementationThree homomorphe
* Remarque : il faudra quand même faire une recherche exhaustive de log discret (g^m)
* @param (p,x) secret key
* @param (gr,mhr) (g^r, h^r * g^m)
* @return the decrypted message
*/
public static BigInteger Decrypt_homomorphe(BigInteger p, BigInteger x, BigInteger g, BigInteger gr, BigInteger hrgm) {
BigInteger hr = gr.modPow(x,p);
BigInteger gm = hrgm.multiply(hr.modInverse(p)).mod(p);
BigInteger m = BigInteger.ONE;
BigInteger gm_prime = g.modPow(m, p);
while (!gm_prime.equals(gm)) {
m = m.add(BigInteger.ONE);
gm_prime = g.modPow(m, p);
}
return m;
}
/**
* Return a prime p = 2 * p' + 1
*
* @param nb_bits is the prime representation
* @param certainty probability to find a prime integer
* @param prg random
* @return p
*/
public static BigInteger getPrime(int nb_bits, int certainty, Random prg) {
BigInteger pPrime = new BigInteger(nb_bits, certainty, prg);
// p = 2 * pPrime + 1
BigInteger p = pPrime.multiply(TWO).add(BigInteger.ONE);
while (!p.isProbablePrime(certainty)) {
pPrime = new BigInteger(nb_bits, certainty, prg);
p = pPrime.multiply(TWO).add(BigInteger.ONE);
}
return p;
}
/**
* Return a random integer in [0, N - 1]
*
* @param N
* @param prg
* @return
*/
public static BigInteger randNum(BigInteger N, Random prg) {
return new BigInteger(N.bitLength() + 100, prg).mod(N);
}
public static void main(String[] args) {
List<List<BigInteger>> pksk = elGamaImplementationThree.KeyGen(200);
// public key
BigInteger p = pksk.get(0).get(0);
BigInteger g = pksk.get(0).get(1);
BigInteger h = pksk.get(0).get(2);
// secret key
BigInteger p_sk = pksk.get(1).get(0);
BigInteger x = pksk.get(1).get(1);
System.out.println("Message : 12");
List<BigInteger> encrypt = elGamaImplementationThree.Encrypt_Homomorph(p, g, h, new BigInteger("12"));
System.out.println("Decrypted : " + elGamaImplementationThree.Decrypt_homomorphe(p_sk, x, g, encrypt.get(0), encrypt.get(1)));
}
}