Tag Info

Hot answers tagged

23

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


17

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


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

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


11

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


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

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


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


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

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

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

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


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


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

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

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


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


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

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

To step through it simply: Step 1: we first compute compute $M^e \bmod p$ (where $p$ is one of the factors of the modulus. By Fermat's Little Theorem, this is the same as $M^{e \mod p-1} \bmod p$ (and that's where the real savings are), and so in your example ($p=5$), we get: $M^e \bmod p = 27^{37 \bmod 4} \bmod 5 = 2^1 \bmod 5 = 2$ Step 2: we do ...


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



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