Algoritmus RSA

Šifrovanie správy

Alica odovzdá svoj verejný kľúč ( n {\displaystyle n\,} & e {\displaystyle e\,} ) Bobovi a svoj súkromný kľúč uchová v tajnosti. Bob chce Alici poslať správu M.

Najprv zmení M na číslo m {\displaystyle m} menšie ako n {\displaystyle n} pomocou dohodnutého reverzibilného protokolu známeho ako schéma vypĺňania. Potom vypočíta šifrový text c {\displaystyle c\,} zodpovedajúci:

c = m e mod n {\displaystyle c=m^{e}\mod {n}}

To sa dá rýchlo vykonať pomocou metódy exponenciácie kvadratickým delením. Bob potom pošle c {\displaystyle c\,} Alici.

Dešifrovanie správy

Alica môže obnoviť m {\displaystyle m\,} z c {\displaystyle c\,} pomocou svojho súkromného kľúča d {\displaystyle d\,} nasledujúcim postupom:

m = c d mod n {\displaystyle m=c^{d}{\bmod {n}}}

Vzhľadom na m {\displaystyle m\,} , môže obnoviť pôvodné rôzne prvočísla, pričom aplikáciou čínskej zvyškovej vety na tieto dve kongruencie dostaneme

m e d ≡ m mod p q {\displaystyle m^{ed}\equiv m{\bmod {pq}}} .

Takto,

c d ≡ m mod n {\displaystyle c^{d}\equiv m{\bmod {n}}} .

Pracovný príklad

Tu je príklad šifrovania a dešifrovania RSA. Tu použité parametre sú umelo malé, ale na vygenerovanie a preskúmanie skutočného páru kľúčov môžete použiť aj OpenSSL.

1. Vyberte si dve náhodné prvočísla.
2.  : p = 61 {\displaystyle p=61} a q = 53 ; {\displaystyle q=53;} Vypočítajte n = p q {\displaystyle n=pq\,}
3.  : n = 61 ∗ 53 = 3233 {\displaystyle n=61*53=3233}
4. Vypočítajte totient ϕ ( n ) = ( p - 1 ) ( q - 1 ) {\displaystyle \phi (n)=(p-1)(q-1)\,}
5.  : ϕ ( n ) = ( 61 - 1 ) ( 53 - 1 ) = 3120 {\displaystyle \phi (n)=(61-1)(53-1)=3120}
6. Zvoľte e > 1 {\displaystyle e>1} koprime to 3120
7.  : e = 17 {\displaystyle e=17}
8. Zvoľte d {\displaystyle d\,} tak, aby vyhovovalo d e mod ϕ ( n ) ≡ 1 {\displaystyle de{\bmod {\phi (n)}}\equiv 1\,}
9.  : d = 2753 {\displaystyle d=2753}
10.  : 17 ∗ 2753 = 46801 = 1 + 15 ∗ 3120 {\displaystyle 17*2753=46801=1+15*3120} .

Verejný kľúč je ( n = 3233 {\displaystyle n=3233} , e = 17 {\displaystyle e=17} ). Pre správu m {\displaystyle m\,} sa šifrovacia funkcia c = m e mod n {\displaystyle c=m^{e}{\bmod {n}}} stáva:

c = m 17 mod 3 233 {\displaystyle c=m^{17}{\bmod {3}}233\,}

Súkromný kľúč je ( n = 3233 {\displaystyle n=3233} , d = 2753 {\displaystyle d=2753} ). Dešifrovacia funkcia m = c d mod n {\displaystyle m=c^{d}{\bmod {n}}} sa stáva:

m = c 2753 mod 3 233 {\displaystyle m=c^{2753}{\bmod {3}}233\,}

Napríklad na zašifrovanie m = 123 {\displaystyle m=123} , vypočítame

c = 123 17 mod 3 233 = 855 {\displaystyle c=123^{17}{\bmod {3}}233=855}

