Schemat identyfikacji Schnorra

Schemat identyfikacji Schnorra

Rodzaj algorytmu	podpis cyfrowy
Data stworzenia	1990
Autorzy	Claus P. Schnorr

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^[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

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 (≈ 2¹⁰²⁴)
• duża liczba pierwsza q (≥ 2¹⁶⁰), która jest dzielnikiem liczby p – 1
• liczba α (≠ 1) taka, że α^q ≡ 1 (mod p)
• parametr bezpieczeństwa t (≥ 40) taki, że 2^t < 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

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

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 ≤ 2^t, którą przekazuje nadawcy
5. nadawca oblicza wartość y = (k+ar) mod q, którą przekazuje adresatowi
6. adresat sprawdza czy γ ≡ α^yv^r (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).

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 α^yv^r (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	α^yv^r	γ 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

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

Bibliografia

• Douglas R. Stinson: Kryptografia. W teorii i praktyce. dr Wiktor Bartol (tłum.). Warszawa: Wydawnictwa Naukowo-Techniczne, 2005, seria: TAO Tajemnica-Atak-Obrona. ISBN 83-204-2982-X. Brak numerów stron w książce
• Bruce Schneier: Kryptografia dla praktyków: protokoły, algorytmy i programy źródłowe w języku C. Warszawa: Wydawnictwa Naukowo-Techniczne, 2002, seria: TAO Tajemnica-Atak-Obrona. ISBN 83-204-2678-2. Brak numerów stron w książce