Slashdot Mirror
RSA-640 Factored
gslin writes to tell us MathWorld News is reporting that RSA-640 has been factored. F. Bahr, M. Boehm, J. Franke, and T. Kleinjung, memebers of the German Federal Agency for Information Technology Security (BSI) announced they had cracked the 193-digit number last Friday using the General Number Field Sieve. The team purportedly used 80 opteron CPUs and 5 months to achieve victory.
640=2*2*2*2*2*2*2*5.
What do I win?
I wish had nothing better to do for five moths than factor numbers...geez...who needs the Internet when there are numbers to factor. :)
This is similar to the issue that the Germans had during WWII, it's a matter of time. If it takes them too long to decrypt, then the data sometimes is useless. Let's hope the problem isn't the same.
I hardly know 'er...
Seriously, this is interesting stuff. Of course, everytime we come up with a new security mechanism, computing power will overcome it. Fortunately, not everyone can do this sort of thing, and it takes time. But, as a mathematician, it is interesting to see both the methods used to crack this sort of thing, and, at least to me, more interestingly, the methods that are used to come up with new encryption systems. I cannot wait to see what will occur in several years, and even bigger prime numbers are known and usable...
The answer was 42!
Now what was the question
hmm this doesn't suprise me that they already factored the 193 digit encryption code. Bring on the 293 digits!
The German Federal Government is short on cash, I know, but resorting to funding the "Agency for Information Technology Security" by winning RSA contests? Besides, if they're so up on IT security, why didn't they just cheat by logging onto RSA's computers?
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
I think that's really cool and would wish them the best of luck, but I would like to know how many processor hours that took them to crack it? Also, with that chunky $30,000 reward, did they turn any profit (after taxes, fees, and such). Second one's a joke, calm down. But it'd be cool to know the processor time it took.
I like suggestions, but I don't like contributing towards them.
Cue tin foil hats.....now!
As the owner of a cryptography website...this news is interesting to hear. I remember people saying that the later sets of problems in RSAs would hold out. Guess not. (Note the growing gaps in dates in the table in TFA). A good read, actually. Congrats, guys.
You know, someone needs to compute the cost of factoring per digit and weight that cost against other priorities. I wouldn't mind if they were testing some new cluster, but testing for 5 months is a bit of a stretch. Even considering that they received 20k$ for their efforts, the waste is just repulsing.
Brute force will eventually figure out the factors, unless the universe experiences heat death first.
The real interesting thing is whether we can solve the problem simply and in a reasonable time (less than 5 seconds on modern hardware). Unfortunately, that algorithm is still not available.
Jesus saved me from my past. He can save you as well.
My TI-82 was just about to solve that one!
Well, he certainly failed miserably at using less than 640k.
I knew that one of the factors ended in a 1 and the other ended in a 9 or that they both ended in 3. Am I eligible to split the prize?
im curious as to how long itd take on the national computing grid? ..gee, couple days, tops?
What if there's a team that started with a slightly slower machine before them and they only needed a few more days to complete the factoring?
should be enough for anyone."
I'm not going to get into an involved response, but had they opted for Celerons rather than Opterons, the time would have been much, much greater, start at any level you want and the Opteron is a better processor for this job.
I like suggestions, but I don't like contributing towards them.
Oh wait. No, that wouldn't have worked. Nevermind.
I wonder how long it would have taken 1.5 million zombie PCs.
To a politician, one email equals one voter.
I won't be interested until they do RSA-2048. Then we could factor the Xbox private key and do whatever we want.
Melissa
"Screw Sun, cross-platform will never work. Let's move on and steal the Java language." - Visual J++ Product Manager
The article summary even says they used the General Number Field Sieve. Nobody uses Trial Division. Try not speaking from a position of ignorance next time.
I've seen these for a while, never thought they'd be on-topic...first prime factorization post, here it is:
1634733 6458092538 4844313388 3865090859 8417836700 3309231218 1110852389 3331001045 0815121211 8167511579 x 1900871 2816648221 1312685157 3935413975 4718967899 6851549366 6638539088 0271038021 0449895719 1261465571
When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl
Why don't we just start using 1.44mb encryption keys. We'd finally have a use for all of these floppies.
I think he was joking.. I hope he was joking
The Wikipedia article on RSA-640 has more info. Check this for easy money ;)
Which means you'll be able to buy a wristwatch next year that can do it in 5 minutes.
And in only 5 months... how P Q ular.
...now if he could just find his keys.
Stop invalid scientific research. Ask your local scientists to feed their lab rats with a phytoestrogen-free chow.
...many are asking. It's hard to find introductory materials on the NFS, because the number of people who actually understand the algorithm is probably in the hundreds, if not less, and most are worried about research not teaching. For those interested in a high-level view, plus some low-level details, of the (special and general) NFS, you can have a look at the slides for a talk that I gave on exactly this topic at a crypto workshop a couple of months ago. I won't even try to summarize the NFS here, because anything other than a very high level, handwaving, bird's eye view of NFS would take the better part of a page to explain. However, in this thread I can answer specific questions that anyone might have about the talk above.
Now for those with the mathematical maturity to delve into the algorithm, I suggest the book Prime Numbers: A Computational Perspective by R. Crandall and C. Pomerance (link to Amazon.com lifted from Google, no referrals), which is certainly one of the best introductions to the algorithm that I have read.
By the way, if anyone wants to help perform huge factorizations in a distributed computing network, check out the NFSNET, although they mostly apply SNFS on values from the Cunningham tables, no cryptographic targets.
Join the NFSNET. Our prime goal is making little numbers out of big ones. http://www.nfsnet.org/
factor:2 72754572016194882320644051808150455634682967172328 67824379162728380334154710731085019195485290073377 24822783525742386454014691736602477652346609' is too large
`310741824049004372135075003588856793003734602284
isomerica.net | Foonetic IRC
how many RSA-640s will there be in the xbox360, and is that more than the ps3 will have?
There can be no factorization algorithm that runs in constant time. It's not even theoretically possible. The lower bound on the time taken to generate the answer is the time taken to verify its certificate, which is linear in the number of bits used to represent the factors. To even find a polynomial time algorithm is to prove that P=NP (Hint: it won't happen -- it's been proven that we don't even have the right kinds of maths to talk about the problem yet.).
And 15,000,000,000 CPU cycles?! Where did you get that number? OK, nevermind, I don't want to know . . . probably no place that I want to talk about. That's like . . . only three hours on my laptop, which is not a very fast laptop. I'm pretty confident right now that you have no idea what you are talking about.
Instead of pharming bank and brokerage website passwords, botnets can just use their resources to do these factorizations! Much safer than financial fraud ;-)
Wow.. 193 bits. I'm quite astounded that it's come this far. I'm actually a little puzzled.. wasn't it only three years ago that it took something like four years and thousands of distributed PCs to crack RC5-64 (64 bits, as I understand it) ?
If I'm not mistaken, shouldn't it be 2^129 times more difficult to factor a 193 bit number than a 64 bit one? Perhaps I'm not understanding something.. someone want to clue me in?
http://cltracker.net -- powerful craigslist multi-city search
if they would of used
if they would have used
The above is a math joke. I'm not going to explain it because it's not funny then, but I think that those who understand it would like it and might not see it at its present "1" level.
we need time travel! then it doesn't matter much how many months it takes to crack!
I don't know who this general Steve is, but he must be one heck of a math whiz!
from http://www.rsasecurity.com/rsalabs/node.asp?id=208 8
;)
To put this in perspective, it would require about 1.4 billion 500 MHz machines, each with about 170 Gbytes of memory to do the sieving for a 1024-bit number in the same time as RSA-512. While a hacker might try to steal cycles on the Internet by creating a ?Number Field Sieve Worm? it is hard to see how such an attack could find enough machines with enough memory to make such an attack feasible. Further, such an attack would be detected and shut down rather quickly as with the Robert Morris worm. Of course increasing speed will reduce the required number accordingly. It would take a single Cray with 6 Terabytes of memory approximately 70 million days (192,000 years) to solve the matrix. One could reduce this to a mere 19 years with 10000 Crays each with only 600 Mbytes of memory running perfectly in parallel. It is likely that within 10 years common desktop machines will be as fast or faster than a Cray C90 is now. However, it is unlikely in the extreme that 10000 machines running in parallel will be anywhere close to 10000 times as fast as one machine. It would require 10 million such machines running perfectly in parallel to solve the matrix in about the same time as that for RSA-512.
So basically, according to the article from RSA it's not feasable... but still an interesting IDEA. Maybe a worm that installs something like folding@home that would have immediate benefits.
I'm glad to see people can still notice a joke. (Yes it was a joke!)
Giggidy Giggidy Gigg-a-dy
The prize money is mostly a prestige thing and a little kickback for what you did spend. The costs of factoring these things are such that the money isn't enough to be considered profitable. If you account for hardware costs and all they are way behind, though I'm sure the hardware will be used for other things now.
:).
In general it's like the X-Prize. The money wasn't intended to be an amount such that winning it would be a major financial reward, it was intended to be a goal to reach and give you enough to hopefully cover a fair bit of your costs.
The only way the money would be worth it in and of itself was if you figured out some dynamite way of factoring RSA quickly. However in that case, I think I'd approach the NSA, I bet they'd pay more
Here is a very useful site, listing estimates of how long various algorithms will be secure, and at what key sizes. It covers public- and secret-key algorithms, as well as hashes.
http://www.keylength.com/
Signature.
this shows security is process then of a black box sloution ...lol
Anyway, see ya later, I'm going straight for the RSA-2048. $200,000 can make you forget that you've spent a good deal of your life trying to unmultiply two numbers.
How long, roughly, can we expect something of a given crypto strength to remain secure, at a given level of means of attackers? That's the real question when trying to evaluate if crypto is good enough or if it needs an upgrade.
I mean let's say I am in a situation where my data is only worth it for 6 months, maybe the data is an access code and it changes every 6 months. Let's also say what it guards is pretty low dollar, my bank account maybe. Ok so my crypto needs to be good enough that someone with at most a couple grand to throw at the problem can't get it in 6 months. Nearly anything would work for that.
Ok so now suppose it's guarding data that needs to be secret for at least 10 years, and it's really valuable and could potentially face attackers with 10s of millions of dollars to throw at it. Well, it's going to have to be much stronger, but how strong?
That's what these kind of things can tell us. So, with basically the best available current technology on a reasonable scale, you can break RSA-640 in a little less than half a year. So probably good enough for my bank code, not good enough for the super secret data. Well using that as a baseline, and looking at trends in growth, we can get a reasonable estimate of what we'd want for the secret data case.
Suppose it was stored with RSA-768, we could run the numbers on it (I'm not going to go through all that trouble, but you can if you want) to see if that's good enough for our criteria, or if we need to move it to better security.
I was checking out the wikipedia link, and this was at the top of the page: /.
This article has recently been linked from Slashdot (backlink).
Please keep an eye on the page history for errors or vandalism.
And then when you leave the office you just throw your encryption key floppy into your attache case with it's three digit combination...
"Maybe a worm that installs something like folding@home that would have immediate benefits. ;)"
If only. Really, if only.
The thing is, though, Vijay frowns on that. It would not make him happy. If you have control over more than a few PCs, he wants proof you have the authority to do that. Not up front, mind you, but the folding community will eventually ask "Who is that guy?" once you've accumulated enough points, and you'd better have a good answer, like you have the authority to run so many clients, or you're out.
--
BMO - www.bumwine.com folding team. Team number 43909
celeron's
(Score:1, Funny)
by rufuseddy (781982) on Tuesday November 08, @11:35PM (#13985872)
(http://www.oceighty.net/)
blah, if they would of used 80 celeron's they would have cracked it twice as fast.......
Dude, what's wrong with you? You wrote "would of"[sic] and "would have" in the same sentence! To make matters worse, you didn't capitalize a proper noun ("Celeron"), you used an apostrophe before an "s" in a plural twice, you didn't capitalize the first word of a sentence, and you ended your "sentence" with seven periods. Go back to the fifth grade. Do not pass go. Do not collect 200 dollars.
That's exactly what I thought. It drives me nuts when people write 'would of', 'could of', 'should of', and the like. Too bad, you're an Anonymous Coward so I can't put you on my friends list.
The thing is, though, Vijay frowns on that. It would not make him happy. If you have control over more than a few PCs, he wants proof you have the authority to do that. Not up front, mind you, but the folding community will eventually ask "Who is that guy?" once you've accumulated enough points, and you'd better have a good answer, like you have the authority to run so many clients, or you're out.
ahh... true! good point! But I'd assume that you could also hide your clients among other groups, especially some of the larger ones. That is, assuming you wouldn't want to recieve credit for your cumulative WU count. Or you could make it choose a random Folding@Home group to join. Or you could choose another distributed project completely.
This is the same RSA that OpenSSH can use for keys, right? Makes me wonder how DSA stacks up. What's the ratio between the time required to break RSA and the time required to break DSA, using the same length for both? What about other algorithms I haven't mentioned? I tried to grep the web, but it didn't turn up any hits.
Please correct me if I got my facts wrong.
For any base b, the sum of the digits (in base b) of a multiple of (b-1) add to a multiple of (b-1). The proof is fairly simple: http://www.pseudorandom.co.uk/2002/maths/divby9/.
For instance, in base 16, 3 * F (45 dec) is 2D, and 2+D=F.
This leads to a (slow) algorithm for primality check. For a given number r, simply (hah!) check all the bases up to about log_b(r) to see if all your base r belong to us.
Raise your children as if you were teaching them to raise your grandchildren, because you are.
I have an even better one. If you convert the number to binary, you'll observe it ends in 1. The only way to get that from two numbers is if they both end in 1. So here's your first digit with 100% certainty!
Please correct me if I got my facts wrong.
A nice result! Interestingly, the same team factored RSA-200 last May, which is 663 bits long (confusingly, there's two series of RSA challenge numbers with different naming conventions) but for which no prize was given for its solution. RSA-640 is shorter, at 640 bits, but carries a US$20,000 prize. It's not entirely clear why the team went for the larger, prizeless number first.
Maybe there's other factors at work here besides prize money? (ROFL etc).
That was the best worst nerd joke ever. :)
Hahaha... ph33r us
I thought the title said "RSA-640 Fuxx0red"
80 CPUs and 5 months to breack lousy 640 bits... Oh what a great achievement.
I wonder how much time they will need to break 1024 bits used everywhere for some time now and then 2048 which is GPG default key size.
Well, we may consider RSA still safe given that most script kiddies don't have even two cpus at their disposal.
As to the guys who did break it, I allow them to have a cookie.
...should be enough to anybody!
I used to have a better sig but it broke.
RSA cost study says "It makes no sense for an adversary to spend (say) $10 million breaking a key if recovering the key will only net (say) $10 thousand." Third party payer negates this asumption. Exceptions to the rule are seen in the everyday spending of U.S. taxpayer's millions by low level government employees and politicians alike for their personal gain or amusement, no matter how minor.
Right on, I was wondering the same shit and this guy answered it.
There were a few simple 'trojans' distributed via p2p (I think they looked for and copied themselves to shared folders, but that doesn't really make them worms) which were wrapped copies of SETI@Home preconfigured to install silently and work under someone else's account. I don't know if the same thing has been done with Folding@Home but it should be possible.
Remember that those calculations assume a specific algorithm.
It could always happen that some bright guy finds a more efficient (or more easily distributed) way to attack the problem. This is always a risk with encryption that relies on "computationally hard" problems.
The "one time pad" has been proven to be the only secure cipher that will ever be available:
http://en.wikipedia.org/wiki/One-time_pad
So, do feel safe about having your personal secrets made public eventually, no matter how careful you are at encryption?
Has anyone publish (theoretical) costs of system capable to break given RSA lenght in one day based on the known systems?
Prize money is great. I will factor it. I'm serious.
And they had to kill poor little lappy, eh steve???
oh for shame! wahhh
This is why I love slashdot people corect your every spelling mistook. Or gramma errer. And they dont even have the courage to own up to who they are!!!?!
Pete takes another karmic hit!!
Better is the enemy of good enough. - Russian proverb.
For the life of me, I can't understand why anyone would take that post seriously. He was joking! Anyone who could possibly think that a celeron is better than a opteron wouldn't be able to tie their own shoe laces much less post a comment on slashdot. What's happened to everyone's sense of humor? Please don't correct people on humorous statements. I think that's the "in" thing with the newest generation. If I had to guess I'd say you are a 14-17 year old. I don't remember correcting humorous comments when I was that age. I'd verify that someone was indeed ignorant before correcting them. Kids, verify someone's stupidity before you make an ass of yourself!
Beer! It's what's for breakfast!
No.
About 1200 years.
Progress in computation of the solution is linear. Moore's law is exponential. By year 3200 the computers will be strong enough to crack it in 6 months.
Anagram("United States of America") == "Dine out, taste a Mac, fries"
So, do feel safe about having your personal secrets made public eventually
I'm 25. If it takes 60 years to crack my files, does that really matter if I'm expected to die at 84?
If the development of quantum computers succeeds then you will need to find a different mechanisim all together as Shor's Algorithm can factor numbers in polynomial time and might cause some problems even for large key lengths.
Warning, comments may not have been passed by the sanity department of my brain.
Does this mean I don't have to have my SecurID with me to log into the VPN at work?
Tony Blair needs to know about this as soon as possible. 90 days isn't long enough, we need to be holding those terror suspects for five months...
Sigs are so 1990s. No way would I be seen dead with one.
I've got $1000 that says you are wrong. RSA-2048 will be solved in the next 25 years.
It hasen't even been proven yet that factoring is a hard problem!
Ninjas don't carry tic tacs
You can't just "switch". If you encrypt material, it is because of the general idea that it might fall into unwanted hands. If it has first fallen into unwanted hands, you can't simply update the data they have so that it isn't encrypted with 256 bits rather than 2048. What you do within seconds leaves a trail of encrypted data that any eavesdroppers could get started on cracking. That includes publicly accessible email archives and keyservers.
The best effort you can do regarding this dilemma is of course to avoid releasing your keys. If you want your keys for the exact reason that you can release them, you better pick an encryption that is estimated not to be able to be cracked within reasonable time, or at least until quantum cryptography.
And yeah, 2048 should stick for now.
Take off every 'ZIG' !!
It's like figuring out how many times you'd need to toss a coin before you'd be likely to get 7 heads in a row... and after figuring this out, actually tossing the coin until you get 7 heads. Anybody who actually did that would a moron. It would show nothing... much like these "factor this" challenges.
General Number Field Sieve? That sounds complicated, they should just try:
for ( n = 2; n sqrt(num); n++ )
if (num % n == 0)
return n;
Took me a minute. Now I just need some opterons. I can taste the prize already!
When the numbers get large enough, is it practical to start writing these algorithms in Python? That would be really cool IMHO.
However, this is not the point. The point is to prove ANYONE (not only cryptanalyst) that it CAN be broken, though it takes some processing, and there is no alternative for doing.
Anonymous Coward? Or just unwilling to bow to Slashdot's "give us your first-born" registration policy?
You win nothing, for your answer is incorrect. You were supposed to factor RSA minus 640. A quick Google search reveals that R*S*A is 8.314472. (Yes, I know that there are a bunch of letters and crap after the number, but ignore them. They're not important.) So you need to take 8.314472 minus 640. A quick Google search reveals that this is -631.685528. So you have to factor this. Try again.
I love Google! It always produces the right answer.
You have no clue what you are talking about. Mathematicians have studied primes. They already know that primes are relatively dense. Between 1 and n there are approximately n/ln(n) primes. That is there are plenty of them, even in the very large numbers. Even at 1000 digit numbers you are only looking at a few hundred tries before you find a useful prime.
Note that I said useful prime. There are numbers that are not prime that will work for RSA encryption (newton primes). A token effort is made to eliminate them, but only because some think they might be less secure than normal primes - there is no known way to exploit a RSA if it contains a newton prime, that doesn't work for regular primes.
Just so you know, it took RSA Laboratories 4.5 months to officially annouce the factoring of RSA-576. :(
As for my first comment in that thread, I remember being in a real bad mood before reading the article: one of my rare outbursts.
This is not my sig.
No, you have that backwards.
What you mean is: the one time pad is the only available cipher that has been proven to be secure. A subtle (but very important) difference.
....and that's exactly how you would determine, to a specified degree of confidence, whether the coin is "fair" or not. And repeating the procedure many more times, in an industrial setting, is how manufacturers set service lives and MTBF's in a meaningful way. And until you actually get those factors and check them, you don't know if your algorithm has been encoded correctly. So there are lots of reasons to do this, but you seem a bit short in the imagination/knowledge department - just because you can't concieve of/know them, don't assume others are as limited as you.
What you mean is: the one time pad is the only available cipher that has been proven to be secure.
No.
from wikipedia:
Universal unbreakability:
Claude Shannon's work showed any perfect encryption system requires that the number of possible plaintext messages does not exceed the number of possible keys. If the number of possible keys and plaintexts are measured in, say, bits, this is equivalent to saying that the key must be at least as long as the plaintext.
You can find the Shannon proof on the web.
You forgot to factor the 2s:
2 = (1+i)*(1-i).
"Nobody will ever need more than 640 bits in their encryption key"
Bill Gates, October 2005
Surely this kind of factoring is an "embarassingly parallel" problem, like SETI, Folding, etc.? If so, shouldn't the complete independence of the calculations each machine runs mean you *do* get an n-fold speedup, minus some trivial adjustment for transmission of the data? It's not like this is a physicist's particle simulation, where every calculation involves every other one.
Media that can be recorded and distributed can be recorded and distributed.
-kfg
I'm told that Yahoo has something in the order of 88,000 BSD systems running across a myriad of data centers, across a network that makes some Tier-1 ISP's look silly.
Imagine what a large search engine with that kind of power and a nice cache of information could try...
no we're not talking about multiplying integers. we are talking about is anything from a family of algorithms based on the observatino that (i think the ro p^2 's algorithm was the first?) p1^2-p2^2=(p1+p2)(p1-p2) but you work in modular arithmatic. you get a whole lot of candidate vectors, and you multiply the vectors together to make p1 and p2, so you can gather the vectors, the candidates on parallel computers, but you have to factor a big matrix formed from these candidates, anyway this big matrix calculation usually is implemented on a single big cpu actually but the assertion tyhat this is necessary is almost certainly not true, i myself believe that it can be parallelized, possibly less efficently but it would overall retain most of the efficiency common to all factorisation algorithms based on the above general scheme, which i belive range over most of the field sieve algorithms. possibly a field (modular arithmatic) is also related to the possible use of eulers little equation? or whatever its called, a generalisation of ... perhaps it was fermats little therom? p^a =1 (modn) ? number theory is hard! but it definately contains the secretes of the universe (pun intended)
You're absolutly right. It shows nothing but how utterly stupid one is to figure something using lots of money and getting nothing back except some number. It's NOT worth that much money. And neither is that number. - - - It is what it is, its not what its not: now thats a thought
One up for flawed logic!!
nor unproven, so let's give it 50:50. :)
Anagram("United States of America") == "Dine out, taste a Mac, fries"
Code 1: 1A
Code 2: 1A2B
Code 3: 1A2B-3
What's the final code?
Who is general failure, and why is he reading my hard drive?
About 5 minutes after I posted that I realized that the subject was too harsh. Sorry about that.
I too am working from memory. It has been 8 years since I studied this. I did a little research myself.
While the constants are large, a multi-gigahertz computer has no problem dealing with 2000 didits numbers. And as computing power goes up, we can deal with large number faster than you can factor them. So for practical purposes I can find 2 primes with 200 didgets relatively fast on a modern computer. However you cannot factor the product of them with any great speed.
We don't generate new public keys very often. Maybe yearly, and it only takes a short time. Generally getting a good seed to the random number generator, and entering a new passphase will take longer. For practical purposes there are plenty of prime numbers.
There is no perfect cipher other than the one time pad; that is true.
But you claimed that there are no other secure ciphers. Most cryptographers would agree that any cipher which operates with arbitrary key lengths in no worse than polynomial time (with knowledge of the key) and for which there is proof that no algorithm exists to decrypt in polynomial time (without knowledge of the key) is "secure". And it is an open question whether any such cipher exists.
>You *could* hit the right key with your first trial encryption, or you could completely exhaust the keyspace before finding the key.
:-) Anything that can be guessed can be guessed on the first try. While you might get lucky on a few keys, statistics suggest that you'll have to compare half the keys on average: 2^(N-1). I realize that you already understand that, but I'm just trying to explain for the rest of the slashdotters.
Such is the nature of NP.
Now I'm going to switch gears and try to drive home the point that that RC5 can probably be cracked a lot faster than brute force.
Remember: All problems in NP are polynomially related to one another (* it's conjectured that all problems in NP are linearly related to one another), and the optimization problem related to every NP decision problem only has to call said decision problem a poly (linear) number of times. Thus, anything that can be guessed can be fully solved in a polynomial number of calls to an NPC solver. The best NPC (decision) solvers run in 2^sqrt(N).
Consider the solver for an optimization problem that works by reducing to an NPC decision problem and iterating until it has the optimized result (i.e. the encryption key). This runs in f(N) + poly(N) * 2^sqrt(f(N)) = O(2^(sqrt(f(n)) + O(logN))) = O(2^O(sqrt(f(N))). If the polynomial reduction function f(N) is less than N^2, then our method runs faster than brute force (i.e. 2^N). Typically you'll be able to find a reduction that's N or N*logN; if such a reduction exists, someone will find it. And when they do, RC5 will not require a brute force search.
Never assume any problem in NP requires a brute force search. Instead, you should assume it can be solved in 2^sqrt(N) or better.
Never assume any problem in NP requires a brute force search. Instead, you should assume it can be solved in 2^sqrt(N) or better.
Under this assumption all modern symmetric ciphers are untrustworthy. Even with 256-bit keys, this would provide an upper bound complexity of 2^16. If there were a good way of finding f(N) for a given NPC problem, I guess we wouldn't necessarily have to abandon encipherment entirely, but we would need some truly enormous keys... and the "or better" part of your statement tends to imply that may not be enough. The crypto geek in me quivers, but the programmer in me wonders what sorts of *other* optimization problems we could solve if we had such tools...
For the present, of course, RC5 (and 3DES, and AES, and Twofish, and...) are considered secure not because it's provably impossible to break them faster than brute force, but because lots of very smart people have tried and failed. That's likely where we'll always be, I suspect :-)
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
>Even with 256-bit keys...may not be enough
.. 255 rounds), each of which would be linear in the size of the key. In this proposal our f(N) is O(N); however, the constant hidden by the Big-Oh notation is fairly large.
;-)
I've been studying NP completeness for a while, and I believe that P < NP < EXP. In other words, I believe that every problem in NP can be solved in less than exponential time, but the hardest problems in NP (i.e. NPC) will never be solved in polynomial time. Mark my words: within the next 5 years, someone will publish a 2^polylog(N) solution for an NPC problem. The day after that happens, all cryptography based on "small" keys will be broken.
Based on my reading of the FAQ on the RSA website, it appears that the complexity of RC5 is created by rounds; however, the rounds are not related to the key size. Bonus: the only operations mentioned are addition, xor and rotation, all of which can be performed in linear time. Proposal: construct 256 different SAT circuits (representing 0, 1, 2,
Once you've got the SAT circuits, simply run the optimization method I described earlier, and you have a RC5 solver that runs in O(2^O(sqrt(N))). Granted: the reduction idea I've presented here may have constants so large that the solver would not actually improve the cracking performance on RC5-64, though it might allow RC5-2040 to be cracked in a reasonable timeframe on today's hardware.