Výskumníci zlomili 768-bitový RSA kľúč, finančne rentabilne

DSL.sk, 8.1.2010

Kombinovaný tím trinástich výskumníkov z oblasti počítačovej bezpečnosti vo štvrtok oficiálne informoval o zlomení konkrétneho 768-bitového RSA kľúča, najväčšieho doteraz zlomeného RSA kľúča.

Pri používaní asymetrického šifrovacieho algoritmu RSA sa v súčasnosti ešte bežne používa, napríklad v certifikátoch pre SSL, 1024-bitový RSA kľúč, hoci od roku 2011 je odporúčaný už prechod na dlhšie kľúče.

Tím zlomil konkrétny kľúč, ktorý publikovala v minulosti spoločnosť RSA Security v rámci verejnej výzvy na zlomenie RSA kľúčov rozličnej dĺžky. Kľúč bol zlomený 12. decembra 2009.

Verejnú časť RSA kľúča tvorí najmä veľké v tomto prípade 768-bitové číslo, ktoré je po rozložení na prvočísla súčinom len dvoch veľkých prvočísel. Sila algoritmu RSA je založená na skutočnosti, že známe algoritmy pre rozloženie veľkého čísla na súčin jeho prvočísel majú vysokú výpočtovú zložitosť.

K zlomeniu kľúča a teda nájdeniu dvoch prvočísiel, ktorých súčinom je prelamovaný RSA kľúč, bola použitá metóda Number Field Sieve s viacerými optimalizáciami.

Výpočet na niekoľkých stovkách procesorov trval celkovo spolu viac ako dva a pol roka, celkovo vyžadoval 10 ^ 20 operácií a napríklad na jednom jednojadrovom 2.2 GHz AMD Opteron procesore by bol uskutočniteľný podľa výskumníkov za približne 2000 rokov.

Útočníci môžu napríklad pri SSL protokole uchovávať odchytené šifrovnané dáta a aj neskoršie zlomenie RSA kľúča im umožňuje následne dešifrovať prenášané dáta. Pre najzávažnejšie praktické útoky je dostatočnou dobou na získanie kľúča rádovo pol roka, keď napríklad kľúče v SSL certifikátoch sa menia približne po roku. Takto rýchle získanie kľúča by umožnilo ešte aj aktívne útoky s predstieraním identity napríklad banky bez spozorovania klientom.

Podľa našich prepočtov by bolo možné dosiahnuť potrebný výpočtový výkon a teda zlomiť 768-bitový RSA kľúč za pol roka približne s 250 dvojprocesorovými servermi s modernými 6-jadrovými procesormi s cenou rádovo 250 tisíc dolárov. Náklady na elektrickú energiu by predstavovali rádovo 50 tisíc dolárov, celkové finančné náklady so započítaním približne tretiny ceny znovupoužiteľného hardvéru je možné odhadnúť na 150 tisíc dolárov.

Podľa výskumníkov vyžaduje zlomenie 1024-bitového kľúča približne 1000-násobne náročnejší výpočet ako v prípade 768-bitového kľúča. Zlomenie 1024-bitového kľúča dostatočne rýchlo by tak samozrejme pri použití x86 hardvéru zatiaľ nebolo rentabilné ani prakticky realizovateľné s potrebnými 250 tisíc servermi.

Nie je jasné nakoľko efektívne by bolo možné preniesť optimalizovaný algoritmus Number Field Sieve na GPU, ktoré poskytujú rádovo 50-krát vyšší hrubý výpočtový výkon pri rovnakej cene a o niečo vyššej spotrebe. Ak by to bolo možné so stopercentným využitím výkonu GPU, so súčasnými technológiami by zlomenie 1024-bitového kľúča mohlo stáť zatiaľ stále rádovo 3 milióny dolárov.

Dokument popisujúci zlomenie 768-bitového RSA kľúča je možné sťahovať z tejto stránky.


Najnovšie články:



Diskusia:

kvanta a kvanta vykonu Od reg.: OmeGa | Pridané: 8.1.2010 9:58 ked za 20 rokov vytiahneme z vrecka kvantovy mobil, tak budeme luskat RSA-cka uz len zo srandy za par sekund, uz sa tesim, a som zvedavy co chcu pouzit v pripade rozsirenia kvantovych cpu's Odpovedať Známka: -4.6 Hodnotiť:

