Filozofia inżynierii: Adi Shamir

Najważniejsze wnioski

• Jest „S” w RSA, pierwszym praktycznym kryptosystemie z kluczem publicznym. Wraz z Ronem Rivestem i Leonardem Adlemanem Adi Shamir współtworzył RSA w MIT w 1977 roku — publicznie opisany w tym samym roku i opublikowany w Communications of the ACM w lutym 1978 roku. Schemat umożliwił szyfrowanie wiadomości do danej osoby oraz weryfikację jej podpisów, bez uprzedniego dzielenia się jakimkolwiek sekretem, a jego bezpieczeństwo opiera się na trudności faktoryzacji dużych liczb. Praca przyniosła całej trójce Nagrodę Turinga ACM z 2002 roku.¹²
• Zamienił wielomian w doskonały sekret. W 1979 roku Shamir opublikował pracę „How to Share a Secret”, przedstawiając schemat progowy, który dzieli sekret między n osób tak, że dowolnych k z nich może go odtworzyć, a dowolne k-1 nie dowiaduje się zupełnie niczego — ani wskazówki, ani zawężenia. Całość zbudowana jest wyłącznie z punktów na wielomianie.³
• Jest mistrzem kryptoanalizy — atakuje, by bronić. Wraz z Elim Bihamem pod koniec lat 80. Shamir publicznie odkrył kryptoanalizę różnicową, ogólną metodę łamania szyfrów blokowych, a wcześniej złamał kryptosystem plecakowy Merkle-Hellmana. Ten sam umysł, który zbudował RSA, przez dekady uczył się łamać systemy, bo w kryptografii to jedyny uczciwy sposób, by przekonać się, że system jest mocny.⁴⁵
• Wciąż przekuwa czystą matematykę w praktyczny mechanizm. Poza RSA i podziałem sekretu Shamir współtworzył heurystykę Fiata-Shamira — sposób na zamianę dowodu interaktywnego w nieinteraktywny podpis za pomocą funkcji skrótu — a także schematy kryptografii opartej na tożsamości oraz kryptografii wizualnej. Profesor Instytutu Weizmanna od 1980 roku, swoją karierą prowadzi długi wywód, że głęboka teoria liczb jest zestawem narzędzi, a nie muzeum.¹⁶

Zasada

„Później okazało się, że kryptoanaliza różnicowa była już znana — i utrzymywana w tajemnicy — zarówno przez IBM, jak i Agencję Bezpieczeństwa Narodowego.” — o technice, którą Biham i Shamir odkryli na nowo w otwartym obiegu, parafrazując zapis historyczny⁴⁵

Większość inżynierii zmierza ku demonstracji. Pisze się daną rzecz, uruchamia, działa, a samo działanie jest dowodem. Kryptografia odmawia tej wygody. Szyfr, który poprawnie szyfruje i deszyfruje, nie wykazał niczego na temat tego, czy jest bezpieczny — szyfr złamany i szyfr nie do złamania zachowują się identycznie, dopóki ktoś ich nie zaatakuje. Dziedzina musiała więc wynaleźć inny standard prawdy: system jest godny zaufania nie wtedy, gdy działa, lecz gdy poważni ludzie usilnie próbowali go złamać i im się nie udało. Cała kariera Shamira jest ucieleśnieniem tego standardu. System zabezpiecza się, ucząc się łamać systemy — atakować, by bronić.⁴

