Algoritmus RSA

Šifrování zprávy

Alice předá svůj veřejný klíč ( n {\displaystyle n\,} & e {\displaystyle e\,} ) Bobovi a svůj soukromý klíč uchová v tajnosti. Bob chce Alici poslat zprávu M.

Nejprve pomocí dohodnutého reverzibilního protokolu známého jako schéma vycpávek změní M na číslo m {\displaystyle m} menší než n {\displaystyle n} . Poté vypočítá šifrový text c {\displaystyle c\,} odpovídající:

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

To lze rychle provést pomocí metody exponenciálního odmocňování. Bob pak pošle c {\displaystyle c\,} Alici.

Dešifrování zprávy

Alice může obnovit m {\displaystyle m\,} z c {\displaystyle c\,} pomocí svého soukromého klíče d {\displaystyle d\,} následujícím postupem:

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

Vzhledem k tomu, že m {\displayyle m\,} , může obnovit původní různá prvočísla, přičemž použitím čínské věty o zbytku na tyto dvě kongruence získáme

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

Tedy,

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

Pracovní příklad

Zde je příklad šifrování a dešifrování RSA. Zde použité parametry jsou uměle zmenšené, ale pomocí OpenSSL můžete také vygenerovat a prozkoumat skutečný pár klíčů.

1. Vyberte dvě náhodná prvočísla.
2.  : p = 61 {\displaystyle p=61} a q = 53 ; {\displaystyle q=53;} Vypočítejte n = p q {\displaystyle n=pq\,}
3.  : n = 61 ∗ 53 = 3233 {\displaystyle n=61*53=3233}
4. Vypočítejte 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. Zvolte e > 1 {\displaystyle e>1} koprimát 3120
7.  : e = 17 {\displaystyle e=17}
8. Zvolte d {\displaystyle d\,} tak, aby splňovalo 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} .

Veřejný klíč je ( n = 3233 {\displaystyle n=3233} , e = 17 {\displaystyle e=17} ). Pro vycpanou zprávu m {\displaystyle m\,} se šifrovací funkce c = m e mod n {\displaystyle c=m^{e}{\bmod {n}}} stává:

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

Soukromý klíč je ( n = 3233 {\displaystyle n=3233} , d = 2753 {\displaystyle d=2753} ). Dešifrovací funkce m = c d mod n {\displaystyle m=c^{d}{\bmod {n}}} se stává:

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

Například pro zašifrování m = 123 {\displaystyle m=123} , vypočítáme

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

Dešifrování c = 855 {\displaystyle c=855} vypočítáme

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

Oba tyto výpočty lze efektivně vypočítat pomocí algoritmu square-and-multiply pro modulární exponencializaci [cs].

Odvození RSA rovnice z Eulerovy věty

RSA lze snadno odvodit pomocí Eulerovy věty a Eulerovy totientní funkce.

Začněme Eulerovou větou,

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

musíme ukázat, že dešifrováním zašifrované zprávy se správným klíčem získáme původní zprávu. Při zadání vycpané zprávy m se šifrový text c vypočítá takto

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

Po dosazení do dešifrovacího algoritmu máme následující hodnoty

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

Chceme ukázat, že tato hodnota je také kongruentní s m. Hodnoty e a d byly zvoleny tak, aby vyhovovaly,

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

To znamená, že existuje nějaké celé číslo k, které je takové, že

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

Nyní nahradíme zašifrovanou a následně dešifrovanou zprá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 větu a dojdeme k výsledku.

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

Schémata vycpávek

Při praktickém použití je nutné RSA kombinovat s nějakou formou schématu výplně, aby žádné hodnoty M nevedly k nezabezpečeným šifrovým textům. Použití RSA bez polstrování může mít určité problémy:

• Hodnoty m = 0 nebo m = 1 vždy vedou k šifrovým textům rovným 0, resp. 1, což je dáno vlastnostmi exponenciálního zápisu.
• Při šifrování s malými šifrovacími exponenty (např. e = 3) a malými hodnotami m může být (nemodulární) výsledek m e {\displaystyle m^{e}} striktně menší než modul n. V takovém případě lze šifrové texty snadno dešifrovat tak, že se vezme etní odmocnina šifrového textu bez ohledu na modul.
• Šifrování RSA je deterministický šifrovací algoritmus. Neobsahuje žádnou náhodnou složku. Útočník proto může úspěšně provést útok na kryptosystém pomocí vybraného otevřeného textu. Může vytvořit slovník zašifrováním pravděpodobných otevřených textů pod veřejným klíčem a uložením výsledných šifrových textů. Útočník pak může pozorovat komunikační kanál. Jakmile uvidí šifrové texty, které se shodují s těmi v jeho slovníku, mohou pak útočníci tento slovník použít k tomu, aby se dozvěděli obsah zprávy.

