Šifrovací algoritmus RSA. RSA šifrovanie. Popis a implementácia algoritmu RSA Technológia implementácie algoritmu RSA

Šifrovací algoritmus verejného kľúča RSA bol jedným z prvých navrhnutých koncom 70. rokov dvadsiateho storočia. Jej názov tvoria prvé písmená priezvisk autorov: R. Rivest, A. Shamir a L. Adleman. Algoritmus RSA je pravdepodobne najpopulárnejší a najpoužívanejší asymetrický algoritmus v kryptografických systémoch.

Algoritmus je založený na skutočnosti, že problém rozdelenia veľkého počtu do prvočísel je zložitý. Kryptografický systém RSA je založený na nasledujúcich dvoch faktoch z teórie čísel:

1. úloha kontroly čísla na primalitu je pomerne jednoduchá;
2. úloha rozkladu čísel tvaru n = pq (p a q sú prvočísla); faktorizácia je veľmi náročná, ak vieme, že iba n a p a q sú veľké čísla (ide o takzvaný problém faktorizácie, podrobnejšie pozri „Základy teórie čísel používaná v kryptografii s verejným kľúčom“).

Algoritmus RSA je blokový šifrovací algoritmus, kde šifrované a nešifrované údaje musia byť reprezentované ako celé čísla medzi 0 a n -1 pre niektoré n.

Šifrovanie

Poďme sa teda pozrieť na samotný algoritmus. Nechajte účastníka A poslať zašifrovanú správu účastníkovi B. V tomto prípade účastník B musí pripraviť pár (verejný kľúč; súkromný kľúč) a poslať svoj verejný kľúč užívateľovi A.

Prvým krokom je vygenerovanie verejných a súkromných kľúčov. Najprv vyberte dve veľké prvočísla P a Q. Potom sa vypočíta súčin N:

Potom sa určí pomocné číslo f:

f = (P - 1) (Q - 1).

Potom sa náhodne vyberie číslo d< f и взаимно простое с f .

Čísla d a N budú verejným kľúčom používateľa a hodnota e bude súkromným kľúčom.

Takže v tomto bode by mal mať používateľ informácie uvedené v nasledujúcej tabuľke:

Keďže používateľ B chce prijať zašifrovanú správu od používateľa A, používateľ B musí poslať svoj verejný kľúč (d, N) používateľovi A. Čísla P a Q už nie sú potrebné, ale nemožno ich s nikým zdieľať; Najlepšie je na ne úplne zabudnúť.

V tomto bode je fáza prípravy kľúča dokončená a na šifrovanie údajov možno použiť hlavný protokol RSA.

Druhá fáza – šifrovanie údajov. Ak chce účastník A poslať nejaké údaje účastníkovi B, musí svoju správu reprezentovať v digitálnej forme a rozdeliť ju do blokov m 1, m 2, m 3, ..., kde m i< N . Šifrovaná správa bude pozostávať z blokov s i .

Účastník A zašifruje každý blok svojej správy pomocou vzorca

c i = m i d mod N

použitím verejné parametre užívateľa B a pošle zašifrovanú správu C=(c 1, c 2, c 3, ...) cez otvorenú linku.

Účastník B, ktorý dostal zašifrovanú správu, dešifruje všetky bloky prijatej správy pomocou vzorca

Všetky dešifrované bloky budú úplne rovnaké ako tie, ktoré prichádzajú od používateľa A.

Útočník, ktorý zachytí všetky správy a pozná všetky verejné informácie, nebude môcť nájsť pôvodnú správu pre veľké hodnoty P a Q.

Príklad výpočtov algoritmu

Umožnite používateľovi A poslať správu používateľovi B. V tomto prípade musí používateľ B najskôr pripraviť verejný a súkromný kľúč. Nechajte ich vybrať napríklad tieto parametre:

P = 3, Q = 11, N = 3 x 11 = 33.

Potom f = (P - l) (Q - 1) = (3-1) (11-1) = 20.

