Linked Questions

31 votes
7 answers
34k views

Why does RSA need p and q to be prime numbers?

Despite having read What makes RSA secure by using prime numbers?, I seek clarification because I am still struggling to really grasp the underlying concepts of RSA. Specifically, why can't we choose ...
sharly's user avatar
  • 413
79 votes
3 answers
58k views

Impacts of not using RSA exponent of 65537

This RFC says the RSA Exponent should be 65537. Why is that number recommended and what are the theoretical and practical impacts & risks of making that number higher or lower? What are the ...
makerofthings7's user avatar
55 votes
2 answers
9k views

What security authorities and standards reject $e=3$ in RSA, when, and with what rationale?

In RSA, some security authorities and/or standards allow the public exponent $e=3$, others require or recommend $e>2^{16}$ (or perhaps some other minimum). I gathered the following: PKCS#1 allows $...
fgrieu's user avatar
  • 140k
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.3k
2 votes
2 answers
288 views

How to handle modular arithmetic with regard to two's-complement negative numbers?

The reason for asking, is that this occurs in real life with CRT calculation of RSA decryption/signing. In CRT RSA, there's the need to calculate subtraction, and it's known negative numbers could ...
DannyNiu's user avatar
  • 9,080
1 vote
2 answers
3k views

In RSA, why would we ever want to find the values of p and q if we already know phi(n)?

I'm studying RSA for the first time, and I know that $p$ and $q$ must be kept secret because with them we can calculate $\phi(n)$, which then lets us calculate the private key $d$. So $p$, $q$, and $\...
Toomany Bees's user avatar
0 votes
2 answers
112 views

Will the value of the "version" fields always be 0 and the "NULL" fields always be "NULL" in PKCS#1, PKCS#8, and X.509/SPKI keys?

Consider the fields highlighted in red in the following keys. Will the "version" fields (i.e. INTEGER 0) always be zero for the specified structure? Will ...
ubiquibacon's user avatar
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
  • 140k
11 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
2 votes
1 answer
160 views

Paillier's scheme generalisation

Paillier's scheme assume has message and ciphertext space equal to $\mathbb{Z}_N$ with $N=pq$, that is $N$ is the product of two different primes. Is there a way to generalise this for $N$ that is ...
Bellali's user avatar
  • 21
-3 votes
1 answer
416 views

How to attack RSA with 13 primes

Could give me method to attack RSA when N decomposes into multiple primes And this is the topic N = ...
user58046's user avatar