2014-05-20

1

Bezpieczeństwo i ochrona

danych

Podpisy elektroniczne

Grzegorz Kołaczek, Ph.D., Eng.

Agenda

1. Podpis elektroniczny - cele
2. Klasyczne metody uwierzytelnienia

użytkownika

3. Mechanizmy tworzenia podpisu elektronicznego

Podpis elektroniczny

Ustawa o podpisie elektronicznym z 18 września 2001 r.
„Bezpieczny podpis, to podpis, który:
- Jest przyporządkowany wyłącznie do osoby

składającej ten podpis,

- Jest sporządzony za pomocą podlegających wyłącznej

kontroli osoby składającej podpis elektroniczny

bezpiecznych urządzeń służących do składania podpisu

elektronicznego i danych służących do składania

podpisu elektronicznego,

- Jest powiązany z danymi, do których został

dołączony, w taki sposób, że jakakolwiek późniejsza

zmiana tych danych jest rozpoznawalna.”

Funkcje podpisu cyfrowego

Podpis tradycyjny

Podpis cyfrowy

Cechy wspólne

1. przypisany jednej osobie

2.

niemożliwy do podrobienia

3.

uniemożliwiający wyparcie się go przez autora

4.

łatwy do weryfikacji przez osobę niezależną

5.

łatwy do wygenerowania

Różnice

6.

związany nierozłącznie z dokumentem 6. może być składowany i transmitowany

niezależnie od dokumentu

7.

taki sam dla wszystkich dokumentów

7. będący funkcją dokumentu

8. stawiany na ostatniej stronie
dokumentu

8. obejmuje cały dokument

Funkcje podpisu cyfrowego

• Uwierzytelnienie
• Niezaprzeczalność
• Integralność
• Identyfikacja

Dystrybucja klucza

• Znajomość klucza publicznego -> pewność

autorstwa

• Certyfikat to klucz publiczny podpisany

przez osobę godną zaufania

2014-05-20

2

STANDARD X509

• Organ certyfikujący – Certification

Authority (CA)

STANDARD X509

• Struktura certyfikatu

– Certyfikat zgodny ze standardem X.509 wersji

3 składa się, najczęściej, z:

• Tematu (subject) – Jednoznacznie

identyfikującego właściciela (np. użytkownika,
komputer, urządzenie sieciowe…) klucza
prywatnego powiązanego z danym certyfikatem,

• Dodatkowych informacji o właścicielu (np. adres,

itp.),

• Informacji o podpisującym CA,

STANDARD X509

• Struktura certyfikatu

– Certyfikat zgodny ze standardem X.509 wersji

3 składa się, najczęściej, z:

• Klucza publicznego,
• Nazw algorytmów kryptograficznych używanych

do stworzenia danego certyfikatu (np. do
wygenerowania podpisu CA),

• Listy rozszerzeń (extensions) zawartych w

certyfikacie,

• Informacji o sposobie uzyskiwania informacji o

ewentualnym odwołaniu certyfikatu (np. adres
www z którego można pobrać listę CRL).

Modele zaufania

Model ze ścisłą hierarchią centrów certyfikacji

Modele zaufania

Model zaufania skoncentrowany na użytkowniku

Schematy podpisu elektronicznego

• Z algorytmem symetrycznym i arbitrem
• Tradycyjne czyli z załącznikiem (ang. appendix)

– RSA, ElGamal, DSA, Shnorr,

• Jednorazowe (ang. one-time)

– Rabin, Merkle,

• Ślepe (ang. blind )

– Chaum,

• Niezaprzeczalne (ang. undeniable)

– Chaum-van Antwerpen,

• Grupowe (ang. group) i pierscieniowe (ang. ring )

– Rivest-Shamir-Tauman,

2014-05-20

3

Podpis z symetrycznym algorytmem
kryptograficznym

1.

„A” szyfruje wiadomość dla „B”

kluczem KA (do arbitra)

2.

Arbiter deszyfruje wiadomość

KA i stwierdza, że pochodzi ona

od „A”

3.

Arbiter szyfruje wiadomość KB i

wysyła do „B”

4.

„B” odszyfrowuje KB i

porównuje z informacją od „A”

Informacje te same - wiadomość

została wysłana przez „A”

Podpis z załącznikiem

