Tag Info

Hot answers tagged

24

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 ...


18

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 ...


17

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 ...


17

FIPS 186-3 tells you how they expect you to generate primes for cryptographic applications. It is essentially Miller-Rabin but it also specify what to do when you need extra properties from your primes.


15

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 ...


13

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 ...


13

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 ...


10

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

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

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. ...


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 ...


9

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 ...


8

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 ...


8

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 ...


8

Let me try a simple explanation of NFS. I will necessarily skip lots of details, but I hope you will get the main ideas. The number field sieve algorithm (NFS) is a member of a large family: index calculus algorithms. All algorithms in the family, which can be used for factoring and discrete logarithms in finite fields, share a common structure: ...


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 ...


7

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, ...


7

Here is the issue about hardware errors that Brent is worried about on the slides (I'm not saying I agree; I just saying what the issue is): Suppose we ran our algorithm, and it gave a result "it's prime"; how can we be certain that the algorithm didn't gave us the wrong answer because of an internal hardware error while running the algorithm? This may ...


7

Update: the formula actually on page 165 in chapter 4 of the HAC is: $t=\lceil{1\over2}\cdot\lg n\rceil$, where $\lg$ is the base-2 logarithm; that is $t=\lceil{1\over2}\cdot k\rceil$; and that crude estimate asks for 512 Miller-Rabin tests for 1024-bit primes, not 5 or 6 tests as stated in the question based on the erroneous $t=\lceil{1\over2}\cdot\lg ...


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

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 are close to $2.27\cdot10^{613}$ primes smaller than $2^{2048}$. There are close to $9.4\cdot10^{79}$ atoms in the observable universe. Even if you could compute all those prime numbers, you wouldn't have any place to store them...


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

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 ...


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 ...


6

There are three distinct computational problems related to RSA. They are: FACTORIZATION: given an RSA modulus $n$, find its prime factors $p$ and $q$; ORDER: given an RSA modulus $n$, find the order $\lambda$ of the multiplicative group modulo $n$; RSA Problem: given a ring element $a \in \mathbb{Z}_n$, a public exponent $e$ and an RSA modulus, find an ...


6

There is consensus that it is safe to use random primes $p$ and $q$ when generating 2048-bit (or wider) RSA public moduli which two prime factors $p$ and $q$ are about half the key size. That is sanctioned by FIPS 186-4, appendix B.3; specifically, wording in B.3.1 item A: Using methods 1 and 2 [yielding provable (1) and probable (2) random primes], ...


6

The table from the Handbook of Applied Cryptography is computed for candidate primes taken as odd integers. This is equivalent to using trial division by $2$ only. Note that section 4.48 specifies that: Using more advanced techniques, the upper bounds on $p_{k,t}$ given by Fact 4.48 have been improved. These upper bounds arise from complicated formulae ...


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 ...



Only top voted, non community-wiki answers of a minimum length are eligible