Podpis cyfrowy

Podział:

• z dodatkiem - do weryfikacji podpisu wymagana jest cała wiadomość, posiada element dodatkowy (zwykle stosuje się tu funkcje skrótu);

• z odtwarzaniem - nie wymagają całej wiadomości;

Podpis cyfrowy z odtwarzaniem

• ogólny schemat podpisywania

• ogólny schemat weryfikacji

Podpis cyfrowy z odtwarzaniem

Korzystamy z dodatkowej funkcji u zwaną funkcją redundancji (funkcja 1→ 1). W tym przypadku funkcja skrótu jest niepotrzebna.

• 
  ogólny schemat podpisywania

• ogólny schemat weryfikacji

1. Sprawdzamy, czy m'= v(s).

2. Jeśli m'∉u(M) to podpis odrzucamy;

3. Jeśli m'∈ U(M) to odtwórz m z m' obliczając m = u ^-1(m).

Podpis cyfrowy z odtwarzaniem i z dodatkiem

• ogólny schemat podpisywania

Ataki na podpis cyfrowy

1. Podrabianie podpisu

• podrabianie egzystencjalne - intruz potrafi podrobić conajmniej jeden podpis;

• podrabianie selektywne - intruz potrafi podrobić podpis dla wybranej wiadomości (lub klasy wiadomości);

• całkowite podrobienie - intruz potrafi zrobić z podpisem co zechce. Jest to przypadek najgorszy.

2. Atak poprzez klucz - przypadek trudny

3. Atak poprzez wiadomość

• atak poprzez tekst znany - intruz zna postać wiadomości jawnej, jak i podpis wiadomości;

• atak poprzez tekst wybrany - intruz może uzyskać podpis dla wybranej przez siebie wiadomości;

• atak adaptacyjny poprzez tekst wybrany - intruz może wykonać eksperyment z wiadomościami wybranymi przez siebie. Nie może natomiast eksperymentować z wiadomością oryginalną, którą w rzeczywistości chce złamać;

Schemat RSA

Jest to schemat podpisu z odtwarzaniem.

Algorytm generowania kluczy dla szyfru RSA (zobacz też wcześniej)

1. Wygeneruj dwie duże losowe i różne liczby pierwsze p i q;

2. Wyznacz n = pq oraz φ(n) = (p-1)(q-1);

3. Wybierz losowo liczbę e z przedziału 1< e <φ(n), taką, że NWD(e, φ(n)) =1;

4. Wyznacz liczbę d, taką, że ed ≡ 1(modφ(n));

5. Przyjmij klucz szyfrujący k_e=(e,n) i deszyfrujący k_d=(d,n);

Problem podpisywania

Wiadomość jest reprezentowana jako liczba.

Przyjmijmy klucze szyfrujące k_e=(e,n) i deszyfrujące k_d=(d,n);

Użytkownik A chce podpisać wiadomość. Wykonuje więc następujące kroki:

1. Oblicz m'= u(m) ∈ {0, 1, …, n-1}