Re: kvanta a kvanta vykonu Od reg.: Pjetro de | Pridané: 8.1.2010 10:06 Tak za 20 rokov kvantovy mobil z vacku nevytiahnes. Raz mozno, ale za 20 rokov asi nie. Za 20 rokov vytiahnes mobil s vykonom mozno 1 000 000-krat vacsim ako dnes (realne tipujem skor "iba" 100 000-krat vacsim ci dokonca iba 10 000-krat), pokial to Mohrov zakon dovoli, ale kvantovy asi este nebude - cca kazdu jednu dekadu sa vykon CPU zvysi asi 100-krat a kapacita diskov az 1000-krat, za 2 dekady teda desattisic a milion krat. Odpovedať Známka: 4.2 Hodnotiť:

Re: kvanta a kvanta vykonu Od: Deer | Pridané: 8.1.2010 20:45 Sam si odporujes - tie tvoje pocty (Moorov zakon) platia pre kremikove procesory. Kvanove CPU su uz tu a do 20 rokov bude mozno taky jeden (56qb kripel vyrobeny z 128qb :) aj na Slovensku. V ten moment stupne vypocetny potencial SR o 10000 radov, cize uplne mimo Moorov zakon. Odpovedať Známka: 6.0 Hodnotiť:

Re: kvanta a kvanta vykonu Od: 2Mino | Pridané: 8.1.2010 21:01 Nato, abz som si zlomil hociaký kľúč, na to ani nepotrebujem byť výskumník a ani mať superpočítač. Stačí mi vypiť si, a zlomím vo dverách hociaký kľúč aj na počkanie... Odpovedať Známka: 5.8 Hodnotiť:

Re: kvanta a kvanta vykonu Od: waveeee | Pridané: 9.1.2010 16:47 ak sa veci nevhodne vyvynu a bude sa pocitat s "butterfly efektom" mozno budeme za 20 rokov pouzivat silon, zapalku a téglik od jogurtu =) Odpovedať Známka: 10.0 Hodnotiť:

Re: kvanta a kvanta vykonu Od reg.: Pjetro de | Pridané: 9.1.2010 9:01 Neodpurujem si, Moohrov zakon som totiz aplikoval cisto na IT v dnesneh podobe, nie na kvantovu eru. Ked kvantova era pride, zakony IT sa zmenia. Odpovedať Známka: 10.0 Hodnotiť:

Re: kvanta a kvanta vykonu Od: k2k | Pridané: 9.1.2010 10:35 ak by sme na to pocitanie isli podla zakona o zdvojnasobeni vykonu za pol roka a predpokladu ze sa tempo nezmeni(ani nezrychly ani nezpomaly) a predpokladu ze sa nepodary vynajst nieco co posunie technologie skokom dopredu tak mozeme pocitat 20 rokov = 40 polrokov a kazdy polrok je 2krat vykonnejsi komp 2^40 = 1 099 511 627 776 teda vykon by mal byt 10^12krat vacsi Odpovedať Hodnotiť:

Re: kvanta a kvanta vykonu Od reg.: Pjetro de | Pridané: 9.1.2010 18:04 1) pise sa nezrychli/nespomali - v prvom slove 1 chyba v druhom 2 chyby - NEPOCHOPITELNE AKO NIEKTO TAKTO NEMOZE OVLADAT VLASTNU MATERINSKU REC !!!!!!! 2) Mohrov zakon presiel jemnymi modifikaciami, resp. korekciami casu, kedy sa vykon a kapacita zdvojnasobi - v sucasnosti je to cca 18 mesiacov, neviem co bluznis o 6. mesiacoch, tak Mohrov zakon nikdy neznel Odpovedať Známka: 5.0 Hodnotiť:

Re: kvanta a kvanta vykonu Od reg.: Pjetro de | Pridané: 8.1.2010 10:11 Na druhej strane uvaha je to zaujimava, ked dnesne supervykonne PC by nieco take pocitalo 2500 rokov a hypoteticke kvantove PC (nechavajuce za sebou trapne polynomicky efektivne algoritmy) niekolko minut/hodin. Asi by zacali casy 10kiloveho RSA, 100 kiloveho RSA, megoveho RSA (1048576 bitoveho), gigoveho RSA (1073741824 bitoveho), teroveho RSA (1099511627776 bitoveho) ... Pride mi dnes ale divne mat tak dlhy kluc ... mozno za 100 rokov to divne nebude. Odpovedať Známka: 6.2 Hodnotiť:

