RSA je asymetrická šifra a je pomenovaná podľa priezvísk jej autorov (Ronald Rivest, Adi Shamir a Leonard Adlemann). Funguje na matematickom výpočte inverzných prvkov zo zvyškovej triede. Jej bezpečnosť je daná našou technologickou nevyspelosťou – je založená na predpoklade, že čím väčšie číslo, tým náročnejšie je ho rozložiť na súčin prvočísel (faktorizácia). Pri číslach, ktoré majú stovky cifier je to už veľmi náročná úloha a v rozumnom čase je prakticky nemožné ju vyriešiť. Je to z toho dôvodu, že v súčasnej dobe nie je známy žiadny efektívny algoritmus ktorý by riešil tento problém. Je teda veľmi dôležité aby v algoritme boli použité veľmi veľké prvočísla a aby neboli príliš blízko seba.
Postup šifrovania s ukážkou na malých číslach:
I. Betka generuje svoj kľúč
- Vygeneruje ľubovoľné dve veľké prvočísla P a Q. Nech zvolí napríklad čísla P = 5 a Q = 11.
- Vypočíta čísla N a F:
N = P × Q = 5 × 11 = 55
F = (P-1) × (Q-1) = 4 × 10 = 40 - Zvolí náhodné číslo B (1 < B < F), nesúdeliteľné s číslom F (ich najväčší spoločný deliteľ je 1). Číslo F je deliteľné 2 a 5 (40 = 23 × 5), ktorými nesmie byť deliteľné číslo B. Nech vyberie napr. číslo B = 3.
- Vypočíta číslo A, ktoré je prevrátená hodnota B vo zvyškovej triede ZF (inverzný prvok, 1/B, resp. B-1). Prevrátená hodnota je definovaná ako (A × B) mod F = 1. Čiže A × B môže byť nejaký násobok F zväčšený o jedna. Matematicky sa to vyjadrí ako A × B = k×F + 1
V našom prípade hľadáme také A, aby A × B bolo 41, 81 alebo 121…
Hľadané číslo je A = 27. - Publikuje čísla N a B ako svoj verejný kľúč. Čiže zverejní N = 55 a B = 3. Číslo A = 27 si ponechá ako svoj súkromný kľúč.
II. Alica zašifruje správu
Textovú (či akúkoľvek inú) správu je nutné najskôr previesť do nejakého číselného tvaru. Povedzme, že Alica chce Betke poslať text, ktorý je reprezentovaný číslom X = 7. Celé šifrovanie spočíva vo výpočte XB mod N, teda 73 mod 55 – výsledok je zašifrovaná správa Y, v našom prípade to bude Y = 13.
Zašifrovanú správu Alica pošle Betke.
III. Betka dešifruje správu
Betka obdržala zašifrovanú správu Y = 13.
Použije svoj tajný dešifrovací exponent (súkromný kľúč) A = 27 a vykoná dešifrovanie: X = YA mod N, teda 1327 mod 55, čo sa rovná 7.
Ako je možné, že to funguje?
Ak by sa šifrovanie aj dešifrovanie dialo vo zvyškovej triede čísla F, teda v ZF, tak by to bolo jednoduché.
Správa X po zašifrovaní by sa matematicky zapísala ako Y = XB mod F.
Šifru Y po dešifrovaní by sme matematicky vyjadrili ako X = YA mod F = (XB mod F)A mod F = XB×A mod F = X1 mod F.
Traja páni autori sa rozhodli to viac sťažiť, tak do toho zakomponovali dva zvyškové priestory, F a N.
Správa X po zašifrovaní sa matematicky zapíše ako Y = XB mod N.
Šifru Y po dešifrovaní matematicky vyjadríme ako X = YA mod N.
Za Y dosadíme vzorec z prvej rovnice: X = (XB mod N)A mod N = XB×A mod N.
Nuž a A a B sme schválne vyberali také, aby (A × B) mod F = 1, teda A × B = k×F + 1
X = Xk×F + 1 mod N = (Xk×F× X) mod N
Mohlo by sa zdať, že už je to hotové, nasleduje však najťažší krok dôkazu. treba ukázať, že Xk×F je 1. Dôkaz sa opiera o Eulerovu vetu a Malú Fermatovú vetu. Ak to čitateľov zaujíma, napíšte do komentára a môžeme článok rozšíriť o tento dôkaz.