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

RSA šifrování je jedním z prvních praktických kryptosystémů s veřejným klíčem, který je široce používán pro bezpečný přenos dat. Jeho hlavní rozdíl od podobných služeb spočívá v tom, že šifrovací klíč je otevřený a liší se od dešifrovacího klíče, který je uchováván v tajnosti. V technologii RSA tuto asymetrii Je založen na praktické složitosti factoringové reprodukce dvou velkých počátečních čísel (faktoringový problém).

Dějiny stvoření

Jméno RSA se skládá z počátečních písmen příjmení Rivest, Shamir a Adleman, vědci, kteří poprvé veřejně popsali podobné šifrovací algoritmy v roce 1977. Clifford Cox, anglický matematik, který pracoval pro britské tajné služby, nejprve v roce 1973 vytvořil ekvivalentní systém, ale nebyl odtajněn až do roku 1997.

Uživatel RSA vytváří a publikuje veřejný klíč založený na dvou velkých počátečních číslech spolu s pomocnou hodnotou. Předvolby by měla být tajná. Kdokoliv může použít veřejný klíč k zašifrování zprávy, ale pokud je dostatečně velký, může zprávu rozpoznat pouze osoba, která má znalosti o primárních číslech. Zveřejnění šifrování RSA je známé jako hlavní problém: dnes zůstává otevřená diskuse o tom, jak je tento mechanismus spolehlivý.

RSA je poměrně pomalý algoritmus, z tohoto důvodu není široce využíván pro přímé šifrování dat uživatele. Nejčastěji se tato metoda používá k odesílání šifrovaných sdílených klíčů pro symetrický šifrovací klíč, který může zase provádět hromadné operace šifrování a dešifrování při mnohem vyšší rychlosti.

Kdy se kryptosystém objevil v moderní 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á společný tajný klíč, vytvořený z exponentiace čísla modulo a prime number. Nicméně ponechali otevřený problém implementace této funkce, protože principy faktoringu nebyly v té době dobře pochopeny.

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í vědci) nabízeli mnoho potenciálních funkcí, zatímco Adleman (jako matematik) hledal "slabiny" algoritmu. Používali mnoho přístupů a nakonec v dubnu 1977 vyvinuli systém, který je dnes konečně znám jako RSA.

EDS a veřejný klíč

Elektronický digitální podpis nebo EDS jsou nedílnou součástí elektronických dokumentů. Je tvořena určitou kryptografickou změnou dat. Pomocí tohoto atributu je možné zkontrolovat integritu dokumentu, jeho důvěrnost a také určit, kdo ho vlastní. Ve skutečnosti je to alternativa k běžnému standardnímu podpisu.

Tento kryptosystém (RSA-šifrování) nabízí veřejný klíč, který se liší od symetrických. Princip fungování je, že se používají dva různé klíče - uzavřené (šifrované) a také otevřené. První se používá k generování EDS a následně k příležitost rozluštit text. Druhý - pro správné šifrování a verifikaci EDS.

Použití podpisu umožňuje lépe porozumět šifrování RSA, jehož příklad lze uvést jako obyčejný tajný dokument uzavřený z očí.

Jaká je podstata algoritmu?

Algoritmus RSA se skládá ze čtyř kroků: generování klíčů, jejich distribuce, šifrování a dešifrování. Jak již bylo uvedeno, šifrování RSA zahrnuje veřejný klíč a soukromý klíč. Open může být známo všem a slouží k šifrování zpráv. Podstatou toho je, že zprávy šifrované veřejným klíčem mohou být dešifrovány pouze v určitém časovém období pomocí soukromého klíče.

Z bezpečnostních důvodů by celá čísla měla být náhodně vybrána a měla by mít stejnou velikost, ale délka by se měla lišit o několik číslic, aby se faktorem ztížil. Stejná čísla lze efektivně nalézt pomocí testu na jejich jednoduchost, takže šifrování informací musí být nutně složitější.

Veřejný klíč se skládá z modulu a veřejného exponentu. Uzavřená skupina se skládá z modulu a soukromého indikátoru, který musí být uchováván v tajnosti.

Šifrování souborů RSA a slabých míst

