Základy kryptografie pro manažery: RSA

Šifra RSA patří v současné době mezi nejpoužívanější a nejoblíbenější asymetrické šifry. V tomto příspěvku se dozvíte, jak tento šifrovací algoritmus funguje.

Verejným kľúčom je dvojica čísel n (modulus), e (verejný exponent). Ako privátny kľúč sa používa dvojica čísel n (modulus) a d (privátny exponent). Voľbu čísel n, e, d si popíšeme v časti Generovanie kľúča. Teraz sa pozrieme na šifrovanie a dešifrovanie v RSA pomocou verejného kľúča (n, e) a privátneho kľúča (n, d). Predpokladajme najskôr, že Bob chce Alici poslať tajné celé číslo m také, že 0≤m<n (číslo m musí byť v tomto rozsahu!). Pomocou Alicinho verejného kľúča (n, e) Bob jednoducho zašifruje číslo m:

c=m^e mod n

Takto spočítané c (šifra čísla m) pošle Alici cez verejný kanál. Alica príjme číslo c,ktoré dešifruje pomocou svojho privátneho kľúča d nasledovne:

c^d mod n=m

To, že dešifrovanie vždy správne funguje, je spôsobené práve špeciálnou voľbou čísel n, e, d (verejného a privátneho kľúča). Alica teda získala číslo m, ktoré jej Bob poslal zašifrované. Zároveň pre útočníka, ktorému sa podarilo zachytiť posielané číslo c, je prakticky nemožné spočítať pôvodné číslo m bez znalosti privátneho kľúča d. Toto je hlavná myšlienka RSA.

Samozrejme, v skutočnom svete Bob posiela Alici správy a nie čísla. K tomu existuje špeciálny protokol, ktorý vie previesť správu na čísla a naopak z čísel vie zrekonštruovať pôvodnú správu. Nie je veľmi komplikovaný, nižšie si povieme jeho hlavnú myšlienku. Ak chce teda Bob poslať Alici správu M, prevedie ju najskôr s použitím protokolu na čísla (tieto čísla budú nezáporné a menšie ako číslo n z verejného kľúča – o to sa postará spomínaný protokol). Takto získané čísla Bob zašifruje, ako sme si ukázali vyššie a pošle ich Alici. Alica ich dešifruje a pomocou protokolu zrekonštruuje pôvodnú správu.

Nespomenieme detaily tohto protokolu, to však k jeho pochopeniu nie je vôbec podstatné. Hlavnou myšlienkou je, že na každú správu uloženú v počítači sa môžeme pozerať ako na číslo. To je dané tým, že v počítači je každá informácia uložená pomocou postupnosti 0 a 1. Napríklad jednoduchá správa M=„:)“ (smajlík) je v počítači uložená ako 0011101000101001, čo je číslo 14889 zapísané v dvojkovej sústave. Teda správu uloženú v počítači môžeme chápať ako nejaké číslo.

Pomocou RSA vieme ale šifrovať iba čísla určitej veľkosti (nesmú byť väčšie ako modulus n z verejného kľúča). Preto, ak je to potrebné, protokol rozdelí správu (číslo) na menšie kúsky (menšie čísla), ktoré potom šifrujeme pomocou RSA. Naopak, ak chceme z čísel zrekonštruovať správu, protokol v podstate iba pospája tieto čísla (presnejšie, pospája ich zápis v dvojkovej sústave). Spôsob, akým protokol správu rozdeľuje na menšie a ako správu rekonštruuje, je presne daný. Tento protokol môžeme obrazne chápať ako súčasť „manuálu na používanie RSA“.

Generovanie kľúča

Generovanie kľúča RSA prebieha v troch hlavných krokoch:

1. Voľba n (modulus): nájdeme dve rôzne prvočísla p, q a položíme n = p*q
2. Voľba e (verejný exponent): e zvolíme tak, aby 2≤e<(p−1)*(q−1) a zároveň, aby e bolo nesúdeliteľné s číslom (p−1)*(q−1)
3. Voľba d (privátny exponent): d zvolíme tak, aby platilo e⋅d mod (p−1)*(q−1)=1

Prvému kroku sa venovať nebudeme, stačí poznamenať, že v súčasnosti nie je problém nájsť prvočísla, ktoré majú viac ako sto cifier. Druhý krok je jednoduchý. Volíme náhodne číslo r v rozsahu 2≤r<(p−1)*(q−1), až kým nenájdeme také, ktoré je nesúdeliteľné s (p−1)*(q−1). Potom iba položíme e = r. Číslo d v treťom kroku sa spočíta pomocou tzv. Rozšíreného Euklidovho algoritmu.

Ako sme už spomínali, privátnym kľúčom sa stáva dvojica čísel (n, d) a verejným kľúčom dvojica (n, e). Je ale dôležité upozorniť, že zverejníme hodnotu n a e, v žiadnom prípade nie prvočísla p, q, z ktorých n „vzniklo“. Prečo tomu tak je, si vysvetlíme v časti V čom spočíva bezpečnosť šifry RSA.

Príklad jednoduchého použitia

Teraz už konečne vieme, ako funguje RSA a vieme si vytvoriť vlastný verejný a privátny kľúč. Skúsme si teda vyrobiť naše prvé vlastné maličké RSA. Vygenerujme si najskôr kľúče podľa postupu z predchádzajúcej časti:

