Schemat identyfikacji Schnorra

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Schemat identyfikacji Schnorra
Rodzaj algorytmu podpis cyfrowy
Data stworzenia 1990
Autorzy Claus P. Schnorr

Schemat identyfikacji Schnorra – w kryptografii, 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[edytuj | edytuj kod]

Twórcą schematu jest niemiecki matematyk i kryptolog Claus P. Schnorr. Algorytm został opatentowany w lutym 1990 roku w amerykańskim[1] i europejskim[2] 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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

  1. 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.
  2. 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.
  3. Nadawca otrzymuje certyfikat I, którym jest trójka (ID, v, s).

Identyfikacja tożsamości[edytuj | edytuj kod]

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

Przykłady[edytuj | edytuj kod]

Przykład 1[edytuj | edytuj kod]

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).

  1. Nadawca losuje liczbę k = 274 i oblicza γ = αk mod p = 37123, którą wysyła do adresata razem z certyfikatem.
  2. Adresat losuje liczbę r = 129 i odsyła ją do nadawcy.
  3. Nadawca oblicza y = (k+ar) mod q = 255, który odsyła do adresata.
  4. Adresat sprawdza, że αyvr (mod p) = 37123 = γ co potwierdza tożsamość nadawcy.

Przykład 2[edytuj | edytuj kod]

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ż[edytuj | edytuj kod]

Przypisy

  1. Patent US4995082 (ang.). www.google.com. [dostęp 2012-10-13].
  2. EP0384475 (A1) (ang.). worldwide.espacenet.com. [dostęp 2012-10-13].

Bibliografia[edytuj | edytuj kod]