RSA šifrování. Popis a implementace algoritmu RSA

RSA šifrování je jedním z prvních praktických veřejného klíče kryptografických který je široce používán pro bezpečný přenos dat. Jeho hlavní rozdíl od podobných služeb je, že šifrovací klíč je otevřená a odlišná od dešifrovací klíč, který je držen v tajnosti. Technologie RSA , tato asymetrie je založen na praktické obtíže factoringových přehrávání dvou velkých prvočísel (problém factoringu).

History of creation

RSA název se skládá z počátečních písmen příjmení Rivest, Shamir a Adleman - vědců, kteří jako první veřejně popsal tyto šifrovací algoritmy v roce 1977. Klifford Koks, anglický matematik, který pracoval pro britské zpravodajské služby, první vyvinout ekvivalentní systém v roce 1973, ale to nebylo až do roku 1997 odtajněny

Uživatel RSA vytvoří a publikuje veřejný klíč na základě dvou velkých prvočísel společně s pomocným hodnotou. Prvočísla by měly být drženy v tajnosti. Kdokoliv může použít veřejný klíč k zašifrování zprávy, ale pokud je to dost velké, pak jen někdo s vědomím prvočísel umí dekódovat zprávu. šifrování zveřejnění RSA je známá jako hlavní problém je dnes otevřená diskuse o tom, jak spolehlivý mechanismus.

RSA algoritmus je poměrně pomalý, a proto to není jak široce používán k přímému zašifrování uživatele. Ve většině případů je tato metoda se používá pro přenos ve sdíleném klíč, kódovaný pro symetrického šifrovacího klíče, které zase mohou provádět operace hromadného šifrování a dešifrování na mnohem vyšší rychlostí.

Když tam byl kryptografický systém ve své současné podobě?

Myšlenka asymetrického kryptografického klíče přičítán Diffie a Hellman, který publikoval koncept v roce 1976, zavádění digitálních podpisů, a snaží se aplikovat teorii čísel. Jejich formulace používá sdílený tajný klíč vygenerovaný z určitého počtu umocňování modulo prvočíslo. Nicméně, oni opustili otevřít problematiku realizace této funkce, protože principy faktoringu nebyl dobře pochopen v té době.

Rivest, Adi Shamir a Adleman u MIT učinili několik pokusů v průběhu let k vytvoření funkce jednosměrné, který je obtížné dekódovat. Rivest a Shamir (jako počítačové odborníky) navrhli mnoho potenciálních funkcí, zatímco Adleman (jako matematika) hledat „slabé“ algoritmu. Oni používali mnoho přístupů a nakonec vyvine konečnou systém, nyní známý jako RSA v dubnu 1977.

Elektronický podpis a veřejný klíč

Digitální podpis nebo elektronický podpis, je nedílnou součástí elektronického typů dokumentů. Je tvořen v určité kryptografické změny dat. S tímto atributem možné kontrolovat integritu dokumentu, jeho důvěrnosti, stejně jako zjistit, kdo ji vlastní. Ve skutečnosti je alternativou běžného standardu podpisu.

Tento šifrovací (RSA-šifrovaný) nabízí veřejný klíč, na rozdíl od symetrické. Jeho princip činnosti je to, že jsou použity dva různé klíče - zavřené (šifrovaný) a outdoor. První z nich je použit pro vytvoření digitálního podpisu a pak budou moci k dešifrování textu. Za druhé - pro skutečné šifrování a elektronického podpisu.

Používání podpisů, aby lépe porozumět šifrování RSA, jehož příkladem může být snížena jako normální tajemství „uzavřené před zvědavýma očima,“ dokumentu.

Co je to algoritmus?

RSA algoritmus se skládá ze čtyř kroků: generování klíčů, distribuci, šifrování a dešifrování. Jak již bylo zmíněno, RSA šifrování obsahuje veřejný klíč a soukromý klíč. Outdoor mohou být známé všem a slouží k šifrování zpráv. Jeho podstata spočívá v tom, že zprávy zašifrované pomocí veřejného klíče lze dešifrovat pouze v daném časovém období pomocí tajného klíče.

Z bezpečnostních důvodů je celá čísla, které mají být vybrány náhodně a musí být identické co do velikosti, ale liší se v délce několika málo čísel, aby se factoring těžší. Stejný Stejný počet může být účinně nalézt zkouškou ve své jednoduchosti, takže šifrování informací musí být nutně složité.

Veřejný klíč se skládá z modulu a veřejný exponent. Vnitřní jednotka se skládá z vlastní postavu, která by měla být držena v tajnosti.

RSA šifrování souborů a slabých stránek

