A prime number is an integer greater than 1 with no divisors other than itself and 1. Primes and prime products play an important role in public key cryptography.
21
votes
4answers
6k views
How can I generate large prime numbers for RSA?
What is the currently industry-standard algorithm used to generate large prime numbers to be used in RSA encryption?
I'm aware that I can find any number of articles on the Internet that explain how ...
13
votes
4answers
545 views
Is Wiener's attack on RSA extendable to larger keys with low hamming weight?
Using small private exponents with RSA improves performance.
However, it has been shown (Wiener, 1990) that if $\log d \leq \frac14 \log N$, the private exponent $d$ can be reconstructed from the ...
8
votes
5answers
422 views
Is it feasible to build an index of prime factors?
Would it be possible to break an RSA key, in for example 1 week of time, if the cracker have already spent X number of years building an index of primes by performing every permutation of existing ...
17
votes
2answers
825 views
How are primes generated for RSA?
As I understand it, the RSA algorithm is based on finding two large primes (p and q) and multiplying them. The security aspect is based on the fact that it's difficult to factor it back into p and q. ...
10
votes
2answers
268 views
Are safe primes $p=2^k \pm s$ with $s$ small less recommandable than others as a discrete log modulus?
I take the definition of safe prime as: a prime $p$ is safe when $(p-1)/2$ is prime.
Safe primes of appropriate size are the standard choice for the modulus of cryptosystems related to the discrete ...
7
votes
2answers
483 views
Selecting a large random prime
Say I want a random 1024-bit prime $p$. The obviously-correct way to do this is select a random 1024-bit number and test its primality with the usual well-known tests.
But suppose instead that I do ...
8
votes
3answers
372 views
Is it reasonable to assure that p-1 and q-1 aren't smooth?
I came across the requirement that, in RSA, $p-1$ and $q-1$ shouldn't be smooth, shouldn't consist of lots of small factors. Therefore my question:
How complicated is it to check whether $p-1$ is ...
5
votes
1answer
278 views
Necessity for finite field arithmetic and the prime number p in Shamir's Secret Sharing Scheme
Shamir's original paper (PDF, 197kb) describing a threshold secret sharing scheme states:
To make this claim more precise, we use modular arithmetic instead of
real arithmetic. The set of ...
4
votes
1answer
115 views
In RSA, rationale for prime $p$ with $p-1$ having prime factor $u$ with $u-1$ having large prime factor?
In the 1978 RSA paper, it is recommended, among other things, to choose primes $p$ such that $(p-1)$ has a large prime factor $u$. This was motivated by Pollard's p-1 algorithm. Further, the authors ...
0
votes
1answer
219 views
What is the correct value for “certainty” in RSA key pair generation?
I'm creating an RSA key pair in Bouncy Castle and need to specify an int value for certainty. This Stack Overflow answer says it is a relative test for how prime the values are.
There is another ...
