# Tag Info

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

12

You might want to look at NIST SP800-57, section 5.2. As of 2011, new RSA keys generated by unclassified applications used by the U.S. Federal Government, should have a moduli of at least bit size 2048, equivalent to 112 bits of security. If you are not asking on behalf of the U.S. Federal Government, or a supplier of unclassified software applications to ...

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

11

The three main general-purpose algorithms for factorization are the quadratic sieve (QS), the elliptic curve method (ECM) and the number field sieve (NFS). On Complexity The running time of these algorithms is expressed with the L-notation: $L_n[a,c]$ means that the asymptotic complexity of factoring a number $n$ is $O(e^{(c+o(1))(\log n)^a(\log \log ... 10 The generic discrete logarithm problem is this: Given a group$(G, ·)$with generator$g$and$y \in G$, find$x \in \mathbb N$such that$y = g^x$. The "classic" discrete logarithm problem (the one used in "classic" DSA and ECDSA) is this with some subgroup of the (multiplicative) group of a prime field, i.e.$(\mathbb Z/p \mathbb Z)^*$: Given a ... 9 If the RSA keys were generated randomly, then it is inconceivable that two different devices would happen to pick the same key. Taking 2048 bit RSA keys as an example, there are approximately$2^{1014}$1024 bit primes; if we consider them pairwise (and realise that about half the pairs yield a 2047 bit number), that means there are about$2^{2026}$RSA ... 8 RSA themselves (the company) say this in their RSA Factoring Challenge FAQ: Why is the RSA Factoring Challenge no longer active? Various cryptographic challenges — including the RSA Factoring Challenge — served in the early days of commercial cryptography to measure the state of progress in practical cryptanalysis and reward researchers for the new ... 8 There is an asymptotic formula for the General Number Field Sieve for factoring big integers. This is the most efficient known algorithm for breaking RSA keys which are longer than 400 bits or so (since the current world record is 768 bits, a 400-bit RSA key is quite weak). For discrete logarithm (to break DH), the best known algorithm is also known as ... 8 I don't believe a lower bound has ever been proven for the "fewest" number of bits needed. Coppersmith showed, however, how given either the$n/4$least or$n/4$most significant bits of$p$where$n$is the size of the modulus$N=pq$,$N$can be efficiently factored. Additionally, given the$n/4$least significant bits of$d$, one can reconstruct$d$(and ... 8 Those appear to be based on the complexity of the General Number Field Sieve, one of the fastest (if not the fastest) classical factoring algorithms. I confirmed this in Mathematica. Here is the complexity for the GNFS (pulled from the linked Wikipedia article):$$\exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\ln n)^{\frac{1}{3}}(\ln \ln ... 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 In addition to Msieve factor is a public-domain integer factorization program for Windows. Qsieve, a suite of programs for integer factorization. Factorization source code and other related code is here There is a database of prime numbers here like List of all saved primes (500 digits+) and here is a list of factorization software and libraries. 7 "Discrete logarithm" is a wide class. Originally, this means that we work in a finite field (e.g. integers modulo a big prime) and, given g, p and gx mod p, it is computationally difficult to recover x (it becomes impossible with today's technology once p is big enough). At some point, someone noticed that discrete logarithm was a special case of a larger ... 7 Yes there are other hard problems you can base asymmetric cryptography on. Lattices. The NTRU systems is based on the shortest vector problem in ideal lattices. Lattice-based cryptography is of much interest these days for two reasons: (1) unlike factorization and discrete logarithms, there isn't an efficient algorithm for breaking these problems on a ... 7 For numbers over about 115 (decimal) digits, the best algorithm currently known in the General Number Field Sieve (GNFS – sometimes just called the Number Field Sieve, though there's also a Special Number Field Sieve for factoring numbers of a special form). The GNFS, unfortunately, is an exceedingly complex algorithm, and I don't know of any online ... 7 No, it not possible to attack RSA (and practical modulus size) with a WalkSat derivative, as far as we know, or using the algorithm in the question. Problem with that algorithm is: in order to have a sizable/constant rate of success as$n$increases, we have to repeat steps 2 and 3 not the stated$t\cdot m^2$times, but rather$t\cdot 2^m$times. That's ... 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

On point 1: the question worded, reduced to common practice, is equivalent to: assume that we generate $k=2$ RSA public keys with public modulii $N$ of $n=2048$ bits, with prime factors $p$, $q$ random in range $[2^{(n-1)/2}\dots2^{n/2}]$, and public exponent $e=2^{16}+1$; what are the odds that any two of the $k$ public keys $(N,e)$ are the same? Applying ...

6

It's probably best to understand Lenstra's Elliptic Curve factorization algorithm by way of contrast with its predecessors, the Pollard's p-1 method, the Williams' p+1 method and the Cyclotomic Polynomial method of Bach and Shallit. These are all Algebraic-group factorisation algorithms which require you to select a stage 1 bound $B_1$ and stage 2 bound ...

5

I don't think there's anything to worry about here. Remarks 4.2 and 4.3 in the second paper point out that these approaches need to first find a point on a curve with a very large conductor/discriminant, and that seems to be very hard. (Harder than factoring the integer using NFS.) There are many ways to compute factorings and discrete logarithms where you ...

5

Yes, using Miller-Rabin with a random witness does give a practical factoring method. When you run the Miller-Rabin algorithm, it can end in one of three ways: The final value is not 1; this case causes Miller-Rabin to output "Composite" An intermediate value was not 1 or N-1, but the next value was 1; this causes Miller-Rabin to output "Composite" The ...

5

Actually, from my examination of the paper, I don't know if the result is of even academic interest. One generic way to factor a value $n$ is to take a function $F$ and define: for i = 1 to some_upper_limit do temp = F( n, i ) factor = gcd( temp, n ) if 1 < factor and factor < n output factor; halt output Failed This will work ...

5

No. The paper reports success factoring integers of 13 digits 15 digits in an hour, or of the form $n = p\cdot (p+2)$, which are factored in seconds with existing algorithms (Pollard rho or ECM, Fermat). There is no comparison of the proposed algorithms against these classics. The proposed algorithms are useless as a direct method for factoring numbers of ...

5

The procedure to do this is: Find a large prime factor $r$ When searching for the prime $p$, look among numbers of the form $rk+1$ When we find our prime $p$, we know that $p-1$ will have $r$ as a factor. Step 1 is comparatively cheap compared to original search from the prime $p$; we select an $r$ which is large (as far as factors of $p-1$ go), but is ...

5

Here's the scenario that this caveat in the documentation worries about: Suppose you had three modulii: $M_1 = p \times q$ $M_2 = p \times r$ $M_3 = q \times s$ Then, when the program outputs the GCD of $M_1$, it'll output $p \times q = M_1$. It'd do this even though the above has enough information to factor $M_1$ efficiently. It does this because it ...

5

Yes, RSA is secure as we know it — although recommended key sizes are ever-increasing, as expected. Any seemingly-simple result that suggests a long-studied, well battle-hardened cryptosystem is insecure should throw up red flags. As an exercise, I wrote up your algorithm in simple C code: #include <stdio.h> #include <stdlib.h> int ...

5

We are dealing here with two assumptions and we always refer to $N=pq$ the product of two $n$ bit primes $p$ and $q$. The one is factoring and the second is the so called RSA assumption which is a formalization of "inverting the RSA function is hard". These two assumption can be described as follows: Factoring assumption: There exists no probabilistic ...

4

If you have to ask, you are probably not the intended audience. Quoting the introduction of the paper: We implemented our method on a PC using Shoup’s NTL library version 5.4.1 [7]. Unfortunately, we have to say that the practical effect of our method is not good on a single PC, it is worse than many known algorithms on this problem. However, we ...

4

How long would that take in permutations and perhaps with the fastest computer in the world? Given the analysis by @fgrieu using the prime number theorem, we know there are roughly $2^{185}$ possible prime numbers which could be used to construct a $384$-bit RSA key pair. Thus there are $2^{185^2}$ possible RSA key pairs (since it takes two primes to ...

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