Strona główna

Jest to szereg kroków, obejmujących dwie lub więcej stron, podejmowanych w celu realizacji zadania. Jest to inaczej mówiąc sekwencja działań, każde z nich musi być kolejno wykonane i żadne nie może być podjęte


Pobieranie 343.43 Kb.
Strona7/10
Data19.06.2016
Rozmiar343.43 Kb.
1   2   3   4   5   6   7   8   9   10

BEZPIECZNE OBLICZENIA Z UDZIAŁEM WIELU STRON




Użytkownik A zna liczbę całkowitą i, użytkownik B zna liczbę całkowitą j. Obydwaj użytkownicy chcą poznać czy i > j lub czy i

Zakładamy dalej, że liczby i i j są liczbami z przedziału (1,100). Użytkownik B posiada parę kluczy jawny/prywatny.
Opis protokołu:

  1. użytkownik A wybiera dużą liczbę losową x i szyfruje ją za pomocą klucza jawnego użytkownika B


c = EB(x) ;


  1. użytkownik A oblicza c – i i przesyła wynik użytkownikowi B;

  2. użytkownik B oblicza 100 następujących liczb:


yu = DB(c – i + u), dla 1  u  100;
użytkownik B wybiera liczbę pierwszą p nieco mniejszą niż x (orientacyjne dane o x dostaje od użytkownika A), następnie oblicza 100 następujących liczb:
zu = yu (mod p), dla 1  u  100
sprawdzając, czy dla wszystkich u  v
|zu – zv|  2
i czy dla wszystkich u
0 < zu < p – 1
Jeżeli nie jest to prawdą, użytkownik B wybiera inną liczbę pierwszą i próbuje ponownie;

  1. użytkownik B przesyła do A ciąg liczb w podanym porządku:


z1, z2, . . . , zj, zj+1 + 1, zj+2 + 1, . . . , z100 + 1, p


  1. użytkownik A sprawdza, czy i-ta liczba w podanym ciągu jest kongruentna do x mod p, jeżeli tak, to wnioskuje, że i  j, jeżeli nie to oznacza, że i > j;

  2. użytkownik A przekazuje swój wniosek użytkownikowi B.


Sprawdzenie w kroku 3) ma na celu zagwarantowanie, że żadna liczba nie pojawi się w ciągu utworzonym w kroku 4) dwukrotnie. Gdyby tak się stało, tzn. za = zb, to użytkownik A wie, że a  j < b.
W protokole tym pewną przewagę ma użytkownik A.
PRZYKŁAD
Stosowany jest system RSA z kluczem jawnym użytkownika B postaci 7 i kluczem tajnym 23, n = 55. Tajną liczbą i użytkownika A jest 4, tajną liczbą użytkownika B jest 2. Jako i i j brane były wartości z zakresu <1,4>.
Opis protokołu:

  1. użytkownik A wybiera x = 39 i c = EB(39) = 19;

  2. użytkownik A oblicza c – i = 19 – 4 = 15, przesyła wartość 15 użytkownikowi B;

  3. użytkownik B oblicza następujące cztery liczby:


y1 = DB(15 + 1) = 26,

y2 = DB(15 + 2) = 18,

y3 = DB(15 + 3) = 2,

y4 = DB(15 + 4) = 39;
wybiera on dużą liczbę p = 31 i oblicza:

z1 = 26 mod 31 = 26,

z2 = 18 mod 31 = 18,

z3 = 2 mod 31 = 2,

z4 = 39 mod 31 = 8;
po wykonaniu wszystkich sprawdzeń stwierdza, że ciąg jest w porządku;

  1. użytkownik B przesyła do A ciąg liczb w porządku jak poniżej:


26, 18, 2+1, 8+1, 31, czyli

26, 18, 3, 9, 31;


  1. użytkownik A sprawdza, czy czwarta liczba w ciągu liczb jest przystająca do x mod p, ponieważ 9 nie przystaje do 39 mod 31, więc i > j;

  2. użytkownik A przekazuje do B wniosek.

OBLICZENIA DLA DANYCH ZASZYFROWANYCH
Jest to grupa problemów polegających na tym, że zleca się osobie trzeciej obliczenia, a zarazem nie można ujawnić tej osobie argumentu obliczeń. Dla zlecających natomiast ważny jest wynik obliczeń na znanym tylko dla nich argumencie. Przykładem może być tu wyznaczanie logarytmu dyskretnego pewnej wartości x przez inne osoby, bez ujawnienia wartości x.
Założenia:

Ustalona i znana jest wszystkim wartość p oraz g, użytkownik A ma pewną liczbę x < p (wartość tajna).


Opis protokołu:

  1. użytkownik A wybiera liczbę losową r mniejszą niż p,

  2. Użytkownik A wykonuje obliczenia:

x’ = x gr mod p




  1. użytkownik A prosi użytkownika B o obliczenie wartości

ge’  x’ mod p




  1. użytkownik B oblicza e’ i przesyła wynik do użytkownika A,

  2. użytkownik A odtwarza e przez wyliczenie

e = e’ – r mod p-1.

