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
0
votes
0answers
37 views

Should I proceed with this for my project? Is it correct?

We have: Select five Prime numbers $p$, $q$, $r$, $s$ and $t$ Compute $n=p*q*r*s*t$ Calculate $Φ(n)=(p-1)(q-1)(r-1)(s-1)(t-1)$ Collect $e$ such that $p < e < Φ(n) … Φ(n)$ and $n$ are co-prime ...
0
votes
0answers
26 views

There are 3 factors in RSA [duplicate]

A Variant RSA. $n$ has 3 factors $p,q,r$. $\gcd(e,\phi(n))=1$, can decrypt it like normal RSA,or should use chinese remainder theory to decrypt it?
2
votes
1answer
222 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 ...
0
votes
1answer
90 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
vote
1answer
248 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?
2
votes
0answers
202 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 ...
9
votes
2answers
850 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 ...
8
votes
1answer
4k 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
102 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
80 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 ...
9
votes
1answer
3k 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
215 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
327 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 \...
28
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
4k 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". ...
16
votes
2answers
8k 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 $...
7
votes
2answers
4k 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?