Transakcje finansowe przy użyciu elektronicznej gotówki

19.01.2011 - Sebastian Bala, Tomasz Wasilczyk
TrudnośćTrudnośćTrudność

W pierwszej połowie lat dziewięćdziesiątych ubie­głego wieku firma Digi­cash opracowała techno­logie kryptograficzne umo­żliwiające realizację pie­niądza cyfrowego. Nowe protokoły miały umo­żliwić bezpieczne transakcje fi­nansowe w sie­ci. Atrakcyjność elektronicznej gotówki miała polegać na anonimowości operacji kupna przy użyciu takich pieniędzy. Wcześniej, jedy­ną formą płatności, która nie ujawniała tożsamości kupującego były tran­sakcje gotówkowe. Główna różnica pomiędzy pieniądzem cyfrowym i banknotami papierowymi miała polegać tylko na tym, że aby obracać gotówką cyfrową niezbędne jest posiadanie konta w banku. W roku dwutysięcznym specjaliści związani z instytucjami pieniądza elektronicznego wyrażali przekonanie, że w roku 2010 transakcje pieniądzem elektronicznym będą nie mniej powszechne niż gotówkowe. Zapowiedzi jeszcze się nie sprawdziły. Pieniądz cyfrowy nie jest dzisiaj powszechny. W tym artykule przedstawimy prosty protokół do realizacji transakcji przy użyciu gotówki cyfrowej. Wyjaśnimy jak działają narzędzia kryptograficzne, których użyto w proto­kole.

Zobowiązanie bitowe

Przypuśćmy, że w leniwej czteroosobowej ro­dzince nikt nie chce wynieść śmieci. Jednym ze sposo­bów wyznaczenia osoby, która prze­spaceruje się tym razem do śmietnika, jest gra w ma­rynarza.

Scenariusz gry zazwyczaj wygląda tak. Ustawiamy osoby w pewnym porządku. Niech porzą­dkiem bę­dzie mama, tato, Kasia, Jacek. Wszyscy jednocześnie wystawiają dłonie pokazując pewną ilość pal­ców. Załóżmy, że liczba palców wystawionych przez każdą z osób wynosi 0, 1, 2 lub 3. Wystawione palce wszystkich czterech dłoni są sumowane. Następnie wykonywana jest standardowa odliczanka: mama, tato, Kasia, Jacek, mama, tato, Kasia... Odliczamy tyle razy, ile wyniosła suma wystawionych palców. Osoba na której skończono wyliczanie idzie wynieść śmieci.

Wyobraźmy jednak sobie, że szybkooki Jacek jest nie tylko spostrzegawczy, ale i potrafi błyska­wicznie liczyć. Przy założeniu, że reszta rodziny gra uczciwie i na sygnał start wyciąga zza pleców ręce z ustalo­ną liczbą palców, Jacek mógłby pokazać swoje palce nieco później – przeliczywszy palce pozostałych uczesników. Wtedy, jeśli reszta wyciągnęła w sumie 4 palce, on pokaże 1, 2 lub 3 i nie pójdzie wynieść śmieci. Cały problem tkwi w jednoczesności.

Problem jednoczesności można rozwiązać wymyślając taki protokół postępowania, w którym:

  1. w chwili $ t_0 $ każdy z uczestników gry ustali swoją liczbę, nie mając żadnych informacji o liczbach ustalanych przez pozostałych uczestników,
  2. w dowolnej chwili $ t_1 $, późniejszej od $ t_0 $, dokonuje się sprawdzenia liczb w taki sposób, aby ża­den z uczestników nie mógł zmienić swej decyzji podjętej w chwili $ t_0 $.

Powyższe warunki nazwijmy własnościami jednoczesności. Niedoskonały protokół może posiadać wady powodujące, że zmiana decyzji podjętej w chwili $ t_0 $ bę­dzie możliwa później.

Przykładem może być historia, która zdarzyła się pierwszemu autorowi. Otóż, dawno dawno te­mu, w cza­sach gdy panele LCD nie były na kieszeń zwykłego użytkownika, DYREKCJA postano­wiła kupić nowe monitory. Między dwoma pracownikami wywiązał się spór, gdyż oświadczono, że zakupiono dla nich dwa monitory – jeden 19 calowy i jeden 17 calowy – bez przypisania do osób. Poproszono ich o ustalenie między sobą, który monitor będzie należeć do kogo. Po dłu­giej dyskusji, nie mogąc dojść do porozumienia, postanowili podczas obiadu ustalić protokół wylosowania osoby, której miał przy­paść większy monitor. Protokół był taki:

  1. teraz ustalamy, który z nas jest "parzystą osobą", a który "nieparzystą",
  2. jutro każdy z nas zapisze na kartce wylosowaną liczbę, z przedziału od 1 do 100,
  3. spotkamy się jutro w południe ze złożonymi kartkami, tak aby nie było widać, co jest na nich na­pisane, dodatkowo zatrudnimy świadka, który będzie oserwatorem, czy wszystko zaszło prawi­dłowo,
  4. wymienimy się kartkami przy świadku,
  5. dodamy zapisane liczby, jeśli suma będzie parzysta, wtedy wygrywa "osoba parzysta", a w prze­ciwnym przypadku "nieparzysta".

