Dešifrování rychlé jako blesk

Metoda Multiprime pro RSA Mají se dokumenty šifrovat? Jednoznačně ano! Nejlépe raději rovnou 1 024bitovým klíčem neb...


Metoda Multiprime pro RSA
Mají se dokumenty šifrovat? Jednoznačně ano! Nejlépe raději rovnou 1 024bitovým
klíčem nebo dokonce 2 048bitovým. Proč škudlit, nyní, kdy se podařilo prosadit
liberalizaci vývozu šifrovacích nástrojů? Tak nějak uvažuje uživatel, který
přičítá velký význam bezpečnosti svých zpráv v elektronické poště. Dlouhé klíče
však mají jeden rozhodující háček. Náklady na šifrování a dešifrování metodou
RSA s veřejnými klíči rostou totiž s třetí mocninou délky klíče.
Výše zmíněné například znamená, že program pro 1 024bitové šifrování při práci
potřebuje osmkrát tolik času než varianta s 512 bity. Zřetelně se přitom
současně mnohonásobně zvýší náklady na rozluštění kódů a to pro délku někde
mezi 512 a 1 024 bity vyžaduje dát dohromady všechny počítače na světě.
Řešení problému
Aby v budoucnu mohli svá data posílat přes Internet šifrovaně také uživatelé
nesrovnatelně pomalých počítačů jako jsou mobilní telefony a PDA, kdy se jen
při zabalení a rozbalení musí zatím velmi dlouho čekat, je třeba použít nějakou
jinou techniku než dosud. A to je právě posláním společné kampaně firem Compaq
a RSA Security. Technika, která má umožnit urychlení, se nazývá "Multiprime" a
pochází od Compaqu. Zatímco metoda RSA založená Ronaldem Rivestem, Adi Shamirem
a Leonardem Adlemanem nyní vytváří páry z veřejného a soukromého klíče pomocí
dvou prvočísel, používá zde popisovaný algoritmus tři nebo více prvočísel.
Počítání ve skupinách
Vývojáři Compaqu navrhují zvolit pro veřejný klíč relativně malá čísla a místo
toho prodloužit posloupnost klíčů privátních. Dnes jsou u RSA programů soukromé
a veřejné klíče stejně velké, totiž 1 024 bitů. V budoucnu mají dosáhnout tajná
čísla délky přibližně 2 x 2 048 bitů.
Co by přineslo zkrácení veřejných klíčů? Protože veřejným klíčem se šifruje a
soukromým dešifruje, prodloužil by se čas nutný pro dešifrování, zatímco
šifrování by šlo rychleji. Multiprime má nyní snížit časovou náročnost při
dešifrování a při podepisování. Zatímco RSA dovoluje analyzovat zpětný výpočet
na čitelný text ve dvou úlohách, člení nová metoda problém na tři a více částí,
což odpovídá počtu použitých prvočinitelů. Tyto dílčí úlohy lze společně
vyřešit rychleji a to tím rychleji, čím větší je jejich počet. Za druhé mohou
být tyto problémy současně řešeny paralelně pracujícími procesy.
Tvůrci této techniky říkají, že Multiprime zvyšuje výkon již na
jednoprocesorovém počítači. A také k tomu poskytují přesný vzorec: n
prvočinitelů urychluje práci ve srovnání s klasickou dvoučlennou variantou s
koeficientem (n2)/4. Se třemi prvočísly to představuje zrychlení 2,25krát, se
čtyřmi to jde čtyřikrát a se šesti devětkrát rychleji. Díky přizpůsobení
programových kódů je tak možné odstranit např. výkonovou bariéru systémů
čipových karet, které budou zajišťovat bezpečnost v budoucích mobilních
přenosových zařízeních.
Ideální pro paralelní počítače
Pro víceprocesorové systémy je navržené řešení ještě výhodnější. Pro případ, že
je počet paralelně pracujících CPU současně stejný jako počet použitých
prvočinitelů, objevili matematikové následující vzorec: nárůst výkonu metody s
n prvočísly v porovnání s metodou RSA na jediném procesoru činí (n3)/4. Protože
se zvyšuje se třetí mocninou, roste také rychleji než u Multiprime na
jednoprocesorových počítačích a např. u čtyřprocesorového systému docházíme až
ke koeficientu 16. Tento efekt by mohl zvýšit výkon bran pro VPN (Virtual
Private Network virtuální privátní síť), které používají k šifrování přídavné
karty s více koprocesory.
Aby svou teorii prověřili, uvedli výzkumníci Compaqu do chodu server Proliant
6000, který pracuje se čtyřmi 200MHz procesory Intel Pentium, může adresovat
650 MB pracovní paměti a být osazen až 512 KB paměti cache. Jako operační
systém vybrali Windows 2000. Výsledek skvěle odpovídal předpovědím.
Graf na této straně ukazuje srovnání mezi tradiční metodou RSA a dvěma dekodéry
Multiprime. Svislá osa reprezentuje čas. Podél horizontální osy je délka modulu
v bitech, která je současně délkou soukromého klíče. Compaq zkoušel také
šifrovací hardware, totiž svou vlastní PCI kartu "AXL 200", která zpracuje
maximálně 24 prvočinitelů. Zisk v porovnání k RSA bez Multiprime vychází menší
než při softwarové variantě; hodnoty leží u 10 ms a 5 ms pro 2 048bitový modul
a osminásobný rozklad (256bitové Multiprime). Pro mobilní zařízení Compaq a RSA
ještě žádné testy nepublikovaly. Tam leží doby dešifrování v rozsahu sekund.
Omezení bezpečnosti
Vývojáři šifrovacích algoritmů nepomíjejí otázku, jak bezpečné jsou jejich
metody. Vždyť by se mohl snížit objem nákladů na odposlech komunikace
zabezpečené pomocí RSA tím, jak se zvětší počet prvočinitelů. Compaq to přesně
prozkoumal a zjistil, že skutečně několikanásobné algoritmy Multiprime hackerům
řemeslo usnadňují. Ovšem doba výpočtu špiona se redukuje teprve při nejmenším
počtu prvočinitelů. Pro prolomení všech jednoduchých systémů Multiprime
potřebujete stejnou dobu jako pro RSA.
Tabulka na této straně ukazuje modul vzhledem k doporučenému počtu koeficientů,
kde se ukazuje, že dnes obvyklé 2 048bitové šifrování se urychluje nejvýše
6,7krát. Přesto má metoda Multiprime oproti dnešní metodě RSA jen výhody: Za
prvé není dražší, protože vyžaduje málo změn ve zdrojovém kódu. Za druhé je
rychlejší. A za třetí dělá šifrování dobrý marketing...
0 2217 / penDoporučený počet prvočinitelů
ModulPočet částíZvýšení výkonu
Ę 51222 (Standard-RSA)
1 0243Ę6,7
2 0483Ę6,7
4 096416,0









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