ZOBOWIĄZANIA BITOWE
Problem w tym przypadku polega na tym, że musimy ustalić pewne wartości, których początkowo nie można ujawnić, natomiast druga strona musi mieć pewność, że tych wartości nie zmienimy w trakcie realizacji zadania wspólnego. Na koniec wartości te są ujawniane celem konfrontacji.
Założenia obiektów stanowiących zobowiązania bitowe:


    • użytkownik A może zobowiązać się co do postaci obiektów bitowych,




    • użytkownik A może otworzyć dowolny obiekt bitowy, co do postaci którego zobowiązała się wcześniej, nie może on jednak ujawnić obiektu bitowego, którego wartość dla użytkownika B wynosiła by jednocześnie zero i jeden,




    • użytkownik B nie może dowiedzieć się niczego o tym, w jaki sposób użytkownik A otwiera dowolny nie ujawniony obiekt bitowy, w stosunku do którego dokonał zobowiązania,




    • obiekty bitowe nie zawierają żadnej innej informacji niż ta, która określa wartość zobowiązania bitowego, same obiekty bitowe, jak i proces zobowiązywania się i otwierania obiektu nie są skorelowane z jakąkolwiek inną informacją, którą użytkownik A pragnąłby utrzymać w tajemnicy przed użytkownikiem B.

Zobowiązanie bitowe z zastosowaniem kryptografii symetrycznej


Założenia:

wykorzystany jest tu algorytm klucza symetrycznego.


Opis protokołu:

  1. użytkownik B generuje ciąg znaków R i wysyła go do użytkownika A,

  2. użytkownik A generuje wiadomość zawierającą przewidywany bit (lub grupę bitów) i ciąg losowy otrzymany od użytkownika B, szyfruje wszystko przy pomocy klucza K i przesyła wynik z powrotem do użytkownika B,

EK(R, b).

Użytkownik B nie zna klucza K, więc nie może odszyfrować wartości b. Gdy nadejdzie pora następuje wykonanie ujawnienia wartości b. W tym celu:


  1. użytkownik A przesyła do B klucz K,

  2. użytkownik B deszyfruje wiadomość i sprawdza czy wartość R jest taka jaką wysyłał, jeśli tak odczytuje wartość b.

Moc takiego rozwiązania tkwi w mocy algorytmu szyfrowania.


Zobowiązanie bitowe z zastosowaniem funkcji jednokierunkowych

Stosuje się tu ogólnej klasy funkcje jednokierunkowe.


Opis protokołu:

  1. użytkownik A generuje dwa ciągi losowe R1 i R2,

  2. użytkownik A tworzy wiadomość składającą się z jego ciągów losowych i bitu (bitów) b, który stanowi zobowiązanie,

  3. użytkownik A oblicza wartość skrótu wiadomości, a użytkownikowi B wysyła wynik i jeden z ciągów losowych,

H(R1, R2, b), R1.


Wartości te stanowią zobowiązanie użytkownika A, Użytkownik B nie może na podstawie skrótu i jednej wartości losowej odtworzyć wartości b. Dokończeniem protokołu powinny być następujące czynności:


  1. użytkownik A przesyła do użytkownika B pierwotną wiadomość:

R1, R2, b




  1. użytkownik B oblicza wartość skrótu wiadomości, porównuje ją z wcześniej uzyskaną, oraz porównuje R1 otrzymane wcześniej i obecnie, jeśli wartości te są zgodne, przyjmuje bity b.

Protokół ten wymaga tylko komunikacji jednokierunkowej od użytkownika A do B. Użytkownik B nie musi odpowiadać.


Zobowiązanie bitowe z zastosowaniem generatorów ciągów pseudolosowych
Opis protokołu:


  1. użytkownik B generuje ciąg znaków i wysyła go do użytkownika A,

  2. użytkownik A wytwarza losową wartość początkową dla generatora bitów pseudolosowych, następnie dla każdego bitu losowego ciągu użytkownika B wysyła on do B jedną z dwóch wiadomości:

    1. wartość wyjściową generatora, jeżeli wartość bitu użytkownika B wynosi zero, albo

    2. sumę modulo 2 wartości wyjściowej generatora i bitu użytkownika A, jeżeli wartość bitu użytkownika B wynosi jeden;

Gdy zajdzie potrzeba zakończenia i ujawnienia bitów użytkownika A, protokół kontynuowany jest w następujących krokach:




  1. użytkownik A przesyła do B wygenerowaną przez siebie losową wartość początkową,

  2. użytkownik B wykonuje krok (2) w celu potwierdzenia, że użytkownik A postępował uczciwie.

Założenia bezpieczeństwa systemu:



    • losowy ciąg użytkownika B musi być wystarczająco długi,

    • generator pseudolosowy jest nieprzewidywalny.

UCZCIWE RZUCANIE MONETĄ


Protokoły tego typu służą do ustalania (losowania) wartości niezależnej od intencji użytkowników protokołów. Mówimy tu o tzw. „rzucaniu monetą”, czyli pewnej modyfikacji lub uzupełnienia protokołów zobowiązania bitowego.
Cechy tego typu protokołów:

    • użytkownik A musi losować jakąś wartość („rzucać monetą”), zanim użytkownik B zacznie odgadywać jej wartość,

    • użytkownik A nie może mieć możliwości dokonania ponownego losowania po usłyszeniu orzeczenia użytkownika B,

    • użytkownik B nie może dowiedzieć się, co wylosował użytkownik A zanim podjął decyzję.

Rzucanie monetą z wykorzystaniem funkcji jednokierunkowej