Re: kvanta a kvanta vykonu Od reg.: Pjetro de | Pridané: 8.1.2010 10:19 Chcelo by to ale hladat dvojicu priblizne rovnako velkych niekolko milion ci miliard cifernych prcovislel, aby sme take gigove ci terove RSA mohli pouzivat. No nadhera. A nemali by to byt samozrejme nejake specialne prvocisla, ale uplne chudence, nijako sa nevymikajuce napr. ako Mersennove prcvosisla, kt. je ako safranu, maju specialny tvar a su to najvacsie zname prvocisla vobec. Odpovedať Známka: 10.0 Hodnotiť:

Re: kvanta a kvanta vykonu Od reg.: __Ondrej | Pridané: 8.1.2010 10:23 Mozno budu pouzivat nieco co sa tazsie dekoduje ako exponencialne. Napriklad so zlozitostou n na n, alebo aj vyssou. Odpovedať Známka: 8.2 Hodnotiť:

Re: kvanta a kvanta vykonu Od reg.: Pjetro de | Pridané: 8.1.2010 11:51 aj to je riesenie, n^n rastie rychlejsie ako a^x ci n! Odpovedať Známka: 10.0 Hodnotiť:

Re: kvanta a kvanta vykonu Od: neznalec | Pridané: 8.1.2010 13:39 tak sa prejde na nieco ine ako rsa.. su aj ine tazke problemy ako fakorizacia, napr diktretny logaritmus alebo elpiticke krivky... a ktovie co este matici vymyslia... Odpovedať Známka: 7.1 Hodnotiť:

Re: kvanta a kvanta vykonu Od: super | Pridané: 8.1.2010 20:26 2,2 Gigové AMD považuječ za supervýkonný počítač? Odpovedať Známka: -7.1 Hodnotiť:

Re: kvanta a kvanta vykonu Od: ...................... | Pridané: 8.1.2010 11:17 No keby se ho hned aj vytiahli, tak pri kvantovom dekryptovani bude aj kvantove kryptovanie a to je podl a momentalneho poznania povazovane za konecne a nedekryptovatelne :)... Odpovedať Známka: 10.0 Hodnotiť:

Re: kvanta a kvanta vykonu Od: 123s | Pridané: 9.1.2010 3:05 trocha paranoje: aj to bude asi jeden s problemov preco sa kvantove PC tak rychlo nerozsiria, aspon do doby kym nebudu mat zase nieco rychlejsie Odpovedať Hodnotiť:

RSA... Od reg.: Pjetro de | Pridané: 8.1.2010 10:02 http://www.dsl.sk/article.php?article=8554 Pjetro de | Pridané: 7.1.2010 16:58 Odpovedať Známka: -4.3 Hodnotiť:

Re: RSA... Od: aleluja | Pridané: 8.1.2010 10:43 neni tam nic take Odpovedať Známka: 10.0 Hodnotiť:

Re: RSA... Od reg.: Pjetro de | Pridané: 8.1.2010 12:02 tak soryy, http://www.dsl.sk/article.php?article=8549 Odpovedať Známka: 10.0 Hodnotiť:

casova zlozitost Od reg.: _MMx_ | Pridané: 8.1.2010 10:24 Poslusne hlasim ze rozlozenie (lubovolneho) cisla na sucin jeho prvocisel nema exponencialnu zlozitost. 1. Sice nie je znamy polynomialny algoritmus, to ale neznamena ze neexistuje (a teda z toho nejde robit zavery o zlozitosti). 2. Existuje algoritmus so zlozitostou O((1+ε)^b) pre vsetky kladne ε a pre nejaku konstantu b, co je lepsie ako exponencialne. Odpovedať Známka: 10.0 Hodnotiť:

Re: casova zlozitost Od reg.: __Ondrej | Pridané: 8.1.2010 10:36 Docital som sa, ze tento problem je z triedy FNP. http://en.wikipedia.org/wiki/FNP_%28complexity%29 Odpovedať Známka: 10.0 Hodnotiť:

Re: casova zlozitost Od reg.: Redakcia DSL.sk | Pridané: 8.1.2010 10:52 Díky, opravené. Odpovedať Známka: 7.3 Hodnotiť:

Re: casova zlozitost Od reg.: Pjetro de | Pridané: 8.1.2010 12:01 dovolim si reagovat: 1) To je samozrejme - to ze nieco este nie je najdene, neznamena to, ze to neexsituje, napr. diofanticka trojica cisel a, b, c splnajuca rovnost a^3 + b^3 = c^3. az vseobecny dokaz ukazal ze taka trojica cisel neexistuje pre ziadny exponent vacsi ako 2 (velka fermatova veta) 2) Ak (1+epsilon)^b, kde epsilon > 0, ale kto santil s analyzou tak vie ze sa tym mysli veeeeeeeeeeeeeelmi male kladne ciselko, t.j. k nule velmi blizko sprava a b je realne cislo. Potom 1+espislon bude > 1, veeeeeeeeelmi malinko vacsie ako 1, ale vacsie ako 1. oznacme ci ho a. b realne preznacme na x (aka trufalost!). Coze to prislo na svet: a^x, kde a > 1 a x je realne. A to ze by nebola exponencialna funkcia? Ano zaklad ma skur.... neslusne maly, to je pravda, ale to neodobera punc exponencialnosti. Odpovedať Známka: 6.0 Hodnotiť:

Re: casova zlozitost Od reg.: Pjetro de | Pridané: 8.1.2010 12:06 Samozrejme z eponencialnych sestier a^x sme mysleli tu, kde 1<a, teda tu rastucu. Jej jednovajecna sestra ma zaklad 0<a<1, ale je klesajuca, co je nam na prd, kedze chceme rast :-) Odpovedať Známka: 10.0 Hodnotiť:

Re: casova zlozitost Od reg.: Pjetro de | Pridané: 8.1.2010 12:10 pri a^x je jedno ako blizko je zaklad "a" k jednotke, vzdy to bude exponencialna svina (ktorej sa boja aj derivacie) Odpovedať Známka: 10.0 Hodnotiť:

Re: casova zlozitost Od reg.: __Ondrej | Pridané: 8.1.2010 12:18 Tiez si dovolim reagovat. Nikto zatial este nedokazal ci P = NP, alebo nie. Keby P = NP, tak to nie je exponencialne ale polynomialne. Ty si hovoril o zlozitosti existujuceho algoritmu, ale moze sa najst aj lepsi. Teoria zatial nevylucuje moznu polynomialnost problemu. Odpovedať Známka: 10.0 Hodnotiť:

Re: casova zlozitost Od reg.: Pjetro de | Pridané: 8.1.2010 12:20 presne :-) nejsou dukazy, nejsou vedomosti, nejsou na to lidi :-) Odpovedať Známka: 10.0 Hodnotiť:

Dolár Od reg.: Spiro | Pridané: 8.1.2010 10:26 Prečo je aj elektrina počítaná na doláre? "MY" sme Slováci nie? Alebo som si nevšimol citáciu? Odpovedať Známka: 0.0 Hodnotiť:

Re: Dolár Od: featherl1ght | Pridané: 8.1.2010 15:34 aj dlh SR je pocitany na USD, so Slovakmi to nema nic spolocne, je to medzinarodna mena, za toto si nezasluzia kritiku, skor by som rypal za to, ze niekedy clanky na dsl.sk(hlavne nadpisy) vyzeraju ako prelozene cez google translate, na tom by mali trosku popracovat, ked uz teda si hovoria redaktori :) Odpovedať Známka: 10.0 Hodnotiť:

Kvantove pocitace Od: _YA_NN_ | Pridané: 8.1.2010 10:31 Ked budu kvantove pocitace tak budu aj kvantove sifry. Takze lamanie sifier za par sekund sa konat nebude. Odpovedať Známka: 10.0 Hodnotiť:

Re: Kvantove pocitace Od: jggggg | Pridané: 8.1.2010 10:37 pokrok a heavy metal nezastavis :D Odpovedať Známka: 8.5 Hodnotiť:

Re: Kvantove pocitace Od: Kapor z Vane | Pridané: 8.1.2010 10:55 Power Button: Off == PANIC! Odpovedať Známka: 8.6 Hodnotiť:

Re: Kvantove pocitace Od: SPX | Pridané: 8.1.2010 12:26 ale on si bude lamat sifry 20rokov stare Odpovedať Známka: 10.0 Hodnotiť:

gramatik Od: jjsanko | Pridané: 8.1.2010 10:56 rádovo 50-vyšší nie 50krat vyssi???? Odpovedať Známka: 6.7 Hodnotiť:

Re: gramatik Od reg.: Pjetro de | Pridané: 8.1.2010 12:15 to vies, hovorene slovo, asi uvazuju nie v 10tkevej sustave, ale bud v 50-tkovej, alebo (50^(1/2)-tkovej, alebo (50^(1/3)-tkovej, alebo (50^(1/4)-tkovej ... ci aj v (50^2)-tkovej, (50^3)-tkovej, (50^4)-tkovej sustave ... nech sa snazim akokolvek, dekadicky logaritmus 50 je 1,6989700043360188047862611052755, co nema najeko extra blizko k 1 (radovo 10), alebo 2 (radovo 100), alebo 3 (radovo 1000) ... Odpovedať Známka: 0.0 Hodnotiť:

Re: gramatik Od reg.: Pjetro de | Pridané: 8.1.2010 12:17 Je jasne ze "radovo" sa mysli celociselny pocet radov (resp. celociselny dekadicky logaritmus ked uz sa hrajkame v 10tkovej sustave), my sme tu velmi nadani intelektuali a nasa uroven abstrakcie je niekde uplne inde ... my mozeme mat aj 1,6989700043360188047862611052755 radu. Pripadne 4,25 kroku v algoritme :-) Odpovedať Hodnotiť:

botnet to vyrieši Od: ..... | Pridané: 8.1.2010 13:30 Náklady pár dolárov ;-) a jedno PC ;-), ktoré bude riadiť botnet a využije jeho potenciál ;-) takže 1 milion CPU by to mohlo zvládnuť aj za mesiac ;-) Odpovedať Známka: 10.0 Hodnotiť:

Re: botnet to vyrieši Od: Matoooo01 | Pridané: 8.1.2010 15:12 Samozrejme, za predpokladu, ze na Linuxovom stroji nespustim Operu, ktora mi to pomocou sikovneho open-source add-onu spravi za par sekund :))))) Odpovedať Známka: 5.6 Hodnotiť:

Re: botnet to vyrieši Od: quix_ | Pridané: 8.1.2010 17:04 ano je to fakt, opera pomocou addonov zvysuje vykon samotneho pc v pripade ze operacny system je linux. pozdrav pani sestricku. Odpovedať Známka: 10.0 Hodnotiť:

Re: botnet to vyrieši Od reg.: __Ondrej | Pridané: 8.1.2010 18:12 Ano je to pravda, navyse cim dlhsie pouzivas operu tym vykonnejsi mas PC. Takto vznikly prve superpocitace na Slovensku. Odpovedať Známka: 10.0 Hodnotiť:

Re: botnet to vyrieši Od: Mentol | Pridané: 8.1.2010 18:26 No to je sice mozne ale nic na svete sa nevyrovna drsnemu vypoctovemu vykonu MS Vista Home Basic, podporovanemu 60-timi beziacimi procesmi predinstalovanych trialovych antivirusov a antispywareov, Google toolbarom a samozrejme Internet explorerom na ktorom je home page www.pokec.sk. Odpovedať Známka: 7.8 Hodnotiť:

Re: botnet to vyrieši Od: Za poslednú hodinu: 1472 meraní | Pridané: 8.1.2010 20:38 dúfam,že si myslel pokec nba azete, v tom prípade je to zaistené Odpovedať Hodnotiť:

Re: botnet to vyrieši Od: sdfhdsh | Pridané: 8.1.2010 21:27 Vista teda musi ma "vypoctoveho vykonu". A to "mozno" aj viac ako ty... Odpovedať Známka: 3.3 Hodnotiť:

Re: botnet to vyrieši Od: Deer | Pridané: 8.1.2010 20:50 Tiez ma napadol napad s botnetom. Az raz budu zidaci z federalnej banky USA kciet uje..t peniaze poplatnikov, zavolaju stevkovi ballmerovi, ze potrebuju tak cca 100M pocitacov na den dva. Odpovedať Hodnotiť:

rsa768 Od: alexander jaray | Pridané: 9.1.2010 1:21 ako ste vypocitali rentabilitu ? Odpovedať Hodnotiť:

Re: rsa768 Od: Motrogon | Pridané: 9.1.2010 10:00 pravdepodobne vynasobenim koeficientu sprostych otazok s dlzkou flaku na osranych slipoch Odpovedať Známka: 3.3 Hodnotiť:

Re: rsa768 Od: alexander jaray | Pridané: 9.1.2010 10:26 takato otazka nie je nerozumna, naklady su v clanku vycislene ale prinos len naznaceny Odpovedať Hodnotiť:

radovo Od: dehfkjhkj | Pridané: 9.1.2010 13:36 radovo, radovo, radovo, radovo... Odpovedať Hodnotiť:

Pridať komentár