# Tag Info

42

I've never heard that RSA becomes less secure when the modulus grows. Obviously the strength doesn't grow as fast as the number of bits, but that only means that it grows sub-exponentially. If it keeps growing (without the growth going near zero) then there is no "trap". Check for instance here where the conclusion is that there is no exponential growth but ...

41

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 (source): $$\exp\left( \left(\sqrt{\frac{64}{9}} + o(1)\right)(\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}}\right)$$ where $n$ is a ...

26

I don't understand at all what this claim is on the website. The claim that RSA becomes very expensive for large $N$ is true, but to say that the gap between encryption/decryption cost and factoring goes down makes no sense at all! The function describing the running time of the best factoring algorithms is clearly asymptotically larger than $n^3$ (the time ...

25

2) Has anyone claimed to make any progress with this challenge? Ah that question I can answer now... I found the solution on the 15th of April 2019 and sent it to the MIT's CSAIL on the 16th of April. Another team shall have the answer by the 11th or 12th of May (they used a FPGA). I noticed around the end of 2015 that if I used GMP I could find the ...

19

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

17

RSA-768 took 2000 years of 2.2Ghz single-core Opteron from the year 2009. DJB et al wrote in 2013 (see page 30) (see also: 29C3: FactHacks (EN); slide 87/112; about 10 minutes) that RSA-1024 would take $2^{70}$ differences with $2^{24}$ per machine per second in 2009, so 2 million years. Hardware improved since then, and GNFS can use GPUs, so maybe better, ...

16

Actually, the problem is that the above quote uses the term "discrete log" in a way that's different from what you're thinking of. When someone uses the term "discrete log", they can mean two things: A discrete log in the group $Z^*_p$; that is, given $p$, $g$ and $g^x \bmod p$, recover $x$ A discrete log in some other group; that is, given a group $G$, a ...

16

First we may want RSA primes to be something like a safe prime, ie a prime $p$ where $(p-1)/2$ is prime as well. Back in 1974 Pollard found an algorithm to factor moduli whereby you can factor $N=pq$ if $p-1$ or $q-1$ are smooth, that is all prime-factors of $p-1$ or $q-1$ are smaller than a bound $B$. The algorithm will then factor $N$ in time $\mathcal O(... 15 Proving P=NP would not necessarily give you an algorithm, because there are many different methods to prove something (i.e. Direct proof, Proof by contradiction, etc.). But it is shown that if you were to find a polynomial time algorithm to solve a NP-complete problem that you could modify that algorithm to solve all NP-problems, including the Integer ... 15 The bozos at Clown Sterling have adapted the advanced technology of bogosort to factoring: randomly blow a candidate solution out your nose and check whether it works. For a semiprime$n$chosen by modern RSA key generation methods, there are approximately$\sqrt n$candidate solutions to check, which is also the expected cost of this method. For instance, ... 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 I'm one of the authors of the paper. In order to make the paper more approachable, we factored each major optimizations out into its own paper. There are three of these sub-papers, and they each stand on their own mostly independent of the others. "Approximate encoded permutations and piecewise quantum adders ". We put small amounts of padding at various ... 13 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 ... 12 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 ... 11 Bill Garsarch just posted about this the other day. The short answer is that there is an explicit algorithm, which is known today, such that if P = NP (or even just FACTORING ∈ P) then the algorithm solves factoring in polynomial time on all instances. However, this algorithm is utterly infeasible for real-world computation because it works by iterating ... 11 The IEEE paper is silly. The factorization method they give is quite slow, except for rare cases. For example, in their table 1, where they proudly show that their improved algorithm takes 653.14 seconds to factor a 67 bit number; well, I just tried it using a more conventional algorithm, and it took 6msec; yes, that's 100,000 times as fast... 10 No, there is no specific vulnerability associated to choosing$p$and$q$with size differing by$i$bits (or$2\cdot i$bits as in the statement) for small$i$. However, if$i$gets too big: That improves the odds that ECM will manage to factor$n$for some fixed size of$n$, and at some point ECM will become the best algorithm; this is the case if$i$is ... 10 Yes, they are (deterministically) equivalent. The original RSA paper (Section IX.C), working off Miller's results (Theorem 3), showed how knowing the secret exponent$d$was probabilistically equivalent to factoring$n$. Later, using more advanced techniques, Coron and May showed how to deterministically reduce finding$d$to factoring$n$. 10 Breaking such a scheme is easy. Suppose Alice wants to transmit a message$M$to Bob. First thing, Alice picks an integer$R_a$and sends the cipher text$C_a = M \times R_a$to Bob. Bob then picks another integer$R_b$and transmits$C_b = C_a \times R_b$back to Alice. Alice calculates$D_a = \frac{C_b}{R_a}$and sends$D_a$to Bob. Bob calculates$D_b = ...

10

Algorithm An RSA modulus $N$ product of large distinct primes can be factored given $(N,e,d)$ per: Compute $f\gets e\,d-1$, and express $f$ as $2^s\,t$ with $t$ odd Set $i\gets s$ and $a\gets2$ Compute $b\gets a^t\bmod N$ , and if $b=1$ then set $a$ to the next prime, and proceed at 3 If $i\ne1$ then compute $c\gets b^2\bmod N$ , and if $c\ne1$ then ...

9

The puzzle has now been solved! The solution was announced in May 2019. It was solved by Bernard Fabrot, who used a modern optimized implementation of big integer multiplication to speed up the computation and finish it in about 3.5 years of computation instead of 35 years. At around the same time, a second team using FPGAs reported being weeks away from ...

9

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

9

Does the factorization of N somehow help me? It sure does. I think I could compute the logarithm modulo each prime and then combine it, but do not know how exactly. Seems similar like problems for Chinese remainder theorem but I cannot find the way how to do it. You're real close; you do recombine them using the Chinese Remainder Theorem; however the ...

9

Since n = pq, then when an integer modulo n is a square, then it has (in general) four square roots. This can be seen by reasoning modulo p and modulo q: a square has two roots modulo p, and two roots modulo q, which makes for four combinations. More precisely, modulo a prime p, if y has a square root x, it also has another square root which is -x. The same ...

9

No, it is not collision-free. All possible sequences of 0's produce the same output: 0 --> (2 ** 0) = 1 00 --> (2 ** 0) * (3 ** 0) = 1 000 --> (2 ** 0) * (3 ** 0) * (5 ** 0) = 1 0000 --> (2 ** 0) * (3 ** 0) * (5 ** 0) * (7 ** 0) = 1 In fact, it can be seen that $f(s) = f(s||0)$, for every bit-string $s$. This could be easily solved by ...

9

Unfortunately you haven't made a scientific discovery. One of the places where large integer division is required is when testing for prime values. Primality tests are required to find real prime numbers within a set of candidate primes. So to find $p$ and $q$ large integer division is already required. That said, doing such a big calculation efficiently ...

8

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

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

8

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

8

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

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