2 Tworzenie kluczy

Są dwa aspekty tworzenia kluczy używanych w protokołach podpisów Schnorra i protokole częściowo ślepych podpisów. Na początku należy wybrać parametry $p$ i $q$, które są dużymi liczbami pierwszymi. Liczby te należy dobrać tak, by łatwo można było obliczyć generator $g$ podgrupy $\mathbb{Z}^*_p$ rozmiaru $q$. Aby móc go wyznaczyć stosunkowo szybko, należy pamiętać, że $\alpha \epsilon \mathbb{Z}^*_n$ jest generatorem grupy $\mathbb{Z}^*_n$ wtedy i tylko wtedy gdy:

$\alpha^{\frac{\phi(n)}{d}} \not\equiv 1 \;mod \; n$ dla $d$ będących dzielnikami $\phi(n)$

dla liczby pierwszej $p$ $\phi(n)$ równa się oczywiście $p - 1$. Zatem użyto następującego algorytmu:

  start:
    znajdź liczbę pierwszą B
    for i := 1 to 1000 do
      znajdź liczbę pierwszą A
      policz P := A * B * 2 + 1;
      jeżeli P jest liczba pierwszą, to return (A, B, P)
    end for;
    idź do "start"

Ten algorytm daje nie tylko liczbę pierwszą $p$, ale też rozkład $\phi(p)$. Warto zaznaczyć, że $p$ jest bezpieczną liczbą pierwszą, czyli taką, dla której $\phi(p)$ ma duży dzielnik pierwszy. Dobierając odpowiednie parametry można spowodować, by $A$ było takiej długości, aby dało się go używać w protokole jako $q$. Ważne jest, by jako pierwsze losować $B$, którego długość powinna wynosić $\vert p\vert - \vert q\vert$ (w implementowanym protokole $\vert p\vert = 768$, a $\vert q\vert = 128$). Wynika to z faktu, iż im dłuższa jest liczba pierwsza, tym dłużej trwa jej znalezienie. Ta część obliczeń jest bardzo czasochłonna, ale jest wykonywana tylko raz i to przez serwery instytucji certyfikującej, gdyż wszyscy uczestnicy protokołu będą posługiwali się tymi samymi parametrami.
Na komputerze z procesorem Celeron 300A taka operacja dla $\vert q\vert = 128$ i $\vert p\vert = 768$ zajmowała od 55 sekund do 8 minut.

By znaleźć generator grupy $\mathbb{Z}^*_p$ użyto następującej procedury (A, B, P to wartości policzone poprzednio):

  start:
    znajdź liczbę pierwszą H mniejszą od P
    jezeli  ( H^A modulo P == 1) idz do "start"
    jezeli  ( H^B modulo P == 1) idz do "start"
    jezeli  ( H^2 modulo P == 1) idz do "start"
    return H

Pozwala ona na obliczenie generatora grupy $\mathbb{Z}^*_p$, jednak w protokole używane jest $g$, które jest generatorem podgrupy $\mathbb{Z}^*_p$ rozmiaru $q = A$. Poszukiwane $g$ oblicza się używając wzoru:

$g := H^{2 * B}$

Kolejnym etapem jest utworzenie kluczy prywatnych i publicznych dla użytkowników systemu. Obliczenia te sprowadzają się tylko do wylosowania elementu $x \epsilon \mathbb{Z}^*_q$, który będzie kluczem prywatnym i policzenia klucza publicznego $X \epsilon \mathbb{Z}^*_p$ jako $X = g^x \; mod \; p$.