Matematický aparát pro RSA

Eulerova funkce \(\phi\)

Nechť \(c \in \mathbb{N}\), Eulerova funkce \(\phi\) udává počet čísel \(k \in \{1, \dots, c-1\}\), která jsou nesoudělná s \(c\) ( \(\gcd(c,k) = 1\) ).

\[\phi(c) = n \Leftrightarrow \\ \exists o \in \widehat{c-1} \forall i \in o : |o|=n \wedge \gcd(c,i)=1 \\ \wedge \\ \forall o \in \widehat{c-1} \exists i \in o : |o|>n \rightarrow \gcd(c,i) \neq 1\]

Pro výpočet Eulerovy funkce lze využít rozkladu na prvočinitele následujícím způsobem:

\[\phi(c) = \prod_{\forall p \in P} (p-1)\]

kde \(P\) je množina všech unikátních prvočíselných dělitelů \(c\) (pro \(c\) jako součin unikátních prvočísel).

Definice (z FIT ČVUT)

Eulerova funkce \(\phi(n)\)

Eulerova funkce \(\phi(n) : \mathbb{N^} \rightarrow \mathbb{N^}\) udává počet kladných celých čísel menších nebo rovných \(n\), která jsou nesoudělná s \(n\).

Věta o \(\phi(m \cdot n)\)

Nechť \(m, n \in \mathbb{N}\) a \(\gcd(m, n) = 1\). Potom \(\phi(m \cdot n) = \phi(m) \cdot \phi(n)\).

Pozorování

Nechť \(n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \dots p_k^{\alpha_k}\) je kanonický rozklad složeného čísla \(n \in \mathbb{N^+}\). Potom:

\[\phi(n) = n \left( 1 - \frac{1}{p_1} \right) \left( 1 - \frac{1}{p_2} \right) \dots \left( 1 - \frac{1}{p_k} \right)\]

Důsledek

Důsledek vede na vztah:

\[\begin{aligned} \phi(n) &= n \cdot \prod_{\forall p_i \in P} \left( 1 - \frac{1}{p_i} \right) \\ \phi(n) &= n \cdot \prod \left( \frac{p_i-1}{p_i} \right) = n \cdot \prod \left( \frac{1}{p_i} \right) \cdot \prod (p_i-1) \\ \phi(n) &= n \cdot \frac{1}{n} \cdot \prod (p_i-1) \\ \phi(n) &= \prod_{\forall p_i \in P}(p_i-1) \end{aligned}\]

Složitost problému faktorizace

Faktorizace čísla na prvočinitele patří do třídy NP (přesněji se předpokládá, že leží v průniku NP a co-NP a není v P).

Neexistuje a nepředpokládá se existence klasického algoritmu, který dokáže faktorizaci provést v polynomiálním čase.

[zdroj]

Složitost problému výpočtu Eulerovy funkce \(\phi(n)\)

Výpočet Eulerovy funkce má stejnou složitost jako faktorizace čísla \(n\). Pokud známe faktorizaci, je výpočet triviální. Bez ní je výpočet v obecném případě považován za výpočetně ekvivalentní faktorizaci.

RSA

  • Nechť \(p\) a \(q\) jsou velká prvočísla.

  • Nechť \(n = p \cdot q\)

  • Zvolte \(e\), které splňuje: \(1 < e < \phi(n)\) a \(\gcd(e, \phi(n)) = 1\).

  • Nechť \(d \equiv e^{-1} \pmod{\phi(n)}\) (modulární multiplikativní inverze).

Privátní klíč je pár \(SK = (n, d)\)

Veřejný klíč je pár \(PK = (n, e)\)

Proces šifrování

\[c = m^e \pmod{n}\]

Proces dešifrování

\[m = c^d \pmod{n} = (m^e)^d \pmod{n} = m^{e \cdot d} \pmod{n}\]

Díky Eulerově větě platí \(m^{e \cdot d} \equiv m \pmod{n}\).

Bonus

Použitá prvočísla \(p\) a \(q\) v příkladech bývají často malá (např. v řádu bitů). To je bezpečnostní problém; taková čísla nezaručují výpočetní bezpečnost. Ze znalosti veřejného klíče \((e, n)\) lze pomocí faktorizace nalézt čísla \(p\) a \(q\), vypočítat \(\phi(n)\) a násled