5 Projekt -- użyte algorytmy

W czasie implementacji systemu, którego architekturę przedstawiam w rozdziale 6, wyszły na jaw różne problemy związane z tworzeniem kluczy i ich dystrybucją, używanymi algorytmami i ich implementacją pozwalają uzyskać zadowalającą wydajność. W niniejszym rozdziale przedstawiam algorytmy zastosowane przy realizacji operacji na dużych liczbach, takie jak mnożenie i potęgowanie w grupie $\mathbb{Z}^*_p$, sprawdzanie czy liczba jest pierwsza, generowanie kluczy dla protokołów podpisów cyfrowych i dla protokołu Wenbo Mao. Czas obliczeń wykonywanych w czasie rzeczywistym jest jednym z podstawowych kryteriów oceny zarówno protokołu, jak i jego realizacji.

W mojej realizacji biblioteki dużych liczb lib_eXnat wykorzystałem bibliotekę nat dostarczoną z systemem Ocaml. Biblioteka nat realizuje część elementarnych operacji na dużych liczbach.