Pirmieji „faktorizavimo fabriko“ bandymai sumušė milžiniškų skaičių skaidymo į pirminius skaičius rekordą. Vieną dieną tai gali priversti kompanijas sustiprinti savo internetinį šifravimą.

Visi ne pirminiai skaičiai gali būti sudaryti iš pirminių skaičių sandaugos. Kriptografiniai algoritmai išnaudoja faktą, kad didelių skaičių šios sandaugos atgaminimas, kitaip faktorizavimas, yra labai sudėtingas. Nauji faktorizavimo metodai bandomi didžiuliais „RSA skaičiais“, kurių kiekvienas yra sandauga dviejų pirminių skaičių, žinomų tik šifravimo firmai RSA Security.

Kiekvieno RSA skaičiaus faktorizavimas reikalauja didžiulių pastangų, sako Arjen Lenstra iš Šveicarijos Federalinio technologijų instituto Lausanne'oje, tad jis su kolegomis sukūrė faktorizavimo fabriką, galintį vienu metu nagrinėti daug skaičių.

Ši technika, pasiūlyta dešimtajame XX a. dešimtmetyje, palengvina užduotį, paskaičiuodama daugybę lygčių, tinkančių visiems skaičiams, į kuriuos taikomasi, o tada su kiekvienu skaičiumi atlikdama skaičiavimus. Technikos bandymas su RSA skaičiais dabar pernelyg sunkus, tad Lenstra ėmėsi Merseno skaičių, kuriuos faktorizuoti šiek tiek lengviau.

Komanda pradėjo 17 šių skaičių puolimą 2010 m. Dabar jie jau sufaktorizavo 10 iš jų, sugaišę 2000 metų aukštos klasės kompiuterio darbo ekvivalentą – maždaug 50% greičiau, nei atliekant kiekvieną atskirai. Didžiausias faktorizuotas skaičius buvo 2¹¹⁹³-1, ir tai yra rekordas (Cryptology ePrint Archive, eprint.iacr.org/2014/653).

Tai maždaug toks pats dydis, kaip 1024 bitų RSA skaičiai, naudojami dabartiniame šifravime – 1024 yra jų dvinarės formos ilgis, – kuriuos labai sunku apskaičiuoti. Anksčiau standartiniai buvo daug mažesni, 512 bitų skaičiai, bet 1999 metais Lenstra vieną jų nulaužė, ir tai prisidėjo prie standarto perėjimo prie 1024 bitų šifravimo. Šis naujausias darbas gali vėl pastūmėti reikalus, sako Lenstra, bet kol kas jaudintis dėl savo internetinio saugumo dar nereikia.

Išsamesnė straipsnio versija

Jacob Aron
New Scientist № 2985

Komentarai (0)