I've seen a few implementations of Paillier cryptosystem that uses probable primes to choose $p$ and $q$.

Assuming that a keypair is generated with $p$ and $q$ that are coprime and that $pq$ is coprime with $(p - 1)(q - 1)$, but either $p$ or $q$ is composite, I'm wondering what security issues afflict such a key.

For example I wonder if, when $p$ is prime but $q$ is composite (so that $q = xy$ with $x$ and $y$ primes), there exists multiple public keys that can encrypt/decrypt a message.

Moreover, I'm wondering how it impacts $g$ and $r$ selection, and if the encryption function is still additively homomorphic. For example, with proper primes, one can use $r$ calculation to prove the sender of an encrypted message his control over the private key without sending the encrypted value over the channel. But is this still true for any $r$ if $p$ or $q$ are not truly primes?

Finally, which kind of cryptographic attacks are excluded by proper prime selection?

I've found a very nice mathematical introduction to the Paillier cryptosystem, but it assumes that $p$ and $q$ are primes from the very beginning.

NOTE: this is a cross-post from Crypto.SE, but since I've received no answer, I've been said to try here. In a somewhat related question, it is said (for RSA) that

If we accidentally try to perform RSA with one of p or q composite (because an error crept in the implementation of the primality test), the usual formulas φ(p⋅q)=(p−1)⋅(q−1) or λ(p⋅q)=lcm(p−1,q−1) will lead to incorrect value, and with overwhelming odds, decryption or signature verification will fail on the first real use (assuming non-malicious choice of p and q, and a random message or proper padding is used).

But what I'm wondering is actually how a malicious choice of $p$, $q$ (and $r$) could enable an attacker to obtain the same encryption for different messages.

  • $\begingroup$ A similar problem happens here as does for RSA. For almost all messages, the decryption process does not succeed in decrypting the message. This is a problem of the public key owner, which is the person receiving the message. I suppose it would be humorous sending the poor unsuspecting public key owner garbage messages that he or she has no hope of decrypting. $\endgroup$ – davidlowryduda Jul 17 '15 at 13:31
  • $\begingroup$ @mixedmath You are just considering a two-party system. Public Key encryption can be also used to prove a third party that a message has been received. If the sender signed somehow the encrypted message, the malicious receiver could forge an alternative message and pretend that that the message sent was different. This is particularly true if the domain of the message is somewhat limited, so that the malicious owner of the public key could have forged it to make certain messages interchangeable. I'm wondering if this kind of attack is theoretically possible... $\endgroup$ – Giacomo Tesio Jul 17 '15 at 13:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.