Schemat identyfikacji Schnorra

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania
Schemat identyfikacji Schnorra
Rodzaj algorytmu podpis cyfrowy
Data stworzenia 1990
Autorzy Claus P. Schnorr

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

  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]