1 Operacje mnożenia i potęgowania w grupie multiplikatywnej $Z^*_p$

Mnożenie w dużej grupie skończonej $A * B \; mod \; N$ jest skomplikowaną i stosunkowo czasochłonną operacją. Jest ona używana również w wykorzystywanym przeze mnie algorytmie potęgowania, generatorze liczb losowych i wielu innych obliczeniach. Ponadto jest najczęściej wykorzystywaną funkcją składową tych algorytmów. Decydując się na korzystanie z biblioteki nat nie uzyskałem możliwości zaimplementowania bardziej wyrafinowanych algorytmów, pozwalających używać operacji mnożenia i modulo naprzemiennie, co pozwala przyspieszyć obliczenia zmniejszając ich złożoność. To ograniczenie w mojej implementacji wynika z faktu, że biblioteka nat jest zrealizowana w asemblerze i modyfikacja jej wymaga napisania procedur w asemblerze dla kilku różnych platform sprzętowych z uwzględnieniem odmiennych wersji języka C. Z tego powodu zdecydowałem się użyć funkcji mnożenia i modulo z biblioteki nat.

Drugą operacją mającą znaczący wpływ na czas generacji kluczy i tworzenia podpisów jest operacja potęgowania w grupie $\mathbb{Z}^*_p$. Jest ona wykorzystywana również w algorytmie generacji liczb pierwszych w teście Millera-Rabina [3]. Należy zauważyć, iż w czasie generacji poświadczeń elektronicznych wykonuje się operacje $g^x \; mod \;p \;$, gdzie $g \;$ i $p \;$ są stałymi. Zatem, by policzyć $g^x \;$ wystarczy mieć $a \;$ i $b \;$, takie że $a + b = x$ oraz policzone uprzednio $g^a \;\; mod \;p \;$ i $g^b \;\; mod \;p \;$. Wtedy łatwo możemy obliczyć $g^x = g^a * g^b \;\; mod \; p$. Niestety zapamiętywanie wszystkich obliczanych potęg jest bardzo kosztowne i niezgodne z prawem (por dodatek A). Pewnym rozwiązaniem jest zapamiętanie wszystkich potęg postaci $g^{2^i} \;$ dla $0 \le i \le log_2q \;$. Można wtedy użyć następującego algorytmu:

    i:=1
    for d := 0 to length( g )
        if x[d] = 1 then i := i * a[d] mod p;
    return i;

W tablicy $a[\;]\;$ przechowujemy zapamiętane $g^{2^i}$.

Można oczywiście przechowywać obliczone wartości postaci $g^{ c_j \:*\: 2^{i*s}}\;$, gdzie $c_j \;$ to niewielkie liczby z przedziału $0 \dots 2^s-1$. Wtedy:

$$x = \sum_{i = 0}^{\frac{l}{s}}\;c_i * 2^i \; , \;\;\;\; l = log_2 x$$

Niech $r = 2^s$, a $\; l = \lceil \frac{log_2g}{s} \rceil$. Wtedy algorytm będzie wyglądał następująco:

    y := x;
    i:=1;
    for d := 0 to l
        i := i * a[d][y mod r] mod p;
        y := y div r;
    return i;

Jednak w tym przypadku skorzystano z tradycyjnego algorytmu ,,podnoś do kwadratu i mnóż''. Korzystamy wtedy z reprezentacji liczby $r$:

$$x = \sum_{i = 0}^l \;c_i * 2^i \;,\;\;\;\; l = log_2 x \;,\;\;\; c_i \; \epsilon \{0,1\}$$

Algorytm ten wykonuje $2 * log_2 r$ mnożeń. Można zapisać go następująco:

    i := x[l];
    for d := (l - 1) downto 0
        i := i * i mod p;
        if x[d] = 1 then i := i * a mod p;
    return i;

W czasie implementacji brano pod uwagę wykorzystanie funkcji realizującej taką operację, wchodzącej w skład biblioteki bignat. Niestety kod tej funkcji zawiera pętlę for, której implementacja w języku funkcyjnym jest bardzo niewydajna. Zapis funkcji umożliwiający wykorzystanie przez kompilator optymalizacji rekursji ogonowej przyspieszył czas wykonywania potęgowania ponad 27 krotnie. W tabeli 5.1 przedstawiono czasy poszczególnych operacji dla $\vert a\vert$, $\vert b\vert$ i $\vert p\vert$ równych 1024. Użyto takich długości, by test był porównywalny z najczęściej spotykanymi wynikami dotyczącymi algorytmu RSA.

Tablica 5.1: Czasy wykonywania mnożenia i potęgowania w $Z^*_p$ dla $\vert a\vert = \vert p\vert = \vert b\vert = 1024$

operacja	czas
$a * b \; mod \; p$	108 ${\mu}s$
$a^b \; mod \; p$ -- wersja korzystająca z optymalizacji rekursji ogonowej	177 ms
$a^b \; mod \; p$ -- wersja korzystająca z implementacji z biblioteki bignat	4770 ms

Natomiast w interesującym nas przypadku, tzn. gdy $\vert a\vert = \vert p\vert = 768 \;$ a $\vert b\vert = 128$, uzyskano wyniki przedstawione w tabeli 5.2.

Tablica 5.2: Czasy wykonywania mnożenia i potęgowania w $Z^*_p$ dla $\vert a\vert = \vert p\vert = 768 \;$ i $\vert b\vert = 128$

operacja	czas
$a * b \; mod \; p$	18 ${\mu}s$
$a^b \; mod \; p$ -- wersja korzystająca z optymalizacji rekursji ogonowej	14 ms
$a^b \; mod \; p$ -- wersja korzystająca z implementacji z biblioteki bignat	340 ms