Najwyraźniejszym tego wyrazem jest to, że wykonuje obie połowy samodzielnie. Zbudował RSA, kamień węgielny kryptografii klucza publicznego, oraz schemat podziału sekretu Shamira, system o dowodliwym bezpieczeństwie teorioinformacyjnym.¹³ Złamał jednak również kryptosystem plecakowy Merkle-Hellmana — konkurencyjny schemat klucza publicznego, który wyglądał na bezpieczny, lecz taki nie był — a także współodkrył kryptoanalizę różnicową, metodę na tyle ogólną, że zagrażała samemu standardowi szyfrowania danych (Data Encryption Standard).⁴⁵ To nie są dwie kariery. To jedna dyscyplina. Praca konstrukcyjna mówi, co jest możliwe; praca destrukcyjna mówi, co jest prawdziwe. Kryptograf, który tylko buduje, zgaduje, a najbardziej mrożący krew w żyłach dowód na to nadszedł później, gdy wyszło na jaw, że IBM i NSA wiedziały o kryptoanalizie różnicowej od połowy lat 70. i utrzymywały to w tajemnicy — co oznacza, że publiczna dziedzina budowała szyfry ślepa na atak, którym jej przeciwnicy już dysponowali.⁴⁵

Zasada ma drugą połowę, cichszą i równie nośną: siłę przekuwania czystej idei matematycznej w praktyczny mechanizm. Podział sekretu to zaledwie interpolacja wielomianowa — fakt, z którym każdy uczeń spotyka się w algebrze, że dwa punkty wyznaczają prostą, a trzy parabolę. Shamir dostrzegł, że ten sam fakt, odczytany wstecz, jest prymitywem bezpieczeństwa: rozdaje się punkty, a krzywa pozostaje ukryta, dopóki nie zbierze się ich dość.³ RSA to zaledwie potęgowanie modularne i trudność faktoryzacji.² Heurystyka Fiata-Shamira to zaledwie zastąpienie rzutu monetą weryfikatora funkcją skrótu.⁶ Znajdź czystą strukturę matematyczną, a następnie odczytaj ją jako mechanizm. Geniusz rzadko polega na nowej matematyce — polega na dostrzeżeniu, że stara matematyka, spojrzeniem z właściwego kąta, już jest tym, co trzeba zbudować.

Kontekst

Adi Shamir urodził się 6 lipca 1952 roku w Tel Awiwie w Izraelu.¹ Licencjat z matematyki uzyskał na Uniwersytecie w Tel Awiwie w 1973 roku, po czym przeniósł się do Instytutu Naukowego Weizmanna na studia podyplomowe, zdobywając tytuł magistra informatyki w 1975 roku i doktorat w 1977 roku.¹ Jego moment, podobnie jak moment całej dziedziny, miał się właśnie odmienić: rok 1977 był rokiem, w którym kryptografia klucza publicznego przeszła od kuszącej idei do działającego systemu.

Po doktoracie spędził rok jako badacz na stażu podoktorskim na Uniwersytecie w Warwick w Anglii, a następnie trafił do Massachusetts Institute of Technology, gdzie w latach 1977–1980 był pracownikiem naukowym.¹ To w MIT powstało RSA. Ron Rivest, kryptograf, ścigał schemat klucza publicznego zainspirowany ideą Diffiego-Hellmana, że dwie strony mogą ustanowić tajemnicę bez wspólnego sekretu; Shamir i Adleman byli jego współpracownikami i — co kluczowe — jego przeciwnikami: Rivest proponował schemat, a Shamir i Adleman łamali go, raz za razem, aż jeden przetrwał. Tym, który przetrwał, było RSA, nazwane od nazwisk całej trójki, opublikowane w 1977 roku i w Communications of the ACM w 1978 roku.² (Bez ich wiedzy brytyjski matematyk Clifford Cocks z GCHQ opisał równoważny system w utajnionym dokumencie z 1973 roku, który pozostał tajny aż do 1997 roku — kolejny przypadek dziedziny budującej po ciemku, podczas gdy agencje wywiadowcze patrzyły.)²

W 1980 roku Shamir wrócił do Instytutu Weizmanna, gdzie od tamtej pory jest profesorem w katedrze informatyki i matematyki stosowanej, a później objął także zaproszoną profesurę w École Normale Supérieure w Paryżu.¹ Niemal wszystko, co go określa — podział sekretu, szturm na szyfry plecakowe, kryptoanaliza różnicowa z jego studentem Elim Bihamem, heurystyka Fiata-Shamira, kryptografia wizualna z Monim Naorem, ataki sześcianowe, urządzenia faktoryzujące TWIRL i TWINKLE — narodziło się w Weizmannie. W 2002 roku Association for Computing Machinery przyznało Rivestowi, Shamirowi i Adlemanowi Nagrodę Turinga, najwyższe wyróżnienie informatyki, za ich wkład w kryptografię klucza publicznego.¹²

