RSA640 factored

aravindsubramanian

Franke et al. factored RSA640 using GNFS


RSA640 31074182404900437213507500358885679300373460228427275457201619488232064 40518081504556346829671723286782437916272838033415471073108501919548529 007337724822783525742386454014691736602477652346609


The Factors are

16347336458092538484431338838650908598417836700330\
92312181110852389333100104508151212118167511579

and

19008712816648221131268515739354139754718967899685\
15493666638539088027103802104498957191261465571

jim mcnamara

Do you have a link?

Zurtex

http://mathworld.wolfram.com/news/2005-11-08/rsa-640/

mathwonk

pardon me, but why is that interesting?

shmoe

It has mass appeal for a few reasons, anyone can understand the problem of factoring and it is related to cryptography, which is always popular. The RSA number factored represents the "most successful" applications of the known general algorithms, so there's also some interest in what the algorithms can actually do in practice (though arguably this is not nearly as interesting as the math behind the various algorithms themselves). It's also an indicator of how secure RSA itself is with moduli of a given size (though obviously no one would go to the trouble of factoring a number of this size to steal your grandma's cookie recipe, unless it's really good).

finchie_88

How does GNFS and QNFS work?

jim mcnamara

Mr Wonk, sir:

It effects the practicality of choosing/not choosing RSA keys of a given size. If you are a professional programmer, you need to be aware of this stuff as well. Think of it as an attempt at making the direct deposit of your paycheck secure - or your ATM transactions secure.

This was "640 bit security" - your paycheck is moved over the (ACH system in the US) wires to your bank account with-- at a maximum -- "256 bit security".

While shmoe is right that the math is interesting, the development of factorization algorithms can be fun too.

finchie_88

I did a lil research on the net, and couldn't really find any thing particularly detailed on the subject (wikipedia as a good bit on it, but a lil more would be nice), or examples of it in use, so I was hoping that someone might be able to tell me somewhere where there is more info on the details, or even better, explain some of the details in this thread. Also, how do they develop these algorithms, where do they start?

Hurkyl

RSA with a 640-bit prime does is not equivalent security-wise to other algorithms with 640-bit cryptovariables.

For those who want to learn about these, you might want to start with this:

http://en.wikipedia.org/wiki/Dixon's_algorithm

mathwonk

thank you.

isn't it relevant to know how long it took to factor this number, and how much computing power, i.e. time and money, to measure the feasibility of such a task by a run of the mill hacker?

also notice that the factors are roughly the same size, which is a big clue to any would be factorer.

-Job-

http://en.wikipedia.org/wiki/Integer_factorization

"As of 2005, the largest semiprime factored using general-purpose methods as part of public research is RSA-200, which is 663 bits long. This was done using a network of computers running in parallel between Christmas 2003 and May 2005, and used very approximately 75 years total computer time. The method used was the general number field sieve."

It's not an unexpensive computation. I imagine that it's best if the factors have the same number of bits because it increases the possible number of combinations. Factors with similar number of digits actually make it harder, it's alot better than having a huge factor and another one of 4 digits. This way i just try all 10^4 combinations to find the smaller factor and easily obtain the other one.

It's worthwhile to mention that a quantum computer would be able to factor any sized RSA number in one computation. As a matter of fact, with just 1000 qubits, the size of the RSA number could have more digits then there are particles in the universe and it wouldn't make a difference. I find that to be cool.

[when i say 1 computation i mean constant # of computations O(1), which would take considerably less than a second]

Hurkyl

Of course, it's bad to have them too close, but with numbers that big, just having a 1% difference between them is an unimaginably huge range!

shmoe

Absolutely and I'd expect more details about RSA-640 shortly. I'd guarantee that more computing power went into it than your average bloke has access to. Resources of potential attackers would be a factor in determining the level of security required (as well as sensitivity of the data, how long it remains sensitive, and other factors).

For sure. New algorithms much are more exciting than modifications or slight improvements of old ones. More success based on more computing power and old algorithms has no mathematical interest, but still of some interest (to me).



There's a nice survey article “A Tale of Two Sieves”, Notices of the AMS 43, no. 12 (1996), 1473–1485 by Pomerance that might be of interest to finchie_88 (and others). It can be found at the AMS website (you'll have to create an account which is free). There are plenty more resources online such as Menzies "Handbook of Applied Cryptography" which has the details of many factoring algorithms (though not the gnfs).