Następnego dnia w południo doszło do wymiany kartek przy świadku. Jedna z osób patrzących na to co otrzymała powiedziała "nie! Grasz nie fair!"

Procedura mogła być prostsza, np. zamiast "osoby parzystej" można było ustalić "osobę orła" i rzucić monetą, ale protokół wymyślany był z dużym dystansem do całej sprawy, gdyż obie stro­ny miały dosyć absurdalnego sporu. Stąd taka skomplikowana procedura. Niestety tylko jedna z osób zauważyła, że protokół ma lukę i postanowiła to wykorzystać.

Zobaczmy co było na kontrowersyjnej kartce:

Zobowiązanie bitowe w kryptografii określane jest jako proces ustalenia pomiędzy dwoma stro­nami, Alicją i Bobem, jednego bitu lub ciągu bitów, w taki sposób, aby wymienione wyżej włas­ności jednoczesności były spełnione. Proces taki może być zobrazowany następującym scenariuszem: Alicja losuje bit lub ciąg bitów, umieszcza go na kartce w sejfie (trudnym do otwarcia bez klu­cza). Zamyka sejf na klucz, którego jedyny egzemplarz posiada wyłącznie ona. Wysyła sejf do Boba. Bob przechowuje sejf do momentu o którym mowa w b). Wtedy Alicja i Bob spotykają się, aby zajrzeć do sejfu. Bob posiada sejf z zawartością, a Alicja klucz, więc nie może być mowy o zmianie decyzji podjętej przez Alicję w czasie pomiędzy zamknięciem a otwarciem sejfu.

Zobowiązania bitowe realizowane są w świecie cyfrowym, zatem nie może być mowy o przesy­łaniu ciężkiego sejfu światłowodami. W praktyce, zobowiązanie najłatwiej zaimplementować przy użyciu funkcji haszujących. Argumentami funkcji haszujących są ciągi bitów. Dla uproszcze­nia będziemy zakładać, że długość argumentów jest ustalona (choć w praktyce jest inaczej). Wartościami są również ciągi bitów ustalonej długości, ale krótsze od tych używanych jako ar­gumenty. Załóżmy, że $ h $ jest odwzorowaniem między ciągami 128 bitowymi i 64 bitowymi, co za­pisujemy $ h:\{0,1\}^{128} \mapsto \{0,1\}^{64} $. Funkcje haszujące posiadają tę własność, że w praktyce nie jest możliwe obliczenie argumentu $ x $, znając wartość funkcji haszującej $ h(x) $ (nazwijmy to nieodwracalnością), oraz trudno jest znaleźć $ y $, taki że $ h(x)=h(y) $ (nazwijmy to odpornością na kolizje).

Wchodząc w szczegóły, zobowiązanie bitowe odbywa się w taki sposób: Alicja i Bob mają do­stęp do algorytmu obliczającego $ h $. Alicja losuje 64 bitowy ciąg $ Z $, oraz ustala 64 bitowe zobo­wiązanie $ X $. Oblicza $ h(XZ) $. Wynik wysyła do Boba. Podczas sprawdzenia zobowiązania, Ali­cja przesyła Bobowi parę $ (X,Z) $, a Bob oblicza $ h(XZ) $ sprawdzając czy Alicja nie oszukuje. Ciąg $ X $ jest zobowiązaniem, natomiast $ Z $ jest losowym ciągiem. $ Z $ ma znaczenie gdy Alicja miałaby tworzyć zobowiązania dla Boba wielokrotnie. Ustalenie zobowiązania $ X $ po raz drugi bez dodatkowego czynnika losowego, powoduje, że Bob ma dodatkową wiedzę o równości zobowiązań Alicji. Inaczej mówiąc, bez użycia ciągu $ Z $, Bob wiedziałby, które sejfy przesłane przez Alicję mają taką samą zawartość.

W dalszej części, dla uproszczenia pominiemy składnik $ Z $. Zobowiązanie bitowe będzie realizo­wane poprzez aplikację funkcji haszującej do zobowiązania $ X $.

5
Twoja ocena: Brak Ocena: 5 (2 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com