Czy przez telefon można grać w karty?

O telefonicznej czy korespondencyjnej grze w szachy słyszał każdy. Ale jak grać w ten sposób w brydża lub w pokera? Problemem jest oczywiście rozdawanie kart...

Przypuśćmy, że grają dwie osoby i mają rozdać po pięć kart. Rozdać to znaczy:

Każdy ma wiedzieć, jakie pięć kart dostał.
Każdy ma wiedzieć, jakie pięć kart dostał.
Karty otrzymane przez graczy są różne.
Żaden z graczy nie ma dodatkowej informacji o kartach partnera, ale po grze może sprawdzić, czy partner nie oszukiwał, czy grał swoimi kartami.
Każdy rozkład kart jest jednakowo prawdopodobny.

Wszystko to należy wykonać porozumiewając się wyłącznie przez telefon i bez pomocy osób trzecich. Oto sposób umożliwiający w praktyce rozdawanie kart (liczb naturalnych $|1,...,52$ ) przez telefon. Gracze wybierają najpierw dwie rodziny funkcji o argumentach i wartościach naturalnych: $α α∈Ω}𝒦 = {K$ - funkcje kodujące i $𝒟 = {D$ - funkcje dekodujące (zbiór $Ω$ nazywamy zbiorem kodów - powinien on mieć dużo elementów). Rodziny $|𝒦$ i $|𝒟$ muszą mieć następujące własności:

Dziedzina każdej funkcji $|K α$ zawiera zbiór ${1,...,52}.$
Dla dowolnego kodu $α$ funkcja $𝒟 α$ jest odwrotna do funkcji $α K$ (rozszyfrowuje ona sygnał zakodowany za pomocą funkcji $K α$ ), tzn. $|D$ dla liczb naturalnych z dziedziny funkcji $α. K$
Dla dowolnych kodów $α$ i $β$ funkcje $α |K$ i $β K$ są przemienne, tzn. $(K(n))=K(K(n)). K αββα$
Różne funkcje kodujące mają rozłączne zbiory wartości.
Znajomość liczb naturalnych $n$ i $(n) K α$ nie daje praktycznie możliwości znalezienia kodu $|α.$

Rozdawanie kart jest już proste. Gracze wybierają (w tajemnicy przed sobą) kody, np. $A$ - kod $α ,$ $B$ - kod $β .$ Gracz $|A$ koduje liczby $|1,...,52$ i przesyła je (w dowolnej kolejności) graczowi $B.$ Ten wybiera wpierw pięć kart dla $|A$ : $α(a1),...,Kα(a5) |K$ i odsyła mu je - $|A$ musi je rozszyfrować funkcją $|D$ Następnie wybiera pięć kart dla siebie: $α(b1),...,Kα(b5), K$ szyfruje je funkcją $β K$ i wysyła do $.A$ Gracz $A$ rozszyfrowuje je funkcją $|D$ i odsyła do gracza $B |$ (tzn. przesyła $|D$ Gracz $|B$ musi jeszcze rozszyfrować je funkcją $|D$ i... karty zostały rozdane.

Po grze partnerzy ujawniają swoje kody. Z drugiej i czwartej własności rodzin $|𝒦$ i $|𝒟$ wynika, że jeśli $α1(m1)=Kα2(m2), |K$ to $α1 = α 2$ i $m1 = m2.$ Tak więc gracze nie mogą oszukiwać i podawać innego układu kart i innego kodu.

Powyższy opis umożliwia w praktyce rozdawanie kart. Teoretycznie bowiem jest to niemożliwe.

***

Komentarz współczesny

Kilka lat temu zapytałem Mordechaja "Motiego" Yunga (obecnie pracuje jako badacz naukowy w Google) o to, na ile zmienił się obraz badań naukowych z dziedziny kryptologii od czasów, gdy zaczynał, a więc od lat 80. W swej odpowiedzi (wyrażonej dość komunikatywną polszczyzną!) jako największą różnicę wskazał liczbę publikowanych prac. Stwierdził, że w początkach swojej kariery był w stanie, bez większego wysiłku, śledzić na bieżąco WSZYSTKIE artykuły dotyczące kryptologii, które ukazywały się na świecie. Dziś natomiast ciężko byłoby młodemu badaczowi przebrnąć w ciągu roku choćby przez połowę publikacji prezentowanych na jednej dużej konferencji kryptologicznej, których organizuje się przecież co najmniej kilka w roku.

Powyższa opinia Motiego dobrze koresponduje z obecnością kryptologii w Delcie. Do końca lat 80. (a więc przez 190 numerów) w Delcie ukazały się tylko dwa krótkie teksty dotyczące zagadnień kryptologicznych - oba prezentujemy w tym numerze. Wówczas była to dziedzina dostarczająca przede wszystkim eleganckich (często zaskakujących) wyników-ciekawostek, kojarzonych głównie ze sztuczkami z teorii liczb. W takim też duchu utrzymane są oba dziś prezentowane wyimki ze $|𝔖 𝔱𝔞 𝔯𝔢𝔧𝔇 𝔢𝔩𝔱𝔶.$

Oczywiście wraz z rozwojem komputerów i sieci komputerowych znaczenie kryptologii wzrosło niebotycznie. Dziś jest to ogromna gałąź informatyki teoretycznej. Również w Delcie artykułów z tej dziedziny w późniejszym okresie było znacznie więcej. Ostatnio prezentowaliśmy nawet niemal roczny cykl A jednak się da (od Delty 10/2018 do Delty 8/2019), poświęcony w całości kryptologii. Co ciekawe: oba zagadnienia z lat 80. były obecne w tym cyklu (choć autorzy wybierali tematy zupełnie niezależnie), a artykuł otwierający cykl dotyczył dokładnie tego samego tematu, co pierwszy artykuł kryptologiczny w Delcie z roku 1980!

Tomasz Kazana

Delta mi!

Nowości z przeszłości

Stara Delta

Czy przez telefon można grać w karty?

***

Komentarz współczesny