• Podpis z załącznikiem wymaga aby w

czasie weryfikacji podpisu użyta została
wiadomość pod którą podpis został złożony

Podpis z asymetrycznym algorytmem
kryptograficznym (RSA)

• Protokół:

– Alicja szyfruje dokument przy użyciu własnego klucza

prywatnego, tym samym go podpisuje

– Alicja przesyła podpisany dokument Bobowi
– W celu sprawdzenia podpisu Bob deszyfruje dokument

za pomocą klucza publicznego Alicji

Podpis z asymetrycznym algorytmem
kryptograficznym (RSA)

Protokół ten spełnia następujące wymagania:

• Podpis jest autentyczny, kiedy odbiorca weryfikuje wiadomość za

pomocą klucza publicznego nadawcy wie, że to on ją podpisał.

• Podpis jest niepodrabialny, gdyż jedynie nadawca zna odpowiedni

klucz prywatny.

• Podpis nie jest ponownie używany; podpis funkcjonuje razem z

dokumentem i nie może być przeniesiony do dowolnego innego

dokumentu.

• Podpisany dokument jest niezmienialny; jeśli wystąpi najmniejsza

modyfikacja dokumentu, to nie może on być nadal sprawdzany przy

użyciu klucza publicznego nadawcy.

• Nie można wyprzeć się podpisu.

Odbiorca nie potrzebuje pomocy ze strony nadawcy, aby sprawdzić

jego podpis.

Tworzenie podpisu cyfrowego

• Jednokierunkowa funkcja skrótu

– Bardzo łatwo obliczyć skrót na podstawie

ciągu wejściowego,

– Bardzo trudno wygenerować ciąg wejściowy

znając funkcję skrótu

– MD-5, SHA, MD-2 128-160 bitów

Tworzenie podpisu cyfrowego

2014-05-20

4

Weryfikacja podpisu cyfrowego

Podpis Shnorra

• Podmiot A podpisuje binarną wiadomość m o

dowolnej długości.

• Dowolny podmiot B może zweryfikować podpis

podmiotu A, stosując jego klucz publiczny

• Jego bezpieczeństwo opiera się na trudności w

rozwiązaniu logarytmu dyskretnego.

• Algorytm jest wydajny i tworzy krótkie podpisy.

Podpis Shnorra

• Klucz publiczny

– (p,q,g,y)
– q – liczba pierwsza (≥ 2^160)
– p – liczba pierwsza taka, że q dzieli (p-1) (≈ 2^1024)
– g - generator
– y=g

a

mod p

• Klucz prywatny

– losowa liczba a, taka że 1



a



p-2

Podpis Shnorra

• Podpisywanie (podmiot A)

– wybierz losowe (tajne) k,

• 1



k



q -1,

– oblicz:

• r = g

k

mod p

• e = h(m||r ),
• s = (ae + k) mod q,

– podpisem pod m jest para (e,s).

Podpis Shnorra

• Weryfikacja

– sprawdź czy 0 < s < q,

• jeśli nie, to odrzuć podpis,

– oblicz v

1

= g

s

y

-e

mod p,

– oblicz v

2

= h(m|| v

1

),

– sprawdź czy v

2

= e

– jeśli tak, to podpis jest poprawny.

Podpis Nyber-Rueppel
z odtwarzaniem wiadomości

• Podmiot A podpisuje binarną wiadomość

m



M.

• Dowolny podmiot B może zweryfikować

podpis podmiotu A i odtworzyć z podpisu
wiadomość m

2014-05-20

5

Idea podpisów jednorazowych

• Mechanizm podpisów, który w sposób bezpieczny

może być użyty dokładnie raz

• Każde użycie schematu wymaga generowania

nowej pary informacji prywatna-publiczna,

• Większość schematów może być bardzo

efektywnie zaimplementowana.

Podpisy jednorazowe Rabina

• Przygotowanie

– wybierz bezpieczny schemat szyfrowania

symetrycznego,

– wylosuj 2n kluczy szyfrujących k

1

; k

2

; …; k

2n

,

– oblicz y

i

= E

ki

(i) dla 1



i



2n,

– publicznym kluczem jest (y

1

; y

2

; …; y

2n

),

– kluczem prywatnym (k

1

; k

2

; …; k

2n

)

Podpisy jednorazowe Rabina