Potom používateľ B vyberie ľubovoľné číslo d, ktoré nemá spoločných deliteľov s f (je to potrebné, aby sa potom dala zašifrovaná správa jednoznačne obnoviť). Nech d = 13. Toto číslo bude jednou zo zložiek verejného kľúča.

Úvod 3

Hlavná časť 5

1 História stvorenia 5

2Popis algoritmu 5

2.1Vytvorenie kľúčov 6

2.2 Šifrovanie a dešifrovanie 6

2.3 Použite príklad 7

Záver 9

Zoznam použitých zdrojov 10

Úvod

Kryptografia je špeciálny systém na zmenu bežného písma, ktorý sa používa na to, aby bol text zrozumiteľný len obmedzenému počtu ľudí, ktorí tento systém poznajú.

Kryptografia je veda o ochrane informácií pomocou matematických metód.

Moderná kryptografia zahŕňa:

symetrické kryptosystémy;

asymetrické kryptosystémy;

systémy elektronického digitálneho podpisu (EDS);

hashovacie funkcie;

správa kľúčov;

získavanie skrytých informácií;

kvantová kryptografia.

Symetrické šifrovanie - symetrické algoritmy sú tie, v ktorých sa na šifrovanie a dešifrovanie používa rovnaký tajný kľúč (známy iba odosielateľovi a príjemcovi).

Bežné symetrické šifrovacie algoritmy:

AES (Advanced Encryption Standard) - americký šifrovací štandard;

GOST 28147-89 - domáci štandard šifrovania údajov;

DES (Data Encryption Standard) - štandard šifrovania dát v USA až po AES;

3DES (Triple-DES, triple DES);

IDEA (International Data Encryption Algorithm);

SEED - kórejský štandard šifrovania údajov;

Camellia je šifra certifikovaná na použitie v Japonsku;

XTEA je najjednoduchší algoritmus na implementáciu.

Asymetrické kryptoalgoritmy sú navrhnuté predovšetkým tak, aby eliminovali hlavnú nevýhodu symetrických kryptosystémov – zložitosť správy a distribúcie kľúčov.

Základom všetkých asymetrických kryptografických algoritmov je vysoká výpočtová zložitosť obnovy otvoreného textu bez znalosti súkromného kľúča.

Príklady asymetrických krypto algoritmov:

Diffie-Hellmann;

RSA - Rivest, Shamir, Adelman - je založená na zložitosti problému faktorizácie veľkých čísel v krátkom čase;

DSA – Algoritmus digitálneho podpisu, americký štandard;

GOST R 34.10 – 94, 2001, normy Ruskej federácie.

V tomto abstrakte sa budeme podrobne zaoberať asymetrickým kryptografickým šifrovacím algoritmom - algoritmom RSA.

Hlavná časť

Algoritmus RSA (skratka pre Rivest, Shamir a Adleman) je kryptografický algoritmus s verejným kľúčom, ktorý využíva výpočtovú zložitosť problému faktorizácie veľkých celých čísel. Kryptosystém RSA bol prvým systémom vhodným na šifrovanie aj digitálne podpisovanie.

História stvorenia

Práca Whitfielda Diffieho a Martina Hellmana „New Directions in Cryptography“, publikovaná v novembri 1976, priniesla revolúciu v chápaní kryptografických systémov tým, že položila základy kryptografie s verejným kľúčom. Následne vyvinutý algoritmus Diffie-Hellman umožnil dvom stranám získať zdieľaný tajný kľúč pomocou nezabezpečeného komunikačného kanála. Tento algoritmus však nevyriešil problém s autentifikáciou. Bez ďalších nástrojov si používatelia nemohli byť istí, s kým vygenerovali zdieľaný tajný kľúč.

