Register to reply

RSA640 factored

by aravindsubramanian
Tags: factored, rsa640
Share this thread:
aravindsubramanian
#1
Nov8-05, 05:03 AM
P: 23
Franke et al. factored RSA640 using GNFS


RSA640 31074182404900437213507500358885679300373460228427275457201619488232064 40518081504556346829671723286782437916272838033415471073108501919548529 007337724822783525742386454014691736602477652346609


The Factors are

16347336458092538484431338838650908598417836700330\
92312181110852389333100104508151212118167511579

and

19008712816648221131268515739354139754718967899685\
15493666638539088027103802104498957191261465571
Phys.Org News Partner Science news on Phys.org
Security CTO to detail Android Fake ID flaw at Black Hat
Huge waves measured for first time in Arctic Ocean
Mysterious molecules in space
jim mcnamara
#2
Nov8-05, 08:40 AM
Sci Advisor
PF Gold
P: 1,381
Do you have a link?
Zurtex
#3
Nov8-05, 10:08 AM
Sci Advisor
HW Helper
P: 1,123
http://mathworld.wolfram.com/news/2005-11-08/rsa-640/

mathwonk
#4
Nov8-05, 12:23 PM
Sci Advisor
HW Helper
mathwonk's Avatar
P: 9,453
RSA640 factored

pardon me, but why is that interesting?
shmoe
#5
Nov8-05, 12:51 PM
Sci Advisor
HW Helper
P: 1,995
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
#6
Nov8-05, 03:24 PM
P: n/a
How does GNFS and QNFS work?
jim mcnamara
#7
Nov8-05, 03:34 PM
Sci Advisor
PF Gold
P: 1,381
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
#8
Nov8-05, 03:55 PM
P: n/a
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
#9
Nov8-05, 03:59 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,092
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
#10
Nov8-05, 06:49 PM
Sci Advisor
HW Helper
mathwonk's Avatar
P: 9,453
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-
#11
Nov8-05, 09:56 PM
Sci Advisor
-Job-'s Avatar
P: 1,132
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
#12
Nov8-05, 11:56 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,092
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
#13
Nov9-05, 09:19 AM
Sci Advisor
HW Helper
P: 1,995
Quote Quote by mathwonk
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).

Quote Quote by jim mcnamara
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).


Register to reply

Related Discussions
Can this trinomial be factored? Precalculus Mathematics Homework 6
RSA-200 Factored Linear & Abstract Algebra 13
Largest n had been factored Linear & Abstract Algebra 5