GNFS Factorization of RSA640 by Franke et al.

[aravindsubramanian]

Franke et al. factored RSA640 using GNFS


RSA640 3107418240490043721350750035888567930037346022842727545720161948823206440518081504556346829671723286782437916272838033415471073108501919548529007337724822783525742386454014691736602477652346609


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 a lot 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]

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?

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

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

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