Po preštudovaní tohto článku začali traja vedci Ronald Linn Rivest, Adi Shamir a Leonard Adleman z Massachusettského technologického inštitútu (MIT) hľadať matematickú funkciu, ktorá by umožnila implementovať model kryptografického systému s verejným kľúčom, ktorý sformulovali Whitfield Diffie a Martin Hellman. . Po prepracovaní viac ako 40 možností prišli s algoritmom založeným na rozdiele v tom, aké ľahké je nájsť veľké prvočísla a aké ťažké je faktorizovať súčin dvoch veľkých prvočísel, ktoré neskôr nazvali RSA. Systém dostal názov podľa prvých písmen priezvisk jeho tvorcov.

Popis algoritmu

Prvým krokom v akomkoľvek asymetrickom algoritme je vytvorenie páru kľúčov – verejného a súkromného – a distribúcia verejného kľúča „po celom svete“.

Vytváranie kľúčov

V prípade algoritmu RSA fáza vytvorenia kľúča pozostáva z nasledujúcich operácií:

Číslo sa nazýva otvorený exponent

Šifrovanie a dešifrovanie

Povedzme, že odosielateľ chce poslať správu príjemcovi.

Správy sú celé čísla v rozsahu od 0 do , t.j. . Obrázok 1 znázorňuje schému algoritmu RSA.

Obrázok 1 – Schéma algoritmu RSA

Algoritmus odosielateľa:

Algoritmus príjemcu:

Rovnice (1) a (2), na ktorých je schéma RSA založená, určujú vzájomne inverzné transformácie množiny.

Príklad použitia

Tabuľka 1 ukazuje príklad použitia algoritmu RSA. Odosielateľ poslal zašifrovanú správu „111111“ a príjemca ju pomocou svojho súkromného kľúča dešifroval.

Tabuľka 1 – Postupné vykonávanie algoritmu RSA

	Popis operácie	Výsledok operácie
Generovanie kľúčov	Vyberte dve prvočísla
	Vypočítajte modul
	Vypočítajte Eulerovu funkciu
	Vyberte otvorený exponent
	Vypočítajte tajný exponent
Šifrovanie	Vyberte text, ktorý chcete zašifrovať
	Vypočítajte šifrový text
Dekódovanie	Vypočítajte pôvodnú správu

Záver

V tomto abstrakte sa podrobne diskutuje o asymetrickom šifrovacom algoritme RSA. Bola popísaná história jeho vzniku, boli popísané algoritmy na vytváranie kľúčov, šifrovanie a dešifrovanie. Uvedený je aj príklad praktického využitia algoritmu RSA.

Zoznam použitých zdrojov

Semenov Yu.A. Internetové protokoly // M.: Prospekt, 2011. – 114 s.

Beljajev A.V. Metódy a prostriedky informačnej bezpečnosti // Black Branch of St. Petersburg State Technical University, 2010. – 142 s.

Venbo M. Moderná kryptografia. Teória a prax // M.: Williams, 2005. - 768 s.

Schneier B. Aplikovaná kryptografia. Protokoly, algoritmy, zdrojové texty // M.: Triumph, 2002. - 816 s.

Algoritmus RSA // Internetový zdroj: http://ru.wikipedia.org/wiki/Rsa

V závislosti od štruktúry použitých kľúčov sa metódy šifrovania delia na:

• symetrický: cudzinci môžu poznať šifrovací algoritmus, ale malá časť tajných informácií je neznáma – kľúč, ktorý je rovnaký pre odosielateľa aj príjemcu správy; Príklady: DES, 3DES, AES, Blowfish, Twofish, GOST 28147-89
• asymetrické šifrovanie: cudzinci môžu poznať šifrovací algoritmus a možno aj verejný kľúč, ale nie súkromný kľúč, ktorý pozná iba príjemca. Kryptografické systémy s verejným kľúčom sú v súčasnosti široko používané v rôznych sieťových protokoloch, najmä v protokoloch TLS a jeho predchodcovi SSL (podkladový HTTPS), ako aj SSH, PGP, S/MIME atď. Ruský štandard využívajúci asymetrické šifrovanie - .

V súčasnosti používa väčšina produktov na trhu informačnej bezpečnosti asymetrické šifrovanie verejným kľúčom RSA (skratka pre Rivest, Shamir a Aldeman - tvorcovia algoritmu).

Jeho kryptografická sila je založená na obtiažnosti faktorizácie veľkých čísel, konkrétne na mimoriadnej náročnosti úlohy určiť tajný kľúč na základe verejného kľúča, pretože by si to vyžadovalo vyriešiť problém existencie deliteľov celého čísla. Najbezpečnejšie systémy používajú 1024-bitové a väčšie čísla.

Pozrime sa na algoritmus RSA z praktického hľadiska.

Najprv musíte vygenerovať verejný a súkromný kľúč:

• Zoberme si dve veľké prvočísla p a q.
• Definujme n ako výsledok vynásobenia p na q (n= p*q).
• Vyberme si náhodné číslo, ktoré nazveme d. Toto číslo musí byť relatívne prvočíslo (nemá spoločného deliteľa okrem 1) s výsledkom násobenia (p-1)*(q-1).
• Definujme číslo e, pre ktoré platí nasledujúci vzťah (e*d) mod ((p-1)*(q-1))=1.
• Nazvime verejný kľúč čísla e a n a tajný kľúč čísla d a n.

Na zašifrovanie údajov pomocou verejného kľúča (e,n) potrebujete nasledovné:

• rozdeliť zašifrovaný text na bloky, z ktorých každý môže byť reprezentovaný ako číslo M(i)=0,1,2..., n-1 (t.j. len do n-1).
• zašifrujte text považovaný za postupnosť čísel M(i) pomocou vzorca C(i)=(M(I)^e)mod n.

Na dešifrovanie týchto údajov pomocou tajného kľúča (d,n) je potrebné vykonať nasledujúce výpočty: M(i) = (C(i)^d) mod n. Výsledkom bude množina čísel M(i), ktoré predstavujú pôvodný text.

Nasledujúci príklad jasne demonštruje šifrovací algoritmus RSA:

Poďme zašifrovať a dešifrovať správu "CAB" pomocou algoritmu RSA. Pre jednoduchosť si zoberme malé čísla – to skráti naše výpočty.

• Zvoľme p=3 a q=11.
• Definujme n= 3*11=33.
• Nájdeme (p-1)*(q-1)=20. Preto sa d bude rovnať napríklad 3: (d=3).
• Zvoľme číslo e pomocou nasledujúceho vzorca: (e*3) mod 20=1. To znamená, že e sa bude rovnať napríklad 7: (e=7).
• Predstavme si zašifrovanú správu ako postupnosť čísel v rozsahu od 0 do 32 (nezabudnite, že končí na n-1). Písmeno A = 1, B = 2, C = 3.

Teraz poďme zašifrovať správu pomocou verejného kľúča (7.33)

C1 = (3^7) mod 33 = 2187 mod 33 = 9;
C2 = (1^7) mod 33 = 1 mod 33 = 1;
C3 = (2^7) mod 33 = 128 mod 33 = 29;

Teraz poďme dešifrovať dáta pomocou súkromného kľúča (3.33).

M1 = (9^3) mod 33 = 729 mod 33 = 3 (C);
M2=(1^3) mod 33 = 1 mod 33 = 1 (A);
M3=(29^3) mod 33 = 24389 mod 33 = 2(B);

Údaje boli dešifrované!

Pri každom šifrovacom cykle kryptosystém RSA transformuje binárny blok otvoreného textu m s dĺžkou veľkosti (n), považovaný za celé číslo, podľa vzorca: c = m e (mod n).

V tomto prípade n = pq , kde p a q sú náhodné prvočísla s veľkou šírkou, ktoré sa po vytvorení modulu a kľúčov zničia. Verejný kľúč pozostáva z dvojice čísel e a n . Podkľúč e sa vyberie ako dostatočne veľké číslo z rozsahu 1< e < φ(n), с условием: НОД(e, j(n)) = 1, где j(n) - наименьшее общее кратное чисел p–1 и q–1. Ďalej pri riešení rovnice xe + yφ(n) = 1 v celých číslach x, y predpokladáme d = x, t.j. ed = 1(j(n)). V tomto prípade pre všetky m platí vzťah: m ed = m(n) , preto znalosť d umožňuje dešifrovať kryptogramy.

Na zabezpečenie spoľahlivej informačnej bezpečnosti majú systémy verejného kľúča nasledujúce dve požiadavky.

1. Transformácia zdrojového textu musí vylúčiť jeho obnovu na základe verejného kľúča.

2. Určenie súkromného kľúča na základe verejného kľúča musí byť tiež výpočtovo neuskutočniteľné. V tomto prípade je žiaduca presná dolná hranica zložitosti (počet operácií) prelomenia šifry.

Šifrovacie algoritmy s verejným kľúčom sú široko používané v moderných informačných systémoch.

Pozrime sa na konštrukciu kryptosystému RSA na jednoduchom príklade.

1. Zvoľte p = 3 a q = 11.

2. Definujte n = 3 ∙ 11 = 33.

3. Nájdite j(n) = (p – 1)(q – 1) = 20.

5. Vyberte číslo d, ktoré vyhovuje 7d = 1 (mod 20).

Je ľahké vidieť, že d = 3 (mod 20).

Predstavme si zašifrovanú správu ako postupnosť celých čísel pomocou korešpondencie: A = 1, B = 2, C = 3, ..., Z = 26. Keďže veľkosť (n) = 6 , potom je náš kryptosystém schopný zašifrovať písmená latinskej abecedy, považované za bloky. Zverejnime verejný kľúč (e, n) = (7, 33) a pozvime ostatných účastníkov tajného komunikačného systému, aby nám zaslané správy zašifrovali pomocou Nech je taká správa CAB , ktorý v nami zvolenom kódovaní má tvar (3, 1, 2). Odosielateľ musí zašifrovať každý blok a poslať zašifrovanú správu na našu adresu:

RSA(C) = RSA(3) = 37 = 2187 = 9 (mod 33);
RSA(A) = RSA(1) = 17 = 1 (mod 33);
RSA(B) = RSA(1) = 27 = 128 = 29 (mod 33).

Po prijatí zašifrovanej správy (9, 1, 29) ju môžeme dešifrovať na základe tajného kľúča (d, n) = (3, 33), čím sa každý blok zvýši na d = 3:

93 = 729 = 3 (mod 33);
13 = 1 (mod 33);
29 3 = 24389 = 2 (mod 33).

Pre náš príklad je ľahké nájsť tajný kľúč hrubou silou. V praxi je to nemožné, pretože Pre praktické použitie sa v súčasnosti odporúčajú nasledujúce hodnoty veľkosti (n): :

· 512–768 bitov – pre jednotlivcov;

· 1024 bitov – pre komerčné informácie;

· 2048 bit - pre utajované skutočnosti.

Príklad implementácie algoritmu RSA je uvedený vo výpisoch 18.1 a 18.2 (kompilátory - Delphi, FreePascal).

Výpis 18.1. Príklad implementácie algoritmu RSA v jazyku Pascal

program Rsa;
($APPTYPE KONZOLE)
($IFDEF FPC)
($MODE DELPHI)
($ENDIF)

používa SysUtils, uBigNumber;

//Generátor náhodných čísel

var t: pole Byte;
var pos: Integer;
var cbox: pole Byte =
(237, 240, 161, 1, 130, 141, 205, 98, 27, 169, 181, 202, 173, 47, 114, 224, 35, 183, 79, 82, 153, 220, 172, 22, 17, 11, 200, 131, 14, 154, 167, 91, 250, 31, 213, 112, 126, 241, 236, 155, 198, 96, 87, 143, 244, 151, 134, 38, 129, 233, 186, 101, 41, 94, 231, 115, 113, 199, 51, 145, 229, 37, 69, 180, 85, 33, 207, 163, 102, 187, 4, 89, 7, 44, 75, 88, 81, 120, 10, 232, 221, 168, 230, 158, 247, 211, 216, 156, 95, 64, 242, 215, 77, 165, 122, 5, 15, 119, 100, 43, 34, 48, 30, 39, 195, 222, 184, 92, 78, 135, 103, 166, 147, 32, 60, 185, 26, 251, 214, 90, 139, 45, 73, 150, 97, 116, 136, 68, 219, 248, 191, 192, 16, 8, 243, 50, 132, 105, 62, 201, 204, 65, 0, 99, 182, 121, 194, 108, 160, 170, 56, 226, 206, 254, 117, 178, 9, 197, 234, 127, 58, 171, 40, 29, 177, 142, 3, 228, 188, 162, 212, 157, 49, 175, 174, 140, 70, 106, 123, 66, 196, 246, 179, 42, 218, 71, 217, 227, 18, 164, 24, 67, 159, 25, 111, 255, 193, 245, 2, 238, 133, 21, 137, 152, 109, 148, 63, 124, 203, 104, 54, 55, 223, 80, 107, 210, 225, 149, 252, 76, 12, 189, 93, 46, 23, 13, 36, 209, 61, 249, 110, 144, 86, 52, 253, 72, 28, 53, 57, 125, 59, 235, 84, 128, 208, 146, 20, 74, 6, 239, 190, 83, 19, 138, 118, 176);

postup IicMyRandom;
var i: celé číslo;
var s: reťazec;
začať
WriteLn("Zadajte nejaký text na inicializáciu generátora
náhodné čísla (až 256 znakov):");
ReadLn(s);
i:= 1;
kým<=255) and (i<=Length(s)) do

Šifrovanie RSA je jedným z prvých praktických kryptosystémov s verejným kľúčom a je široko používané na bezpečný prenos dát. Jeho hlavným rozdielom od podobných služieb je, že šifrovací kľúč je verejný a líši sa od dešifrovacieho kľúča, ktorý je utajený. Technológia RSA je založená na praktickej náročnosti faktorizácie dvoch veľkých prvočísel (problém faktorizácie).

História stvorenia

Názov RSA sa skladá zo začiatočných písmen priezvisk Rivest, Shamir a Adleman, vedci, ktorí ich prvýkrát verejne opísali v roku 1977. Clifford Cox, anglický matematik, ktorý pracoval pre britské spravodajské služby, prvýkrát vyvinul ekvivalentný systém v roku 1973, ale odtajnený bol až v roku 1997.

Používateľ RSA vytvorí a potom zverejní verejný kľúč založený na dvoch veľkých prvočíslach spolu s pomocnou hodnotou. musí zostať v tajnosti. Každý môže použiť verejný kľúč na zašifrovanie správy, ale ak je dostatočne veľký, potom môže správu dekódovať iba niekto, kto pozná prvočísla. Je známe, že prelomenie šifrovania RSA je hlavným problémom: dnes prebieha otvorená diskusia o tom, ako bezpečný je mechanizmus.

RSA je relatívne pomalý algoritmus, a preto ho priamy používateľ príliš nepoužíva. Najbežnejšie použitie tejto metódy je prenos zašifrovaných zdieľaných kľúčov pre symetrický šifrovací kľúč, ktorý zase môže vykonávať hromadné šifrovacie a dešifrovacie operácie oveľa vyššou rýchlosťou.

Kedy sa kryptosystém objavil vo svojej modernej podobe?

Myšlienka kryptosystému asymetrického kľúča sa pripisuje Diffiemu a Hellmanovi, ktorí tento koncept zverejnili v roku 1976, predstavili digitálne podpisy a pokúsili sa aplikovať teóriu čísel. Ich formulácia využíva zdieľaný tajný kľúč vytvorený z exponentu nejakého čísla modulo prvočíslo. Problém implementácie tejto funkcie však nechali otvorený, keďže princípy faktoringu v tom čase neboli dobre pochopené.

Rivest, Adi Shamir a Adleman na MIT urobili v priebehu roka niekoľko pokusov o vytvorenie jednosmernej funkcie, ktorú je ťažké dekódovať. Rivest a Shamir (ako počítačoví vedci) navrhli mnoho potenciálnych funkcií, zatiaľ čo Adleman (ako matematik) hľadal slabé stránky algoritmu. Využili mnoho prístupov a nakoniec v apríli 1977 vyvinuli konečný systém, dnes známy ako RSA.

Digitálny podpis a verejný kľúč

Elektronický digitálny podpis alebo EDS je neoddeliteľnou súčasťou elektronických dokumentov. Vzniká určitou kryptografickou zmenou údajov. Pomocou tohto atribútu je možné skontrolovať integritu dokumentu, jeho dôvernosť a tiež určiť, kto je jeho vlastníkom. V podstate ide o alternatívu k bežnému štandardnému podpisu.

Tento kryptosystém (šifrovanie RSA) ponúka verejný kľúč, čím sa líši od symetrických. Princíp jeho fungovania spočíva v tom, že sa používajú dva rôzne kľúče – súkromný (šifrovaný) a verejný. Prvý slúži na vygenerovanie elektronického podpisu a následne možnosť dešifrovať text. Druhá je na samotné šifrovanie a overenie digitálneho podpisu.

Použitie podpisu nám umožňuje lepšie pochopiť šifrovanie RSA, ktorého príklad možno uviesť ako obyčajný klasifikovaný dokument „zatvorený pred zvedavými očami“.

Čo je podstatou algoritmu?

Algoritmus RSA pozostáva zo štyroch fáz: generovanie kľúča, distribúcia kľúča, šifrovanie a dešifrovanie. Ako už bolo uvedené, šifrovanie RSA zahŕňa verejný kľúč a súkromný kľúč. Open môže byť známy každému a používa sa na šifrovanie správ. Jeho podstatou je, že správy zašifrované pomocou verejného kľúča je možné dešifrovať iba v určitom časovom období pomocou súkromného kľúča.

Aby ste boli v bezpečí, celé čísla by mali byť vybrané náhodne a mali by mať rovnakú veľkosť, ale mali by sa líšiť v dĺžke o niekoľko číslic, aby sa faktoring sťažil. Identické čísla možno efektívne nájsť pomocou testu ich primality, takže šifrovanie informácií sa musí nevyhnutne skomplikovať.

Verejný kľúč pozostáva z modulu a verejného exponentu. Private pozostáva z modulu a súkromného indikátora, ktorý musí byť utajený.

Šifrovanie súborov RSA a slabé stránky

Existuje však množstvo mechanizmov na prelomenie jednoduchého RSA. Pri šifrovaní s nízkymi rýchlosťami a malými číslami je možné šifru ľahko prelomiť, ak nájdete koreň šifrového textu cez celé čísla.

Pretože šifrovanie RSA je deterministický algoritmus (t. j. nemá žiadnu náhodnú zložku), útočník môže úspešne spustiť vybraný útok otvoreného textu proti kryptosystému zašifrovaním hodnoverných otvorených textov pod verejným kľúčom a skontrolovaním, či sa zhodujú so šifrovaným textom. O kryptosystéme sa hovorí, že je sémanticky bezpečný, ak útočník nedokáže rozlíšiť dve šifry od seba, aj keď pozná zodpovedajúce texty vo vyčistenej forme. Ako je popísané vyššie, RSA bez doplnenia o ďalšie služby nie je sémanticky bezpečné.

Ďalšie šifrovacie a bezpečnostné algoritmy

Aby sa predišlo vyššie uvedeným problémom, praktické implementácie RSA sa pred šifrovaním zvyčajne zabudujú do nejakej formy štruktúrovanej, náhodnej výplne. To zaisťuje, že obsah nespadá do rozsahu nezabezpečeného otvoreného textu a že správa nemôže byť náhodne kompromitovaná.

