Questions tagged [multi-prime-rsa]
A variant of RSA where the modulus is the product of more than two primes.
20
questions
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 ...
- 51
2
votes
1
answer
317
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$ ...
- 21
0
votes
1
answer
177
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 ...
- 103
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 ...
- 21
0
votes
1
answer
355
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 = ...
- 1
4
votes
2
answers
3k
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?
- 253
2
votes
0
answers
402
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 ...
- 263
13
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 ...
- 15.1k
11
votes
1
answer
10k
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 ...
- 117
1
vote
0
answers
140
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 ...
- 45.7k
2
votes
1
answer
120
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 ...
- 21
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 ...
- 93
0
votes
1
answer
243
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 ...
2
votes
1
answer
491
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 ...
- 121
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,...
- 169
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 \...
- 36.2k
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 ...
- 138k
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".
...
- 711
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 $...
- 355
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?
- 71