1
$\begingroup$

Denote $\mathcal N_r=\{n\in\mathbb Z:\exists\mbox{ distinct equal bit primes }p_1,\dots,p_r:n=p_1p_2\dots p_{r-1}p_r\}$.

$\mathcal N_1$ refers to primes and $\mathcal N_2$ referes to balanced semiprimes used in $RSA$.

  1. Does $\mathcal N_{2^t}$ at $t\in\mathbb N_{>1}$ help beyond single user-single receiver secret channel establishment?

  2. Is there good references?

$\endgroup$
  • 1
    $\begingroup$ Does it help ... what, exactly? The question is not clear. $\endgroup$ – Gerry Myerson Aug 7 '18 at 22:44
  • $\begingroup$ @GerryMyerson Is there a multiparty protocol? In Diffie-Hellman extending to three party is straightforward. $\endgroup$ – 1.. Aug 8 '18 at 4:31
  • $\begingroup$ i don't know why answer below is getting upvote. This answer was pulled up from crypto.stackexchange.com/questions/11287/…. $\endgroup$ – 1.. Aug 8 '18 at 8:34
  • $\begingroup$ 'Having more than two prime factors is already supported by the PKCS#1 standard. This is called a "multiprime RSA" algorithm. On the plus size, this may offer some computational performance improvement via the Chinese Remainder Theorem. For instance, if you use a modulus with $k$ factors, the CRT speedup factor is about $k^2.$ However, using too small factors may weaken the modulus. $\endgroup$ – 1.. Aug 8 '18 at 8:35
  • $\begingroup$ The best known factorization algorithms depend only on the modulus unless the factors are small enough to enter the range feasible with Elliptic Curve Multiplication which has a cost which depends (mostly) on the size of the smallest factor. More generally, a batch RSA algorithm (not multiprime RSA) can be used to speed up batch processing of many RSA signatures at once in a server setting, with substantial speedups. The paper by Boneh and Scacham [here][1] describes these ideas. [1]: hovav.net/ucsd/dist/survey.pdf' $\endgroup$ – 1.. Aug 8 '18 at 8:35
4
$\begingroup$

Having more than two prime factors is already supported by the PKCS#1 standard. This is called a "multiprime RSA" algorithm.

On the plus size, this may offer some computational performance improvement via the Chinese Remainder Theorem. For instance, if you use a modulus with $k$ factors, the CRT speedup factor is about $k^2.$

However, using too small factors may weaken the modulus. The best known factorization algorithms depend only on the modulus unless the factors are small enough to enter the range feasible with Elliptic Curve Multiplication which has a cost which depends (mostly) on the size of the smallest factor.

More generally, a batch RSA algorithm (not multiprime RSA) can be used to speed up batch processing of many RSA signatures at once in a server setting, with substantial speedups. The paper by Boneh and Scacham here describes these ideas.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Problem here is whether it helps multiparty secret channel establishment. $\endgroup$ – 1.. Aug 8 '18 at 4:25
  • $\begingroup$ i don't know why this answer is getting upvote. This answer was pulled up from crypto.stackexchange.com/questions/11287/…. Even there is a typo 'size' should be 'side' (same typo in other answer). I do not know where batch RSA was taken from. It comes no close to answering the problem. At least post from where the answer was taken so people can follow up. $\endgroup$ – 1.. Aug 8 '18 at 8:39
  • $\begingroup$ If the answer doesn't come close to answering the question, it might be that the question is unclear. $\endgroup$ – Gerry Myerson Aug 8 '18 at 8:45
  • $\begingroup$ What is unclear here? It says 'help beyond single user-single receiver secret channel establishment?' (the context is clear $\mathcal N_2$ helps single user-single receiver channel establishment which has been known at least since $70$s as 'the RSA' algorithm). $\endgroup$ – 1.. Aug 8 '18 at 8:52

Your Answer

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

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