Jedyny w Polsce serwis o internecie, prywatności i mediach społecznościowych pisany z perspektywy technologicznej, humanistycznej i społecznej

Laboratorium Informatyki i Sztucznej Inteligencji (CSAIL) MIT ogłosiło w tym tygodniu, że 20-letnia łamigłówka kryptograficzna została rozwiązana przez belgijskiego programistę-samouka Bernarda Fabrota. Stało się to 15 lat wcześniej niż oczekiwali tego naukowcy z MIT.

Historia łamigłówki

W 1999 roku kapsuła czasu z łamigłówką stworzoną przez amerykańskiego kryptografa Ronalda Rivesta (jednego z twórców algorytmu RSA) została przekazana architektowi Frankowi Gehry’emu, który projektował wówczas siedzibę dla Laboratorium Informatyki i Sztucznej Inteligencji MIT. W kapsule znajdowało się wiele rzadkich przedmiotów dostarczonych przez współtwórcę usługi WWW Tima Bernersa Lee i byłego CEO Microsoftu Billa Gates’a (który przekazał m.in. interpreter języka programowania BASIC – Altair BASIC).

Rozwiązania słynnej łamigłówki podjęła się również inna osoba – były inżynier Intela Simon Peffers. Fabrot i Peffers przyjęli jednak różne podejścia naukowe do rozwiązania zagadki. Belg użył zwykłego komputera z procesorem Intel Core i7-6700 i obliczył rozwiązanie korzystając z biblioteki programistycznej GNU Multiple Precision Arithmetic Library (GMP). Tymczasem zespół Peffersa wykorzystał nowatorski algorytm (zaprojektowany przez Erdinca Öztürka z Sabanci Üniversitesi w Istambule), który był uruchomiony na układzie FPGA (Bezpośrednio programowalna macierz bramek (Field-programmable gate array). Zespół – który pracuje w ramach współpracy Cryptophage – ma ukończyć swoje obliczenia 11 maja br., po zaledwie dwóch miesiącach obliczeń.

To, co sprawia, że kryptograficzna łamigłówka jest trudna do rozwiązania, to fakt, że nie można jej rozwiązać wykorzystując do tego obliczeń równoległych. Zagadka musi być rozwiązana tylko przez sekwencyjne obliczenia.

Ronald Rivest zaprojektował zagadkę w taki sposób, aby jej rozwiązanie zajęło dokładnie 35 lat. Jednak belgijski samouk Bernard Fabrot rozwiązał ją 15 lat wcześniej niż się spodziewano.

Na czym polega łamigłówka?

Łamigłówka polega na przeprowadzeniu operacji kwadratowania 80 bilionów razy (np. kwadrat liczby 2 wynosi 4, kwadrat liczby 4 to 16). Odpowiedź na postawioną przez naukowców łamigłówkę miała być uzyskana przez powtórzenie tego procesu 80 bilionów razy.

Liczba, która będzie wynikiem tych żmudnych operacji, zostanie następnie połączona z liczbą podaną na kapsule czasu. W rezultacie otrzymuje się zwrot gratulacyjny, który można wykorzystać do otwarcia kapsuły czasu.

Sprzęt i oprogramowanie rozwinęły się o wiele bardziej niż przewidywałem to w 1999 rokuocenił prof. MIT Ronald Rivest, który zaprojektował zagadkę w kwietniu 1999 r. w ramach obchodów 35-lecia badań w CSAIL. Podstawowe wyzwanie łamigłówki, jakim było wykonanie 80 bilionów operacji kwadratowania pozostaje jednak nierozwiązane, ale zasoby potrzebne do wykonania pojedynczej operacji zostały zmniejszone o wiele bardziej niż przewidywałem – dodał naukowiec.

Jak Fabrot rozwiązał łamigłówkę?

Fabrot twierdzi, że na łamigłówkę natknął się przypadkowo w 2015 roku i postanowił ją rozwiązać. Zajęło mu to w sumie ponad trzy lata i jak podkreśla – za wyjątkiem przerw w dostawie prądu oraz wyjazdów na wakacje – jego komputer działał nieprzerwanie przez 24 godziny na dobę.

Teraz, kiedy łamigłówka została już rozwiązana, kapsuła czasu zostanie oficjalnie otwarta 15 maja br. podczas uroczystości w MIT Stata Center.

Opublikowano w: Oprogramowanie
Więcej na podobne tematy: , , , , , ,
// Ronald Muroń Więcej wpisów

Specjalizuje się w prawnych aspektach technologii informatycznych. Interesuje się stosunkami międzynarodowymi, prawem międzynarodowym oraz tematyką gospodarczą

2 odpowiedzi na “Programista-samouk rozwiązał 20-letnią łamigłówkę kryptograficzną MIT”

  1. Rivest chciał przyszpanować, a nie przewidział, że mu to rozwali zwykły brute force na i7 z GMP (na miraclu by im to poszło o rok krócej zapewne) 😀

    Lepsze wyzwania to te od kompresji danych, które prowadzą do rewolucyjnych rozwiązań algorytmicznych, głównie dzięki pracy Matta Mahoneya i publikowane w benchmarku na najlepsze ratio w kompresji 1GB danych z Wikipedii

    Benchmark
    http://mattmahoney.net/dc/text.html

    Dodatkowe informacje
    http://mattmahoney.net/dc/

  2. […] koniec kwietnia na łamach naszego serwisu ukazał się artykuł, w którym informowaliśmy o tym nieco już zapomnianym przez świat nauki wydarzeniu. Teraz […]

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *