密码学之BGN同态加密算法
BGN同态加密算法:
BGN是⼀种同态加密⽅案,是Bonel h等⼈在2005提出的⼀种具有全同态性质的加密⽅案。和传统的仅能⽀持单同态的elgamal和paillier加密⽅案不⼀样,BGN能够同时⽀持加同态和⼀次乘同态运算。
由于乘法同态的实现是通过双线性对性质实现的,所以仅仅只能实现⼀次的乘同态。
BGN⼀般的加密⽅案如下:
BGN在JAVA中的实现:
BGN的实现主要使⽤JAVA中的⼤整数math.BigInteger类以及双线性库JPBC实现,具体代码如下:
package BGN;
import java.math.BigInteger;
import java.curity.SecureRandom;
import it.unisa.dia.gas.jpbc.Element;
import it.unisa.dia.gas.jpbc.Field;
import it.unisa.dia.gas.jpbc.PairingParameters;
import it.unisa.dia.gas.plaf.jpbc.pairing.a1.TypeA1CurveGenerator;
import it.unisa.dia.gas.plaf.jpbc.pairing.a1.TypeA1Pairing;
import it.unisa.dia.gas.plaf.jpbc.util.math.BigIntegerUtils;
public class BGNEncryption {
public static final String start = "start";
public static final String end = "end";
private PairingParameters param;
private BigInteger r;
private BigInteger q; // This is the private key.
private BigInteger order;
private SecureRandom rng;
public PublicKey gen(int bits) {
rng = new SecureRandom();
TypeA1CurveGenerator a1 = new TypeA1CurveGenerator(rng, 2, bits);
param = a1.generate();
TypeA1Pairing pairing = new TypeA1Pairing(param);
order = BigInteger("n");
r = BigInteger("n0");
q = BigInteger("n1");
Field f = G1();
Element P = f.newRandomElement();
P = P.BigInteger("l"));
Element Q = f.newElement();
Q = Q.t(P);
Q = Q.mul(r);
return new PublicKey(pairing, P, Q, order);
}
public Element encrypt(PublicKey PK, int msg) {
BigInteger t = N());
int m = msg;
// System.out.println("Hash is " + m);
Field f = PK.getField();
Element A = f.newElement();
Element B = f.newElement();
Element C = f.newElement();
A = A.P());
A = A.mul(BigInteger.valueOf(m));
B = B.Q());
B = B.mul(t);
C = C.t(A);
C = C.add(B);
return C;
}
public Element add(PublicKey PK, Element A, Element B) {
BigInteger t = N());
Field f = PK.getField();
Element output = f.newElement();
Element aux = f.newElement();
aux.Q());
aux.mul(t);
output.t(A);
output.add(B);
output.add(aux);
return output;
}
public Element mul(PublicKey PK, Element C, Element D) {
BigInteger t = N());
// double t1 = System.currentTimeMillis();
Element T = PK.doPairing(C, D);
// double t2 = System.currentTimeMillis();
// System.out.println("⼀次对运算操作的时间"+(t2-t1)+"ms");
Element K = PK.Q(), PK.getQ());
K = K.pow(t);
return T.mul(K);
}
public String decryptMul(PublicKey PK, BigInteger sk, Element C) { Element PSK = PK.P(), PK.getP());
PSK.pow(sk);
Element CSK = C.duplicate();
CSK.pow(sk);
Element aux = PSK.duplicate();
BigInteger m = new BigInteger("1");
while (!aux.isEqual(CSK)) {
aux = aux.mul(PSK);
m = m.add(BigInteger.valueOf(1));
}
String();
}
public String decrypt(PublicKey PK, BigInteger sk, Element C) {
Field f = PK.getField();
Element T = f.newElement();
Element K = f.newElement();
Element aux = f.newElement();
T = T.P());
T = T.mul(sk);
K = K.t(C);
K = K.mul(sk);
aux = aux.t(T);
BigInteger m = new BigInteger("1");
while (!aux.isEqual(K)) {
// This is a brute force implementation of finding the discrete
// logarithm.
/
/ Performance may be improved using algorithms such as Pollard's // Kangaroo.
aux = aux.add(T);
m = m.add(BigInteger.valueOf(1));
}
String();
}
public static void main(String[] args) {
BGNEncryption b = new BGNEncryption();
PublicKey PK = b.gen(256);
BigInteger f = PK.getN();
Element P = PK.getP();
Element Q = PK.getQ();
BigInteger order = PK.getN();
int len1 = P.getLengthInBytes();
int len2 = Q.getLengthInBytes();
int len3 = order.bitLength();
Element msg1 = b.encrypt(PK, 20);
int len = LengthInBytes();
Element msg2 = b.encrypt(PK, 25);
int len6 = LengthInBytes();
Element add = b.add(PK, msg1, msg2);
String jiemi = b.decrypt(PK, b.q, add);
System.out.println("Addition: "+jiemi);
int len4 = LengthInBytes();
// double t5 = System.currentTimeMillis();
Element mul = b.mul(PK, msg1, msg2);
// double t6 = System.currentTimeMillis();
// System.out.println("⼀次同态乘法的时间"+(t6-t5)+"ms");
System.out.println("Mul: " + b.decryptMul(PK, b.q, mul));
int len5 = LengthInBytes();
System.out.println("P的长度:"+len1);
System.out.println("Q的长度:"+len2);
System.out.println("阶为:"+len3);
System.out.println("msg1的长度:"+len);
System.out.println("加同态"+len4);
System.out.println("乘同态"+len5);
package BGN;
import it.unisa.dia.gas.jpbc.Element;
import it.unisa.dia.gas.jpbc.Field;
import it.unisa.dia.gas.plaf.jpbc.pairing.a1.TypeA1Pairing;
import java.math.BigInteger;
public class PublicKey {
private TypeA1Pairing map;
private Element P, Q;
private BigInteger n;
private Field f;
public PublicKey(TypeA1Pairing pairing, Element gen, Element point, BigInteger order) {
map = pairing;
P = gen.t(gen);
Q = point.t(point);
n = order;
f = G1();
}
public Element doPairing(Element A, Element B) {
return map.pairing(A, B);
}
public Element getP() {
return this.P;
}
public Element getQ() {
return this.Q;
}
public BigInteger getN() {
return this.n;
}
public Field getField() {
return this.f;
}
}
同态实验结果:
Addition: 45
Mul: 500
P的长度:130
Q的长度:130
阶为:512
msg1的长度:130
加同态130
乘同态130