如何在paillier密码系统中除2个数字？

Question

我使用 Paillier 密码系统加密了 2 个数字。当我想除以这些数字时，数字的加密值是大整数，该值是十进制数 例如：9的第一个加密值是12446486760457687016046 3的加密值为98647617673416817617，除法的结果很可能是十进制。在这种情况下，最终结果为 0，因为 paillier 将 bigInteger 作为参数。我该如何划分它们？

    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();
BigInteger o1 = (paillier.Encryption(new BigInteger("9")));
BigInteger o2 = (paillier.Encryption(new BigInteger("3")));
BigInteger od = o2.divide(o1);
System.out.println(paillier.Decryption(od));

Answer 1

正如我之前解释的，在密码学应用中，通常使用乘法逆元而不是除法。

在小学时，我学会了 9 除以 3：9 ÷ 3 = 3。稍后我了解到

乘以除数的倒数会做同样的事情：9 × ⅓ = 3。对于有理数， ⅓ 是 3 的 乘法逆元： 3 × ⅓ = 1 在模算术中，乘法逆元类似于倒数。假设我正在处理以 256 为模的数字。我想“除”3。如上所述，我可以使用“除数”的乘法逆元来完成此操作。 3 × 171 mod 256 = 1，所以 171 是 3 的乘法逆元。但是等等，9 × 171 = 1539。它不应该是 3 吗？哦，等等，我们忘记了我们正在计算模 256：1539 mod 256 = 3。

在您的示例中，您有两个可以用作模数的数字，

n

或

nsquare

。我相信，如果您

 研究一下，

您会发现在使用 Paillier 执行同态算术时应使用哪个。然后你可以使用 modInverse()

 函数来执行你的“减法”。

Paillier paillier = new Paillier();
BigInteger o1 = (paillier.Encryption(new BigInteger("9")));
BigInteger o2 = (paillier.Encryption(new BigInteger("3")));
BigInteger od = o1.multiply(o2.modInverse(???));
System.out.println(paillier.Decryption(od));

Answer 2

# !pip install lightphe
from lightphe import LightPHE
from lightphe.models.Ciphertext import Ciphertext

# build a multiplicatively homomorphic cryptosystem - RSA or ElGamal
cs = LightPHE(algorithm_name = "RSA")

# public modulo of the cryptosystem
modulo = cs.cs.modulo

# define plaintexts
m1 = 9
m2 = 3

# calculate ciphertexts
c1 = cs.encrypt(m1)
c2 = cs.encrypt(m2)

# perform homomorphic operation
# c1 / c2 = c1 * c2 ^ -1
c3_value = c1.value * pow(c2.value, -1, cs.cs.modulo)

# create a ciphertext object from its value
c3 = Ciphertext(
   algorithm_name = "RSA",
   keys = cs.cs.keys,
   value = c3_value,
)

assert cs.decrypt(c3) == m1 / m2