Dzieło

Podział sekretu Shamira: parabola, która dochowuje sekretu

Zacznijmy stąd, bo to zasada w najczystszej, najpiękniejszej postaci. Załóżmy, że ma się sekret — klucz główny, kod startowy, hasło do skarbca — i chce się go podzielić między pięciu powierników tak, by dowolnych trzech z nich, razem, mogło go odzyskać, lecz żadnych dwóch nie mogło niczego się dowiedzieć. Można by próbować fizycznie pociąć klucz na kawałki, ale to przecieka: każdy kawałek zawęża zgadywanie. Wnioskiem Shamira z 1979 roku, w pracy „How to Share a Secret”, było to, że wielomiany już rozwiązują ten problem dokładnie.³

Sztuczka odczytuje wstecz fakt rodem ze szkoły podstawowej. Dwa punkty wyznaczają jednoznacznie prostą; trzy punkty wyznaczają jednoznacznie parabolę; ogólnie k punktów wyznacza jednoznacznie wielomian stopnia k-1. By więc podzielić sekret między n osób z progiem k, ukrywa się sekret jako wyraz wolny losowego wielomianu stopnia k-1 — wartość krzywej w punkcie x = 0 — i wręcza każdej osobie jeden punkt tej krzywej.³ Dowolne k z nich może interpolować jednoznaczną krzywą przechodzącą przez ich punkty i odczytać jej wartość w zerze. Lecz zdumiewające jest bezpieczeństwo: mając tylko k-1 punktów, krzywa nie jest jedynie trudna do znalezienia — jest naprawdę nieokreślona. Dla każdej możliwej wartości sekretu istnieje dokładnie jedna krzywa właściwego stopnia, która przechodzi przez ich punkty i przyjmuje tę wartość w zerze. Jak gwarantuje schemat Shamira, „znajomość dowolnych k-1 lub mniej udziałów pozostawia S całkowicie nieokreślonym”.³ Mniej niż próg nie ujawnia niczego; próg ujawnia wszystko. Ta czysta granica wszystko-albo-nic sprawia, że jest on bezpieczny teorioinformacyjnie — bezpieczny nie dlatego, że jego złamanie jest obliczeniowo trudne, lecz dlatego, że informacji po prostu tam nie ma.³

Dlaczego ma to znaczenie jako inżynieria: schemat jest kanonicznym przykładem odczytywania przez Shamira matematyki jako mechanizmu. Nie wynalazł interpolacji wielomianowej — ma ona wieki. Dostrzegł, że jej tryb porażki — że nie da się odtworzyć krzywej ze zbyt małej liczby punktów — jest właśnie własnością bezpieczeństwa, a jej tryb sukcesu — że dość punktów wyznacza ją dokładnie — jest właśnie własnością odtwarzania. Ten sam fakt, użyty w obu kierunkach, staje się prymitywem kryptograficznym, który działa dziś wewnątrz sprzętowych modułów bezpieczeństwa, w przechowywaniu kryptowalut i u urzędów certyfikacji. Czysta matematyka, odczytana jako narzędzie.³

RSA: szyfrowanie do nieznajomego

RSA odpowiedziało na pytanie, które wydawało się niemal paradoksalne: jak dwie osoby, które nigdy się nie spotkały i komunikują się wyłącznie przez przewód podsłuchiwany przez przeciwnika, mogą wymienić się sekretami? Klasyczna kryptografia wymagała wspólnego klucza ustanowionego z wyprzedzeniem — lecz nie da się dzielić kluczem przez ten sam kanał, który próbuje się chronić. Przełomem, który Rivest, Shamir i Adleman wbudowali w działający system w 1977 roku, była jednokierunkowa funkcja z zapadnią (trapdoor one-way function): operacja łatwa do obliczenia w przód i niewykonalna do odwrócenia, chyba że dysponuje się tajną informacją.²

