prywatność albo poufność - utrzymywanie informacji w sekrecie dla wszystkich podmiotów, które nie są uprawnione do jej znajomości;
Warunki:
1. Przy zastosowaniu metod obliczeniowych nie powinno być możliwe systematyczne określanie przekształcenia deszyfrującego Dk 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:
1. Powinno być obliczeniowo niemożliwe systematyczne określenie przekształcenia szyfrującego EK przy danym C nawet wówczas, gdy odpowiadająca mu jawna treść M jest znana
2. Powinno być obliczeniowo niemożliwe, aby w sposób systematyczny doprowadzić do ustalenia takiej zaszyfrowanej treści C’, aby DK(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 = Dd( h (m) )
• wysłanie podpisanej wiadomości ( m, s ).
Procedura weryfikacji podpisu:
Funkcja weryfikująca:
prawda , jeżeli Ee ( s ) = h (m)
VA( 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);
SA - przekształcenie ze zbioru M na zbiór S
( przekształcenie podpisujące dla podmiotu A -
utrzymywane w tajemnicy przez podmiot A);
VA - 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 SA jest znanym algorytmem zależnym od utrzymywanego w sekrecie klucza kA.
Przekształcenia SA i VA 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 = SA( 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ą VA ;
• oblicza wartość u = VA( 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 ⇔
⇔ VA( m, s ) = prawda
• obliczeniowo niewykonalne jest wyznaczenie dla dowolnej wiadomości m ∈ M przez podmiot inny niż A
takiej wartości s , że:
VA( 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 { Ee : e ∈ K } będzie zbiorem przekształceń szyfrujących, zaś { Dd : d ∈ K } odpowiadającym mu zbiorem przekształceń deszyfrujących.
Jeżeli dla dowolnej pary ( Ee , Dd ), mimo znajomości Ee , jest obliczeniowo niewykonalne wyznaczenie dla dowolnego losowego kryptogramu c ∈ C takiej wiadomości jawnej m ∈ M , że:
Ee ( 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 Ee będzie przekształceniem szyfrującym, Dd - odpowiadającym mu przekształceniem deszyfrującym oraz niech przekształcenia te będą endomorficzne ( C = M ) :
∀ m ∈ M : Dd ( Ee ( m )) = Ee ( Dd( 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 SA = Dd .
• obliczenie podpisu: s = Dd( m )
• wysłanie podpisanej wiadomości ( m, s ).
Procedura weryfikacji podpisu:
Funkcja weryfikująca:
prawda , jeżeli Ee ( s ) = m
{
fałsz w przypadku przeciwnym
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 AM (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 = Dd( m )
• wysłanie podpisu s.
Procedura weryfikacji podpisu:
Funkcja weryfikująca:
prawda , jeżeli Ee ( s ) ∈ M’
V
{
A( 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 = Ee( 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:
Li=Ri-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
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) = gk(mod p )
b (podpis) liczba taka, że M=xa +kb (mod p-1)
Weryfikacja:
Akceptacja podpisu, jeżeli yaab (mod p) = gM (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,gra (mod n)
2. B wybiera liczbę los. rb i oblicza
K=gra x rb (mod n)
Generuje ciąg losowy Rb, a następnie oblicza i przesyła do A
P(grb (mod n)), K(Rb)
3. A deszyfruje pierwszą połowę wiadomości B w celu uzyskania grb (mod n). Następnie oblicza K i stosuje do odszyfrowania Rb. Wytwarza inny ciąg losowy Ra, szyfruje oba ciągi za pomocą K i przesyła wynik B.
K(Ra,Rb)
4. B deszyfruje wiadomość w celu uzyskania Ra i Rb. Jeżeli ciąg Rb, który otrzymał od A, jest taki sam jak ten, który wysłał A w kroku 2, to szyfruje Ra, przy użyciu klucza K i przesyła do A .
K(Ra)
5. A deszyfruje wiadomość w celu uzyskania Ra. Jeżeli ciąg jest ten sam, jak ten który wysłała do B w kroku 3, to protokół jest ukończony. Obie strony komunikują się teraz za pomocą K jako klucza sesyjnego.