prywatność albo poufność - utrzymywanie informacji w sekrecie dla wszystkich podmiotów, które nie są uprawnione do jej znajomo

prywatność albo poufność - utrzymywanie informacji w sekrecie dla wszystkich podmiotów, które nie są
uprawnione do jej znajomości;
Warunki:

Przy zastosowaniu metod obliczeniowych nie powinno być możliwe systematyczne określanie
przekształcenia deszyfrującego D

na podstawie przechwyconej, zaszyfrowanej treści C, nawet

wówczas, gdy jest znany jej jawny odpowiednik.

2. Stosując metody obliczeniowe kryptoanalityk nie powinien mieć możliwości systematycznego

określenia jawnej treści M na podstawie znajomości przechwyconej, zaszyfrowanej treści C.

integralność danych - zapewnienie, iż informacja nie zostanie zmodyfikowana przez nieuprawnione lub
nieznane podmioty;
Warunki:

Powinno być obliczeniowo niemożliwe systematyczne określenie przekształcenia szyfrującego E

przy

danym C nawet wówczas, gdy odpowiadająca mu jawna treść M jest znana

Powinno być obliczeniowo niemożliwe, aby w sposób systematyczny doprowadzić do ustalenia takiej
zaszyfrowanej treści C’, aby D

(C’) było jednym z elementów zbioru M.

FUNKCJE SKRÓTU

Mianem funkcji skrótu (hash function) określa się efektywną obliczeniowo funkcję odwzorowującą

ciągi binarne o dowolnej długości na ciągi binarne o ustalonej długości.

Z punktu widzenia konieczności znajomości określonych sekretów dla dokonania obliczeń funkcji skrótu

istnieją dwa ich rodzaje :

•

funkcja skrótu bez klucza - wartość funkcji jest zależna wyłącznie od argumentu funkcji skrótu h = f(x)

•

funkcja skrótu z kluczem (kryptograficzna funkcja/suma kontrolna) - wartość funkcji jest zależna także od
klucza, którego znajomość jest niezbędna do obliczenia wartości skrótu h = f( x, k )

"Dobre" (czyli przydatne dla potrzeb kryptografii) funkcje skrótu musi cechować pseudolosowość, tzn.

dowolna wartość funkcji skrótu powinna być jednakowo prawdopodobna, zaś zmiana jednego bitu argumentu
funkcji skrótu powinna powodować zmianę około połowy bitów wartości funkcji dla tego nowego argumentu.

Klasyfikacja jednokierunkowych funkcji skrótu

•

uniwersalne jednokierunkowe funkcje skrótu (UOH - universal one-way hash functions), zwane słabymi
- charakteryzujące się tym, że przy danym ciągu początkowym x jest obliczeniowo trudne wyznaczenie
różnego od x ciągu y, który byłby w kolizji z ciągiem x (dwa różne ciągi x i y są w kolizji, jeśli h(x) = h(y));

•

funkcje skrótu odporne na kolizje (CIH - collision intractable hash functions), zwane silnymi - w
przypadku których jest obliczeniowo trudne wyznaczenie takiej pary różnych ciągów x i y, by były one w
kolizji.

Zastosowania funkcji skrótu:

•

w podpisach cyfrowych dla potrzeb realizacji usługi integralności danych; długa wiadomość jest zazwyczaj
przekształcana przez funkcję skrótu do łańcucha binarnego o ustalonej długości, zaś podpisywana jest tylko
wartość funkcji skrótu; weryfikator przekształca znana funkcją skrótu otrzymaną wiadomość jawną i
sprawdza poprawność podpisu cyfrowego porównując tą wartość z wartością dołączoną jako podpis, np:

Procedura podpisywania wiadomości:

•

obliczenie wartości funkcji skrótu h (m) dla wiadomości m

•

obliczenie podpisu: s = D

( h (m) )

•

wysłanie podpisanej wiadomości ( m, s ).

Procedura weryfikacji podpisu:
Funkcja weryfikująca:

prawda , jeżeli E

( s ) = h (m)

( m, s ) =

fałsz w przypadku przeciwnym

