Skip to main content

Questions tagged [multi-prime-rsa]

A variant of RSA where the modulus is the product of more than two primes.

Filter by
Sorted by
Tagged with
39 votes
1 answer
2k views

Who first published the interest of more than two prime factors in RSA?

Multi-prime RSA is now a well known technique (described here): it uses $k>2$ distinct secret prime factors in the public RSA modulus, with the advantage that, using the CRT, we can gain a speed ...
fgrieu's user avatar
  • 142k
17 votes
2 answers
12k views

RSA with modulus product of many primes

I would like to ask what happens if we build an RSA system with modulus a product of more than 2 primes, for example let $n=p_{1}p_{2}...p_{L}$. I know only the classical RSA system with $n=pq$ with $...
CryptoBeginner's user avatar
16 votes
2 answers
2k views

Why is pqRSA in the NIST PQC submissions?

In the NIST post-quantum cryptography workshop, the round one submissions included pqRSA. If memory serves, this is an implementation of RSA using the product of a very large number of 4096-bit primes ...
forest's user avatar
  • 15.3k
16 votes
2 answers
4k views

Multiple-prime RSA; how many primes can I use, for a 2048-bit modulus?

In standard RSA, the modulus $n=p_1 p_2$ is a product of two primes $p_1,p_2$ of the same size. Suppose we construct the modulus as a product of multiple primes $p_1,\dots,p_k$, i.e., $n=p_1 p_2 \...
D.W.'s user avatar
  • 36.5k
12 votes
1 answer
11k views

RSA with 3 primes

I was trying to understand how does RSA with 3 primes work. I have checked Wikipedia but yet I didn’t fully understand their solution. I would like to know how do you encrypt for $n=p*q*r$ How do you ...
Jeremy Shiklov's user avatar
9 votes
1 answer
6k views

RSA encryption and decryption with multiple prime modulus using CRT

Every information I found on internet about RSA-CRT encryption/decryption uses only two primes. I'm interested in my project in doing that using multiple (up to 8) primes. The general idea is to ...
tomQrsd's user avatar
  • 93
7 votes
2 answers
5k views

Are there any standards of multi-prime RSA key generation?

FIPS 186-3 specifies a method to generate DSA parameters. Is there anything similar (official standard or widely-accepted recommendation) that shows how to generate the primes for multi-prime RSA?
chouki's user avatar
  • 71
6 votes
4 answers
1k views

Subverting the key generation step in RSA public key cryptography

I am interested in the ways an RSA key generation implementation can or cannot be subverted so that the subverter has an advantage, but the owner of the key, and the people who interact with the owner,...
Pascal Cuoq's user avatar
5 votes
4 answers
6k views

RSA with composite numbers

It has been said that RSA uses a modulus product of two prime numbers for security reasons. But does RSA even work correctly if we allow composite integers instead? I think that the answer is "NO". ...
Aria's user avatar
  • 711
5 votes
2 answers
2k views

Does any proof exist for the optimal number of primes in a RSA key?

My guess is: Known attack algorithms only work on 2 primes factorization, they don't work on 3+ RSA primes. More than 3 primes is cpu waste time, better is to increase key length. So 3 primes will be ...
alainalain's user avatar
4 votes
2 answers
4k views

What is multi-prime RSA (RSA-MP)?

I found some related question but no real explanation of what it is and when and why to use it. What are the benefits and downsides and is it recommended?
Erwin's user avatar
  • 253
2 votes
1 answer
2k views

Decrypting Multi-Prime RSA with e, N, and factors of N given

I was wondering if there was any way to compute the private key $d$ when knowing only $e$ and $N$, and being able to factor $N$ as 4 prime numbers $p, q, r$ and $s$. I've been searching for days and I ...
Dominic's user avatar
  • 21
2 votes
1 answer
507 views

what are multi-primes and how are they different from semiprimes?

I came to know of semiprimes recently. The simplest explanation of semiprimes is you take any two prime numbers and you multiply them, say 3*11 = 33 in which case 33 would be a semiprime. The numbers ...
shirish's user avatar
  • 121
2 votes
1 answer
505 views

RSA: exploiting consecutive primes

It's given 2 plaintexts $m_1$ and $m_2$, and 5 different values of $n\quad\{n_1, n_2, n_3, n_4, n_5\}$ which are generated as follows: $n_1$ is a a product of two relatively small 128-bit $p$ and $q$ ...
Alden Luthfi's user avatar
2 votes
1 answer
122 views

Can multi-prime RSA be used to create an abuse-resistant lawful interception mechanism?

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 ...
wjv3's user avatar
  • 21
2 votes
0 answers
423 views

Chinese Remainder Theorem and Elgamal

I am studying an encryption scheme which is Elgamal-like where I think CRT can help optimise the encryption and decryption but I am not sure if I am applying CRT the correct way. I have a cyclic ...
Papa Delta's user avatar
1 vote
1 answer
118 views

Why are the primes all the same size in pqRSA?

pqRSA is MP-RSA with 4096-bit primes to build up a modulus of up to 1TB. If the objective is to make processing the modulus as expensive as possible for the quantum computer why not use just two 4096-...
user avatar
1 vote
0 answers
141 views

Lower bound for the size of prime factors?

We all know classic RSA and that we should pick moduli of at least 2048-bit length to get decent (112 bit) security. Now there's also multi-prime RSA, which can yield significant speed-ups using the ...
SEJPM's user avatar
  • 46.1k
0 votes
1 answer
246 views

Of what use is my code for finding prime numbers of a certain size? [closed]

I've developed a bit of Mathematica code that can find primes within a range of numbers. For example, if I wanted all the primes between one million and two million, it could do that. Of what use is ...
user24719's user avatar
0 votes
1 answer
193 views

Can we do Multi-Prime Diffie-Hellman?

What is the correct way, if any, to do Multi-Prime DH? From security point of view, is there any benefit to do it? Multi-Prime is not about multi participants. Multi prime is when we use two or more ...
Mendi Barel's user avatar
0 votes
1 answer
368 views

Plain RSA with $3$ primes, find all integers $x$ so that $x$ is equal to $y$ when $y= e_K(x) = x^{b} \bmod n$

I'm using the notation from the book: Cryptography: Theory and Practice, Third Edition. I have a cryptosystem with the following information: $n = p_1 p_2 p_3$ and integer $x$ is encrypted using $y = ...
Asaf's user avatar
  • 1