Šifry přežily útok

Tři indičtí matematici objevili způsob, jak v polynomiálním čase určit, zda zkoumané číslo je či není prvočísle...


Tři indičtí matematici objevili způsob, jak v polynomiálním čase určit, zda
zkoumané číslo je či není prvočíslem. Nejedná se ale o bezprostřední ohrožení
současných šifrovacích technologií.
Při generování veřejného klíče dochází k vynásobení dvou velkých prvočísel.
Útok na šifru se provádí realizací inverzní operace, tzv. faktorizací (rozklad
čísla na dvě prvočísla). Bezpečnost současné kryptografie do značné míry závisí
na tom, že výpočetní složitost faktorizace není polynomiální jinak řečeno, s
růstem délky čísla roste doba potřebná na faktorizaci exponenciálně.
Trojice indických matematiků Agrawal, Kayal a Saxena objevila, že zjištění
prvočíselnosti je úlohou s pouze polynomiální složitostí. Z hlediska
teoretického se jedná o velmi zajímavý objev, kryptografie však kvůli tomu
nemusí být budována na nových základech. Odhalení složeného čísla totiž ještě
neznamená, že ho v polynomiálním čase umíme také rozložit (tedy provést
faktorizaci), a dostat se tak k soukromému klíči. Naopak platí, že rychlejší
prvočíselný test by mohl urychlit generování šifrovacích klíčů.









Komentáře
K tomuto článku není připojena žádná diskuze, nebo byla zakázána.