Schemat identyfikacji Schnorra
| Rodzaj algorytmu | |
|---|---|
| Data stworzenia | |
| Autorzy |
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[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]
- 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[edytuj | edytuj kod]
- 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[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).
- 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[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]
- ↑ Patent US4995082. www.google.com. [dostęp 2012-10-13]. (ang.).
- ↑ EP0384475 (A1). worldwide.espacenet.com. [dostęp 2012-10-13]. (ang.).
Bibliografia[edytuj | edytuj kod]
- 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.
- 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.