Zakamarki Kryptografii

Schemat Goldwasser-Micali szyfrowania probabilistycznego

Algorytm generowania kluczy

Wybierz losowo dwie duże liczby pierwsze $p$ oraz $q$ (podobnego rozmiaru),
Policz $n = pq$
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$),
Klucz publiczny stanowi para $(n, y)$, zaś odpowiadający mu klucz prywatny to para $(p, q)$.

Algorytm deszyfrowania

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

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

For $i$ from $1$ to $t$ do
  wybierz losowe $x ∈ Z^{∗}_{n}$
  If $m_{i} = 1$ then set $c_{i} ← yx^{2}$ $mod$ $n$,
  Otherwise set $c_{i} ← x^{2}$ $mod$ $n$

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:

For $i$ from $1$ to $t$ do
  policz symbol Legendre’a $e_{i}$ = $(\frac{c_{i}}{p})$,
  If $e_{i}$ = $1$ then set $m_{i} ← 0$
  Otherwise set $m_{i} ← 1$

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

Reszta/Niereszta z dzielenia

Definicja.
Niech $a \in$ $\mathbb{Z}_n$. Mówimy, że $a$ jest resztą kwadratową modulo $n$ (kwadratem modulo $n$), jeżeli istnieje $x \in$ $\mathbb{Z}^*_n$ takie, że $x^2 \equiv a \ (mod \ p)$. Jeżeli takie $x$ nie istnieje, to wówczas $a$ nazywamy nieresztą kwadratową modulo $n$. Zbiór wszystkich reszt kwadratowych modulo $n$ oznaczamy $Q_n$, zaś zbiór wszystkich niereszt kwadratowych modulo $n$ oznaczamy $\bar{Q}_n$.

Symbol Legendre’a i Jacobiego

Faza inicjalizacji:

Definicja.
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}}$$

Faza łączenia udziałów w sekret:

Definicja.
Niech $n \geq 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: $$\left( \frac{a}{n} \right) = \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 \geq 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}}$

Z własności symbolu Jacobiego wynika, że jeżeli $n$ nieparzyste oraz $a$ nieparzyste i w postaci $a = 2^e a_1$, gdzie $a_1$ też nieparzyste to: $$\left( \frac{a}{n} \right) = \left( \frac{2^e}{n} \right) \left( \frac{a_1}{n} \right) = \left(\frac{2}{n} \right)^e \left( \frac{n \ mod \ a_1}{a_1} \right) (-1)^{\frac{(a_1 - 1)(n - 1)}{4}}$$

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

JACOBI(a, n)

If $a = 0$ then return $0$
If $a = 1$ then return $1$
Write $a = 2^{e}a_{1}$, gdzie $a_{1}$ nieparzyste
If $e$ parzyste set $s ← 1$, Otherwise set $s ← 1$ if $n ≡ 1$ $or$ $7 \ (mod \ 8)$, or set $s ← −1$ if $n ≡ 3$ $or$ $5 \ (mod \ 8)$
If $n ≡ 3$ $(mod \ 4)$ $and$ $a1 ≡ 3$ $(mod \ 4)$ then set $s ← −s$
Set $n_{1} ← n$ $mod$ $a_{1}$
If $a_{1} = 1$ then return $s$ Otherwise, return $s * JACOBI (n_{1}, a_{1})$

Schemat progowy $(t, n)$ dzielenia sekretu Shamira

Cel: Zaufana Trzecia Strona $T$ ma sekret $S \geq 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 \leq i \leq 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)$.

Interpolacja Lagrange'a

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 \leq j \leq 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 \leq j \leq t, j\neq i} \frac{x_j}{x_j - x_i} \right) mod \ p$$