Zakamarki Kryptografii

Algorytm generowania kluczy

1. Wybierz losowo dwie duże liczby pierwsze $p$ oraz $q$ (podobnego rozmiaru),
2. Policz $n = pq$
3. Wybierz $y \in \mathbb{Z}_n$, takie, że $y$ jest nieresztą kwadratową modulo $n$ i symbol Jacobiego $\left( \frac{y}{n} = 1 \right)$ (czyli $y$ jest pseudokwadratem modulo $n$),
4. Klucz publiczny stanowi para $(n, y)$, zaś odpowiadający mu klucz prywatny to para $(p, q)$.

Algorytm szyfrowania

Chcąc zaszyfrować wiadomość $m$ przy uzyciu klucza publicznego $(n, y)$ wykonaj kroki:

1. Przedstaw $m$ w postaci łańcycha binarnego $m = m_1m_2...m_t$ długości $t$

2. For $i$ from $1$ to $t$ do
       wybierz losowe $x \in \mathbb{Z}^*_n$
       If $m_i = 1$ then set $c_i \leftarrow yx^2$ mod $n$
       Otherwise set $c_i \leftarrow x^2$ mod $n$

3. Kryptogram wiadomości $m$ stanowi $c = (c_1, c_2, ..., c_t)$

Algorytm deszyfrowania

Chcąc odzyskać wiadomości z kryptogramu $c$ przy uzyciu klucza prywatnego $(p, q)$ wykonaj kroki:

1. For $i$ from $1$ to $t$ do
       policz symbol Legendre'a $c_i = \left( \frac{c_i}{p} \right)$
       If $c_i = 1$ then set $m_i \leftarrow 0$
       Otherwise set $m_i \leftarrow 1$

2. Zdeszyfrowana wiadomość to $m = m_1m_2...m_t$

Defincja. Niech $p$ będzie nieparzystą liczbą pierwszą, a $a$ liczbą całkowitą.
Symbol Legendre'a $\left( \frac{a}{p}\right)$ jest zdefiniowany jako: $$\left( \frac{a}{p} \right )= \left\{ \begin{array}{lll} & 0 & \textrm{jeżeli $p | a$}\\ & 1 & \textrm{jeżeli $a \in Q_p$}\\ & -1 & \textrm{jeżeli $a \in \bar{Q}_p$}\\ \end{array} \right. $$

Własności symbolu Legendre'a. Niech $a, b \in \mathbb{Z}$, zaś $p$ to nieparzysta liczba pierwsza. Wówczas:

• $\left( \frac{a}{p} \right) \equiv a^{\frac{(p-1)}{2}} (\mod p)$
• $\left( \frac{ab}{p} \right) = \left( \frac{a}{p} \right) \left( \frac{b}{p} \right)$
• $a \equiv b(\mod p) \Rightarrow \left( \frac{a}{p} \right) = \left( \frac{b}{p} \right)$
• $\left( \frac{2}{p} \right) = (-1)^{\frac{(p^2 - 1)}{8}}$
• Jeżeli $q$ jest nieparzystą liczbą pierwszą inną od $p$ to: $$\left( \frac{p}{q} \right) = \left( \frac{q}{p} \right) (-1)^{\frac{(p - 1)(q - 1)}{4}}$$

Definicja. Niech $n \geqslant 3$ będzie liczbą nieparzystą, a jej rozkład na czynniki pierwsze to $n = p^{e_1}_1 p^{e_2}_2 \ldots p^{e_k}_k$. Symbol Jacobiego $\left( \frac{a}{n} \right)$ jest zdefiniowany jako: $$\bigg( \frac{a}{n} \bigg) = \left( \frac{a}{p_1} \right)^{e_1} \left( \frac{a}{p_2} \right)^{e_2} \ldots \left( \frac{a}{p_k} \right)^{e_k} $$ Jeżeli $n$ jest liczbą pierwszą, to symbol Jacobiego jest symbolem Legendre'a.

Własności symbolu Jacobiego. Niech $a, b \in \mathbb{Z}$, zaś $m, n \geqslant 3$ to nieparzyste liczby całkowite. Wówczas:

• $\left( \frac{a}{n} \right) = 0, 1$, albo -1. Ponadto $\left( \frac{a}{n} \right) = 0 \iff gcd(a, n) \neq 1$
• $\left( \frac{ab}{n} \right) = \left( \frac{a}{n} \right) \left( \frac{b}{n} \right)$
• $\left( \frac{a}{mn} \right) = \left( \frac{a}{m} \right) \left( \frac{a}{n} \right)$
• $a \equiv b (\mod n) \Rightarrow \left( \frac{a}{n} \right) = \left( \frac{b}{n} \right)$
• $\left( \frac{1}{n} \right) = 1$
• $\left( \frac{-1}{n} \right) = (-1)^{\frac{(n - 1)}{2}}$
• $\left( \frac{2}{n} \right) = (-1)^{\frac{(n^2 - 1)}{8}}$
• $\left( \frac{m}{n} \right) = \left( \frac{n}{m} \right) (-1)^{\frac{(m - 1)(n - 1)}{4}}$

Algorytm obliczania symbolu Jacobiego $\left( \frac{a}{n} \right)$ (i Legendre'a) dla nieparzystej liczby całkowitej $n \geqslant 3$ oraz całkowitego $0 \leqslant a < n$

JACOBI($a, n$)

1. If $a = 0$ then return $0$

2. If $a = 1$ then return $1$

3. Write $a = 2^ea_1$, gdzie $a_1$ nieparzyste

4. If $e$ parzyste set $set \leftarrow 1$
   Otherwise set $s \leftarrow 1$ if $n \equiv 1 $ or $7 ($mod$8)$, or set
   $s \leftarrow -1$ if $n \equiv 3$ or $5 ($mod$8)$

5. If $n \equiv 3 ($mod$4)$ and $a_1 \equiv 3($mod$3)$ then set $s \leftarrow -s$

6. Set $n_1 \leftarrow n$mod$a_1$

7. If $a_1 = 1$ then return $s$
   Otherwise reurn $s \cdot$JACOBI($a_1, n_1$)

Cel: Zaufana Trzecia Strona $T$ ma sekret $S \geqslant 0$, który chce podzielić pomiędzy $n$ uczestników tak, aby dowolnych $t$ spośród niech mogło sekret odtworzyć.

Faza inicjalizacji:

• $T$ wybiera liczbę pierwszą $p \ge max(S, n)$ i definiuje $a_0 = S$,
• $T$ wybiera losowo i niezależnie $t - 1$ współczynników $a_1, ..., a_{t-1} \in \mathbb{Z}_p$,
• $T$ definiuje wielomian nad $\mathbb{Z}_p$: $$f(x) = a_0 + \sum^{t-1}_{j = 1} a_jx^j,$$
• Dla $1 \leqslant i \leqslant n$ Zaufana Trzecia Strona $T$ wybiera losowo $x_i \in \mathbb{Z}_p$, oblicza: $S_i = f(x_i) \mod p$ i bezpiecznie przekazuje parę $(x_i, S_i)$ uzytkownikowi $P_i$.

Faza łączenia udziałów w sekret: Dowolna grupa $t$ lub więcej użytkowników łączy swoje udziały - $t$ róznych punktów $(x_i, S_i)$ wielomianu $f$ i dzięki interpolacji Lagrange'a odzyskuje sekret $S = a_0 = f(0)$.

Mając dane $t$ różnych punktów $(x_i, y_i)$ nienanego wielomianu $f$ stopnia mniejszego od $t$ możemy policzyć jego współczynniki korzystając ze wzoru: $$f(x) = \sum^t_{i = 1}\left( y_i \prod_{1 \leqslant j \leqslant t,\, j\neq i} \frac{x - x_j}{x_i - x_j} \right) \mod p$$ Wskazówka: w schemacie Shamira, aby odzyskać sekret S, użytkownicy nie muszą znać całego wielomianu $f$. Wsstawiając do wzoru na iterpolację Lagrange'a $x = 0$, dostajemy wersję uproszczoną, ale wystarczającą aby policzyć sekret $S = f(0)$: $$f(x) = \sum^t_{i = 1} \left(y_i \prod_{1 \leqslant j \leqslant t,\, j\neq i} \frac{x_j}{x_j - x_i} \right) \mod p$$