• Podpis

– oblicz h(m),
– oblicz s

i

= E

ki

(h(m)) dla 1



i



2n

– podpisem jest (s

1

; s

2

; …; s

2n

).

Podpisy jednorazowe Rabina

• Weryfikacja podpisu

– weź m, (s

1

; s

2

; …; s

2n

) i klucz publiczny (y

1

; y

2

; …; y

2n

).

– oblicz h(m),
– wylosuj n liczb 1



r

j



2n,

– zażądaj od podpisującego kluczy k

rj

dla 1



j



n,

– sprawdź czy y

rj

= E

k(rj)

(r

j

) dla 1



j



n,

• jeśli NIE, to odrzuć podpis,

– sprawdź czy s

rj

= E

k(rj)

(h(m)) dla 1



j



n,

• jeśli TAK, to zaakceptuj podpis.

Podpisy jednorazowe Rabina

• Klucz publiczny jest zobowiązaniem podpisującego co do

wyboru kluczy k

i

,

• podpisywanie

– 2n szyfrogramów wiadomości (h(m))z użyciem różnych kluczy,

• weryfikacja

– losowe sprawdzenie poprawności n szyfrogramów poprzez

ujawnienie n kluczy k

i

,

• Wady:

– rozmiar podpisu,
– weryfikacja podpisu wymaga interakcji podpisującego i

weryfikującego.

Podpisy jednorazowe Merkle

• Przygotowanie

– Aby podpisać n-bitową wiadomość:

• wylosuj t = n +



log

2

n



+ 1

losowych, tajnych l -bitowych liczb k

i

,

• oblicz v

i

=h(k

i

), 1



i



t,

• publicznym kluczem jest (v

1

,v

2

,...v

2n

),

• prywatnym (k

1

,k

2

,...k

2n

)

2014-05-20

6

Podpisy jednorazowe Merkle

• Podpis wiadomości ‚m’ długości ‚n’ bitów

– oblicz w,

gdzie c jest binarną reprezentacja liczebności ‚0’ w
liczbie m;
w=m||c =(a

1

a

2

...a

t

)

– ustal pozycje ‚1’

i

1

<i

2

...<i

u

w liczbie w, a

ij

=1

– Niech s

j

=k

ij

, 1



j



u.

– Podpisem jest (s

1

,...s

u

)

Podpisy jednorazowe Merkle

• Weryfikacja podpisu

– weź m oraz klucz publiczny(v

1

; v

2

; …; v

2n

).

– oblicz c,
– wyszukaj wszystkie bity i

j

liczby w = m||c, takie że

w

ij

= 1,

– sprawdź czy v

ij

= h(k

ij

) dla 1



j



u, jeśli TAK, to

zaakceptuj podpis,

Podpisy jednorazowe Merkle

• Mniejszy rozmiar podpisu – podpisujemy tylko

jedynki w bitowym zapisie h(m),

• Większa efektywność – funkcja skrótu zamiast

szyfrowania,

• Kolejne wykorzystanie protokołu z tymi samymi

parametrami zwiększa prawdopodobieństwo
podrobienia podpisu (ujawnia coraz więcej
sekretów).

Ślepe podpisy

• Protokół realizowany przez dwie strony (A i B), w których

A wysyła do B pewną informację m’, która B podpisuje.

• Na podstawie uzyskanego podpisu A jest w stanie

wygenerować podpis pod wybraną wcześniej
wiadomością m, tym razem już bez udziału B.

– B nie wie co podpisuje – nie zna m,
– B nie potrafi powiązać m’ z podpisem pod m,
– B widząc swój podpis pod m nie potrafi powiedzieć dla kogo ją

wygenerował.

• Potrzebne np.:

– przy elektronicznych wyborach, systemach elektronicznych

płatności

Ślepe podpisy Chauma

• Przygotowanie

– Analogiczne jak w schemacie RSA, przy czym B

posiada swoją parę kluczy

• prywatny (d; n)
• publiczny (e; n).

– Druga strona – A, musi tylko znać klucz

publiczny B.

Ślepe podpisy Chauma

• Podpisywanie

– A losuje 1 < k < n-1, takie, ze NWD(k, n) = 1,
– A oblicza m’ = mk

e

mod n i wysyła do B,