Zapadnią RSA jest faktoryzacja. Wybiera się dwie duże liczby pierwsze i mnoży je w moduł n; n oraz publiczny wykładnik stają się kluczem publicznym, który można ogłosić światu. Każdy może go użyć, by zaszyfrować do nas wiadomość, poprzez potęgowanie modularne. Lecz deszyfrowanie wymaga klucza prywatnego, który można wyprowadzić tylko z dwóch pierwotnych liczb pierwszych — a odzyskanie tych liczb pierwszych z ich iloczynu oznacza faktoryzację bardzo dużej liczby, problem bez znanego efektywnego rozwiązania.² Jak ujmuje to sformułowanie, choć skonstruowanie kluczy jest praktyczne, „mając jedynie e oraz n, obliczenie pierwiastków e-tego stopnia modulo n jest niewykonalne”.² Ogłasza się zamek; tylko my mamy klucz; a przepaść między nimi to trudność faktoryzacji.

Warto wyraźnie określić konkretną rolę Shamira, bo to znów ta zasada: był on, obok Adlemana, kryptoanalitykiem trójki. Historia powstania RSA jest historią łamania — Rivest proponował kandydujące schematy, a Shamir i Adleman je atakowali, aż tylko jeden wytrzymał szturm. Schemat, który przetrwał, był mocny właśnie dlatego, że przetrwał ataki dwojga ludzi zdeterminowanych, by go złamać. RSA nie jest systemem, który zaprojektowano jako bezpieczny, a potem żywiono nadzieję, że taki będzie; to system, który zasłużył na to miano, przeżywając swoich własnych autorów.²

Atakować, by bronić: łamanie plecaków i kryptoanaliza różnicowa

Jeśli RSA pokazuje Shamira budującego, kolejny zbiór prac pokazuje go robiącego to, czego dziedzina potrzebuje jeszcze bardziej: łamanie. Pod koniec lat 70. kryptosystem plecakowy Merkle-Hellmana był czołowym rywalem RSA, a jego bezpieczeństwo opierało się na problemie „sumy podzbioru” (subset-sum), który jest NP-zupełny i przez to wyglądał na groźnie trudny. Shamir go złamał. Wykazał, że konkretne plecaki, których używał Merkle-Hellman, nie były trudnym przypadkiem ogólnym, lecz szczególnym, ustrukturyzowanym, który da się rozwiązać efektywnie — burząc schemat, któremu wielu ufało.¹ Lekcja jest jedną z tych, które kryptografia wciąż odkrywa na nowo: to, że problem jest trudny w ogólności, nie oznacza, że trudne są instancje, których faktycznie używa twój szyfr. Tylko atak ujawnia różnicę.

Jego najbardziej wpływowa praca kryptoanalityczna powstała wraz z jego studentem Elim Bihamem pod koniec lat 80.: kryptoanaliza różnicowa, opublikowana około 1990 roku.⁴⁵ To ogólna technika, która bada, jak różnice między parami wejść szyfru propagują się do różnic na wyjściu. Jeśli pewne różnice wejściowe prowadzą do pewnych różnic wyjściowych z nielosowym prawdopodobieństwem, to ta statystyczna nierównowaga jest rysą — przeciekiem informacji o kluczu — a Biham i Shamir przekuli ją w ataki na całą gamę szyfrów blokowych, w tym na teoretyczną słabość w Data Encryption Standard, ówcześnie najważniejszym szyfrze świata.⁴⁵