2. s = (m')^d mod n - podpis użytkownika pod wiadomością m.

Problem weryfikacji

1. Zadbaj o to, aby klucz publiczny (e, n) był prawdziwy;

2. s^e mod n = m', jeśli m'∉S to odrzuć m' jako podpis;

3. Odtwórz wiadomość m = u^-1 (m');

Podpis możemy chcieć zaszyfrować za pomocą przekształcenia publicznego. Problemem jest podpis wiadomości i szyfrowanie. Istnieją dwie możliwości:

1. najpierw podpisujemy, a później szyfrujemy - zalecane;

2. najpierw szyfrujemy, a później podpisujemy - w tym przypadku ktoś może dostać się do szyfrogramu, a potem już własny zmodyfikowany podpis zaszyfrować - nie zalecane;

Pierwsza z powyższych możliwości posiada pewną trudność - problem przepełnienia (reblocking problem).

Przykład:

(e_A, n_A) - klucz do podpisywania;

(e_B, n_B) - klucz do szyfrowania;

n_B > n_A

n_A=107 * 211 = 28907

e _A=13

n_B=127*173 = 21971

e _B=13

d _A= 2197

d _B=20005

m = 13983

Podpis

s = 13893 ²¹⁹⁷ mod 28907 = 25215

Szyfrowanie

c =25215 ¹³ mod 21971 = 5479 - postać zaszyfrowana podpisu;

Weryfikacja

c ^d mod n_B=5479 ²⁰⁰⁰⁵ mod21971 = 3244

Weryfikacja podpisu

m” = 3244 ¹³ mod 28907 = 276

m ≠ m”

Błąd w tym przypadku nie jest w obliczeniach, a w metodologii wykorzystywania przekształceń. Błąd polega na obliczaniu wartości n_A, n_B Aby się jego pozbyć moduł podpisujący (n_A), powinien mieć mniejszą wartość niż moduł szyfrujący (n_B). Warunek ten możemy otrzymać dokonując np. narzucenia aby n_A miało r bitów, a n_B r+1.

Prawdopodobieństwo wystąpienia błędu:

Funkcje redundancji

1. u(m) = m - funkcja identyczności;

2. u(m)=m || m - konkatenacja wiadomości sama z sobą;

3. funkcja Π - wg normy ISO/IEC 9796

Niech m = m_r || m _r-1 || … || m₁

Oznaczmy naszą poszukiwaną funkcje u(m) przez MR

MR = MR _2r || MR _{2r - 1} || … || MR ₁

Rozpatrzmy przypadek dla r=5:

Każdy z bloków nieoznaczonych jest funkcją bloku poprzedniego Π. Jest to permutacja:

Schemat Rabina

Przestrzeń podpisów - zbiór reszt kwadratowych modulo n - S =QR _n.

Algorytm generowania kluczy (zobacz szyfr Rabina)

Klucze: publiczny i prywatny;

1. Wygeneruj dwie duże, losowe, różne liczby pierwsze p i q;

2. Wyznacz n = pq;

3. Przyjmij k_e = n oraz k_d =(p, q);

Generowanie podpisu

1. Oblicz m' = u (m);

2. Wyznacz pierwiastek kwadratowy m' mod n i oznacz go przez s;

3. s jest podpisem wiadomości m;

Weryfikacja podpisu s

1. Zadbaj o to, aby klucz publiczny był prawdziwy;

2. Oblicz m' = s² mod n;

3. Sprawdź, czy m'∈ S, jeśli nie podpis odrzuć;

4. Wyznacz m = u ^-1 (m);

Przykład:

p=7, q=11, n=77;

S = QR₇₇={1, 4, 9, 15, 16, 23, 25, 36, 37, 53, 58, 60, 60, 64, 67, 71}

Załóżmy, że u(m)=m;

Niech m=23

Chcemy podpisać wiadomość m. Musimy znaleźć √ 23 mod 27. Pierwiastkami tymi są 10, 32, 45, 67.  Wybierzemy s=32.

Weryfikacja:

m'=32 ² mod 77 = 23

m' = m

Standard amerykański DSS - norma FIPS 186

Standard ten przedstawiony jest w algorytmie DSA. Mechanizm podpisu wymaga funkcji skrótu h:{0, 1}*→Z_p, dla pewnej liczby pierwszej p. DSS wymaga zastosowania SHA-1.

Algorytm generowania kluczy

Każdy użytkownik tworzy klucz publiczny i odpowiadający mu klucz prywatny, wykonując:

1. Wybierz liczbę pierwszą p, taką że 2 ¹⁵⁹<p<2¹⁶⁰.

2. Wybierz r takie, że 0≤r≤8 oraz liczbę pierwszą q, taką, że 2 ^511+64r<p<2^512+64r o takiej właściwości, że p|(q-1).

3. { Wybierz generator g grupy cyklicznej rzędu p w Z_q*}

1. Wybierz element b∈ Z_q* i wyznacz g=b^(q-1)/p mod q.

2. Jeśli g=1 to przejdź do kroku 3.1.

4. Wybierz liczbę losową a, taką że 1≤a≤p-1.

5. Wylicz g^a mod q.

6. Publicznym kluczem użytkownika A jest czwórka (p, q, g, y), a kluczem prywatnym liczba a.

Algorytm generowania podpisu

Użytkownik A podpisuje binarną wiadomość m o dowolnej długości, wykonując następujące operacje:

1. Wybiera losowo tajną liczbę naturalną r, 0<r<p i zachowuje ją w sekrecie.

2. Oblicza t = (g^r mod q) mod p.

3. Oblicza r ^-1mod p.

4. Wyznacza s = r ^-1(h(m)+bt) mod p.

5. Podpisem użytkownika A jest paa (s, t).

Algorytm generowania podpisu

Użytkownik B weryfikuje podpis (s, t) wiadomości m wykonany przez użytkownika A, wykonując następujące czynności:

1. Sprawdza, czy 0<s<p i 0<t<p. Jeśli nie, to odrzuca podpis.

2. Oblicza v=^-1mod p i wyznacza h(m).

3. Oblicza w₁= v*h(m) mod p oraz w₂= tv mod p.

4. Oblicza

5. Akceptuje podpis gdy z=t.

Dowód poprawności tego schematu.

Jeśli (s, t) jest właściwym podpisem użytkownika A pod wiadomością m, to:

Schemat ElGamala

Generuje podpis z dodatkiem dla wiadomości binarnej dowolnej długości i wymaga funkcji skrótu h:{0,1}*→Z_q dla pewnej liczby pierwszej q.

Algorytm generowania kluczy

Każdy użytkownik tworzy klucz publiczny i odpowiadający mu klucz prywatny, wykonując:

1. Wybierz liczbę pierwszą q i generator grupy multiplikatywnej Z_g*.

2. Wybierz losowo liczbę całkowitą a∈{1,2,…q - 2}.

3. Oblicz y= g^a mod q.

4. Publicznym kluczem użytkownika A jest trójka (g, y, q), a kluczem prywatnym liczba a.

Algorytm generowania podpisu

Użytkownik A podpisuje wiadomość m, wykonując następujące operacje:

1. Wybiera losowo tajną liczbę naturalną r, 0<r<q-2, taką że NWD(r, q-1)=1.

2. Oblicza t = g^r mod q.

3. Oblicza r ^-1 mod p.

4. Wyznacza s= r ^-1 (h(m) - at) mod (q-1).

5. Podpisem użytkownika A jest para (s, t).

Algorytm weryfikacji podpisu

Użytkownik B weryfikuje podpis (s, t) wiadomości m wykonany przez użytkownika A, wykonując następujące operacje:

1. Sprawdza czy 0<t<q-1. Jeśli nie, to odrzuca podpis.

2. Oblicza w₁=y^t t^s mod q.

3. Wylicza skrót h(m) wiadomości m.

4. Oblicza w₂=g^h(m) mod q.

5. Akceptuje podpis s gdy w₂= w₁.

Dowód poprawności schematu:

Jeśli (s, t) jest właściwym podpisem użytkownika A pod wiadomością m, to:

Warianty schematu ElGamala

Istnieje wiele wariantów schematu ElGamala różniących się w zależności od równania podpisującego (krok 4 alg. Generowania podpisu):

s= r ^-1 (h(m) - at) mod (q-1)

Po przekształceniu otrzymuje się:

h(m) = (rs + at) mod (q-1)

lub jeśli przyjąć, że u=h(m), v=t, z=s, to:

u=(rz + av) mod (q-1).

Można teraz otrzymać kolejne równania podpisujące przyjmując w równaniu powyższym, że każda ze zmiennych u, v, z może przyjmować nie powtarzające się wartości ze zbioru {h(m), t, s}. Takich możliwych permutacji jest 3! = 6. Zebrano je w poniższej tablicy podając także postać równania podpisującego I weryfikującego.

Lp.	u	v	z	Podpis	Weryfikacja
								w1 = y^v v^z	w2 = g^u
1	h(m)	s	t	h(m)= rt+as	g^ass^t	g^h^(m)
2	h(m)	t	s	h(m) = rs+at	g^att^s	g^h^(m)
3	s	h(m)	t	s = rt+ah(m)	g^ah(m)h(m)^t	g^s
4	s	t	h(m)	s = rh(m)+at	g^a^tt^h(m)	g^s
5	t	h(m)	s	t = rs+ah(m)	g^a^h(m)h(m)^s	g^t
6	t	s	h(m)	t = rh(m)+as	g^ass^h(m)	g^t

W kolumnie „podpis” wynik należy brać modulo (q-1). W kolumnach w₁ i w₂ wynik należy obliczać modulo q.

y = g^a mod q.

Mechanizmy kryptograficzne - podpis cyfrowy

6

---