– B podpisuje s’ = (m’)

d

mod n i odsyła s’ do A,

– A oblicza s = s’k

-1

mod n, które jest podpisem

B pod m.

• Weryfikacja

– Analogicznie jak w przypadku RSA

2014-05-20

7

Podpisy niezaprzeczalne

• Podpis, którego użytkownik nie może się wyprzeć

– można pokazać, że podpis został wygenerowany z

użyciem klucza prywatnego użytkownika,

– weryfikacja zawsze przeprowadzana on-line,
– wymagają dodatkowej procedury odrzucenie podpisu,

która jest wykonywana zawsze jeśli weryfikacja
zakończyła się brakiem akceptacji podpisu

– procedura ma za zadanie ustalić, czy oszukuje

podpisujący czy rzeczywiście podpis nie jest jego,

Schemat Chaum-van Antwerpen

• Przygotowanie

– wybierz losową liczbę pierwszą p = 2q + 1

gdzie q jest pierwsze,

– wybierz generator g podgrupy Z

q

,

– wybierz losowa liczbę 1



a < q,

oblicz y = g

a

mod p,

– kluczem publicznym jest (y; g; p),
– prywatnym a.

Schemat Chaum-van Antwerpen

• Podpis

– oblicz s = m

a

mod p,

– podpisem pod m jest s.

• Weryfikacja

– weryfikujący (B) wybiera losowe liczby 1



x

1

; x

2

< q,

– B oblicza z = s

x1

y

x2

mod p i wysyła do A,

– A oblicza w = z

a-1

mod p i odsyła w do B,

– B sprawdza czy m

x1

g

x2

= w,

• jeśli TAK to akceptuje podpis,
• jeśli NIE to wykonuje procedurę odrzucenia podpisu.

Schemat Chaum-van Antwerpen

• Procedura odrzucenia podpisu

–

weryfikujący (B) wybiera losowe liczby 1



x

1

; x

2

< q,

–

B oblicza z = s

x1

y

x2

mod p i wysyła do A,

–

A oblicza w = z

a-1

mod p i odsyła w do B,

–

B sprawdza czy m

x1

g

x2

= w, jeśli TAK to akceptuje podpis i kończy,

– jeśli NIE, to B losuje liczby 1



x

1

’, x

2

’ < q

– B oblicza z’ = s

x1’

y

x2’

mod p i wysyła do A,

– A oblicza w’ = z’

a-1

mod p i odsyła w’ do B,

– B sprawdza czy m

x1’

g

x2’

= w’,

• jeśli TAK to akceptuje podpis i kończy,
• jeśli NIE to sprawdza czy: (wg

-x2

)

x1’

= (w’g

-x2’

)

x1

– jeśli TAK to s jest fałszywe,
– jeśli NIE to A oszukuje.

Podpisy grupowe

• Podpis, który został złożony przez jednego

z użytkowników należących do pewnej
grupy.

• Weryfikujący może jedynie stwierdzić, że

podpis złożył członek grupy, ale nie jest w
stanie powiedzieć który.

Podpisy pierścieniowe

• Przygotowanie

– każdy użytkownik 1



i



t posiada parę kluczy

(P

i

; S

i

)

• asymetryczny algorytm szyfrowania, np: RSA,

– każdy użytkownik zna klucze publiczne pozostałych

użytkowników,

– każdy użytkownik zna klucz K symetrycznego

algorytmu szyfrowania,

• np: AES.

2014-05-20

8

Podpisy pierścieniowe

• Podpis

– użytkownik u oblicza:

• v = h(m)
• losuje wartości y

i

dla 1



i



t i i



u,

– dla wylosowanych y

i

oblicza x

i

= D

Pi

(y

i

),

– oblicza x

u

takie, że

• v

= E(x

1



E(x

2



E(…

x

u



E(…x

t



E(v)))))

– oblicza y

u

= E

Si

(x

u

),

– podpisem pod m jest (v; y

1

; y

2

; ..; y

u

;…; y

t

).

Podpisy pierścieniowe

• Weryfikacja

– weryfikujący (B) oblicza

• x

i

= D

Pi

(y

i

) dla 1



i



t,

– sprawdza czy

• v = E(x

1



E(x

2



E(… x

u



E(…x

t



E(v)))))

Dziękuję za uwagę