3 RSA

Założenia: chcemy ukryć przed serwerem tajny klucz $d$. Nie będziemy zajmować się ukrywaniem wiadomości $m$. Bedziemy używać standardowych oznaczeń:

• $(e,n)$, $(d,n)$ -- klucz jawny i tajny
• $m$ , $c$ -- wiadomośći kryptogram

PROTOKÓŁ:

1. Klient losuje wektor liczb całkowitych $D = [d_0, d_1,\:\ldots,d_M]$ i wektor binarny $F = [f_0, f_1, \: \ldots, f_M]$, tak że
   
   $$\sum_{i = 0}^M f_id_i \equiv d \;\;\; (mod \: \phi(n))\;\; oraz \;\; 1 \leq d_i \leq n$$
   
   
   
   
   $$\sum_{i=1}^M f_i \leq L$$
   
   
   gdzie $M$ i $L$ są pewnymi liczbami naturalnymi.

2. klient wysyła do serwera ${n,\:D,\:m}$. serwer oblicza i odsyła do klienta $Z = [z_0, z_1, \ldots, z_M]$, takie że
   
   $$z_i \equiv m^{d_i} \;\;\; mod \: n$$
   
   

3. klient oblicza $c$ jako $c = c_M$ w następujący sposób

   $y_0 = 1,\;\;\;\;\;$
   $y_i \equiv y_{i-1} z_i \;\;\;mod \: n, \;\;\;jesli\;\;\; f_i = 1$
   $y_i = y_{i-1} jesli f_i = 0$
   $dla \;\;\;\;i = 1, \ldots, M$

Istnieje tu możliwość określania poziomu bezpieczeństwa przez zmienianie parametru $M$. Łatwo zauważyć, iż nie znając $L$ aby znaleźć $d$ należało by przeszukać wszystkie $2^M$ możliwości. Jako że bezpieczeństwo protokołu RSA jest w szczególności związane wykładniczo z dlugościa kluczy $d$ i $e$ oraz, że złożoność obliczeniowa opracji postaci $a^b \;\;\; mod \;k$ jest rzędu $O(\:max (\log b, \log k))$ przedstawione powyżej rozwiązanie mozna bardziej traktować jako inspirację niż pełna i poważną propozycję.