Delta mi!

Jak dobrze wiemy, żyjemy w wyjątkowym okresie w dziejach, w którym dostęp do informacji jest niesłychanie łatwy, i w zasadzie z roku na rok ułatwienia w tym zakresie zwiększają się. Z pewnością tym bardziej zwiększą się one w bieżącym roku - 2020. Podobnie jest z ilością danych, zbieramy ich coraz więcej. Gromadzimy olbrzymie ilości zdjęć, muzyki, filmów, ale również i innych danych, takich jak teksty, wszelkiego rodzaju informacje o ruchu w sieci itd. Przykładowo w ciągu każdej minuty na serwis YouTube wrzucanych jest około 500 godzin filmów. Powstała nawet dziedzina badań zajmująca się analizą dużych danych, zwana z angielska Big Data...

W naszych czasach coraz więcej rzeczy staje się tajnych. To dlatego, że nasze życie jest coraz bardziej uzależnione od setek i tysięcy drobiazgów, a kontrolę nad nimi każdy chce zachować dla siebie. Przyjdzie może czas, kiedy na posiadanie tablic logarytmicznych wymagane będzie zezwolenie. Żarty? Mam nadzieję. Na razie grozi nam utajnienie tablic rozkładów liczb na czynniki pierwsze. A oto dlaczego...

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...

Teoria liczb to prawdopodobnie najstarsza dziedzina wiedzy matematycznej, badana intensywnie już w czasach starożytnych (a zapewne jeszcze wcześniej; możliwe, że nawet zanim powstała jakakolwiek cywilizacja operująca przekazem pisemnym).

Niniejszy odcinek jest ostatni z serii. Przez niemal rok, wraz z Łukaszem Rajkowskim, próbowaliśmy pokazać Czytelnikowi, co ciekawego, a przede wszystkim - co zaskakującego, wiąże się z kryptologią. Naszą wielką nagrodą będzie, gdy - po przeczytaniu tych 9 odcinków - choć niewielka część Czytelników chociaż przez chwilę zawaha się, gdy w życiu codziennym będzie stwierdzać, że czegoś się nie da...

W poprzednim odcinku naszej sagi przedstawiliśmy miłosną historię Aldony i Bogumiła. Poniżej prezentujemy jej dość dramatyczną kontynuację, widzianą oczami Aldony...

Wyobraźmy sobie następującą wakacyjną historię miłosną, która miała prawo się zdarzyć przed nastaniem ery wszechobecnych mediów społecznościowych...

Za co kochamy gotówkę? Chyba przede wszystkim za anonimowość transakcji. To znaczy: jeśli Aldona oraz Celina podejmą z banku po banknocie stuzłotowym; następnie Aldona wyda te pieniądze w sklepiku Bogumiła, a Celina u Dobromira; po czym zarówno Bogumił, jak i Dobromir zdeponują zarobione pieniądze z powrotem w banku, to oczywiście bank w żaden sposób nie będzie w stanie stwierdzić, czy klientką Bogumiła była Aldona, czy też może Celina.

Jedną z drobnych przyjemności w życiu milionera jest porównywanie swojego bogactwa z bogactwem innych milionerów. Czasem nie jest to trywialne zadanie, gdyż afiszowanie się ze stanem swojego konta (nawet przybliżonym) mogłoby zostać uznane za naruszenie krezusowej etykiety. Istnieje co prawda szeroki wachlarz subtelnych wskaźników, w rodzaju rozmiaru posiadłości czy liczby luksusowych aut, jednak te bywają bardzo mylące. Czy jest możliwa wymiana informacji między dwoma bogaczami w taki sposób, by każdy z nich dowiedział się, który z nich jest bogatszy, i byłaby to jedyna informacja o stanie posiadania rozmówcy?

Ence-pence w której ręce? - za moich dziecięcych lat przedstawiona formułka, której towarzyszyły często dwie wyciągnięte przez wypowiadającą ją osobę ręce, była zwiastunem jakiejś bardzo przyjemnej (najczęściej słodkiej) niespodzianki. Każda wyciągnięta dłoń skrywała bowiem coś dobrego, jednak jako szkrab i tak poświęcałem chwilę zastanowienia nad jej wyborem, będąc świadomym ryzyka, że niewskazana przeze mnie ręka zawiera bardziej atrakcyjny podarek i powędruje on do mojego brata.

Bywa tak, że chcemy o czymś przekonać niedowiarków, jednak w taki sposób, aby uwierzyli, ale też aby za dużo się nie dowiedzieli. Fabularna, nieinformatyczna ilustracja, którą lubię przywoływać, gdy próbuję wyrazić, o co mi chodzi, jest następująca. Wyobraźmy sobie, że potrafię zliczyć liczbę liści na drzewie, jeśli tylko spojrzę na nie przez 5 sekund. Więcej: twierdzę, że umiem to publicznie udowodnić w przeciągu 5 minut, i to tak, że wszyscy mi uwierzą, ale nikt się nie zorientuje, jak ja to robię!

Zapewne każdy z czytających te słowa grał kiedyś w marynarza, ale na wypadek gdyby któryś z Czytelników miał smutne dzieciństwo pozbawione tej gry, pokrótce wyjaśnię zasady: na ustalony sygnał każdy z uczestników przedstawia wybraną przez siebie liczbę (najczęściej przy użyciu własnych palców). Następnie rozpoczyna się (cykliczne) wyliczanie uczestników aż do sumy przedstawionych przez nich liczb (oczywiście, należy zawczasu ustalić, od kogo rozpoczyna się wyliczanka). Osoba, na której zakończy się wyliczanie, jest "zwycięzcą" (wziętym w cudzysłów, gdyż "nagrodą" może być, na przykład, zmywanie naczyń)...

