Czy mieliście kiedyś jakiś sekret? Ale taki naprawdę ważny, ciekawy sekret, którego nie mogliście nikomu zdradzić? Na pewno!
A czy udało się wam go nie rozpowiedzieć? To zawsze strasznie kusi, zwłaszcza, gdy słyszymy wszędzie dookoła “Wiesz coś o tym? To powiedz! Nie? To pewnie wcale nie wiesz!”.
W niniejszym artykule rozwiążemy między innymi problem tego, jak nie dać się sprowokować powyższymi zaczepkami, a przy tym udowodnić, że zna się sekret bez zdradzania go. Brzmi dobrze? W takim razie opowiem wam bajkę...
Dochodzi do wniosku, że z jaskinią musi być coś nie w porządku. Słusznie podejrzewając, że nie jest jedyną ofiarą złodziejskiej siatki, ukrywa się wśród pustych worków na samym końcu drugiego korytarza i czeka. Po kilku godzinach niewygody i bezowocnego czekania, dochodzi go wreszcie tupot biegnących stóp, zbliżających się do niego. Zastyga w bezruchu, oczekując odkrycia tajemnicy przestępczej szajki. Ma szczęście - ofiara goni złodzieja drugim korytarzem, dokładnie tym, w którym skrył się Ali-Baba oraz - chwilowo - przestępca z łupem. Niemal czując oddech pokrzywdzonego kupca na karku, złodziej szepcze magiczną formułę “Sezamie, otwórz się” i skały jaskini rozstępują się, ukazując jej prawdziwy kształt.
Opryszek znika w korytarzu jaskini, szepcząc na odchodne “Sezamie, zamknij się”, co skutkuje, jak można się było spodziewać, ponownym zwarciem ścian.
Ali-Baba odkrył, w jaki sposób złodziejom udawało się go ominąć przez czterdzieści dni. Ale było mu mało - chciał sprawić, żeby nikt nigdy więcej nie był okradany w ten sposób. Pracując dzień i noc zmienił magiczne słowa w podobny sposób, jak zmienia się je w niektórych zamkach szyfrowych. Następnego dnia udało się złapać złodzieja wraz z łupem i nikt więcej nie padł już ofiarą czterdziestu rozbójników.
Kupiec opisał całą swą przygodę w przepięknym manuskrypcie. Zawarł w nim także subtelne wskazówki na temat nowych “magicznych słów”.
Manuskrypt Ali-Baby został odnaleziony w średniowiecznych Włoszech. Rozszyfrowanie wskazówek w nim zawartych nie było łatwe, jednak po kilku wiekach niektórym uczonym udało się odkryć zdanie otwierające tajemne przejście.
Wiele ekip archeologów przez lata przeszukiwało targ w Bagdadzie w poszukiwaniu śladów przedziwnej jaskini. Stosunkowo niedawno udało się odnaleźć miejsce, przypominające do złudzenia opisywaną prze Ali-Babę jaskinię rozbójników.
Cały świat zainteresował się cudownym, pełnym magii miejscem mimo, że brakło dowodów na jej niezwykłość - nikt oficjalnie nie podał magicznych słów otwierających wrota, nie było więc możliwości sprawdzenia, czy rewelacje z manuskryptu są prawdziwe.
Uwaga prasy i telewizji była skupiona wokół jednego z badaczy - Micka Aliego, który ogłosił, że zna sekret jaskini. Jak jednak uwierzyć komuś, kto odmawia podania hasła?
Ali zaproponował pewnej bogatej stacji telewizyjnej wyłączność na materiał, w którym będzie on prezentował swoją znajomość magicznych słów.
Eksperyment-dowód przebiegał następująco:
W konkurencyjnej stacji telewizyjnej inny reporter próbował skontaktować się z Mickiem Ali. Niestety, archeolog przekazał już wyłączność prawa do transmisji, odmówił zatem prezentacji “sztuczki” osobom niezwiązanym ze stacją . Podał jednak pomysł, jak sfilmować odkrycie sekretu jaskini, nie znając go.
Reporter stacji długo zastanawiał się nad tym, co przekazał mu odkrywca. Wreszcie zrozumiał - sposób, w jaki Ali udowadniał, że zna sekret jaskini, może być powtórzony z podstawionym aktorem! Trzeba będzie nakręcić nieco więcej ujęć, bo aktor, nie znając sekretu, może wyjść ze złego wyjścia, ale da się to zrobić..
Dziennikarz zatrudnił więc aktora, którego ucharakteryzowano tak, by wyglądał jak archeolog-odkrywca tajemnicy jaskini. Następnie przeprowadził identyczną próbę, jak jego kolega po fachu ze stacji . Powtarzał ją tyle razy, żeby uzyskać sukcesów.
Z całą pewnością fałszywe nagranie nie udowadniało nic na temat wiedzy o sekrecie. Skoro było nierozróżnialne od prawdziwej taśmy, to także ona nie stanowiła dowodu - a jednak reporter, który ją nakręcił, był przekonany, że Mick Ali zna sekret jaskini.
Nie był on jednak w stanie - to kluczowe w tej sprawie! - przekonać o tym ani widowni, ani sędziów.
Obie sprawy sąd umorzył z braku dowodów, a archeolog osiągnął ostatecznie swój prawdziwy cel - przekonał reportera stacji o swojej prawdomówności, ale w taki sposób, że ten nie był w stanie przekonać nikogo innego, że Ali zna sekret. Tajemnica pozostała bezpieczna!
Mick Ali nauczył nas, jak pokazywać, że się coś potrafi, bez ujawniania metody. Zastanówmy się przez chwilę, czy prezentowany przez niego sposób da się uogólnić lub przyspieszyć - w końcu przedstawienie czterdziestu prób-dowodów to zabieg nader czasochłonny.
Izraelscy badacze wpadli na ciekawy pomysł. Wyobraźmy sobie, że zamiast jednej jaskini mamy wielopiętrowy budynek, w którym na każdym poziomie znajduje się jaskinia. Zamiast jednego badacza, mamy ich tylu, ile pięter w budynku.
Jeśli do jaskini na każdym poziomie jest takie samo hasło, to przekonać o znajomości hasła możemy w jednej scenie, kręcąc widok na wszystkich piętrach równocześnie.
Pozostawmy już za sobą bajkę o kupcu z Bagdadu i jego krewnym, archeologu. W zamian zajmiemy się ciekawszym problemem. Jak być może wiesz, problem znajdowania izomorfizmu grafów (czyli przyporządkowania wierzchołkom jednego grafu wierzchołków drugiego w taki sposób, żeby krawędzie w obu grafach łączyły te same wierzchołki) to zadanie trudne - nie jest znany szybki algorytm rozwiązujący ten problem. Jak bardzo trudne? Przekonasz się o tym na przykład przy okazji czytania artykułu Damiana Rusaka Czy dostrzegasz podobieństwo [2]. Znajdziesz w nim także więcej informacji o samym problemie.
I już! Proste, prawda? A jednak działa - zauważ, że wiedza o izomorfizmie między i którymś z dwóch grafów nie zbliża Jego ani o krok do znalezienia Twojego cennego izomorfizmu między a .
Można zadać sobie pytanie - co to wszystko ma wspólnego z kryptografią? Otóż, wbrew pozorom, całkiem dużo. Umiemy teraz pokazać, że znamy jakąś informację, ale bez ujawniania jej!
To ważne na przykład w procesie uwierzytelniania, kiedy przekonujemy kogoś, że znamy swoje własne hasło, ale nie chcemy go przesłać przez sieć.
Innym, dużo ważniejszym przykładem jest upewnianie się (“dowodzenie”), że dane, które są przesyłane w komunikacji sieciowej, są zgodne z jakimś ustalonym protokołem. Ale to zupełnie inna historia, do której może kiedyś wrócimy...
Odnośniki:
[1] http://informatyka.wroc.pl/node/243
[2] http://informatyka.wroc.pl/node/100
[3] http://pl.wikipedia.org/
[4] http://pl.wikipedia.org/w/index.php?title=Plik:Ali-Baba.jpg&filetimestamp=20061218015205
[5] http://commons.wikimedia.org/wiki/File:Thucydides_Manuscript.jpg?uselang=pl