Bezpečnosť kryptosystému RSA a šifrovanie informácií sú založené na dvoch matematických problémoch: problém faktorizácie veľkých čísel a samotný problém RSA. Úplné zverejnenie šifrovaného textu a digitálneho podpisu v RSA sa považuje za neprijateľné za predpokladu, že oba tieto problémy nemožno vyriešiť spoločne.

Vďaka schopnosti obnoviť prvočísla však môže útočník vypočítať tajný exponent z verejného kľúča a následne text dešifrovať pomocou štandardného postupu. Hoci dnes nebola nájdená žiadna existujúca metóda na faktorizáciu veľkých čísel na klasickom počítači, nebolo dokázané, že neexistuje.

automatizácia

Na zefektívnenie tohto procesu možno použiť nástroj s názvom Yafu. Automatizácia v YAFU je najmodernejšia funkcia, ktorá kombinuje faktorizačné algoritmy v inteligentnej a adaptívnej metodológii, ktorá minimalizuje čas na nájdenie faktorov ľubovoľných vstupných čísel. Väčšina implementácií algoritmu je viacvláknová, čo Yafu umožňuje plne využívať výhody viacerých alebo viacerých (vrátane SNFS, SIQS a ECM). V prvom rade je to spravovaný nástroj príkazového riadku. Čas strávený hľadaním šifrovacieho faktora pomocou Yafu na bežnom počítači možno skrátiť na 103,1746 sekúnd. Nástroj produkuje kapacitu spracovania 320 bitov alebo viac. Ide o veľmi zložitý softvér, ktorého inštalácia a konfigurácia vyžaduje určité technické zručnosti. Šifrovanie RSA C teda môže byť zraniteľné.

Hackerské pokusy v modernej dobe

V roku 2009 Benjamin Moody pomocou RSA-512 bitového kľúča pracoval na dešifrovaní kryptotextu 73 dní len pomocou bežného softvéru (GGNFS) a priemerného stolného počítača (dvojjadrový Athlon64 na 1900 MHz). Ako ukázala táto skúsenosť, na proces „preosievania“ bolo potrebných o niečo menej ako 5 gigabajtov disku a približne 2,5 gigabajtov pamäte RAM.

Od roku 2010 bolo najväčšie faktorizované číslo RSA dlhé 768 bitov (232 desatinných číslic alebo RSA-768). Jeho nasadenie trvalo dva roky na niekoľkých stovkách počítačov súčasne.

V praxi sú kľúče RSA dlhšie – zvyčajne od 1024 do 4096 bitov. Niektorí odborníci sa domnievajú, že 1024-bitové kľúče sa môžu v blízkej budúcnosti stať nezabezpečenými, alebo ich dokonca už môže prelomiť primerane financovaný útočník. Málokto by však namietal, že v dohľadnej dobe môžu byť odhalené aj 4096-bitové kľúče.

Perspektívy

Preto sa všeobecne predpokladá, že RSA je bezpečná, ak sú čísla dostatočne veľké. Ak je základné číslo 300 bitov alebo menej, šifrový text a digitálny podpis je možné rozložiť v priebehu niekoľkých hodín na osobnom počítači pomocou softvéru, ktorý je už voľne dostupný. 512-bitové kľúče sa ukázali byť prelomiteľné už v roku 1999 pomocou niekoľkých stoviek počítačov. V súčasnosti je to možné v priebehu niekoľkých týždňov pomocou verejne dostupného hardvéru. Je teda celkom možné, že v budúcnosti bude šifrovanie RSA ľahko prelomené na prstoch a systém bude beznádejne zastaraný.

Oficiálne bola v roku 2003 spochybnená bezpečnosť 1024-bitových kľúčov. V súčasnosti sa odporúča mať dĺžku aspoň 2048 bitov.