Założenia:

użytkownicy wcześniej ustalili funkcję jednokierunkową.


Opis protokołu:

  1. użytkownik A wybiera losową liczbę x, oblicza y = f(x), gdzie f(x) jest funkcją jednokierunkową i przesyła wartość y do użytkownika B,

  2. użytkownik B odgaduje, czy x jest parzyste czy nieparzyste i przesyła swoje przypuszczenie do użytkownika A,

  3. jeśli przypuszczenie użytkownika B jest poprawne, to wynikiem jest „reszka”, jeżeli nieprawdziwe, to „orzeł”, użytkownik A przesyła rezultat do użytkownika B,

  4. użytkownik B potwierdza, że y = f(x).

Bezpieczeństwo zależy od wyboru funkcji f(x), jeżeli użytkownik A może wyznaczyć takie x i x’, że f(x) = f(x’) oraz x jest parzyste, natomiast x’ nieparzyste, to użytkownik A może oszukiwać.


Rzucanie monetą z wykorzystaniem kryptografii z kluczem jawnym.
Protokół ten jest poprawny zarówno z użyciem kryptografii z kluczem jawnym, jaki i symetrycznej, pod warunkiem, aby algorytm był przemienny. To znaczy:

W ogólności nie jest to spełnione dla algorytmów symetrycznych, jednak niektóre algorytmy klucza publicznego cechę tę posiadają np. RSA.
Opis protokołu:

  1. użytkownicy A i B niezależnie tworzą dla siebie pary kluczy jawny/prywatny (lub przemienne klucze tajne),

  2. użytkownik A generuje dwie wiadomości: w jednej wynikiem rzutu monetą jest reszka, a w drugiej – orzeł, wiadomości te powinny zawierać pewien niepowtarzalny ciąg losowy, tak że później będzie można sprawdzić ich autentyczność, użytkownik A szyfruje obie wiadomości za pomocą swojego klucza prywatnego i wysyła je użytkownikowi B,

EA(M1), EA(M2),




  1. użytkownik B, który nie może odczytać żadnej wiadomości, wybiera losowo jedną z nich, szyfruje ją za pomocą swego klucza i odsyła z powrotem do użytkownika A,

EB(EA(M)),




  1. użytkownik A, nie mogąc odczytać wiadomości do niego przysłanej, deszyfruje ją za pomocą swojego klucza jawnego i wysyła z powrotem do użytkownika B:

DB(EB(EA(M1))) = EB(M1) lub DB(EB(EA(M2))) = EB(M2)




  1. użytkownik B deszyfruje wiadomość za pomocą swojego klucza jawnego, celem ujawnienia wyniku rzutu monetą, przesyła odszyfrowaną wiadomość użytkownikowi A,