Wtedy dziedzina dowiedziała się czegoś otrzeźwiającego. W 1994 roku Don Coppersmith ujawnił, że IBM — który zaprojektował DES w latach 70. — wiedział o kryptoanalizie różnicowej „już w 1974 roku”, że obrona przed nią była jawnym celem projektowym DES, a NSA naciskała, by utrzymać tę technikę w tajemnicy, ponieważ „ujawnienie założeń projektowych zdradziłoby technikę kryptoanalizy różnicowej, potężną technikę, której można by użyć przeciwko wielu szyfrom”.⁴⁵ Tajemnicze wewnętrzne stałe DES, od dawna podejrzewane o ukrywanie tylnej furtki, okazały się ukrywać obronę przed atakiem, o którego istnieniu opinia publiczna nie wiedziała. Epizod ten jest najsilniejszym możliwym argumentem za zasadą Shamira. Przez dwie dekady otwarta społeczność budowała szyfry i ufała im, pozostając ślepa na fundamentalny atak, którym przeciwnicy już dysponowali. Publiczne odkrycie na nowo przez Bihama i Shamira nie osłabiło kryptografii — wzmocniło ją, wyciągając atak na światło, gdzie każdy mógł projektować z myślą o obronie. Atakować, by bronić, w skali całej dziedziny.⁴⁵

Fiat-Shamir i rozległość zestawu narzędzi

Ten sam instynkt — znajdź czystą strukturę, odczytaj ją jako mechanizm — przewija się przez inne wynalazki Shamira. Heurystyka Fiata-Shamira, opracowana z Amosem Fiatem w połowie lat 80., rozwiązała praktyczny problem z interaktywnymi dowodami wiedzy: takie dowody wymagają żywej wymiany, w której weryfikator wysyła losowe wyzwanie, a dowodzący odpowiada. Fiat i Shamir dostrzegli, że jedynym zadaniem weryfikatora było dostarczenie nieprzewidywalnej losowości i że kryptograficzna funkcja skrótu zastosowana do własnej wiadomości dowodzącego mogła dostarczyć tej losowości równie dobrze — zamieniając rozmowę w pojedynczy, samodzielny, nieinteraktywny dowód, czyli podpis cyfrowy.⁶ Ta jedna transformacja stanowi podstawę dużej części nowoczesnych schematów podpisu i systemów wiedzy zerowej. Zaproponował również kryptografię opartą na tożsamości (używającą tożsamości osoby jako jej klucza publicznego), współtworzył kryptografię wizualną z Monim Naorem (dzielącą obraz na przezrocza, które ujawniają sekret dopiero po nałożeniu — podział sekretu, który można zobaczyć), a później rozwinął ataki sześcianowe oraz urządzenia faktoryzujące TWIRL i TWINKLE.¹ Przez to wszystko utrzymuje się wzorzec: znany element matematyki, obrócony we właściwą stronę, staje się narzędziem.

Metoda

Przyjrzyj się RSA, podziałowi sekretu, złamanym plecakom, kryptoanalizie różnicowej i Fiatowi-Shamirowi, a powracają te same zobowiązania. Metoda Shamira jest mniej hasłem, a bardziej zestawem trwałych nawyków.

Buduj i łam tymi samymi rękami. Charakterystycznym ruchem jest odmowa podziału pracy między tych, którzy konstruują systemy, a tych, którzy je atakują. Shamir współtworzył RSA i złamał plecak Merkle-Hellmana; udowodnił bezpieczeństwo podziału sekretu i współodkrył kryptoanalizę różnicową. Lekcja sięga daleko poza kryptografię: nie rozumiesz tego, co zbudowałeś, dopóki nie spróbowałeś, na serio, tego pokonać. To bramka dowodu podniesiona do rangi sposobu na życie — „działa” nie jest dowodem bezpieczeństwa; „poważni ludzie próbowali to złamać i nie mogli” — jest.²⁴

Ufaj tylko temu, co przetrwa atak. Szyfr, który jedynie został starannie zaprojektowany, jest nadzieją; szyfr, który wytrzymał skoncentrowaną kryptoanalizę, jest faktem. Dyscyplina polega na traktowaniu własnego systemu jako winnego, dopóki nie zostanie zaatakowany — na założeniu, że istnieje rysa, i wyruszeniu na jej poszukiwanie, zamiast czekać, aż przeciwnik znajdzie ją za ciebie. To kryptograficzna postać „Reflections on Trusting Trust” Thompsona: założycielskiego wglądu, że nie da się ufać temu, czego nie zbadało się przeciwniczo, bo zagrożeniem, które cię dopadnie, jest to, którego nie widzisz — jak dowiodła utajniona historia kryptoanalizy różnicowej.⁴⁵

