JAVA：算法：如何在加密值中执行减法运算
JAVA: Algorithms : How can i perform Subtraction Operation in Encrypted Values
我有一个Paillier同态算法的代码，其中乘法和加法在加密值中执行。
我需要以与加法[=]相同的方式实现减法和除法（至少是减法） 33=] 已实现（在加密值中运行），
我试过了，但没有得到预期的输出，
代码是 -
import java.math.*;
import java.util.*;
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 = p.multiply(q);
nsquare = n.multiply(n);
g = new BigInteger("2");
lambda = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE)).divide(
p.subtract(BigInteger.ONE).gcd(q.subtract(BigInteger.ONE)));
/* check whether g is good.*/
if (g.modPow(lambda, nsquare).subtract(BigInteger.ONE).divide(n).gcd(n).intValue() != 1) {
System.out.println("g is not good. Choose g again.");
System.exit(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 g.modPow(m, nsquare).multiply(r.modPow(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 g.modPow(m, nsquare).multiply(r.modPow(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 = g.modPow(lambda, nsquare).subtract(BigInteger.ONE).divide(n).modInverse(n);
return c.modPow(lambda, nsquare).subtract(BigInteger.ONE).divide(n).multiply(u).mod(n);
}
/**
* 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 = paillier.Encryption(m1);
BigInteger em2 = paillier.Encryption(m2);
/* printout encrypted text*/
System.out.println("En Result1="+em1);
System.out.println("En Result2="+em2);
/* printout decrypted text */
System.out.println("Dec Result1="+paillier.Decryption(em1).toString());
System.out.println("Dec Result2="+paillier.Decryption(em2).toString());
/* test homomorphic properties -> D(E(m1)*E(m2) mod n^2) = (m1 + m2) mod n */
BigInteger product_em1em2 = em1.multiply(em2).mod(paillier.nsquare);
BigInteger sum_m1m2 = m1.add(m2).mod(paillier.n);
System.out.println("original sum: " + sum_m1m2.toString());
System.out.println("decrypted sum: " + paillier.Decryption(product_em1em2).toString());
/* test homomorphic properties -> D(E(m1)^m2 mod n^2) = (m1*m2) mod n */
BigInteger expo_em1m2 = em1.modPow(m2, paillier.nsquare);
BigInteger prod_m1m2 = m1.multiply(m2).mod(paillier.n);
System.out.println("original product: " + prod_m1m2.toString());
System.out.println("decrypted product: " + paillier.Decryption(expo_em1m2).toString());
}
}
我的尝试是这样的
BigInteger sub_m1m2 = em1.subtract(em2).mod(paillier.nsquare);
System.out.println("original result: " + sub_m1m2.toString());
System.out.println("decrypted result: " + paillier.Decryption(sub_m1m2).toString());
但是我得到了输出
original result: 10293905733728092798312442334016670915623579115754799359001594575265037444846358865955447355482410894470382250544497599054315984048041610855086875271446876264557306222798287261349828881510552405863659535527193007559975944762965701441522047569562634431616852659521060136138153805278432999456874447872696991987
decrypted result: 5329364443144332451351943891466568608903938067239264159825694002586308632766687575085696305071770727742308734013289113539866112418155659162072887614141015
Expected output
-40
至少给我正确逻辑的方法。
谢谢
使用 javascript 的 Pallier 密码系统的非常棒的演示。
我将此演示用于减法作为一种加法 - A + (-B) 。只要 |A| 就有效大于 |B|。当 |B| 时，它给了我一个看似加密的数字更大。
另一个link虽然没有给出明确的答案或算法
加密值的减法
我得到了逻辑 A + (-B)
的部分答案
例如：-
BigInteger m1 = new BigInteger("200");
BigInteger m2 = new BigInteger("-100");
BigInteger em1 = paillier.Encryption(m1);
BigInteger em2 = paillier.Encryption(m2);
BigInteger product_em1em2 = em1.multiply(em2).mod(paillier.nsquare);
System.out.println("decrypted Result: " + paillier.Decryption(product_em1em2).toString());
你得到的输出
decrypted Result:100
逻辑上的问题是如果B > A，那么你会得到一个错误的结果，如
8731467600700263693874424644022096065561525426062533141985672767376667419304955165494349828630814277855336552046469491700406386664031693931688991036643291
这是mod元运算，答案居然是modn。如果你想要在这种情况下签名的答案，你可以通过 result-n if b > a 来获得它。完整示例，
a=100, b=200
a-b = a + (-b)
public n: 189073144844662281547025573708278983341
private lambda: 94536572422331140759761643656524564142
[A] = 14186854275058373459357566990685202758595128512711002543934861918137101534797
[B] = 27267516796978636717778486386991056397778775888737369113501780748148589365346
[A + B] = 23137393292983120368330149560489233461976816700037321139211632742863926737409
res = 189073144844662281547025573708278983241
res - n = -100
我有一个Paillier同态算法的代码，其中乘法和加法在加密值中执行。
我需要以与加法[=]相同的方式实现减法和除法（至少是减法） 33=] 已实现（在加密值中运行），
我试过了，但没有得到预期的输出，
代码是 -
import java.math.*;
import java.util.*;
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 = p.multiply(q);
nsquare = n.multiply(n);
g = new BigInteger("2");
lambda = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE)).divide(
p.subtract(BigInteger.ONE).gcd(q.subtract(BigInteger.ONE)));
/* check whether g is good.*/
if (g.modPow(lambda, nsquare).subtract(BigInteger.ONE).divide(n).gcd(n).intValue() != 1) {
System.out.println("g is not good. Choose g again.");
System.exit(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 g.modPow(m, nsquare).multiply(r.modPow(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 g.modPow(m, nsquare).multiply(r.modPow(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 = g.modPow(lambda, nsquare).subtract(BigInteger.ONE).divide(n).modInverse(n);
return c.modPow(lambda, nsquare).subtract(BigInteger.ONE).divide(n).multiply(u).mod(n);
}
/**
* 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 = paillier.Encryption(m1);
BigInteger em2 = paillier.Encryption(m2);
/* printout encrypted text*/
System.out.println("En Result1="+em1);
System.out.println("En Result2="+em2);
/* printout decrypted text */
System.out.println("Dec Result1="+paillier.Decryption(em1).toString());
System.out.println("Dec Result2="+paillier.Decryption(em2).toString());
/* test homomorphic properties -> D(E(m1)*E(m2) mod n^2) = (m1 + m2) mod n */
BigInteger product_em1em2 = em1.multiply(em2).mod(paillier.nsquare);
BigInteger sum_m1m2 = m1.add(m2).mod(paillier.n);
System.out.println("original sum: " + sum_m1m2.toString());
System.out.println("decrypted sum: " + paillier.Decryption(product_em1em2).toString());
/* test homomorphic properties -> D(E(m1)^m2 mod n^2) = (m1*m2) mod n */
BigInteger expo_em1m2 = em1.modPow(m2, paillier.nsquare);
BigInteger prod_m1m2 = m1.multiply(m2).mod(paillier.n);
System.out.println("original product: " + prod_m1m2.toString());
System.out.println("decrypted product: " + paillier.Decryption(expo_em1m2).toString());
}
}
我的尝试是这样的
BigInteger sub_m1m2 = em1.subtract(em2).mod(paillier.nsquare);
System.out.println("original result: " + sub_m1m2.toString());
System.out.println("decrypted result: " + paillier.Decryption(sub_m1m2).toString());
但是我得到了输出
original result: 10293905733728092798312442334016670915623579115754799359001594575265037444846358865955447355482410894470382250544497599054315984048041610855086875271446876264557306222798287261349828881510552405863659535527193007559975944762965701441522047569562634431616852659521060136138153805278432999456874447872696991987
decrypted result: 5329364443144332451351943891466568608903938067239264159825694002586308632766687575085696305071770727742308734013289113539866112418155659162072887614141015
Expected output
-40
至少给我正确逻辑的方法。 谢谢
使用 javascript 的 Pallier 密码系统的非常棒的演示。
我将此演示用于减法作为一种加法 - A + (-B) 。只要 |A| 就有效大于 |B|。当 |B| 时，它给了我一个看似加密的数字更大。
另一个link虽然没有给出明确的答案或算法
加密值的减法
我得到了逻辑 A + (-B)
的部分答案例如：-
BigInteger m1 = new BigInteger("200");
BigInteger m2 = new BigInteger("-100");
BigInteger em1 = paillier.Encryption(m1);
BigInteger em2 = paillier.Encryption(m2);
BigInteger product_em1em2 = em1.multiply(em2).mod(paillier.nsquare);
System.out.println("decrypted Result: " + paillier.Decryption(product_em1em2).toString());
你得到的输出
decrypted Result:100
逻辑上的问题是如果B > A，那么你会得到一个错误的结果，如
8731467600700263693874424644022096065561525426062533141985672767376667419304955165494349828630814277855336552046469491700406386664031693931688991036643291
这是mod元运算，答案居然是modn。如果你想要在这种情况下签名的答案，你可以通过 result-n if b > a 来获得它。完整示例，
a=100, b=200
a-b = a + (-b)
public n: 189073144844662281547025573708278983341
private lambda: 94536572422331140759761643656524564142
[A] = 14186854275058373459357566990685202758595128512711002543934861918137101534797
[B] = 27267516796978636717778486386991056397778775888737369113501780748148589365346
[A + B] = 23137393292983120368330149560489233461976816700037321139211632742863926737409
res = 189073144844662281547025573708278983241
res - n = -100