Hot answers tagged prime-numbers
18
You don't use a pre-generated list of primes. That would make it easy to crack as you note. The algorithm you want to use would be something like this (see note 4.51 in HAC, see also an answer on crypto.SE):
Generate a random $512$ bit odd number, say $p$
Test to see if $p$ is prime; if it is, return $p$; this is expected to occur after testing about ...
14
The standard way to generate big prime numbers is to take a preselected random number of the desired length, apply a Fermat test (best with the base $2$ as it can be optimized for speed) and then to apply a certain number of Miller-Rabin tests (depending on the length and the allowed error rate like $2^{-100}$) to get a number which is very probably a prime ...
14
No, it is not at all feasible to build an index of prime factors to break RSA.
Even if we consider 384-bit RSA, which was in use but breakable two decades ago, the index would need to include a sizable portion of the 160 to 192-bit primes, so that the smallest factor of the modulus has a chance to be in the index. Per the Prime number theorem there are in ...
14
A Mersenne prime is a prime number that can be written in the form $M_p = 2^n-1$, and they’re extremely rare finds. Of all the numbers between 0 and $2^{25,964,951}-1$ there are 1,622,441 that are prime, but only 42 are Mersenne primes.
The second sentence is wrong.
What they meant to say is that there are 1,622,441 numbers of the form they mentioned ...
10
mpz_nextprime states in the documentation and source (file: mpz/nextprime.c) that it simply finds the next prime larger than the provided input. There are various methods of doing so (depending on how efficient it tries to be), but they should all produce the same answer. Looking at the code, mpz_nextprime first tests a number against a large quantity of ...
9
I have asked a similar question to Arjen Lenstra a few years ago: I was investigating three 2048-bit primes of low Hamming weight:
$p_1 = 2^{2048} - 2^{1056} + 2^{736} - 2^{320} + 2^{128} + 1$
$p_2 = 2^{2048} - 2^{1376} + 2^{992} + 2^{896} + 2^{640} - 1$
$p_3 = 2^{2048} - 2^{2016} + 2^{1984} - 2^{1856} - 2^{1824} + 2^{1792} - 2^{1760} + 2^{1696} + 2^{1664} ...
9
This procedure is known as incremental search and his described in the Handbook of Applied Cryptography (note 4.51, page 148). Although some primes are being selected with higher probability than others, this allows no known attacks on RSA; roughly speaking, incremental search selects primes which could have been selected anyway and there are still ...
9
Wiener's result has been improved several times, and it is hard to tell how big the private exponent must be to be safe from further progress.
Also, the proposed technique, assuming $d>n^{1/3}$, requires a minimum of ${1\over3}\cdot log_2(n)$ modular multiplications for the sparsest $d$ conceivable (a power of two), compared to say ${7\over6} \cdot ...
7
It has to do with optimizing RSA.
It turns out that using the Chinese Remainder Theorem with $p$, $q$, $d\pmod{p-1}$, and $d\pmod{q-1}$ (i.e., prime1, prime2, exponent1, exponent2 from the data structure in the question) to run the decryption operation faster than if you only had $d,n$.
For more information on how it is done, I found this reference ...
7
Well, to answer your questions in order:
How big should $p$ be? Well, it should be large enough to defend against the known attacks against it. The most efficient attack is NFS; that has been used against numbers on the order of $2^{768}$ (a 232 digit number). It would appear wise to pick a $p$ that's considerably bigger than that; around 1024 bits at a ...
7
The problem of generating prime numbers reduces to one of determining primality (rather than an algorithm specifically designed to generate primes) since primes are pretty common: π(n) ~ n/ln(n).
Probabilistic tests are used (e.g. in java.math.BigInteger.probablePrime()) rather than deterministic tests. See Miller-Rabin.
...
7
No, the fact that there's no known practical formula that produces only prime numbers doesn't really come into play; if someone found one tomorrow, that wouldn't have any cryptographical implications.
You may want to go through the How does asymmetric encryption work? thread; the short answer is that for public key operations, the public and the private ...
6
Checking for smoothness can be computationally expensive, depending on the size of the "small" primes (there is no "natural" definition of "small", one has to define an arbitrary limit). Also, it is not really useful.
The need for non-smooth integers comes from the $p-1$ factorization method. Let $n = pq$ be a RSA modulus that we wish to factor. Now suppose ...
6
For Diffie-Hellman or any variants like Elgamal or DSA, you're better off using the established primes. It doesn't matter what primes you use, really, as long as they're prime.
The standard primes have had someone nod at them. If you generate your own prime and there's a problem (e.g. it's not really prime), then you're on your own and we will all laugh at ...
6
Short answer: Yes.
The discrete logarithm can be attacked in a multitude of ways: Baby-step giant-step (BSGS), Pollard's Rho, Pohlig-Hellman, and the several variants of Index Calculus, the best of which currently is the Number Field Sieve.
Let $n$ be the order of the generator of our field $\mathbb{F}_p$; it is $n = p-1$. We are trying to find $x$ given ...
6
The question to answer is "Is N the product of P*Q?" I believe that the easiest way to understand Shor is to imagine two sine waves, one length P and one length Q. Assuming that P and Q are co-prime, then the question above can also be answered "At what point does the harmony of P overlapped with Q repeat itself?" And the answer can be determined quickly, ...
6
Pure nonsense. For choosing the random $\Delta$ between $\sqrt{\min(N, Ň)}$ and $\sqrt{\max(N, Ň)}$ there are too many possibilities for it to work. For example whenever the first and last digits of $N$ differ, you get something like $\frac{1}{10} \cdot \sqrt N$ possibilities (the exact formula doesn't matter).
So you can replace the first formula $gcd[N, ...
6
There is no reason in Shamir's scheme for the finite field $\mathbb F$
to have a prime number $p$ of elements; the field can have $p^m$ elements for
suitable prime $p$ and integer $m \geq 1$.
So, using $F_{2^8}$, the field with $2^8$ elements is perfectly all right.
However, choosing $m = 1$ has the advantage that calculations in $\mathbb F_p$
can be done ...
5
This issue, and its history, was discussed at length in Silverman and Rivest. The relevant passage here is in Section 6, which I quote:
In 1977 Simmons and Norris [53] discussed the following "cycling" or
"superencryption" attack on the RSA cryptosystem: given a ciphertext
C, consider decrypting it by repeatedly encrypting it with the same
public ...
5
Generating your own group for Diffie-Hellman is not a tough issue; but it is somewhat expensive (it depends on the context, but a 25 MHz ARM device would not like to do it often) and it is not really needed: a good point of DH (and DSA) is that the group parameters can be shared between many users, with no ill effect on the confidentiality of their ...
5
There's nothing wrong with generating your own primes for DH, as long as you know what you're doing.
On the other hand, if you are a bit weak on number theory (or just glad that someone else has done the work, and had it double-checked), there's also nothing wrong with the modulii and generators in RFC 3526.
As for the paper, well, it chiefly noted that ...
5
Let's assume for an instant that you could build a large table of all primes. Then... what ? How would you use it ? What would you look up ?
If you "just" scan the table and try to divide the number to factor by each prime, then this is known as trial division; there is no need to store the primes (they can be regenerated on-the-fly; that's the division ...
5
The other answers explain why you shouldn't take shortcuts like this and why it won't provide much of a speedup anyway. As for an actual attack, here's an obvious one: brute force.
With the parameters you gave, there are only $\binom{309}{3} = 4869634$ possible values for d, which is small enough to easily check every value.
5
There are no known implications of the ABC Conjecture to RSA. The ABC problem doesn't have even a superficial resemblance to the security of RSA.
(The only point of connection is the fact that they both relate to prime numbers, but that is extremely thin. Much of number theory can say it is somehow related to prime numbers. It'd be like assuming that ...
5
This is actually a special case of a more general property of the Euler totient function: it is a multiplicative function, meaning that, for any two coprime numbers $p$ and $q$, $\phi(pq) = \phi(p)\phi(q)$.
The special case where $p$ and $q$ are (distinct) primes is easy to prove.
By definition, $\phi(n)$ gives the number of positive integers coprime to and ...
4
In the general case, for proper security with Diffie-Hellman, we need a value $g$ such that the order of $g$ (the smallest integer $n \geq 1$ such that $g^n = 1 \mod p$) is a multiple of a large enough prime $q$. "Large enough" means "of length at least $2t$ bits if we target $t$-bit security". Since $n$ necessarily divides $p-1$, $q$ divides $p-1$.
We ...
4
We choose $p$ to be such that $p = 2k +1$ where $k$ is also a prime. It is relatively fast to find such $p$.
Then any number in $\mathbb{Z}^*_p$ will have an order which is one of ${2, k, 2k, 1}$
We pick a random number $x$ and check if $x, x^2, x^k \not\equiv 1 \pmod{p}$. If so, then $x$ is a primitive root of $p$, otherwise, we start over.
If we pick ...
4
No, it is not believed to be a problem, probably because:
No known factoring method can take advantage of the bias
The bias really isn't that large, at least, when you compare it to the number of primes. Given the density of primes around 2^1024, there are likely primes that come immediately after 2000 consecutive odd composites; such a prime would have a ...
4
Yes there are several algorithms, as simple or even simpler as the proposed algorithm, that are expected to factor $N$ much faster. The simplest and oldest is the Sieve of Eratosthenes (which works for any $N$); there's also Fermat's factoring method, preferably with the easy sieve improvement to recognize squares efficiently (which works when $N$ is the ...
Only top voted, non community-wiki answers of a minimum length are eligible