1. Zvolíme prvočísla p, q: p=3, q=11. Spočítame n: n=p*q=3*11=33.
2. Hľadáme e, tak aby 2≤e<(3−1)*(11−1) a zároveň, aby e bolo nesúdeliteľné s číslom 20. Túto podmienku spĺňa napr. číslo 3, teda môžeme položiť e=3.
3. Chceme nájsť číslo d, pre ktoré platí 3*d mod 20=1. Pre takto malé čísla sa dá hľadané d celkom ľahko uhádnuť, takže nemusíme použiť spomínaný Rozšírený Euklidov algoritmus. Napríklad 3*7 mod 20=1, teda môžeme zvoliť d=7.

Verejným kľúčom je dvojica n=33, e=3 a privátnym kľúčom dvojica n=33, d=7. Pomocou verejného kľúča zašifrujeme teraz m=9:

c=m^mod n=9^3 mod 33=729 mod 33=3

Pomocou privátneho kľúča dešifrujeme c=3:

c^d mod n=3^7 mod 33=2187 mod 33=9

Ako vidíme, výsledkom dešifrovania je pôvodné číslo m=9. Môžete si to vyskúšať aj pre iné čísla v rozsahu 0 až 32. Skúsme teraz zašifrovať smajlíka, t.j. správu M=„:)“. Protokol prevedie správu M na čísla: m1=7, m2=8, m3=20. Správa je síce iba dvojznaková, náš kľúč je ale príliš malý, preto nám ju protokol previedol až na tri čísla. Tie zašifrujeme pomocou verejného kľúča:

c1=m1^e mod n=7^3 mod 33=343 mod 33=13
c2=m2^e mod n=8^3 mod 33=512 mod 33=17
c3=m3^e mod n=20^3 mod 33=8000 mod 33=14

Šifrou správy M = „:)“ je teda trojica čísel (c1, c2, c3)=(13,17 ,14). Čo urobí majiteľ privátneho kľúča, ktorý príjme zašifrovanú správu (c1, c2, c3) ? Najskôr dešifruje jednotlivé čísla:

c1^d mod n=137 mod 33=62 748 517 mod 33=7
c2^d mod n=177 mod 33=410 338673 mod 33=8
c3^d mod n=147 mod 33=105 413 504 mod 33=20

Z trojice čísel (7,8,20)=(m1,m2, m3) vie už príjemca správy pomocou protokolu odvodiť pôvodnú správu M = „:)“.

V čom spočíva bezpečnosť šifry RSA

Bezpečnosť šifry RSA (tak ako bezpečnosť každej asymetrickej šifry) záleží najmä na tom, aké ťažké je pre útočníka odhaliť privátny kľúč, ak pozná iba kľúč verejný. V našom prípade teda, aké náročné je len zo znalosti (n, e) odvodiť privátny exponent d. Vieme, že n=p*q (viď časť Generovanie kľúča). Všimnime si, že ak by útočník poznal p, q, nerobilo by mu už problém spočítať privátny kľúč d (presne podľa kroku č. 3 v časti Generovanie kľúča). Naopak, ak čísla p, q útočník nepozná, nemá prakticky žiadnu možnosť, ako d odhaliť. Preto je podstatné, že súčasťou verejného kľúča je číslo n a nie prvočísla p, q.

Môže nás napadnúť, že na tom nezáleží, predsa keď už útočník pozná n, nemal by byť problém odhaliť prvočísla p, q. (delitele čísla n). Skutočne, ak je n veľmi malé (napr. n=15 alebo n=77), tak p, q spočítame z hlavy (15=3*5, 77=7*11). Ak je n väčšie, mal by to za nás zvládnuť počítač. To už ale tak úplne neplatí. Ak n je naozaj veľké (povedzme viac ako 300-ciferné číslo) a pri jeho generácii (podľa kroku č. 1 v časti Generovanie kľúča) boli p, q šikovne zvolené, potom pri znalosti iba čísla n odhaliť jeho delitele p, q je veľmi náročná úloha aj pre dnešné počítače. Takýto výpočet by trval niekoľko rokov aj na v súčasnosti najvýkonnejších počítačoch pri použití najlepších známych algoritmov. Na tomto fakte stojí bezpečnosť RSA.

Parametre súčasnej RSA

V našom príklade sme vytvorili verejný kľúč n=33, e=3 a privátny exponent d=7. Pozrime sa teraz na to, ako môžu vyzerať kľúče pri praktickom použití RSA. Pri reálnom nasadení RSA sa v súčasnosti volí číslo n väčšinou približne 300, resp. 600 ciferné (presnejšie 1024, resp. 2048 bitové). Volí sa také veľké práve preto, aby bolo prakticky nemožné zo znalosti n spočítať prvočísla p, q a tým prelomiť RSA.

Poznámka: Šifru založenú na rovnakom princípe ako RSA popísal už v roku 1974 britský matematik Clifford Cocks pracujúci pre britskú spravodaskú agentúru GCHQ. Tá ju v tom čase zavrhla ako v praxi nepoužiteľnú. Napriek tomu Cocks svoj objav zverejniť nemohol, pretože jeho práca podliehala utajeniu. Nezávisle na práci Clifforda Cocksa objavila šifru RSA trojica ľudí Ron Rivest, Adi Shamir a Leonard Adleman (odtiaľ pochádza aj názov šifry, ktorý je tvorený prvými písmenami ich priezvisok). Tí ju spoločne publikovali v roku 1978.

Autor: Ján Jančo

Štítky: informační bezpečnost, kryptografie

Diskuse na tomto webu je moderována. Pod článkem budou zobrazovány jen takové komentáře, které nebudou sloužit k propagaci konkrétní firmy, produktu nebo služby. V případě, že chcete, aby z těchto stránek vedl odkaz na váš web, kontaktujte nás, známe efektivnější způsoby propagace.