Odczytuj matematykę jako mechanizm. Najpotężniejsze prymitywy rzadko są nową matematyką; są starą matematyką ujrzaną pod nowym kątem. Interpolacja wielomianowa staje się podziałem sekretu; trudność faktoryzacji staje się zapadnią; funkcja skrótu staje się zastępstwem dla interaktywnego weryfikatora. Nawykiem jest spojrzeć na czystą strukturę i zapytać nie „czym to jest?”, lecz „co to mogłoby zrobić?” — ta sama oszczędność środków, która sprawia, że najmocniejsze prymitywy są zarazem najprostsze, w duchu minimalnego godnego produktu.³⁶

Tam, gdzie możesz, wybieraj bezpieczeństwo dowodliwe, a wszędzie indziej — bezpieczeństwo zasłużone. Podział sekretu jest bezpieczny teorioinformacyjnie — żaden komputer, choćby najpotężniejszy, nie wydobędzie sekretu ze zbyt małej liczby udziałów, bo informacji tam nie ma.³ RSA jest bezpieczne obliczeniowo — bezpieczne tylko tak długo, jak faktoryzacja pozostaje trudna. Shamir działa na obu poziomach i jest precyzyjny co do tego, który ma. Dyscyplina polega na dokładnym wiedzeniu, na czym opiera się twoje zapewnienie bezpieczeństwa, i na nieutożsamianiu nigdy „nikt jeszcze tego nie złamał” z „tego nie da się złamać”. To jakość jest jedyną zmienną zastosowane do zaufania: liczy się tylko jedno — czy gwarancja jest prawdziwa.²³

Nie ufaj przypadkowi szczególnemu ukrytemu w ogólnym. Złamanie Merkle-Hellmana nauczyło dziedzinę, że to, iż problem jest NP-zupełny w ogólności, nie mówi nic o konkretnych instancjach, których faktycznie używa szyfr.¹ Trwałym nawykiem jest podejrzewać, że wygodna, ustrukturyzowana wersja trudnego problemu — ta dość prosta, by zbudować wokół niej system — może być dokładnie tą wersją, którą łatwo złamać. Ten sam sceptycyzm, który Leslie Lamport wniósł do systemów rozproszonych: nie ufaj własności, którą założyłeś; znajdź dokładny warunek, pod którym faktycznie zachodzi.

Łańcuch wpływów

Kto go ukształtował

Diffie, Hellman i idea klucza publicznego. RSA było bezpośrednią odpowiedzią na propozycję Whitfielda Diffiego i Martina Hellmana z 1976 roku, że tajemnicę można ustanowić bez uprzednio współdzielonego klucza. Diffie-Hellman postawili pytanie — kryptosystem klucza publicznego powinien istnieć — a Rivest, Shamir i Adleman zbudowali pierwszą praktyczną odpowiedź.² (Wpływ bezpośredni)

Ron Rivest i Leonard Adleman. Współpraca przy RSA była naprawdę trójręczna: Rivest jako niestrudzony proponent, Shamir i Adleman jako niestrudzeni łamacze. Przeciwnicza struktura tego partnerstwa — zaproponuj, zaatakuj, powtórz — ukształtowała trwające całe życie przekonanie Shamira, że konstrukcja i kryptoanaliza to jedna dyscyplina.² (Wpływ formacyjny)

Tradycja teorioliczbowa. Charakterystyczny ruch Shamira — odczytywanie klasycznej matematyki jako kryptograficznego mechanizmu — wywodzi się z długiej tradycji łączącej teorię liczb, trudność faktoryzacji i algebrę ciał skończonych z obliczeniami. Jego geniusz polegał na zastosowaniu, nie na wynalezieniu tej matematyki. (Wpływ formacyjny)