Nicméně, existuje celá řada jednoduchých hackerských mechanismů RSA. Když zašifruje s nízkými a malé hodnoty kódových čísel lze snadno otevřít, pokud kořenový pick ciphertext nad celými čísly.

Vzhledem k tomu, RSA šifrování je deterministický algoritmus (tj nemá náhodné komponenty), útočník může úspěšně spustit vybraný text otevřený útok na šifrovací systém tím, že zašifruje pravděpodobné holé texty na základě veřejného klíče a kontrolu, zda jsou rovné ciphertext. Sémanticky bezpečný kryptografický systém je spuštěna v případě, že útočník nemůže rozlišovat mezi dvěma šifrování od sebe navzájem, i když ví, že příslušné texty v rozšířené formě. Jak bylo popsáno výše, RSA ostatní služby bez polstrování není sémanticky bezpečné.

Mezi další algoritmy pro šifrování a ochranu

Aby se zabránilo výše uvedených problémů, při praktickém provádění RSA jsou obvykle vloženy do nějaké formy strukturovaného, randomizované náplně před šifrováním. To zajišťuje, že obsah nespadá do rozsahu nejistých holých, a že tato zpráva nemůže být vyřešen náhodným výběrem.

Bezpečnost RSA kryptografický systém a šifrování založené na dvou matematických problémech: problém factoring velká čísla a skutečný problém RSA. Úplné zveřejnění ciphertext a podpis v JAR je považována za nepřípustnou z předpokladu, že oba tyto problémy nelze vyřešit společně.

Nicméně, s možností obnovení prvočísla, útočník může vypočítat tajný exponent veřejného klíče a poté dešifrování textu pomocí standardního postupu. Navzdory tomu, že dnes žádný existující metoda pro factoring velká celá čísla na klasickém počítači nelze nalézt, že nebylo prokázáno, že neexistuje.

automatizace

Nástroj, nazvaný YAFU, mohou být použity k optimalizaci procesu. Automatizace v YAFU je pokročilá funkce, která kombinuje faktorizace algoritmy v intelektuálním a adaptivní metody, která minimalizuje čas najít faktory libovolných vstupních čísel. Většina implementací multithreaded algoritmus umožňuje YAFU plné využití multi- nebo mnoha vícejádrové procesory (včetně SNFS, SIQS a ECM). Za prvé, to je řízen nástroj příkazového řádku. Čas strávený hledáním šifrování YAFU faktor při použití běžného počítače, může být snížena na sekund 103.1746. Nástroj zpracovává binární kapacitu 320 bitů nebo více. Jedná se o velmi složitý software, který vyžaduje určité množství technických dovedností k instalaci a konfiguraci. Tak, RSA šifrování, mohou být ohroženy C.

Hacking v nedávné době

V roce 2009, Bendzhamin Mudi pomocí RSA-512 bitového klíče pracoval na rozluštění kriptoteksta dobu 73 dnů, s použitím pouze dobře známý software (GGNFS) a průměrnou plochu (dual-core Athlon64 na 1900 MHz). Jak ukazuje praxe, vyžaduje o něco méně než 5 GB disku a asi 2,5 GB paměti pro proces „prosévání.“

Od roku 2010, největší počet byl zapracovány RSA 768 bitů dlouhé (232 desetinných míst, nebo RSA-768). Jeho odhalení trvalo dva roky zprávu o několika stech počítačích najednou.

V praxi jsou klíče RSA jsou dlouhé - zpravidla od 1024 do 4096 bitů. Někteří odborníci se domnívají, že 1024-bitové klíče může být nespolehlivé v blízké budoucnosti, nebo dokonce déle může být popraskané útočníky velmi dobře financované. Nicméně málokdo by mohl namítnout, že 4096-bitové klíče mohou být také zveřejněny v blízké budoucnosti.

vyhlídky

Proto zpravidla se předpokládá, že RSA je bezpečný jestliže čísla jsou dostatečně velké. V případě, že základní počet 300 bitů nebo kratší, a ciphertext digitálního podpisu lze rozložit během několika hodin na osobním počítači pomocí software k dispozici již ve veřejné doméně. Délkou klíče 512 bitů, jak je znázorněno, může být otevřena již v roce 1999, s využitím několika stovek počítačů. V současné době je možné během několika týdnů za použití veřejně dostupného hardwaru. Tak je možné, že v buduschembudet snadno popsány RSA-šifrována na prstech, a systém bude beznadějně zastaralé.

Oficiálně v roce 2003, byla zpochybněna bezpečnost na 1024-bitové klíče. V současné době, je doporučeno mít minimální délku 2048 bitů.