Schemat identyfikacji Schnorra – podpis cyfrowy wygenerowany algorytmem Schnorra. Jego bezpieczeństwo opiera się na trudności w rozwiązaniu logarytmu dyskretnego. Algorytm jest wydajny i tworzy krótkie podpisy.

Historia Twórcą schematu jest niemiecki matematyk i kryptolog Claus P. Schnorr. Algorytm został opatentowany w lutym 1990 roku w amerykańskim i europejskim urzędzie patentowym. Patent opisuje sprzętową metodę identyfikacji za pomocą kart elektronicznych wydawanych przez centrum certyfikacji. Patent amerykański wygasł w lutym 2008 roku.

Algorytm Schemat identyfikacji Schnorra przewiduje udział centrum certyfikacji w celu wiarygodnego poświadczenia tożsamości i wystawienia certyfikatu nadawcy, który będzie mógł być weryfikowany przez adresata.

Parametry systemu Parametry schematu identyfikacji, które są ustalane przez centrum weryfikacji to: duża liczba pierwsza p (≈ 21024) duża liczba pierwsza q (≥ 2160), która jest dzielnikiem liczby p – 1 liczba α (≠ 1) taka, że αq ≡ 1 (mod p) parametr bezpieczeństwa t (≥ 40) taki, że 2t < q bezpieczny schemat podpisu, gdzie algorytm podpisu sig jest tajny a algorytm weryfikacji ver jest publiczny (szyfrowanie niesymetryczne) kryptograficzna funkcja skrótu (do skracania informacji przed podpisaniem)

Parametry p, q, α i algorytm weryfikacji ver są podane do wiadomości publicznej. Algorytm sig jest znany jedynie centrum certyfikacji.

Wystawienie certyfikatu Nadawca wybiera tajną losową wartość a (tajny klucz) taką, że 0 ≤ a ≤ q – 1, a następnie oblicza wartość v = α–a mod p (publiczny klucz), który przekazuje do centrum certyfikacji. Centrum certyfikacji, po poświadczeniu tożsamości nadawcy, generuje ciąg ID zawierający dane identyfikacyjne nadawcy, a następnie podpisuje wiadomość (ID,v) uzyskując wartość s. Nadawca otrzymuje certyfikat I, którym jest trójka (ID, v, s).

Identyfikacja tożsamości nadawca losuje liczbę k taką, że 0 ≤ k ≤ q – 1 i wylicza wartość γ = αk mod p nadawca przekazuje adresatowi liczbę γ i swój certyfikat I adresat weryfikuje certyfikat I tj. sprawdza podpis algorytmem ver dla (ID,v,s) adresat losuje liczbę r, taką że 1 ≤ r ≤ 2t, którą przekazuje nadawcy nadawca oblicza wartość y = (k+ar) mod q, którą przekazuje adresatowi adresat sprawdza czy γ ≡ αyvr (mod p)

Przykłady Przykład 1 Niech będą ustalone następujące parametry systemowe: p = 48731, q = 443, α = 11444 oraz t = 8.

Nadawca wybiera tajny klucz a = 357 i wylicza wartość v = α–a mod p = 7355, która jest częścią certyfikatu (proces weryfikacji certyfikatu I jest pominięty dla przejrzystości schematu). Nadawca losuje liczbę k = 274 i oblicza γ = αk mod p = 37123, którą wysyła do adresata razem z certyfikatem. Adresat losuje liczbę r = 129 i odsyła ją do nadawcy. Nadawca oblicza y = (k+ar) mod q = 255, który odsyła do adresata. Adresat sprawdza, że αyvr (mod p) = 37123 = γ co potwierdza tożsamość nadawcy.

Przykład 2 Ustalając parametr p = 11 niejako automatycznie uzyskuje się „jedyny wielki” parametr q = 5. Za parametr bezpieczeństwa t przyjmuje się 1.

Odpowiedni parametr α można znaleźć przeszukując wszystkie możliwe rozwiązania takie, że αq ≡ 1 (mod p):

α αq αq mod p 2 32 10 3 243 1 4 1024 1 5 3125 1 6 7776 10 7 16807 10 8 32768 10 9 59049 1 10 100000 10

Z powyższej tabelki widać, że dopuszczalne wartości α to 3, 4, 5 i 9.

Dla powyższych wartości parametrów systemowych zakres wartości a i k to 0, 1, 2, 3 i 4, a za r można podstawić 1 lub 2. Poniższa tabelka zawiera zestawienie kluczowych wartości dla kilku przypadków użycia:

α a (α–a) αp–1–a v k αk γ nadawcy r k+ar y αyvr γ adresata 3 0 59049 1 0 1 1 1 0 0 1 1 4 1 262144 3 2 16 5 2 4 4 2304 5 5 3 78125 3 2 25 3 2 8 3 1125 3 9 4 531441 9 4 6561 5 1 8 3 6561 5

Zobacz też Digital Signature Algorithm

Przypisy

Bibliografia

Kategoria:Algorytmy kryptograficzne Kategoria:Kryptografia klucza publicznego