Kogo ukształtował

Eli Biham i nowoczesna kryptoanaliza. Kryptoanaliza różnicowa, rozwinięta z jego studentem Bihamem, stała się standardowym narzędziem, przed którym każdy poważny projektant szyfrów blokowych musi się teraz bronić — przekształciła sposób budowania szyfrów, w tym kryteria projektowe dla Advanced Encryption Standard.⁴⁵

Cały ekosystem klucza publicznego. RSA stanowiło podstawę dekad bezpiecznej komunikacji, podpisów cyfrowych i wymiany kluczy. Za każdym razem, gdy przeglądarka nawiązuje bezpieczne połączenie lub weryfikuje certyfikat, opiera się na fundamencie klucza publicznego, który Shamir pomógł położyć.²

Schematy wiedzy zerowej i podpisu. Heurystyka Fiata-Shamira jest koniem roboczym leżącym pod ogromnym wachlarzem nowoczesnych podpisów cyfrowych i systemów dowodów wiedzy zerowej, w tym tych dziś kluczowych dla kryptografii chroniącej prywatność i opartej na blockchainie.⁶

Nić przewodnia

Shamir jest bezpieczeństwowym zwornikiem tej serii — postacią, która czyni resztę stosu godną zaufania. Tim Berners-Lee zbudował sieć przeznaczoną dla wszystkich, ale sieć, w której można robić zakupy, korzystać z bankowości i swobodnie się wypowiadać, zależy całkowicie od kryptografii klucza publicznego — od jej połączeń TLS i podpisanych certyfikatów — co znaczy, że zależy od RSA i dziedziny, którą Shamir pomógł założyć. Thompson i Ritchie dali nam systemy, na których działamy, oraz, w „Reflections on Trusting Trust”, założycielskie ostrzeżenie, że nie da się ufać temu, czego nie zbadało się przeciwniczo — dokładnie ten instynkt, na którym Shamir zbudował karierę. A Leslie Lamport dał systemom rozproszonym dyscyplinę precyzyjnego definiowania poprawności i dowodzenia jej, przeciwko bizantyjskim przeciwnikom zachowującym się dowolnie; podział sekretu Shamira to ten sam impuls w postaci kryptograficznej, prymityw z dowodem zamiast nadziei. Tam, gdzie Berners-Lee mówi to jest dla wszystkich, a Thompson mówi nie ufaj niczemu, czego sam nie zbudowałeś, Shamir mówi: zbuduję ci coś bezpiecznego, a potem spędzę życie, próbując to złamać — bo to jedyny sposób, byśmy oboje wiedzieli, że jest prawdziwe. (Pomost serii)

Co z tego wynoszę

Lekcją, którą zachowuję po Shamirze, jest ufaj tylko temu, co przetrwa atak. Mój instynkt, jak u większości twórców, każe traktować działający kod jako dowód — testy przechodzą, demonstracja działa, wysyłamy. Kryptografia zabrania tej wygody, bo system złamany i solidny wyglądają identycznie, dopóki ktoś ich nie zaatakuje, a odpowiedzią Shamira jest być tym kimś pierwszym. Złamał szyfry plecakowe; on i Adleman łamali kandydujące schematy Rivesta, aż RSA przetrwało; on i Biham złamali DES na tyle dotkliwie, by obnażyć to, co agencje wywiadowcze ukrywały przez dwadzieścia lat. Gdy więc buduję teraz coś — przepływ uwierzytelniania, granicę uprawnień, potok danych — staram się założyć kapelusz atakującego, zanim zrobi to atakujący, by założyć, że istnieje rysa, i ruszyć na jej poszukiwanie, zamiast czekać, aż ktoś mi o niej powie. Pewność, która się liczy, to nie „nie widzę, jak to się łamie”; to „usilnie próbowałem to złamać i nie mogłem”.

