同态加密算法简述
/**
* This program is free software: you can redistribute it and/or modify it
* under the terms of the GNU General Public License as published by the Free
* Software Foundation, either version 3 of the License, or (at your option)
* any later version.
*
* This program is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
* more details.
*
* You should have received a copy of the GNU General Public License along with
* this program. If not, see </licenses/>.
*/
import .*;
import .*;
/**
* Paillier Cryptosystem <br>
* <br>
* References: <br>
* [1] Pascal Paillier,
* "Public-Key Cryptosystems Based on Composite Degree Residuosity Classes,"
* EUROCRYPT'99. URL:
* <a href="/smart/rd/publications/pdf/">http:
* ///smart/rd/publications/pdf/</a><br>
*
* [2] Paillier cryptosystem from Wikipedia. URL:
* <a href="/wiki/Paillier_cryptosystem">http://en.
* /wiki/Paillier_cryptosystem</a>
*
* @author Kun Liu (kunliu1@)
* @version 1.0
*/
public class Paillier {
/**
* p and q are two large primes. lambda = lcm(p-1, q-1) =
* (p-1)*(q-1)/gcd(p-1, q-1).
*/
private BigInteger p, q, lambda;
/**
* n = p*q, where p and q are two large primes.
*/
public BigInteger n;
/**
* nsquare = n*n
*/
public BigInteger nsquare;
/**
* a random integer in Z*_{n^2} where gcd (L(g^lambda mod n^2), n) = 1.
*/
private BigInteger g;
/**
* number of bits of modulus
*/
private int bitLength;
/**
* Constructs an instance of the Paillier cryptosystem.
*
* @param bitLengthVal
* number of bits of modulus
* @param certainty
* The probability that the new BigInteger represents a prime
* number will exceed (1 - 2^(-certainty)). The execution time of
* this constructor is proportional to the value of this
* parameter.
*/
public Paillier(int bitLengthVal, int certainty) {
KeyGeneration(bitLengthVal, certainty);
}
/**
* Constructs an instance of the Paillier cryptosystem with 512 bits of
* modulus and at least 1-2^(-64) certainty of primes generation.
*/
public Paillier() {
KeyGeneration(512, 64);
}
/**
* Sets up the public key and private key.
*
* @param bitLengthVal
* number of bits of modulus.
* @param certainty
* The probability that the new BigInteger represents a prime
* number will exceed (1 - 2^(-certainty)). The execution time of
* this constructor is proportional to the value of this
* parameter.
*/
public void KeyGeneration(int bitLengthVal, int certainty) {
bitLength = bitLengthVal;
/*
* Constructs two randomly generated positive BigIntegers that are
* probably prime, with the specified bitLength and certainty.
*/
p = new BigInteger(bitLength / 2, certainty, new Random());
q = new BigInteger(bitLength / 2, certainty, new Random());
n = (q);
nsquare = (n);
g = new BigInteger("2");
lambda = ().multiply(())
.divide(().gcd(()));
/* check whether g is good. */
if ((lambda, nsquare).subtract().divide(n).gcd(n).intValue() != 1) {
("g is not good. Choose g again.");
(1);
}
}
/**
* Encrypts plaintext m. ciphertext c = g^m * r^n mod n^2. This function
* explicitly requires random input r to help with encryption.
*
* @param m
* plaintext as a BigInteger
* @param r
* random plaintext to help with encryption
* @return ciphertext as a BigInteger
*/
public BigInteger Encryption(BigInteger m, BigInteger r) {
return (m, nsquare).multiply((n, nsquare)).mod(nsquare);
}
/**
* Encrypts plaintext m. ciphertext c = g^m * r^n mod n^2. This function
* automatically generates random input r (to help with encryption).
*
* @param m
* plaintext as a BigInteger
* @return ciphertext as a BigInteger
*/
public BigInteger Encryption(BigInteger m) {
BigInteger r = new BigInteger(bitLength, new Random());
return (m, nsquare).multiply((n, nsquare)).mod(nsquare);
}
/**
* Decrypts ciphertext c. plaintext m = L(c^lambda mod n^2) * u mod n, where
* u = (L(g^lambda mod n^2))^(-1) mod n.
*
* @param c
* ciphertext as a BigInteger
* @return plaintext as a BigInteger
*/
public BigInteger Decryption(BigInteger c) {
BigInteger u = (lambda, nsquare).subtract().divide(n).modInverse(n);
return (lambda, nsquare).subtract().divide(n).multiply(u).mod(n);
}
/**
* sum of (cipher) em1 and em2
*
* @param em1
* @param em2
* @return
*/
public BigInteger cipher_add(BigInteger em1, BigInteger em2) {
return (em2).mod(nsquare);
}
/**
* main function
*
* @param str
* intput string
*/
public static void main(String[] str) {
/* instantiating an object of Paillier cryptosystem */
Paillier paillier = new Paillier();
/* instantiating two plaintext msgs */
BigInteger m1 = new BigInteger("20");
BigInteger m2 = new BigInteger("60");
/* encryption */
BigInteger em1 = (m1);
BigInteger em2 = (m2);
/* printout encrypted text */
(em1);
(em2);
/* printout decrypted text */
((em1).toString());
((em2).toString());
/*
* test homomorphic properties -> D(E(m1)*E(m2) mod n^2) = (m1 + m2) mod
* n
*/
// m1+m2,求明文数值的和
BigInteger sum_m1m2 = (m2).mod();
("original sum: " + sum_m1m2.toString());
// em1+em2，求密文数值的乘
BigInteger product_em1em2 = (em2).mod();
("encrypted sum: " + product_em1em2.toString());
("decrypted sum: " + (product_em1em2).toString());
/* test homomorphic properties -> D(E(m1)^m2 mod n^2) = (m1*m2) mod n */
// m1*m2,求明文数值的乘
BigInteger prod_m1m2 = (m2).mod();
("original product: " + prod_m1m2.toString());
// em1的m2次方，再mod
BigInteger expo_em1m2 = (m2, );
("encrypted product: " + expo_em1m2.toString());
("decrypted product: " + (expo_em1m2).toString());
//sum test
("--------------------------------");
Paillier p = new Paillier();
BigInteger t1 = new BigInteger("21");(());
BigInteger t2 = new BigInteger("50");(());
BigInteger t3 = new BigInteger("50");(());
BigInteger et1 = (t1);(());
BigInteger et2 = (t2);(());
BigInteger et3 = (t3);(());
BigInteger sum = new BigInteger("1");
sum = p.cipher_add(sum, et1);
sum = p.cipher_add(sum, et2);
sum = p.cipher_add(sum, et3);
("sum: "+());
("decrypted sum: "+(sum).toString());
("--------------------------------");
}
}