Problem szyfrowania przesyłanych wiadomości sięga jeszcze czasów starożytnych, więc naszego nowego deltowego cyklu artykułów o kryptologii prezentowanego w rubryce "A jednak się da!" nie możemy nie zacząć od przypomnienia najstarszego znanego systemu szyfrowania, mianowicie szyfru Cezara. Szyfr ten nie jest specjalnie wyrafinowany...

Tak zwana "kryptografia krzywych eliptycznych" to bardzo modne i popularne pojęcie, które rzeczywiście jest ważne, ale - niestety - o którym mówi się najczęściej niezwykle powierzchownie, bez wchodzenia w "detale matematyczne". Niniejszy artykuł próbuje pójść takiemu podejściu pod prąd - chcemy w elementarny sposób objaśnić, o co tak naprawdę chodzi z tymi krzywymi eliptycznymi.

Zawodowo zajmuję się kryptologią, czyli dziedziną nauki badającą różne aspekty bezpieczeństwa cyfrowego świata. Jest to nauka ścisła, czyli taka, w której królują stricte matematyczne rozumowania. Solą matematyki są, oczywiście, dowody. Również główne wyniki kryptologiczne to właśnie twierdzenia i ich dowody. A twierdzenie to para: założenie i teza. W kryptologii teza zwykle jest podobna: proponowany system jest bezpieczny. Ciekawym i ważnym pytaniem jest jednak wątpliwość: ale przy jakich założeniach?!

Jednym z ważniejszych osiągnięć informatyki opartej o komputer kwantowy, które zresztą eksponujemy w tym numerze Delty, jest opracowanie efektywnego (wielomianowego od rozmiaru danych) algorytmu na rozkład dużych liczb na czynniki pierwsze. Wspaniały, budzący zachwyt wynik. Nie dość, że przepiękny, korzystający z bardzo ładnego fragmentu matematyki, to jeszcze pozwalający wierzyć, że komputer kwantowy złożony z kubitów jest istotnie lepszy od komputera klasycznego, zawierającego pamięć o bitach. Albo inaczej: że (też prezentowany w tym numerze) model obliczeń komputera kwantowego ma istotnie większą siłę wyrazu (przy założeniu wielomianowego czasu działania) niż klasyczny model Turinga czy inne równoważne.

Jak można dowiedzieć się z rozlicznych filmów akcji, nieodłączną częścią życia każdego szanującego się tajnego agenta jest wymiana tajnych informacji, najlepiej takich z wielką, czerwoną pieczęcią "Top Secret". Jeśli agent ma taką możliwość, najlepiej przekazać teczkę pełną tajemnic osobiście, jednak jest to luksus, na który może on pozwolić sobie w niewielu sytuacjach, gdyż nierzadko odbiorca tych tajemnic znajduje się na drugim końcu globu. W tej sytuacji konieczne staje się odpowiednie zaszyfrowanie naszych sekretów, aby nawet w przypadku przechwycenia ich przez oślizgłe macki szwarccharakterów, pozostały one sekretami.

Mam pewien sekret, może lepiej nawet powiedzieć: tajemnicę. Nie mogę sobie pozwolić, żeby ktoś ją poznał. Sprawa jest poważna, ujawnię ją dopiero za pewien czas, gdy tylko Świat będzie na to gotowy. Może to rozwiązanie pewnego ważnego problemu matematycznego, zresztą, nie będę dzwonił kluczami do tajemnic. W każdym razie nie mogę sobie również pozwolić, żeby na wypadek mojej śmierci ta informacja przepadła bezpowrotnie. Co robić?

Czym jest Bitcoin? Najkrótsza odpowiedź na to pytanie brzmi: kryptowalutą. Ale nie w takim sensie krypto-, jak w słowie kryptoreklama. Pierwszy człon tego terminu pochodzi od kryptologii, czyli nauki kojarzącej nam się głównie z szyframi i maszyną szyfrującą Enigma używaną przez Niemców podczas wojny. To właśnie twierdzenia i konstrukcje z tej dziedziny stoją za funkcjonowaniem i bezpieczeństwem Bitcoina.

Lubię próżnie mówić o sobie, że jestem matematykiem. Bardziej precyzyjnie to jestem informatykiem, ale przecież informatyka to gałąź matematyki, więc w zasadzie nie oszukuję. Czasem, gdy ktoś mnie ciągnie za język, i pojawi się to, z niejasnych powodów nielubiane przeze mnie, słowo na "i", to i tak od razu uściślam: tak, jestem informatykiem, ale informatykiem teoretycznym. Zawsze miałem to dziwne przekonanie, że "teoretyczny" znaczy w jakimś sensie lepszy, ważniejszy, mądrzejszy, głębszy.

Kryptografia wizualna to metoda komputerowego szyfrowania obrazów, w której do rozszyfrowania wystarczy... popatrzeć. Konkretniej, z obrazu, który chcemy zaszyfrować ("obrazem" może być też napisany na kartce tekst), tworzymy dwa "pstrokate" obrazy, z których nic nie można odczytać.

W fizyce szkolnej nieustannie przewijającym się motywem są dwa znane miasta: miasto A oraz miasto B. W kryptografii takimi gwiazdami są Alicja i Bob, którzy ciągle się komunikują, uwierzytelniają, a zwykle przeszkadza im w tym złowroga Ewa.