Druga lekcja brzmi: najpotężniejsze mechanizmy to czysta matematyka odczytana we właściwy sposób. Podział sekretu nieco mnie zaskoczył, gdy pierwszy raz go zrozumiałem — to zaledwie szkolny fakt, że punkty wyznaczają wielomian, a mimo to daje sekret dowodliwie, teorioinformacyjnie bezpieczny. Shamir nie wynalazł trudniejszej matematyki; dostrzegł, że matematyka, którą już miał, była, z pewnego kąta, dokładnie prymitywem bezpieczeństwa. To zmieniło sposób, w jaki patrzę na struktury już przede mną. Funkcja skrótu, której używam do wyszukiwań, może być zobowiązaniem; nadmiarowość, którą dodałem dla niezawodności, może być schematem progowym; ograniczenie, które potraktowałem jako utrapienie, może być zamkiem. Umiejętność nie zawsze polega na wynalezieniu czegoś nowego — polega na rozpoznaniu, że czysta rzecz, którą już rozumiesz, obrócona we właściwą stronę, jest mechanizmem, którego potrzebowałeś.

FAQ

Z czego znany jest Adi Shamir?

Adi Shamir to izraelski kryptograf i profesor Instytutu Naukowego Weizmanna, najbardziej znany jako „S” w RSA — pierwszym praktycznym kryptosystemie z kluczem publicznym, który współtworzył z Ronem Rivestem i Leonardem Adlemanem w MIT w 1977 roku. Cała trójka otrzymała wspólnie Nagrodę Turinga ACM z 2002 roku za tę pracę. Wynalazł również podział sekretu Shamira (1979), współodkrył kryptoanalizę różnicową z Elim Bihamem oraz współtworzył heurystykę Fiata-Shamira, a do tego dołożył wiele innych wkładów do kryptografii.¹²

Czym jest podział sekretu Shamira?

To metoda, opublikowana przez Shamira w 1979 roku w pracy „How to Share a Secret”, dzielenia sekretu między n osób tak, by dowolnych k z nich mogło go odtworzyć, lecz dowolne k-1 nie dowiadywało się niczego. Sekret ukryty jest jako wyraz wolny losowego wielomianu stopnia k-1, a każda osoba otrzymuje jeden punkt tej krzywej. Ponieważ k punktów jednoznacznie wyznacza wielomian stopnia k-1, dowolne k udziałów odtwarza sekret — natomiast mniej niż k pozostawia go „całkowicie nieokreślonym”, co daje schematowi bezpieczeństwo teorioinformacyjne.³

Czym jest „S” w RSA i jak działa RSA?

„S” to Shamir; RSA to skrót od Rivest, Shamir i Adleman. RSA to kryptosystem z kluczem publicznym: każdy użytkownik ma klucz publiczny, którego każdy może użyć, by zaszyfrować do niego wiadomości lub zweryfikować jego podpisy, oraz klucz prywatny, który tylko on posiada. Jego bezpieczeństwo opiera się na zapadni — klucz publiczny zbudowany jest z iloczynu dwóch dużych liczb pierwszych, a odzyskanie klucza prywatnego wymaga faktoryzacji tego iloczynu z powrotem na jego liczby pierwsze, co dla dostatecznie dużych liczb jest obliczeniowo niewykonalne. RSA opublikowano w Communications of the ACM w 1978 roku.²

Czym jest kryptoanaliza różnicowa?

Kryptoanaliza różnicowa to ogólna technika, publicznie odkryta przez Elego Bihama i Adiego Shamira pod koniec lat 80., atakowania szyfrów blokowych poprzez badanie, jak różnice między parami wejść propagują się do różnic na wyjściu. Statystyczne nierównowagi w tej propagacji mogą przeciekać informacje o tajnym kluczu; Biham i Shamir użyli jej, by znaleźć teoretyczną słabość w DES. Później okazało się, że IBM i NSA znały tę technikę od połowy lat 70. i utrzymywały ją w tajemnicy, potajemnie projektując DES tak, by jej się opierał.⁴⁵

Źródła