Linked Questions

80 votes
3 answers

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
32 votes
7 answers

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
  • 423
55 votes
2 answers

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
  • 143k
16 votes
2 answers

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

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
39 votes
1 answer

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
  • 143k
1 vote
2 answers

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
2 votes
2 answers

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,509
-3 votes
1 answer

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
2 votes
1 answer

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
0 votes
2 answers

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