Dešifrovanie c = 855 {\displaystyle c=855} , vypočítame

m = 855 2753 mod 3 233 = 123 {\displaystyle m=855^{2753}{\bmod {3}}233=123}

Oba tieto výpočty sa dajú efektívne vypočítať pomocou algoritmu square-and-multiply pre modulárne exponenciovanie [en].

Odvodenie RSA rovnice z Eulerovej vety

RSA možno ľahko odvodiť pomocou Eulerovej vety a Eulerovej funkcie totient.

Začíname Eulerovou vetou,

m ϕ ( n ) ≡ 1 ( mod n ) {\displaystyle m^{\phi (n)}\equiv 1{\pmod {n}}}

musíme ukázať, že dešifrovaním zašifrovanej správy so správnym kľúčom získame pôvodnú správu. Pri danej zašifrovanej správe m sa zašifrovaný text c vypočíta takto

c ≡ m e ( mod n ) {\displaystyle c\equiv m^{e}{\pmod {n}}}

Po dosadení do dešifrovacieho algoritmu máme

c d ≡ ( m e ) d ≡ m e d ( mod n ) {\displaystyle c^{d}\equiv (m^{e})^{d}\equiv m^{ed}{\pmod {n}}}

Chceme ukázať, že táto hodnota je tiež zhodná s m. Hodnoty e a d boli zvolené tak, aby vyhovovali,

e d ≡ 1 ( mod ϕ ( n ) ) {\displaystyle ed\equiv 1{\pmod {\phi (n)}}}

To znamená, že existuje nejaké celé číslo k, že

e d = k × ϕ ( n ) + 1 {\displaystyle ed=k\times \phi (n)+1}

Teraz nahrádzame zašifrovanú a následne dešifrovanú správu,

m e d ≡ m k ϕ ( n ) + 1 ≡ m × m k ϕ ( n ) ≡ m × ( m ϕ ( n ) ) k ( mod n ) {\displaystyle {\begin{aligned}m^{ed}&\equiv m^{k\phi (n)+1}\&\equiv m\times m^{k\phi (n)}\&\equiv m\times \left(m^{\phi (n)}\right)^{k}{\pmod {n}}\end{aligned}}}

Použijeme Eulerovu vetu a dostaneme výsledok.

m × ( 1 ) k ≡ m ( mod n ) {\displaystyle m\times (1)^{k}\equiv m{\pmod {n}}}

Schémy vypĺňania

Pri praktickom používaní sa RSA musí kombinovať s nejakou formou vypchávkovej schémy, aby žiadne hodnoty M neviedli k nezabezpečeným šifrovým textom. RSA používaná bez vypĺňania môže mať určité problémy:

• Hodnoty m = 0 alebo m = 1 vždy vytvárajú šifrové texty rovné 0, resp. 1, vzhľadom na vlastnosti exponenciácie.
• Pri šifrovaní s malými šifrovacími exponentmi (napr. e = 3) a malými hodnotami m môže byť (nemodulárny) výsledok m e {\displaystyle m^{e}} striktne menší ako modul n. V takomto prípade možno šifrové texty ľahko dešifrovať tak, že z šifrového textu vezmeme etickú odmocninu bez ohľadu na modul.
• Šifrovanie RSA je deterministický šifrovací algoritmus. Neobsahuje žiadnu náhodnú zložku. Útočník preto môže úspešne vykonať útok na zvolený otvorený text proti kryptosystému. Môže vytvoriť slovník zašifrovaním pravdepodobných otvorených textov pod verejným kľúčom a uložením výsledných šifrových textov. Útočník potom môže pozorovať komunikačný kanál. Akonáhle uvidí šifrové texty, ktoré sa zhodujú s tými v jeho slovníku, útočníci potom môžu tento slovník použiť na zistenie obsahu správy.