{

•

jako uogólnienie pojęcia tzw. sumy kontrolnej, w celu sprawdzenia integralności pewnego pakietu danych
(np.dla potrzeb profilaktyki antywirusowej lub zwalczania „piractwa” oprogramowania); wartość funkcji
skrótu jest obliczana podczas tworzenia oryginalnego pakietu i przechowywana dla potrzeb późniejszej
weryfikacji;

•

w   protokołach   kryptograficznych   opartych   na   tzw.  zobowiązaniach   bitowych,  w   których   np.   dwa   ciągi
binarne   pochodzące   od   dwóch   różnych   podmiotów   są   konkatenowane   (lub   łączone   w   inny   sposób)   a
następnie   poddawane   działaniu   funkcji   skrótu;   takie   rozwiązanie   stosuje   się   przy   pewnych   schematach
podpisów cyfrowych lub określonych mechanizmach identyfikacji podmiotów.

PODPIS CYFROWY

Podpis cyfrowy jest środkiem (metodą) powiązania tożsamości podmiotu z pewną informacją.

M - zbiór wiadomości, które mogą być podpisywane;
S - zbiór elementów zwanych podpisami

(np. ciągi binarne o ustalonej długości);

- przekształcenie ze zbioru M na zbiór S

(przekształcenie podpisujące dla podmiotu A -
utrzymywane w tajemnicy przez podmiot A);

- przekształcenie ze zbioru M x S na zbiór { prawda, fałsz }

(przekształcenie weryfikujące dla podpisów A -
ujawniane publicznie i wykorzystywane do weryfikacji podpisów
wytworzonych przez podmiot A)

UWAGA: W praktyce S

jest znanym algorytmem zależnym od utrzymywanego w sekrecie klucza k

Przekształcenia S

i V

tworzą schemat (mechanizm) podpisu cyfrowego dla podmiotu A.

Procedura podpisywania wiadomości:
Podmiot A wytwarza podpis cyfrowy dla wiadomości m

∈

M :

•

obliczając wartość s = S

( m );

•

wysyłając parę ( m, s ), gdzie s jest podpisem wiadomości m.

Procedura weryfikacji podpisu:
Podmiot B (weryfikator) w celu zweryfikowania podpisu A ”złożonego” na wiadomości m :

•

pozyskuje funkcję weryfikującą V

;

•

oblicza wartość u = V

( m, s );

•

jeżeli u = prawda , to akceptuje podpis „złożony” przez A na wiadomości m , w przeciwnym przypadku ( u
= fałsz ) odrzuca podpis (uznaje go za nieprawdziwy).

Właściwości wymagane od funkcji podpisującej i weryfikującej:

•

s jest ważnym podpisem podmiotu A na wiadomości m

⇔

( m, s ) = prawda

•

obliczeniowo niewykonalne jest wyznaczenie dla dowolnej wiadomości m

∈

M przez podmiot inny niż A

takiej wartości s , że:

( m, s ) = prawda

UWIERZYTELNIANIE I IDENTYFIKACJA

Mechanizmy identyfikacji (albo inaczej: uwierzytelniania podmiotów) umożliwiają jednej (lub obu stronom)
uzyskanie potwierdzenia tożsamości drugiej strony biorącej udział w komunikacji, a także potwierdzenie, że
druga strona była aktywna w czasie, gdy to potwierdzenie tożsamości było wytworzone lub uzyskane.

Przykład uwierzytelniania jednostronnego:
A wprowadza swój PIN-kod do bankomatu, jednocześnie przedstawiając bankomatowi kartę magnetyczną,
zawierającą oprócz danych personalnych A także dane umożliwiające weryfikację poprawności wprowadzonego
PIN-kod. W ten sposób urządzenie (bankomat) dokonuje jednostronnego uwierzytelniania podmiotu A.

Przykład uwierzytelniania wzajemnego:
A nawiązuje głosowe połączenie telefoniczne z B. Oba podmioty znają swoje głosy, dzięki czemu dokonują
wzajemnego uwierzytelniania

Mechanizmy uwierzytelniania pochodzenia danych umożliwiają stronie otrzymującej wiadomość nabycie
pewności, że określony podmiot był twórcą tej wiadomości (z reguły nie wymaga to weryfikacji czasu powstania
wiadomości - np. potwierdzanie autentyczności poczty elektronicznej).

KRYPTOGRAFIA KLUCZA PUBLICZNEGO

Szyfrowanie kluczem publicznym:

Niech { E

: e

∈

K } będzie zbiorem przekształceń szyfrujących, zaś { D

: d

∈

K } odpowiadającym mu

zbiorem przekształceń deszyfrujących.

Jeżeli dla dowolnej pary ( E

, D

), mimo znajomości E

, jest obliczeniowo niewykonalne wyznaczenie dla

dowolnego losowego kryptogramu c

∈

C takiej wiadomości jawnej m

∈

M , że:

( m ) = c

to taki system kryptograficzny jest systemem klucza publicznego (systemem kryptografii asymetrycznej).

Powyższe stwierdzenie jest równoważne temu, iż znajomość e nie umożliwia wykonalności obliczenia drugiego
klucza z pary, czyli d.

Podpisy cyfrowe realizowane odwracalnymi przekształceniami kryptografii asymetrycznej

Niech E

będzie przekształceniem szyfrującym, D

- odpowiadającym mu przekształceniem deszyfrującym oraz

niech przekształcenia te będą endomorficzne ( C = M ) :

∀

∈

M : D

( E

( m )) = E

( D

( m )) = m;

tak zdefiniowany system jest odwracalnym systemem klucza publicznego.

Schemat podpisu cyfrowego:

Niech M będzie przestrzenią podpisywanych wiadomości,

C - przestrzenią podpisów S (warunek C = M jest konieczny),
zaś ( e, d ) parą kluczy odwracalnego systemu asymetrycznego.

Procedura podpisywania wiadomości:

Funkcja podpisująca S

= D

•

obliczenie podpisu: s = D

( m )

•

wysłanie podpisanej wiadomości ( m, s ).

Procedura weryfikacji podpisu:

Funkcja weryfikująca:

prawda , jeżeli E

( s ) = m

{

Podpis cyfrowy umożliwiający odtwarzanie/odzyskiwanie wiadomości jawnych

(digital signature with message recovery)

Niech M’

⊂

M zawiera tylko pewne elementy przestrzeni wiadomosci jawnych o określonej strukturze

(formacie), np. o ustalonej długości t symboli alfabetu A

(a ogólnie: tzw. wiadomości z redundancją).

Jeżeli podmiot A będzie podpisywał tylko wiadomości m

∈

M’ , to wiadomości te mogą być łatwo odtwarzane/

rozpoznawane przez podmiot weryfikujący podpis na podstawie samego podpisu.

Procedura podpisywania wiadomości (z odtwarzaniem):

•

obliczenie podpisu: s = D

( m )

•

wysłanie podpisu s.

Procedura weryfikacji podpisu:

Funkcja weryfikująca:

prawda , jeżeli E

( s )

∈

M’

( s ) =

fałsz w przypadku przeciwnym

Istotny jest fakt, że moc zbioru M’ jest liczbą kardynalną o wiele mniejszą od liczby kardynalnej określającej

moc zbioru M.

UWAGA: Podmiot B może wybrać losowy element s

∈

S jako podpis pewnej wiadomości, a następnie

wyznaczyć u = E

( s ) i wysłać u jako wiadomość m podpisaną przez A (czyli „podrobić” albo sfałszować

podpis A). Określona powyżej relacja między mocami zbiorów M i M’ skutecznie utrudnia taki atak.

Standard szyfrowania danych (DES)

DES jest szyfrem blokowym; dane są szyfrowane blokami o długości 64 bitów. Blok 64 bitów tekstu jawnego
pojawia się na jednym końcu algorytmu, a blok 64 bitów szyfrogramu wychodzi na jego drugim końcu. Zarówno
podczas     szyfrowania,   jak   i   deszyfrowania   wykorzystuje   się   ten   sam   algorytm   (za   wyjątkiem   różnic   w
operowaniu kluczem).
Klucz ma długość 56 bitów. (Zwykle klucz jest liczbą zapisaną za pomocą 64 bitów, przy czym każdy co ósmy
bit jest bitem parzystości, który jest pomijany).Całe zabezpieczenie spoczywa na kluczu.
Na   najniższym   poziomie   algorytm   jest   niczym   innym   jak   kombinacją   dwóch   podstawowych   technik
szyfrowania: mieszania i rozpraszania. Podstawowy blok, z którego jest zbudowany DES, stanowi pojedynczą
kombinację tych technik   (podsumowanie, za którym następuje permutacja) działająca, z udziałem klucza, na
tekst. Ciąg tych działań nazwany jest cyklem. W DES występuje 16 cykli.

Szkic algorytmu
DES pracuje na 64-bitowych blokach testu jawnego. Po początkowej permutacji blok wejściowy jest dzielony na
lewą i prawą połowę, każda o długości 32 bitów. Następnie wykonywanych jest 16 cykli jednakowych operacji,
nazywanych funkcjami f, w czasie których dane są łączone z kluczem. Po 16 cyklu lewa i prawa połowa są
łączone i końcowa permutacja (będąca odwrotnością permutacji początkowej) kończy przebieg algorytmu.
W każdym cyklu bity klucza są przesuwane, następnie jest wybieranych 48 bitów z 56 bitów klucza. Prawa
połowa bloku danych jest rozszerzana do 48 bitów za pomocą permutacji z rozszerzeniem, łączona za pomocą
poelementowej sumy modulo 2 z 48 bitami przesuniętego i spermutowanego klucza, jest dokonywane
podstawienie bloku 32 nowych bitów za pomocą algorytmu podstawiania, a potem jeszcze raz jest dokonywana
permutacja. Te cztery operacje tworzą funkcję f. Ciąg wyjściowy funkcji f jest dalej łączony z lewą połową za
pomocą poelementowej sumy modulo 2. Wynikiem tych operacji jest nowa lewa połowa bloku; stara lewa
połowa staje się nową połową prawą. Operacje te są powtarzane 16 razy.
Jeżeli Bi jest wynikiem i-tej iteracji algorytmu, Li i Ri są lewą i prawą połową Bi, Ki jest 48-bitowym kluczem
dla cyklu i, a f jest tą funkcją, która odpowiada za wszystkie podstawienia i permutacje oraz sumowanie modulo
2 z kluczem, to cykl i może być zapisany równaniami:
L

i-1

{

i-1

⊕

f(R

i-1

)

Algorytm IDEA
IDEA jest szyfrem blokowym. Pracuje na 64-bitowych blokach tekstu jawnego. Klucz ma długość 128 bitów.
Ten sam algorytm jest stosowany do szyfrowania i deszyfrowania.
IDEA wykorzystuje mieszanie i rozpraszanie.
Blok danych o długości 64 bitów jest dzielony na 4 16-bitowe podbloki: x1, x2, x3 i x4. Te cztery podbloki
stanowią wejście do pierwszego cyklu algorytmu. W sumie jest osiem cykli. W każdym cyklu te cztery podbloki
są sumowane modulo 2, dodawane i mnożone ze sobą oraz z sześcioma 16-bitowymi podblokami klucza.
Między cyklami podblok drugi i trzeci są zamieniane miejscami.
W każdym cyklu ciąg zdarzeń jest następujący:
1) Mnożymy x1 przez pierwszy podblok klucza.
2) Dodajemy x2 do drugiego podbloku klucza.
3) Dodajemy x3 do trzeciego podbloku klucza
4) Mnożymy x4 przez czwarty podblok klucza.
5) Dodajemy modulo 2 wyniki kroków (1) i (3).
6) Dodajemy modulo 2 wyniki kroków (2) i (4).
7) Mnożymy wyniki kroku (5) przez piąty podblok klucza.
8) Dodajemy wyniki kroków (6) i (7).
9) Mnożymy wynik kroku (8) przez szósty podblok klucza.
10) Dodajemy wyniki kroków (7) i (9).
11) Dodajemy modulo 2 wyniki kroków (1) i (9).
12) Dodajemy modulo 2 wyniki kroków (3) i (9).
13) Dodajemy modulo 2 wyniki kroków (2) i (10).
14) Dodajemy modulo 2 wyniki kroków (4) i (10).