DB(EB(M1) = M1 lub DB(EB(M2) = M2




  1. użytkownik A odczytuje wynik rzutu monetą i sprawdza, czy ciąg jest poprawny,

  2. użytkownicy ujawniają swoje klucze celem sprawdzenia czy druga strona nie oszukiwała.

Protokół ten zaliczamy do protokołów samowymuszających.


Rzucanie monetą przy zastosowaniu pierwiastków kwadratowych
Opis protokołu:

  1. użytkownik A wybiera dwie duże liczby pierwsze p i q i oblicza ich iloczyn

n = p q

przesyłając jego wynik do użytkownika B,



  1. użytkownik B wybiera losową liczbę całkowitą r taką, że r jest mniejsze lub równe n/2, oblicza

z = r2 mod n

i przesyła wartość z do użytkownika A,



  1. użytkownik A oblicza cztery pierwiastki kwadratowe z (mod n), gdyż zna rozkład liczby n, pierwiastki te oznaczamy +x, -x, +y, -y, oznaczamy x’ mniejszą z tych dwóch liczb:

x mod n ,

-x mod n ,

podobnie y’ oznaczmy mniejszą z nich

y mod n,


-y mod n,

należy zauważyć, że r jest równe albo x’, albo y’,



  1. użytkownik A zgaduje, czy r = x’ lub r = y’, przesyła użytkownikowi B jeden bit swojego przypuszczenia (najmniej znaczącego bitu na pozycji którego te dwie liczby różnią się i przesyła od użytkownika B wiadomość: „ i-ty bit twojej liczby r ma wartość 0” lub „ i-ty bit twojej liczby r ma wartość 1”,

  2. jeżeli przypuszczenie użytkownika A jest poprawne, to wynikiem rzutu monetą jest reszka, jeśli nie to wynikiem jest orzeł, użytkownik B obwieszcza wynik rzutu monetą.

Celem sprawdzenia czy któraś ze stron nie oszukiwała na koniec wykonywane są kroki:



  1. użytkownik B przesyła r do A,

  2. użytkownik A przesyła do B wartości p i q.

Bezpieczeństwo protokołu opiera się na trudności faktoryzacji dużej liczby złożonej.

Rzut monetą przy zastosowaniu potęgowania modulo p


Opis protokołu:

  1. użytkownicy A i B wspólnie wybierają liczbę pierwszą p w taki sposób, że jest znany rozkład liczby p-1 na czynniki,

  2. użytkownik B wybiera dwa elementy pierwotne h i t z GF(p), przesyła je użytkownikowi A,

  3. użytkownik A wybiera losową liczbę całkowitą x względnie pierwszą z p-1, oblicza jedną z dwóch wartości:

y = hx (mod p) lub y = tx (mod p)


i przesyła ją użytkownikowi B,

  1. użytkownik B odgaduje, czy y jest funkcją h lub t, i przesyła swoje przypuszczenie użytkownikowi A,

  2. jeżeli przypuszczenie użytkownika B jest poprawne, to wynikiem rzutu monetą jest reszka, natomiast gdy nie – orzeł, użytkownik A ogłasza wynik rzutu.

Uzupełnienie sprawdzające protokół obejmuje krok:




  1. użytkownik A ujawnia x użytkownikowi B, użytkownik B oblicza hx mod p i tx mod p dla potwierdzenia uczciwości działań użytkownika A.

Bezpieczeństwo protokołu opiera się na trudności obliczania logarytmu dyskretnego, gdyż użytkownik A mógł oszukiwać, musi z znaleźć takie liczby x i x’, że hx  tx’ mod p, czyli musi wyznaczyć przy danym x wartość x’, czyli:


logt hx (mod p).
Rzut monetą przy zastosowaniu liczb całkowitych Bluma
Liczby całkowite Bluma – liczby złożone, będące iloczynem liczb pierwszych p i q takich, że:

p 3 mod 4

q 3 mod 4.

Jeżeli n jest liczbą Bluma, to każda reszta kwadratowa (modulo n) ma dokładnie cztery pierwiastki kwadratowe. Jeden z tych pierwiastków jest także kwadratem, jest to pierwiastek kwadratowy główny.

Na przykład mamy liczby p = 19, q = 23, stąd n = 19 x 23 = 437. Głównym pierwiastkiem kwadratowym liczby 139 mod 437 jest 24, natomiast pozostałe trzy pierwiastki kwadratowe to: 185, 252, 413.

Opis protokołu:




  1. użytkownik A generuje liczbę całkowitą Bluma n, losowe x względnie pierwsze z n x0 = x2 mod n i x1 = x02 mod n, przesyła n i x1 do użytkownika B,

  2. użytkownik B odgaduje, czy x0 jest parzyste, czy nieparzyste,

  3. użytkownik A przesyła do B x i x0,

  4. użytkownik B sprawdza, czy n jest liczbą całkowitą Bluma (użytkownik A powinien przekazać do B czynniki liczby n lub zrealizować protokół o wiedzy zerowej w celu przekonania go, że jest rzeczywiście liczbą całkowitą Bluma) i czy x0 = x2 mod n oraz x1 = x02 mod n, jeżeli wszystko się zgadza, to użytkownik B wygrywa.

W przypadku gdy n nie jest liczbą całkowitą Bluma, to użytkownik A może znaleźć takie x’, że x0 x2 mod n = x’2 mod n, kiedy x’ mod n jest także resztą kwadratową. Jeżeli x jest parzyste natomiast x’ nieparzyste (lub odwrotnie), to użytkownik A może oszukiwać.

UCZCIWE SYSTEMY KRYPTOGRAFICZNE
Systemy, w których klucz prywatny użytkownika jest dzielony na części i rozdysponowany różnym instytucjom. Podział klucza wykonuje się z wykorzystaniem protokołów dzielenia wiadomości. Dodatkową cechą jest tu możliwość sprawdzania indywidualnego poszczególnych części. Odtworzenie klucza możliwe jest po zebraniu wszystkich części.
Opis protokołu:


  1. użytkownik A wytwarza parę kluczy: klucz prywatny/ klucz jawny, klucz prywatny dzieli na kilka części jawnych i prywatnych,

  2. użytkownik A przesyła po jednej części jawnej i odpowiadającej jej części prywatnej obie w formie zaszyfrowanej każdemu z zaufanych powierników, natomiast klucz jawny umieszcza w KDC,

  3. powiernicy indywidualnie wykonują obliczenia w ramach tych danych, które otrzymali celem sprawdzenia ich poprawności, każdy z nich przesyła część jawną do KDC, natomiast część prywatną ukrywa,

  4. KDC sprawdza części jawne uzyskane od powierników z wykorzystaniem klucza jawnego otrzymanego od użytkownika A, w przypadku poprawności uzyskanych wyników podpisuje klucz jawny i umieszcza go w swojej bazie danych lub podpisany odsyła do użytkownika A.


Uczciwy system Diffiego-Hellmana
Warunki początkowe:

Grupa użytkowników współdzieli liczbę pierwszą p i generator g. Kluczem prywatnym użytkownika A jest s, a kluczem jawnym



t = gs mod p.
Przekształcenie do uczciwego systemu D-H:

  1. użytkownik A wybiera pięć liczb całkowitych s1, s2, s3, s4 i s5, każda z nich mniejsza niż p; kluczem prywatnym użytkownika A jest:


S = (s1 + s2 + s3 + s4 + s5) mod p,
a kluczem jawnym jest

T = gs mod p,
użytkownik A oblicza także:
ti = gsi (mod p) dla i = 1, 2, . . . , 5;
częściami klucza jawnego użytkownika A są ti, a częściami jej klucza prywatnego są si;

  1. użytkownik A przesyłą części prywatne i odpowiadające im części jawne do każdego powiernika, natomiast T przesyła do KDC;

  2. każdy powiernik sprawdza, czy

ti = gsi mod p,
w przypadku zgodności, podpisuje ti i przesyła do KDC, a si przechowuje w bezpiecznym miejscu;

  1. KDC po otrzymaniu wszystkich pięciu części ti sprawdza, czy

T = (t1 x t2 x t3 x t4 x t5) mod p,
jeśli wynik jest zgodny, to klucz jawny użytkownika A jest zaakceptowany.
UJAWNIANIE TAJEMNIC TYPU „WSZYSTKO ALBO NIC” (ANDOS)
Protokoły tego typu wymagają co najmniej dwóch stron, przy czym jedna – dystrybutor tajemnicy - nazywana jest sprzedawcą, natomiast druga – osoba zainteresowana uzyskaniem informacji - nazywana jest kupującym.
Założenia wstępne:

Użytkownik A jest dystrybutorem informacji, użytkownicy B i C odbierającymi. Tajemnicami są S1, S2, . . . , Sk, użytkownik B chce poznać tajemnicę Sb, natomiast użytkownik C tajemnicę Sc.


Opis protokołu:

  1. użytkownik A wytwarza dwie pary kluczy prywatny/jawny i przekazuje użytkownikowi B (i tylko B) klucz jawny z pierwszej pary, natomiast użytkownikowi C (i tylko C) klucz jawny z drugiej pary,

  2. użytkownik B wytwarza k liczb n-bitowych B1 , B2, . . . , Bk i przekazuje je do użytkownika C, użytkownik wytwarza swoje k liczb n-bitowych C1 , C2, . . . , Ck i przekazuje je do użytkownika B,

  3. użytkownik B szyfruje Cb za pomocą klucza jawnego otrzymanego od użytkownika A, oblicza indeks zgodności bitowej IZB dla Cb i otrzymanego wyniku, przesyła IZB do użytkownika C, użytkownik C szyfruje Bc za pomocą klucza jawnego użytkownika A, oblicza IZB wartości Bc i otrzymanego wyniku i przesyła go do użytkownika B;

  4. użytkownik B pobiera każdą z n-bitowych liczb B1 , B2, . . . , Bk i zastępuje każdy bit, którego numer nie znajduje się w IZB otrzymanym od użytkownika C jego uzupełnieniem, przesyła tak otrzymaną listę liczb n-bitowych B1’ , B2’, . . . , Bk do użytkownika A, użytkownik C robi to samo ze swoimi liczbami i IZB uzyskanym od użytkownika B, przesyłając do A C1’ , C2’, . . . , Ck;




  1. użytkownik A deszyfruje wszystkie Ci przy użyciu klucza prywatnego stowarzyszonego z kluczem jawnym przekazanym do B i otrzymuje k liczb n-bitowych: C1”, C2”, . . . , Ck, oblicza sumę modulo 2 liczb Si i Ci, dla i = 1, . . . , k, i przesyła wyniki użytkownikowi B, następnie użytkownik A deszyfruje wszystkie Bi przy użyciu klucza prywatnego stowarzyszonego z kluczem jawnym przekazanym do C i otrzymuje k liczb n-bitowych: B1”, B2”, . . . , Bk, oblicza sumę modulo 2 liczb Si i Bi, dla i = 1, . . . , k, i przesyła wyniki użytkownikowi C,

  2. użytkownik B oblicza Sb przez zsumowanie modulo 2 Cb i b-tej liczby otrzymanej od użytkownika A, natomiast użytkownik C oblicza Sc przez zsumowanie modulo 2 Bc i c-tej liczby otrzymanej od użytkownika A.


PRZYKŁAD
Użytkownik A ma na sprzedaż osiem następujących 12-bitowych tajemnic: S1 = 1990, S2 = 471, S3 = 3860, S4 = 1487, S5 = 2235, S6 = 3751, S7 = 2546, S8 = 4043. Użytkownik B chce uzyskać informację S7, a użytkownik C – S2. Użytkownik A wykorzystuje system RSA.
Realizacja protokołu:

  1. użytkownik A generuje parę kluczy do komunikacji z użytkownikiem B n = 7387, e = 5145 i d = 777, natomiast do C n = 2747, e = 1421 i d = 2261, do użytkowników B i C przesyła klucze jawne;

  2. użytkownik B wytwarza osiem 12-bitowych liczb losowych: B1 = 743, B2 = 1988, B3 = 4001, B4 = 2942, B5 = 3421, B6 = 2210, B7 = 2306, B8 = 222 i przekazuje je do C, użytkownik C generuje swoje liczby losowe postaci C1 = 1708, C2 = 711, C3 = 1969, C4 = 3112, C5 = 4014, C6 = 2308, C7 = 2212, C8 = 222 i przekazuje je do B;



  1. użytkownik B pragnąc poznać S7, szyfruje C7 za pomocą klucza jawnego otrzymanego od użytkownika A

22125145 (mod 7478) = 5928

IZB:

2210 = 0100010100100



5928 = 1011100101000
stąd IZBb = {0, 1, 4, 5, 6}, użytkownik B przekazuje do C wartość IZBb; użytkownik C chce poznać S2, szyfruje więc B2 za pomocą klucza otrzymanego od użytkownika A i oblicza IZBc dla B2 i wyniku szyfrowania otrzymując IZBb = {0, 1, 2, 6, 9, 10} i przesyła ją do użytkownika B;

  1. użytkownik B zastępuje w wartościach B1, B2, . . . , B8 każdy bit, którego indeks nie jest w zbiorze {0, 1, 2, 6, 9, 10}, jego uzupełnieniem według przykładu:


B2 = 111111000100 = 1988

B2= 011001111100 = 1660
przesyła B1’, B2’, . . . , B8 do użytkownika A;

użytkownik C zastępuje w wartościach C1, C2, . . . , C8 każdy bit, którego indeks nie jest w zbiorze {0, 1, 4, 5, 6}, jego uzupełnieniem według przykładu:


C2 = 0100010100100 = 2212

C2’= 1011100101000 = 5928


przesyła C1’, C2’, . . . , C8 do użytkownika A;

  1. użytkownik A deszyfruje wszystkie wartości Ci za pomocą klucza prywatnego stowarzyszonego z kluczem jawnym użytkownika B i sumuje modulo 2 wynik z Si, np. dla i = 7

5928777 (mod 7387) = 2212

2546  2212 = 342,
przesyła wynik użytkownikowi B,

użytkownik A deszyfruje wszystkie wartości Bi’ za pomocą klucza prywatnego stowarzyszonego z kluczem jawnym użytkownika C i sumuje modulo 2 wynik z Si, np. dla i = 2


16602216 (mod 2747) = 1988

471  1988 = 1555,


przesyła wynik użytkownikowi C;

  1. użytkownik B oblicza S7 przez zsumowanie modulo 2 C7 i siódmej liczby otrzymanej od użytkownika A:

2212  342 = 2546,


użytkownik C oblicza S2 przez zsumowanie modulo 2 B2 i drugiej liczby otrzymanej od A:
1988  1555 = 471.

ŚLEPE PODPISY CYFROWE


Pojęcie wprowadzone przez Davida Chaum
Cechy podpisów


Podpis ręczny

Podpis cyfrowy

Ślepy podpis cyfrowy

Niepodrabialność

Niepodrabialność

Niepodrabialność

Autentyczność

Autentyczność

Autentyczność

Jest częścią integralną dokumentu, podpisu nie można ponownie użyć

Podpisu nie można ponownie użyć, może istnieć niezależnie

Podpisu nie można ponownie użyć, może istnieć niezależnie

Niezmienialność podpisanego dokumentu

Niezmienialność podpisanego dokumentu

Niezmienialność podpisanego dokumentu

Niezaprzeczalność

Niezaprzeczalność

Niezaprzeczalność

Podpisujący zna dokument

Podpisujący zna dokument

Podpisujący nie zna dokumentu

Jest taki sam dla wszystkich dokumentów

Jest różny dla różnych dokumentów

Jest różny dla różnych dokumentów

Występuje na ogół na ostatniej stronie dokumentu

Obejmuje cały dokument

Obejmuje cały dokument



Tradycyjny podpis cyfrowy – podpisujący wie co podpisuje.
Ślepy podpis cyfrowy – podpisujący nie wie co zawiera podpisywany dokument.

Całkowicie ślepe podpisy cyfrowe
Warunki wstępne:

użytkownik B jest osobą zaufaną – notariuszem świadczącym usługi potwierdzania faktu istnienia dokumentu; użytkownik A posiada dokument, do którego chce uzyskać podpis, jednak nie chce go ujawnić.
Opis protokołu:

  1. użytkownik A pobiera dokument i wymnaża go przez liczbę losową, ta liczba nazywa się czynnikiem zaciemniającym;

  2. użytkownik A przesyła zaciemniony dokument użytkownikowi B;

  3. użytkownik B podpisuje zaciemniony dokument;

  4. użytkownik A dzieli wynik przez czynnik zaciemniający, pozostawiając kopię oryginalnego dokumentu podpisanego przez użytkownika B.


Warunki działania protokołu:

funkcja podpisująca i funkcja mnożąca są przemienne
Warunki wystąpienia oszustwa:

  • użytkownik B nie może uzyskać informacji co do zawartości dokumentu;

  • użytkownik B nie może zaprzeczyć poprawności jego podpisu;

  • użytkownik A ma pewne możliwości oszustwa gdy znajdzie inną liczbę która pomnożona przez inny dokument da ten sam wynik.


Wada - brak możliwości pewnej kontroli przez użytkownika B nad tym co podpisuje.
Modyfikacja – użytkownik B może otrzymać zestaw dokumentów zaciemnionych i po skontrolowaniu losowo wybranych może podpisać ostatni z nich.

Opis protokołu po modyfikacji:




  1. użytkownik A przygotowuje np. dziesięć dokumentów do podpisu;




  1. zaciemnia każdy z nich za pomocą odmiennych elementów zaciemniających;




  1. użytkownik A przesyła zaciemnione dokumenty do użytkownika B;




  1. użytkownik B wybiera losowo kilka dokumentów i żąda podania do nich elementów zaciemniających;




  1. użytkownik A przesyła odpowiednie elementy zaciemniając;




  1. użytkownik B usuwa zaciemnienie z wybranych dokumentów i sprawdza ich poprawność;




  1. użytkownik B podpisuje wybrany przez siebie z puli nie skontrolowanej dokument i przesyła do użytkownika A;




  1. użytkownik A usuwa zaciemnienie i uzyskuje podpisany dokument.



Zalety w stosunku do poprzedniego rozwiązania:

użytkownik A musi przewidzieć co wybierze użytkownik B.
Wykorzystanie RSA do realizacji ślepych podpisów cyfrowych
Zasady ogólne:

Użytkownik B posiada klucz jawny e, klucz prywatny d i moduł jawny n. Użytkownik A chce by użytkownik B podpisał na ślepo wiadomość m.
Opis protokołu:


  1. użytkownik A wybiera losowo k z przedziału między 1 a n;




  1. zaciemnia m obliczając:


t m ke (mod n)
wynik przesyła do użytkownika B;


  1. użytkownik B podpisuje t:


td (m ke)d (mod n)
wynik przesyła do użytkownika A;


  1. użytkownik A usuwa zaciemnienie td poprzez obliczenie:


s td/k (mod n) (md k)/k (mod n) md (mod n).

Rozbudowana wersja
Podpisujący posiada kilka kluczy jawnych e1, e2, . . . , ei oraz odpowiadających im kluczy prywatnych d1, d2, . . . , di. Osoba oczekująca podpisania przez osobę podpisującą partycypuje w wyborze jakim kluczem posłuży się podpisujący jednak ostatecznie podpisujący tego dokonuje.
Opis protokołu:

  1. użytkownik A wybiera losowo r z przedziału między 1 a n;




  1. zaciemnia m obliczając:


t m re1e2 (mod n)
wynik przesyła do użytkownika B;


  1. użytkownik B podpisuje t stosując d1 lub d2:


td1 (m re1e2)d1 (mod n)

lub

td2 (m re1e2)d2 (mod n)
wynik przesyła do użytkownika A;


  1. użytkownik A usuwa zaciemnienie td1 lub td2 poprzez obliczenie:


m’1 (mre1e2)d1r-e2 (mod n)

lub

m’2 (mre1e2)d2r-e1 (mod n).
Systemy bazujące na generatorach grupy multiplikatywnej
Generatory grupy multiplikatywnej dla danego n są jawne. Użytkownik A celem zaciemnienia wybiera losowo k z zakresu między 1 a n2.
Opis protokołu:

  1. użytkownik A wybiera generator g i wykonuje działanie zaciemniania:


t m gk (mod n)
wynik wysyła do użytkownika B (podpisującego);


  1. użytkownik B podpisuje wykonując działanie:


t’ (m gk)di (mod n)
wynik przesyła do użytkownika A;


  1. użytkownik A odsłania dokument wykonując działanie:


m [(mgk)di]g-dik (mod n).

Drugie rozwiązanie:


  1. użytkownik A wybiera generator g, liczby k1, k2 i wykonuje działanie zaciemniania:


t m gk1k2 (mod n)
wynik wysyła do użytkownika B (podpisującego);


  1. użytkownik B podpisuje wykonując działanie:


t’ (m gk1k2)di (mod n)
wynik przesyła do użytkownika A;


  1. użytkownik A odsłania dokument wykonując działanie:


m [(mgk1k2)di]g-dik1k2 (mod n).

Warunek: k1 wybierane jak poprzednio, k2 może przybierać wartości 1 lub n-1.
Trzecie rozwiązanie:

Bazuje na następujących kongruencjach:
t m g1k1 g2k2 . . . grkr (mod n)
t’ (m g1k1 g2k2 . . . grkr)di (mod n)
m’ [(m g1k1 g2k2 . . . grkr)di] g1-dik1 . . . gr-dikr (mod n).
Warunek: ki wybierane są jak k z pierwszej wersji.
Przykład zastosowania ślepych podpisów
Użytkownik A chce kupić jakiś towar korzystając z elektronicznej portmonetki, użytkownik B jest bankiem, użytkownik C jest sprzedawcą.

Pojedyncza transakcja kupna za pomocą elektronicznego pieniądza może wyglądać następująco:


  1. użytkownik A generuje wartość stanowiącą kwotę, którą chce wydać, tworzy n kopii zaciemniając każdą z nich w inny sposób (np. innym ciągiem losowym);

  2. wszystkie kopie wysyła do banku;

  3. bank losowo wybiera n-1 kopii i żąda podania ciągu zaciemniającego celem sprawdzenia zawartości;

  4. w przypadku poprawnych danych podpisuje n-tą kopię i obciąża kwotą odczytaną w pozostałych przekazach rachunek użytkownika A, podpis przesyła do użytkownika A;

  5. użytkownik A zdejmuje zaciemnienie;

  6. użytkownik A w dowolnym momencie zgłasza się do sprzedawcy celem wykonania zakupu, wręcza mu potwierdzony przez bank przekaz;

  7. sprzedawca sprawdza czy przekaz jest poprawny, sprawdza podpis i wysyła przekaz do banku;

  8. bank sprawdza poprawność podpisu i czy nie był przekaz wcześniej zrealizowany;

  9. wysyła potwierdzenie do sprzedawcy, że przekaz jest OK i dodaje sumę przekazu do konta sprzedawcy;

  10. sprzedawca wydaje towar użytkownikowi A.

CYFROWE PIENIĄDZE


Protokół naturalny dla anonimowych przekazów pieniężnych.
Opis protokołu:


  1. użytkownik A przygotowuje 100 anonimowych przekazów pieniężnych na kwotę 1000 zł;

  2. użytkownik A wkłada każdy przekaz wraz z kawałkiem kalki maszynowej do 100 odrębnych kopert, następnie przekazuje je wszystkie do banku;

  3. bank otwiera 99 kopert i stwierdza, że każda zawiera przekaz pieniężny na kwotę 100 zł;

  4. bank podpisuje jedną pozostałą nie otwartą kopertę, podpis przez kalkę odbija się na przekazie pieniężnym, bank wręcza kopertę z powrotem użytkownikowi A i odejmuje kwotę 100 zł z jego rachunku;

  5. użytkownik A otwiera kopertę i wydaje kwotę przekazu na zakupy;

  6. kupiec sprawdza podpis bankowy, aby upewnić się, że przekaz pieniężny jest ważny (właściwy);

  7. kupiec zabiera przekaz pieniężny do banku;

  8. bank sprawdza swój podpis i przelewa kwotę 100 zł na konto kupca.


Wada: użytkownik A może skopiować przekaz pieniężny i usiłować wykorzystać go w sąsiednim sklepie, stoisku w krótkim czasie.
Zmodyfikowany protokół przekazu pieniężnego
Opis protokołu:


  1. użytkownik A przygotowuje 100 anonimowych przekazów pieniężnych na kwotę 1000 zł, dołączając do każdego z nich unikalny ciąg losowy, odpowiednio długi by zminimalizować możliwość jego powtórzenia przez inną osobę;

  2. użytkownik A wkłada każdy przekaz wraz z kawałkiem kalki maszynowej do 100 odrębnych kopert, następnie przekazuje je wszystkie do banku;

  3. bank otwiera 99 kopert i stwierdza, że każda zawiera przekaz pieniężny na kwotę 100 zł, a dołączany do każdego przekazu ciąg losowy jest unikalny;

  4. bank podpisuje jedną pozostałą nie otwartą kopertę, podpis przez kalkę odbija się na przekazie pieniężnym, bank wręcza kopertę z powrotem użytkownikowi A i odejmuje kwotę 100 zł z jego rachunku;

  5. użytkownik A otwiera kopertę i wydaje kwotę przekazu na zakupy;

  6. kupiec sprawdza podpis bankowy, aby upewnić się, że przekaz pieniężny jest ważny (właściwy);

  7. kupiec zabiera przekaz pieniężny do banku;

  8. bank sprawdza swój podpis, sprawdza swoją bazę danych o przekazach zrealizowanych czy ten przekaz w niej nie figuruje, jeśli tam się nie znajduje, przelewa kwotę 100 zł na konto kupca i zapisuje unikalny ciąg losowy dołączony do przekazu do swojej bazy danych czeków zrealizowanych.


Wada: brak możliwości wskazania kto oszukuje w przypadku wystąpienia nadużycia.

Protokół przekazu pieniężnego z wykryciem kto oszukuje
Opis protokołu:


  1. użytkownik A przygotowuje 100 anonimowych przekazów pieniężnych na kwotę 100 zł, dołączając do każdego z nich unikalny ciąg losowy, odpowiednio długi by zminimalizować możliwość jego powtórzenia przez inną osobę;

  2. użytkownik A wkłada każdy przekaz wraz z kawałkiem kalki maszynowej do 100 odrębnych kopert, następnie przekazuje je wszystkie do banku;

  3. bank otwiera 99 kopert i stwierdza, że każda zawiera przekaz pieniężny na kwotę 100 zł, a dołączany do każdego przekazu ciąg losowy jest unikalny;

  4. bank podpisuje jedną pozostałą nie otwartą kopertę, podpis przez kalkę odbija się na przekazie pieniężnym, bank wręcza kopertę z powrotem użytkownikowi A i odejmuje kwotę 100 zł z jego rachunku;

  5. użytkownik A otwiera kopertę i wydaje kwotę przekazu na zakupy;

  6. kupiec sprawdza podpis bankowy, aby upewnić się, że przekaz pieniężny jest ważny (właściwy);

  7. kupiec prosi o napisanie ciągu identyfikacyjnego na przekazie pieniężnym;

  8. kupiec zabiera przekaz pieniężny do banku;

  9. bank sprawdza swój podpis, sprawdza swoją bazę danych o przekazach zrealizowanych czy ten przekaz w niej nie figuruje, jeśli tam się nie znajduje, przelewa kwotę 100 zł na konto kupca i zapisuje unikalny ciąg losowy dołączony do przekazu do swojej bazy danych czeków zrealizowanych;

  10. jeżeli ciąg losowy znajduje się już w bazie danych czeków zrealizowanych, to bank odmawia wykonania przelewu , następnie porównuje ciąg identyfikacyjny z przekazu pieniężnego z przechowywanym w bazie danych, jeżeli nie są zgodne, to bank wie o tym, że kupiec chciał oszukać, jeżeli są różne to oznacza, że oszukał kupujący.


Wady: możliwe próby oszustwa ze strony kupującego poprzez skopiowanie przekazu wraz kopią numeru identyfikacyjnego, wymagane jest by transakcja kupna kończyła się po zaakceptowaniu przekazu przez bank, co wydłuża czas zakupu,


1   2   3   4   5   6   7   8   9   10


©snauka.pl 2016
wyślij wiadomość