V praxi môžu prvé dva problémy vzniknúť pri odosielaní krátkych správ ASCII. V takýchto správach môže byť m spojením jedného alebo viacerých znakov kódovaných v ASCII. Správa pozostávajúca z jedného znaku ASCII NUL (ktorého číselná hodnota je 0) by bola zakódovaná ako m = 0, čo by viedlo k šifrovému textu 0 bez ohľadu na to, aké hodnoty e a N sa použijú. Podobne, jeden znak ASCII SOH (ktorého číselná hodnota je 1) by vždy vytvoril šifrový text 1. Pre systémy, ktoré bežne používajú malé hodnoty e, napríklad 3, by všetky správy s jedným znakom ASCII kódované pomocou tejto schémy boli nezabezpečené, pretože najväčšie m by malo hodnotu 255 a 255³ je menej ako akýkoľvek rozumný modul. Takéto otvorené texty by sa dali obnoviť jednoduchým použitím odmocniny zo šifrového textu.

Aby sa predišlo týmto problémom, praktické implementácie RSA zvyčajne vkladajú do hodnoty m pred jej zašifrovaním určitú formu štruktúrovanej, náhodne vybranej výplne. Toto vypĺňanie zabezpečuje, že m nespadá do rozsahu nezabezpečených otvorených textov a že daná správa sa po vypĺňaní zašifruje do jedného z veľkého počtu rôznych možných šifrových textov. Posledná vlastnosť môže zvýšiť náklady na slovníkový útok nad možnosti rozumného útočníka.

Štandardy, ako je PKCS, boli starostlivo navrhnuté tak, aby bezpečne vypĺňali správy pred šifrovaním RSA. Pretože tieto schémy vypĺňajú otvorený text m určitým počtom dodatočných bitov, veľkosť nevypĺňanej správy M musí byť o niečo menšia. Schémy vypĺňania RSA musia byť starostlivo navrhnuté tak, aby zabránili sofistikovaným útokom. To môže uľahčiť predvídateľná štruktúra správy. Rané verzie štandardu PKCS používali ad-hoc konštrukcie, ktoré sa neskôr ukázali ako zraniteľné praktickým adaptívnym útokom na vybraný šifrový text. Moderné konštrukcie využívajú bezpečné techniky, ako je optimálne asymetrické šifrovanie (Optimal Asymmetric Encryption Padding - OAEP), ktoré chránia správy a zároveň zabraňujú týmto útokom. Norma PKCS obsahuje aj schémy spracovania určené na zabezpečenie dodatočnej bezpečnosti podpisov RSA, napr. pravdepodobnostnú podpisovú schému pre RSA (RSA-PSS).

Podpisovanie správ

Predpokladajme, že Alica použije Bobov verejný kľúč, aby mu poslala zašifrovanú správu. V správe môže tvrdiť, že je Alica, ale Bob nemá žiadnu možnosť overiť, že správa bola skutočne od Alice, pretože ktokoľvek môže použiť Bobov verejný kľúč na odosielanie zašifrovaných správ. Na overenie pôvodu správy sa teda RSA môže použiť aj na podpísanie správy.

Predpokladajme, že Alica chce poslať podpísanú správu Bobovi. Vytvorí hash hodnotu správy, zvýši ju na mocninu d mod n (rovnako ako pri dešifrovaní správy) a pripojí ju k správe ako "podpis". Keď Bob dostane podpísanú správu, zvýši podpis na mocninu e mod n (rovnako ako pri šifrovaní správy) a porovná výslednú hodnotu hash so skutočnou hodnotou hash správy. Ak sa tieto dve hodnoty zhodujú, vie, že autor správy mal Alicin tajný kľúč a že so správou odvtedy nikto nemanipuloval.

Všimnite si, že schémy bezpečného vypĺňania, ako je RSA-PSS, sú rovnako dôležité pre bezpečnosť podpisovania správ ako pre šifrovanie správ a že ten istý kľúč by sa nikdy nemal používať na účely šifrovania aj podpisovania.