# Tag Info

62

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 $Log(p)... 36 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 ... 29 Primes are important because the security of many encryption algorithms are based on the fact that it is very fast to multiply two large prime numbers and get the result, while it is extremely computer-intensive to do the reverse. When you have a number which you know is the product of two primes, finding these two prime numbers is very hard. This problem is ... 26 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, ... 25 The premise "we don't have a way of generating and verifying a 2048-bit prime number with 100% accuracy" is wrong (if we trust the computers performing the operations): it has long been known practicable ways to generate randomly-seeded provable primes, and it is a (somewhat marginal) practice in RSA key generation (see FIPS 186-4 appendix B.3.2). We can ... 25 Is this number specified anywhere? It was formally specified in this RFC as the 1536 bit MODP group (although its use predates that RFC). However, from what I've seen, the 2048 bit MODP group from that same document is actually more popular. Why was this particular number picked? Well, it's a safe prime; in addition, the leading 64 bits and the ... 23 However, factoring a large integer is extremely difficult, even for a computer using known factoring algorithms. Not categorically. Factoring a large integer is trivial if it is only composed of small factors. A fairly naive algorithm for factoring N is the following: while N > 1: for p in increasing_primes: while p divides N: N = N / p ... 21 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 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$...

17

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} +... 17 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 ... 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 in ... 15 The main reasons we usually choose$p$an$q$prime numbers are: For a given size of$N=pq$, that makes$N$harder to factor, hence RSA safer. Although efficient factoring algorithms do not find factors by trial division, it remains much easier to find very small prime factors than large ones. If we chose$p$and/or$q$at random without consideration for ... 14 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 ... 14 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 http://... 14 If$p=2q+1$is a safe prime (that is,$q$is a prime as well), then$p-1=2q$has exactly two prime factors:$2$and$q=(p-1)/2$. 14 The algorithm you quote is usually called textbook RSA and is not used in practice for numerous security reasons (the problem you pointed out, is just one of them). In practice, you have to pad (or armor) your message. This should be done using the RSA-OAEP (also called PKCS#1 v2.0) scheme. It transforms your message (1) into a pseudorandom block (not 1) ... 13 I can think of two places where we use a Mersenne Prime within cryptogaphy: As a modulus within a prime elliptic curve.$2^{521}-1$is a prime, and so we can define an elliptic curve using$GF(2^{521}-1)$, which is in moderately common use. One reason we use such a modulus (rather than another prime of approximately the same size) is that the special form ... 13 The critical facts enabling to find such$p$in practice are: We can easily tell with practical certainty if an integer with many thousand bits is prime or not, using a primality test such as Miller-Rabin, even though we are typically unable to tell all its factors when it is not prime. About$1.4/b$integers of$b$bits are prime. Thus it is more likely ... 12 "I understand that the typical approach is to use pre-generated lists of large primes." This is what I also thought. But I had not considered how many primes we might choose from. As it turns out you choose from ~2.8x10^147 primes with a 1024 bit RSA key and from about ~7.0x10^613 with a 4096 bit RSA key. Then you have up to 4.9x10^1227 possible pairs of ... 12 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 ... 12 What we really need is a number$\lambda$satisfying$x^{\lambda+1} \equiv x \pmod n$for all integers$x$(which, by induction, then implies that$x^{k\lambda+1} \equiv x \pmod n$for any$k$). Given such a$\lambda$, and an arbitrary encryption exponent$e$which is coprime to it, we can then find the multiplicative inverse of$e$modulo$\lambda$, i.e. a ... 11 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 ... 11 There are two approaches to such a validation: Test: you can look at the number and decide without involving the person who gave it to you. Proof: The person who generated the number can also give you additional information that will convince you it is a correct RSA number. There are no tests for RSA numbers. There are proofs for RSA numbers, including "... 11 In order to generate a RSA key pair, you are to find a public exponent$e$and a private exponent$d$such that, for all$m \in \mathbb Z_n^*$, i.e.$m$is relatively prime to$n$,$(m^e)^d \equiv m \pmod n$. It is a consequence of Euler's theorem that if$e, d$satisfy the equation$ed \equiv 1 \pmod {\phi(n)}$, they are such a valid public/private exponent ... 11 RSA moduli are generally of the form$N = pq$for two primes$p$and$q$. It is also important that$p$and$q$have (roughly) the same size. The main reason is that the security of RSA is related to the factoring problem. The most difficult numbers to factor are numbers that are the product of two primes of similar size. Note. There are basically two ... 10 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 log_2(...

10

We want a non-trivial factorization of a moderate odd integer $n$ into positive integers $p$ and $q$, knowing that such factorization with $|p-q|$ suitably small exists. Perhaps the most elementary method answering the question is trial division by integers starting at $\lfloor\sqrt n\rfloor$, going down. This succeeds after checking divisibility of $n$ by ...

10

There is no more efficient way of generating a safe prime. Even in OpenSSL's optimized code, it can take a long time to generate a safe prime (30 seconds, a minute, 2 minutes). Run "openssl gendh 1024" on your computer to see (on my 2015 MacBook pro it can take a long time, but the variance is really high so try a few times). The comments talk about safe ...

9

The key is that the test used by crypto libraries to determine whether a number is prime is probabilistic. That is, if the test uses a randomly-chosen value (the "witness") which serves as the basis for the test. If the test passes, then the number is probably prime, but possibly not. We can repeat the same test with a new "witness", and if the test passes ...

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