První dva problémy mohou v praxi nastat při odesílání krátkých zpráv ASCII. V takových zprávách může být m zřetězením jednoho nebo více znaků kódovaných v ASCII. Zpráva sestávající z jediného znaku ASCII NUL (jehož číselná hodnota je 0) by byla zakódována jako m = 0, což by vedlo k šifrovému textu 0 bez ohledu na to, jaké hodnoty e a N by byly použity. Podobně by jediný znak ASCII SOH (jehož číselná hodnota je 1) vždy vytvořil šifrový text o hodnotě 1. Pro systémy, které běžně používají malé hodnoty e, například 3, by všechny zprávy s jedním znakem ASCII kódované pomocí tohoto schématu byly nezabezpečené, protože největší m by mělo hodnotu 255 a 255³ je méně než jakýkoli rozumný modul. Takové otevřené texty by bylo možné získat jednoduše odmocninou z šifrového textu.

Aby se těmto problémům předešlo, praktické implementace RSA obvykle vkládají do hodnoty m před jejím zašifrováním nějakou formu strukturovaného, náhodně vybraného polštáře. Tato výplň zajišťuje, že m nespadá do rozsahu nezabezpečených otevřených textů a že daná zpráva bude po vyplnění zašifrována do jednoho z velkého počtu různých možných šifrových textů. Tato druhá vlastnost může zvýšit náklady na slovníkový útok nad možnosti rozumného útočníka.

Standardy, jako je PKCS, byly pečlivě navrženy tak, aby před šifrováním RSA bezpečně chránily zprávy. Protože tato schémata doplňují otevřený text m určitým počtem bitů navíc, musí být velikost nezaplněné zprávy M o něco menší. Schémata RSA s polstrováním musí být pečlivě navržena tak, aby zabránila sofistikovaným útokům. To může usnadnit předvídatelná struktura zprávy. Rané verze standardu PKCS používaly ad-hoc konstrukce, které byly později shledány zranitelnými vůči praktickému adaptivnímu útoku na vybraný šifrový text. Moderní konstrukce využívají bezpečné techniky, jako je optimální asymetrické šifrování (Optimal Asymmetric Encryption Padding, OAEP), které chrání zprávy a zároveň zabraňují těmto útokům. Standard PKCS obsahuje také schémata zpracování určená k zajištění dodatečné bezpečnosti podpisů RSA, např. pravděpodobnostní podpisové schéma pro RSA (RSA-PSS).

Podepisování zpráv

Předpokládejme, že Alice použije Bobův veřejný klíč, aby mu poslala zašifrovanou zprávu. Ve zprávě může tvrdit, že je Alice, ale Bob nemá žádnou možnost ověřit, že zpráva byla skutečně od Alice, protože kdokoli může použít Bobův veřejný klíč k zasílání zašifrovaných zpráv. K ověření původu zprávy lze tedy RSA použít i k podepsání zprávy.

Předpokládejme, že Alice chce odeslat podepsanou zprávu Bobovi. Vytvoří hash hodnotu zprávy, zvýší ji na mocninu d mod n (stejně jako při dešifrování zprávy) a připojí ji ke zprávě jako "podpis". Když Bob obdrží podepsanou zprávu, zvýší podpis na mocninu e mod n (stejně jako při šifrování zprávy) a porovná výslednou hodnotu hash se skutečnou hodnotou hash zprávy. Pokud se obě hodnoty shodují, ví, že autor zprávy vlastnil Alicin tajný klíč a že se zprávou od té doby nikdo nemanipuloval.

Všimněte si, že bezpečná schémata pro vyplňování, jako je RSA-PSS, jsou pro bezpečnost podepisování zpráv stejně důležitá jako pro šifrování zpráv a že stejný klíč by se nikdy neměl používat pro účely šifrování i podepisování.