Na wyjściu cyklu otrzymujemy cztery podbloki będące wynikiem kroków (11),(12),(13) i (14). Po zmianie
miejscami dwóch wewnętrznych podbloków (w ostatnim cyklu nie wykonuje się tej operacji) otrzymujemy blok
wejściowy do następnego cyklu.
Po ósmym cyklu są wykonywane końcowe przekształcenia:
1) Mnożymy x1 przez pierwszy podblok klucza
2) Dodajemy x2 do drugiego podbloku klucza
3) Dodajemy x3 do trzeciego podbloku klucza
4) Mnożymy x4 przez czwarty podblok klucza

Ostatecznie, otrzymane w wyniku powyższych operacji cztery podbloki są łączone w jeden blok szyfrogramu.
Tworzenie podbloków klucza jest także łatwe. Algorytm wykorzystuje ich w sumie 52 (sześć dla każdego z
ośmiu cykli i cztery w końcowym przekształceniu). Najpierw 128-bitowy klucz jest dzielony na osiem 16-
bitowych podkluczy. Jest to osiem pierwszych podkluczy do rozpoczęcia pracy algorytmu (sześć dla pierwszego
cyklu i pierwsze dwa dla cyklu drugiego). Następnie klucz jest przesuwany cyklicznie o 25 bitów w lewo i
ponownie dzielony na osiem podkluczy. Pierwsze cztery są użyte w cyklu drugim, a pozostałe cztery – w cyklu
trzecim. Z kolei klucz jest przesuwany cyklicznie o dalsze 25 bitów w lewo, dzielony na 8 podkluczy i procedura
ta jest powtarzana aż do końca algorytmu.
Deszyfrowanie przebiega tak samo, z wyjątkiem tego, że podbloki klucza są odwracane i trochę zmienione.
Podbloki klucza przy deszyfrowaniu są zarówno addytywnymi, jak i multiplikatywnymi odwrotnościami
podbloków klucza użytego do szyfrowania. (Dla alg. IDEA przyjęto, że multiplikatywną odwrotnością 0 jest 0).
Obliczenia z tym związane wymagają pewnego wysiłku, lecz wykonuje się tylko jeden raz dla każdego klucza
deszyfrującego.

RSA
Klucz publiczny

n iloczyn dwóch liczb pierwszych p i q (p i q muszą pozostać utajnione)
e liczba względnie pierwsza z (p-1)x(q-1)

Klucz prywatny

d=e^(-1) (mod (p-1)x(q-1))

Szyfrowanie

c=m^e (mod n)

deszyfrowanie

m=c^d (mod n)

Ze  wszystkich   algorytmów  z   kluczem  jawnym     zaproponowanych  przez   lata  jest  to,  dotychczas,  algorytm
najłatwiejszy do zrozumienia i implementacji( 1978 )
Zabezpieczenie dawane przez RSA wynika z trudności faktoryzacji dużych liczb Klucze jawne i prywatne są
funkcjami pary dużych (100 do 200 cyfr  lub dłuższych) liczb pierwszych. Przypuszcza się, że uzyskiwanie
tekstu jawnego przy znajomości jednego z tych kluczy i szyfrogramu jest równoważne faktoryzacji iloczynu
tych dwóch liczb pierwszych. Nigdy nie zostało matematycznie udowodnione że należy rozłożyć  n na czynniki
pierwsze aby obliczyć m znając e i c Można sobie wyobrazić zupełnie inny sposób kryptoanalizy RSA

Algorytm ElGamala (podpis cyfrowy)