Existuje však řada mechanismů pro hackování jednoduchého RSA. Při šifrování s nízkými hodnotami a malými hodnotami čísel lze šifru snadno otevřít, pokud vyberete kořen šifrového textu nad celá čísla.

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, služba RSA bez dalších služeb není sémanticky bezpečná.

Další algoritmy pro šifrování a ochranu

Aby se předešlo výše uvedeným problémům, při praktické implementaci RSA je před šifrováním obvykle zabudována strukturovaná náhodná náplň. Tím je zajištěno, že obsah nespadá do rozsahu nebezpečných otevřených textů a že tato zpráva nemůže být odhalena náhodným výběrem.

Bezpečnost kryptosystému RSA a šifrování informací jsou založeny na dvou matematických problémech: problému faktoringu velkých čísel a aktuálních problémů RSA. Plné zveřejnění šifrového textu a EDS v RSA se považuje za nepřijatelné za předpokladu, že oba tyto problémy nelze vyřešit souhrnně.

Nicméně vzhledem k možnosti obnovení jednoduchých násobitelů může útočník vypočítat tajný klíč z veřejného klíče a dešifrovat text pomocí standardního postupu. Navzdory skutečnosti, že dnes nebyla nalezena žádná existující metoda pro faktorování velkých čísel na klasickém počítači, nebylo prokázáno, že neexistuje.

Automatizace

Nástroj Yafu lze využít k optimalizaci tohoto procesu. Automatizace v YAFU je moderní funkce kombinující algoritmy faktorizace v intelektuální a adaptivní metodice, která minimalizuje čas k nalezení faktorů libovolných vstupních čísel. Většina implementací algoritmu je multithreaded, což umožňuje společnosti Yafu plné využití multi- nebo multi- vícejádrových procesorů (včetně SNFS, SIQS a ECM). Nejdříve je to nástroj pro příkazové řádky. Čas strávený při hledání šifrovacího faktoru pomocí nástroje Yafu na konvenčním počítači lze snížit na 103,1746 sekund. Nástroj zpracovává binární soubory s kapacitou 320 bitů nebo více. Jedná se o velmi složitý software, který vyžaduje určité množství technických dovedností pro instalaci a konfiguraci. RSA šifrování C může být proto zranitelné.

Pokusy o lámání v moderní době

V roce 2009 Benjamin Moody s použitím RSA-512 bitkey pracoval na dešifrování šifrovací techniky po dobu 73 dní pomocí pouze dobře známého softwaru (GGNFS) a průměrného stolního počítače (dual-core Athlon64 na 1900 MHz). Jak ukázala tato zkušenost, trvalo méně než 5 gigabajtů disku a zhruba 2,5 GB paměti RAM pro proces "prosévání".

Od roku 2010 mělo největší faktorizované RSA číslo 768 bitů (232 desetinných míst nebo RSA-768). Jeho odhalení trvalo dva roky na několika stovkách počítačů najednou.

V praxi však mají klíče RSA dlouhou délku - obvykle od 1024 do 4096 bitů. Někteří odborníci se domnívají, že 1024-bitové klíče se mohou v blízké budoucnosti stát nespolehlivými, nebo dokonce již mohou být prasknuty dobře financovaným útočníkem. Nicméně málo lidí tvrdí, že 4096-bitové klíče mohou být také zpřístupněny v dohledné budoucnosti.

Vyhlídky

Proto se obecně předpokládá, že RSA je bezpečná, pokud jsou čísla dostatečně velká. Pokud je hlavní číslo 300 bitů nebo kratší, lze šifrový text a digitální podpis rozložit několik hodin na osobním počítači pomocí softwaru, který je již k dispozici ve veřejné doméně. Klíče s délkou 512 bitů, jak bylo prokázáno, mohly být otevřeny v roce 1999 pomocí několika set počítačů. V dnešní době je to možné během několika týdnů s použitím veřejného hardwaru. Je tedy možné, že šifrování RSA na prstech bude v budoucnu snadno odhaleno a systém bude beznadějně zastaralý.

Oficiálně v roce 2003 byla zpochybněna bezpečnost 1024bitových klíčů. V současné době se doporučuje mít délku nejméně 2048 bitů.