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.
-Not always true. Say I can come up with a 2048 bit encryption, that is just increase the key size from 256 to 2048, I can to that in a second. It is going to take _a lot more time_ for the computing power to overcome that increase.
If quantum computing will come around, I'll just switch to quantum encryption. Then you'll have to break the laws of QM to "break" the scheme. There are already rudimentary quantum encryption devices but there are no quantum computers that can take on even a 64 bit key space.
The best bet instead of brute force is to do "human engineering" and look for other ways to obtain the information. The inherent math of the algorithm is rarely the weakest link, it is the people and then the particular implementations of the algorithms that are exploited the most.
However what if that team had decrypted a banks RSA key. Sure it may have taken 5 months and the bank may well have changed keys since. But what if they captured all the packets sent/recieved using the cracked key. I guarentee there would be a bit of useful information in them. I know I don't change account numbers / credit card numbers every 5 months.
From a security point of view, "less than five seconds on modern hardware" is absolutely unnecessary. After a transmission has been intercepted, and we work under the assumption that essentially all of them are these days, that transmission has to remain secure potentially for a very, very long time (sure, an encrypted radio communication might have no operational significance in two hours -- an encrypted dossier of a field agent had better stay secure until he's dead, and an encrypted report on security breaches in US nuclear command&control protocols better stay unbroken for the better part of the next century). And what takes a beowulf cluster of supercomputers 5 months to do today will be possible to crack on a botneck in less than a week by 2010, I guarantee you (I write distributed applications for a living and worked with a three-letter agency which was rather miffed that a competing TLA had the existence of their own internal distributed cracker leaked to the press back in 2002 or so). A couple years after that it will be a few minutes on dedicated hardware and a few years after that a desktop machine will smash it as a matter of course. Events like this are warning flares to people with serious security needs that you need to start transitioning to harder codes or longer key lengths.
Help poke pirates in the eyepatch, arr.
And will not be, unless P=NP, or we use some form of new computers.
Factoring is almost certainly not NP-hard. It could very well be that P != NP, and yet factoring is easy.
this shows security is process then of a black box sloution ...lol
The 'encryption' does take place - it is encoding information using quantum states (so far photon polarization or particle entanglement) which would make eavesdropping detectable. Imagine encrypting a file and then everytime someone tries to decrypt it, it will actually change the file itself and you cannot make copies.
Also, if you say that what quantum encryption only does is help detect eavesdroppers, I could also claim that the public key distribution schemes also mostly "do nothing but" help distribute keys for further communication in a 'safe way'.
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.
Although it's identical to the issue that the UK police claim they currently have. Which is why they want 90 days to lock citizens up without charge while they 'factor' their hard-drives.
I realize you were joking, but I'd like to respond anyway.
RSA keys are based on having two large prime numbers whose product is then difficult to factor. In general, the larger these numbers are, the harder it is to factor: trial division is O(sqrt(n)), and even the best methods of factoring are still of increasing time for increasing numbers. Using a general method, a 1.44mb key would take a LONG time to factor. However, there is one very important caveat...
If you go high enough, people don't know very many primes. In fact, there are lists of the largest known primes. I'd wager that there are less than a few thousand known primes greater than 2^720k, probably a lot less. This means that if you have a 1.44Mb number which you know to be the product of two primes, then either you can do trial divisions from a short list to factor the number, or else someone has discovered a new large prime.
In short, if you have a large enough key, the task of generating primes is difficult enough that factoring becomes much easier. To give you an idea of how difficult finding primes is, n has about a 1/(ln n) chance of being prime, and using a specialized algorithm, it takes about a day to check a mersenne number of this size for primality. General algorithms are, of course, slower. This means that, to perhaps an order of magnitude or two, it would take about million 1Ghz computer days to find two new suitible primes to multiply together. Of course, if you do this, its not likely that someone will crack your key without a quantum computer, but its also not likely that you will find a key pair until quantum computers are widespread.
I guess if you want big keys like that, you should look into eliptic curves. At least by the time you generate a key, there is a chance that it won't be trivial to break!
Sorry to break it to you boys but I know an algorithm that can do that in constant time
Sorry to spoil your answer, but just returning the prime number as output requires time that is logarithmic in the size of the prime, not constant (one step for each digit in the answer).
The only way to prove that a number is prime is to prove that it has no factors other than one and itself. Once you have proven that a number is prime than clearly you can factor it in constant time, but that's hardly impressive. Factor 32805592099748442548107420314645062399211606732283 97988106903434895134644511401975437619140698905949 45251948581425823146167636637467081207415218524627 02588083274954144328560376197355667343748447038499 56013739736469532109844544298776968942978978890220 34799326380695035625184794996536629337396640718552 25483719779649039616697060568502684734994955621508 03425209326447449946707724181021885226359431271227 10612401241669525952545358847814155202494892941888 32211842157911715344812739811606414850139336562428 90390457916792222939860320591041870758622733339305 63236338155282341943896540996586475435821049572165 62303277296229480468077667511380363488470015931141 68160373304535957389399079461511868362789851845537 09439246752539740109055794552962678403088798522051 82796574842175841102587473888251717732920982403724 53997665644480984113047103511360106063909010618595 47228609572651064383396563278829228488848257724585 62691141677028588001666708376672267165525578357382 80866039175470150006085403549022233305729196059999 and let us know what you find.
80 Opterons = 5 Months
288,000 Opterons = 1 second.
think Seti at home