Klucz publiczny:
p liczba pierwsza
g<p
y=g’( mod p)
Klucz prywatny:
x<p
Podpisywanie:
k liczba wybierana losowo, względnie pierwsza z p-1
a (podpis) = g

(mod p )

b (podpis) liczba taka, że M=xa +kb (mod p-1)
Weryfikacja:
Akceptacja podpisu, jeżeli y

(mod p) = g

(mod p)

Skuteczność zabezpieczenia tego algorytmu wynika z trudnośći obliczania logarytmów dyskretnych.

Wymiana klucza zaszyfrowanego
Protokół wymiany klucza zaszyfrowanego (EKE) .
Podstawowy protokół:
A i B dzielą wspólne hasło P. Przy wykorzystaniu tego protokołu mogą wzajemnie uwierzytelnić się i
wytworzyć wspólny klucz sesyjny K.

1) A generuje losowy klucz jawny K’. Szyfruje go za pomocą algorytmu symetrycznego i klucza P: Ep(K’).

Przesyła następnie B wiadomość:

A, Ep(K’)

2) B zna P. Deszyfruje wiadomość, aby uzyskać K’. Następnie wytwarza losowy klucz sesyjny K i szyfruje go

przy użyciu klucza jawnego otrzymanego od A i klucza tajnego P:

Ep(Ek,(K))

Przesyła to do A.
3) A deszyfruje wiadomość, aby uzyskać K. Wytwarza następnie ciąg losowy Ra, szyfruje go przy użyciu K i

przesyła wynik B:

Ek(Ra)

4) B deszyfruje wiadomość, aby uzyskać Ra. Wytwarza następnie inny ciąg losowy Rb, szyfruje oba ciągi przy

użyciu K i przesyła wynik do A:

Ek(Ra,Rb)

5) A deszyfruje wiadomość, aby uzyskać Ra i Rb. Jeżeli ciąg Ra, który otrzymała od B, jest taki sam jak ten,

który wysłała do B w kroku 3, to szyfruje Rb za pomocą K i wysyła go do B.

Ek(Rb)

6) B deszyfruje wiadomość, aby uzyskać Rb. Jeżeli ciąg rb, który otrzymał od A, jest taki sam jak ten, który

wysłał do A w kroku 4, to protokół dobiegł końca. Obie strony mogą teraz komunikować się za pomocą K
jako klucza sesyjnego.

Dla alg. Diffiego-Hellmana
1. A wybiera liczbę losową Ra i wys. Do B

A,g

(mod n)

2. B wybiera liczbę los. rb i oblicza

K=g

ra x rb

(mod n)

Generuje ciąg losowy Rb, a następnie oblicza i przesyła do A

P(g

(mod n)), K(Rb)

Document Outline