On the security of distributed multiprime RSA

Ivan Damgård, Gert Læssøe Mikkelsen*, Tue Skeltved

*Corresponding author for this work

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

1 Citation (Scopus)


Threshold RSA encryption and signing is a very useful tool to increase the security of the secret keys used. Key generation is, however, either done in a non-threshold way, or computationally inefficient protocols are used. This is not a big problem in a setup where one organization has a few high profile keys to secure, however, this does not scale well to systems with a lot of secret keys, like eID schemes where there exist one key pair per user, especially not if the we want the users’ personal devices like smart phones to participate in the threshold setup. In this paper we present novel approaches to distributed RSA key generation which are efficient enough to let smart phones participate. This is done by generating keys consisting of more than two primes instead of generating standard RSA keys. We present a 2-party protocol based on the ideas of [BH98] which produces a 3-prime modulo. We demonstrate that the protocol is efficient enough to be used in practical scenarios even from a mobile device which has not been demonstrated before. Then we show the first 2-party distributed multiprime RSA key generation protocol that are as efficient as standard centralized key generation, even if security against malicious adversaries is desired. Further, we show that RSA keys based on moduli with more than two prime factors and where part of the factorization is leaked to the adversary are useful in practice by showing that commonly used schemes such as PSS-RSA and OAEP-RSA is secure even if the adversary knows a partial factorization of the multiprime moduli. From all other parties the generated keys cannot be distinguished from standard RSA keys, which is very important as this make these protocols compatible with existing infrastructure and standards.

Original languageEnglish
Title of host publicationInformation Security and Cryptology - ICISC 2014 - 17th International Conference, Revised Selected Papers
EditorsJongsung Kim, Jooyoung Lee
Number of pages16
Publication date1 Jan 2014
ISBN (Electronic)9783319159423
Publication statusPublished - 1 Jan 2014
Event17th International Conference on Information Security and Cryptology, ICISC 2014 - Seoul, Korea, Republic of
Duration: 3 Dec 20145 Dec 2014


Conference17th International Conference on Information Security and Cryptology, ICISC 2014
Country/TerritoryKorea, Republic of
SponsorKorean Institute of Information Security and Cryptology
SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)


Dive into the research topics of 'On the security of distributed multiprime RSA'. Together they form a unique fingerprint.

Cite this