Matematika

Šifrování RSA (prvočíselný rozklad)

Existují dva typy šifer - symetrické a asymetrické. Symetrické šifry mají pouze jeden klíč, pomocí kterého se přenášená zpráva šifruje a inverzním postupem dešifruje.

Asymetrické šifry mají klíče dva – soukromý a veřejný. Zatímco veřejný klíč jeho držitel oznámí celému světu, ten soukromý si pečlivě uschová. Zprávu zašifrovanou veřejným klíčem lze rozšifrovat pouze odpovídajícím klíčem soukromým.

Algoritmus RSA publikovali v roce 1978 Ronald Rivest, Adi Shamir a Leonard Adleman - proto se mu říká RSA. Jedná se o asymetrickou šifru, která je založena na tom, že zatímco vynásobit dvě velká čísla je snadné, tak rozložit velké číslo na součin prvočísel (neboli faktorizace) je časově velmi obtížná úloha.

počet cifer prvočísla

a
b

Výsledek

součin
čas

a
b
čas

Princip algoritmu

Prvním krokem je převést zprávu na číslo, případně více čísel, která se budou kódovat samostatně, pokud je zpráva příliš dlouhá. Tento převod není součástí algoritmu RSA.

Veřejný klíč tvoří dvojice čísel n a s, pro která platí:

• n je součinem dvou velkých prvočísel p a q
• s je rovněž prvočíslo

Postup zakódování:

• Číselnou podobu zprávy označíme A
• Zakódovanou zprávu zprávu označíme B
• Zakódování pomocí veřejného klíče se provede
  
  B ≡ A^S (mod n)

Zakódovanou zprávu B odešleme.

Platí

Pokud A^S ≡ B (mod n),

pak B^D ≡ A (mod n),

kde D je inverze k S (mod φ(n)), neboli

S.D ≡ 1 (mod φ(n))

a φ(n) je hodnota Eulerovy funkce v bodě n

Důkaz

Důkaz je založen na malé Fermatově větě a jejím Eulerově zobecnění:

Pokud jsou čísla a a p nesoudělná, pak

a^p-1 ≡ 1 (mod p)

Euler větu zobecnil pomocí Eulerovy funkce φ(n) na

a^φ(n) ≡ 1 (mod n) pro libovolná nesoudělná čísla a a n

Eulerova funkce φ(n) je definovaná jako počet všech přirozených čísel k takových, že 1 ≤ k ≤ n pro nesoudělná čísla k a n.

Pro prvočísla platí φ(p) = p - 1

Můžeme tedy psát:

a^φ(n) ≡ 1 (mod n) pro nesoudělná a a n

Pokud umocníme rovnici na k, nic se nezmění:

a^k*φ(n) ≡ 1 (mod n)

Stejně tak ji můžeme vynásobit a

a^k*φ(n)+1 ≡ a¹ (mod n)

Tedy umocníme-li číselnou zprávu na k * φ(n) + 1 (mod n), dostaneme opět tu samou zprávu.

Dále vidíme, že:

Výraz k * φ(n) + 1 ≡ 1 platí vždy pokud ho upravíme mod φ(n) ... k * φ(n) mod φ(n) je vždy 0

a^E ≡ a (mod n), pokud E ≡ 1 (mod φ(n))

Pokud E rozložíme na E = S * D, platí opět, že

a^{S * D} ≡ a (mod n), pokud S * D ≡ 1 (mod φ(n))

A^{S * D} = A^SD = B^D = A (vše mod n)

Příklad 1

- vyzkoušejte si, jak funguje zašifrování a dešifrování maximálně třípísmenného slova

Zpráva
Zpráva v číselné podobě (A)
p
q
S (číslo nesoudělné s φ(n))
n = p * q
Zašifrovaná zpráva B = As (mod n)

φ(n) = (p - 1) * (q - 1)
D
Zpráva v číselné podobě
Původní zpráva

Příklad 2

- zkuste dešifrovat následující zprávu

Zašifrovaná zpráva B
S
n = p * q
p
q
φ(n) = (p - 1) * (q - 1)
D
Zpráva v číselné podobě
Původní zpráva