RSA640 factored

  1. Franke et al. factored RSA640 using GNFS


    RSA640 3107418240490043721350750035888567930037346022842727545720161948823206440518081504556346829671723286782437916272838033415471073108501919548529007337724822783525742386454014691736602477652346609


    The Factors are

    16347336458092538484431338838650908598417836700330\
    92312181110852389333100104508151212118167511579

    and

    19008712816648221131268515739354139754718967899685\
    15493666638539088027103802104498957191261465571
     
  2. jcsd
  3. jim mcnamara

    jim mcnamara 1,517
    Science Advisor
    Gold Member

    Do you have a link?
     
  4. Zurtex

    Zurtex 1,123
    Science Advisor
    Homework Helper

  5. mathwonk

    mathwonk 9,761
    Science Advisor
    Homework Helper

    pardon me, but why is that interesting?
     
  6. shmoe

    shmoe 1,994
    Science Advisor
    Homework Helper

    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).
     
  7. How does GNFS and QNFS work?
     
  8. jim mcnamara

    jim mcnamara 1,517
    Science Advisor
    Gold Member

    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.
     
  9. 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?
     
  10. Hurkyl

    Hurkyl 16,089
    Staff Emeritus
    Science Advisor
    Gold Member

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

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

    http://en.wikipedia.org/wiki/Dixon's_algorithm
     
    Last edited: Nov 8, 2005
  11. mathwonk

    mathwonk 9,761
    Science Advisor
    Homework Helper

    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.
     
  12. -Job-

    -Job- 1,132
    Science Advisor

    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. :smile:

    [when i say 1 computation i mean constant # of computations O(1), which would take considerably less than a second]
     
    Last edited: Nov 8, 2005
  13. Hurkyl

    Hurkyl 16,089
    Staff Emeritus
    Science Advisor
    Gold Member

    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!
     
  14. shmoe

    shmoe 1,994
    Science Advisor
    Homework Helper

    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).
     
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?