Slashdot Mirror

← Back to Stories (view on slashdot.org)

A Mighty Number Falls

Posted by kdawson on from the time-to-generate-new-keys dept.

space_in_your_face writes "An international team has broken a long-standing record in an impressive feat of calculation. On March 6, computer clusters from three institutions (the EPFL, the University of Bonn, and NTT in Japan) reached the end of eleven months of strenuous calculation, churning out the prime factors of a well-known, hard-to-factor number — 2^1039 - 1 — that is 307 digits long." The lead researcher believes "the writing is on the wall" for 1024-bit encryption. "Last time, it took nine years for us to generalize from a special to a non-special hard-to factor number (155 digits). I won't make predictions, but let's just say it might be a good idea to stay tuned."

4 of 348 comments (clear)

  1. Re:What are they? by Anonymous Coward · · Score: 5, Informative

    2^1039-1=
    1159420574 0725730643698071 48876894640753899791 70201772498686835353882248385
    9966756608 0006095408005179 47205399326123020487 44028604353028619141014409345
    3512334712 7396798885022630 75752809379166028555 10550042581077117617761009413
    7970787973 8061870084377771 86828680889844712822 00293520180607475545154137071
    1023817

    factors:

    5585366661 9936291260 7492046583 1594496864
    6527018488 6376480100 5234631985 3288374753
    ×
    2075818194 6442382764 5704813703 5946951629
    3970800739 5209881208 3870379272 9090324679
    3823431438 8414483488 2534053344 7691122230
    2815832769 6525376091 4101891052 4199389933
    4109711624 3589620659 7216748116 1749004803
    6597355734 0925320542 5523689

    (spaces added because of lameness filter)

  2. Re:Next step: FPGA cracking by shofutex · · Score: 5, Informative

    Adi Shamir designed one already. Instead of 11 months, it takes 12--but it could (in theory) factor any 1024-bit number.

  3. Re:"the writing is on the wall" for 1024-bit by Palmyst · · Score: 5, Informative

    Yes, The RSA Algorithm for public key encryption is based on the difficulty of factoring very large numbers. The key size is the number of bits in the number that has to be factored to break the encryption. Many of the modern security systems, including Verisign certificates for secure websites are based on RSA encryption and 1024 is a very common key size in use. Thus the ease of factoring 1024 bit numbers would indeed be a matter of concern.

    RSA 101.

  4. Damn, beaten, somewhat. by DemonThing · · Score: 5, Informative

    There are actually three prime factors; the two you listed, and the small factor 5080711. Thus:

    2^1039-1 = 5080711 * 55853666619936291260749204658315944968646527018488 637648010052346319853288374753 * 20758181946442382764570481370359469516293970800739 52098812083870379272909032467938234314388414483488 25340533447691122230281583276965253760914101891052 41993899334109711624358962065972167481161749004803 659735573409253205425523689

    is the correct factorization, as can be readily verified.

    Also:
    http://www.heise.de/english/newsticker/news/90031