Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [multi-prime-rsa]

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

0
votes
0answers
55 views

Advantages and disadvantages of multiprime RSA [duplicate]

What if in RSA $N = pqr$ except $N = pq$? I know that this will also work. But what exactly are the advantages and the disadvantages of this? Could you give me at least one of each?
2
votes
0answers
75 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 ...
6
votes
2answers
300 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 ...
0
votes
0answers
117 views

Rsa factoring best method and time

I am going to participate in a local challenge where you have to guess the two prime numbers(p and q), they give you a 8 bits number, 16 bits number..., 128 bits number... , 512,1024,2048... and wins ...
6
votes
1answer
3k 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 ...
1
vote
0answers
79 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 ...
2
votes
1answer
59 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 ...
8
votes
1answer
2k views

RSA enc/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 ...
0
votes
1answer
203 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
1answer
270 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 ...
6
votes
4answers
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,...
14
votes
2answers
3k 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 \...
25
votes
0answers
1k 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 ...
3
votes
4answers
3k 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". ...
12
votes
2answers
6k 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 $...
5
votes
2answers
3k 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?