2
$\begingroup$

New to site so this may have been asked before: Can multi-prime RSA, i.e. where N is product of three or more distinct primes, be used for secure communication while allowing distinct authoritative entities to decrypt the messages when under a proper court order to do so?

For instance, let $N=p\cdot q\cdot r$, let $(N,e)$ be the public key and let $(N,d)$ the private key as usual. But have the generating algorithm securely send $(N,e,p)$ to, say, the Supreme Court, $(N,e,q)$ to the Executive and $(N,e,r)$ to Congress. Then no one entity alone could decrypt, but any pair could. Can this or some variation work? Would this require that two-prime RSA be outlawed?

It is also known that multi-prime RSA has a narrower range of exponents vulnerable to the lattice-based reduction algorithm attack. See N. Ojha and S. Padhye "Cryptanalysis of Multi Prime RSA with Secret Key Greater than Public Key", IJNS, Jan. 2014.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

That sorts of works, but:

  • Whatever decrypts will need the full private key, and will be a potential single point of failure.
  • The system can be secure only if each of $pq$, $qr$, and $rp$ is wide enough to be hard to factor; so if you want to be as secure a 4096-bit RSA, you need a 6144-bit public modulus.
  • We can achieve the same functionality by using two-factors RSA (thus reducing the size of the public modulus at equivalent security), and Shamir's secret sharing for the private key (or the seed that was used to generate the private key, with the added bonus that the shared secrets can be short enough to be keyed-in).
  • We can achieve better functionality using two-factors RSA and a private/public key pair per entity, with each file encrypted with secret-key cryptography like AES and a random key, shared using Shamir's secret sharing, with the secret shares RSA-encrypted. That way, the number of autorities necessary to decipher, thresold... can be chosen on a per-file basis; and most importantly, the multiple private keys never need to be brought together.
Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks fgrieu. I will have to become informed about Shamir's secret sharing to understand your answer. Thanks for the reference. $\endgroup$
    – wjv3
    Commented Apr 22, 2016 at 16:21
  • 1
    $\begingroup$ The problem with using Shamir's secret sharing is that it may be nontrivial to prove to the three entities that the shares you've given them is actually the shares to the real private key, and not a random value. Yes, you could design a ZKP for that, but that's a fall-out with wjv3's suggestion; all you need to do is have (say) supreme's court factor have lsbits (001), the executive's factor have lsbits (011) and congresses factor have lsbits (101). They can then validate that they have correct and distinct factors by exchanging public information. $\endgroup$
    – poncho
    Commented Apr 22, 2016 at 16:57
  • $\begingroup$ @poncho: yes, using Shamir's secret sharing for the private key suffers form the problem you describe. I do not see that there's a similar issue with the last system that I propose. Sure, the shares could be meaningless, but there's a similar problem in the question's system: the RSA cryptogram could be gibberish, only trying (which requires rebuilding the private key) can tell. $\endgroup$
    – fgrieu ♦
    Commented Apr 22, 2016 at 21:57
  • $\begingroup$ Actually, with the submitter's system, if all three parties verify that the prime they were given was indeed prime, a factor of the modulus, of the expected size, and have the lsbits are the expected pattern (so all they must get different factors), and they verify with each other that they received the same modulus, then all three must jointly hold the complete factorization of that modulus. $\endgroup$
    – poncho
    Commented Apr 22, 2016 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.