Moderators: phlip, Prelates, Moderators General
themuffinking wrote:This may or may not belong in Computer Science, but everything in CS belongs in Coding and most questions in Coding belong here, so... yeah.
entropomorphic wrote:256-bit keys are generally breakable on desktop computers in a couple hours
necroforest wrote:entropomorphic wrote:256-bit keys are generally breakable on desktop computers in a couple hours
Is that true? I thought the best known factoring algorithm ran in O(2^n) time. Even if you could do a billion steps a second, that algorithm would still take 2^226 seconds to run. Maybe I'm wrong.
Yakk wrote:necroforest wrote:entropomorphic wrote:256-bit keys are generally breakable on desktop computers in a couple hours
Is that true? I thought the best known factoring algorithm ran in O(2^n) time. Even if you could do a billion steps a second, that algorithm would still take 2^226 seconds to run. Maybe I'm wrong.
You are assuming constants. You can't assume an O(2^n) algorithm will take at least 2^n instructions.
In addition, we have faster than 2^n algorithms.
One of the best ones out there is:
O( e^(64/9b^(1/3)*ln(b)^(2/3)))
(GNFS)
entropomorphic wrote:256-bit keys are generally breakable on desktop computers in a couple hours
Bruce Schneier wrote: ...brute force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.
Therefore, it is generally presumed that RSA is secure if n is sufficiently large. If n is 256 bits or shorter, it can be factored in a few hours on a personal computer, using software already freely available. If n is 512 bits or shorter, it can be factored by several hundred computers as of 1999. A theoretical hardware device named TWIRL and described by Shamir and Tromer in 2003 called into question the security of 1024 bit keys.
Rysto wrote:Wikipedia:Therefore, it is generally presumed that RSA is secure if n is sufficiently large. If n is 256 bits or shorter, it can be factored in a few hours on a personal computer, using software already freely available. If n is 512 bits or shorter, it can be factored by several hundred computers as of 1999. A theoretical hardware device named TWIRL and described by Shamir and Tromer in 2003 called into question the security of 1024 bit keys.
Was Schneier talking about symmetric-key algorithms or assymetric(public) key algorithms? I might believe that about symmetric-key algorithms.
Rysto wrote:Was Schneier talking about symmetric-key algorithms or assymetric(public) key algorithms? I might believe that about symmetric-key algorithms.
Users browsing this forum: No registered users and 3 guests