Po przestudiowaniu Części V powinieneś być w stanie:

•  Definiować wymagania matematyczne dla prostego głębokiego uczenia się
•  Wykonywać zadania matematyczne skalarne, wektorowe i macierzowe
•  Zrównać naukę z optymalizacją

Po przestudiowaniu Części IV powinieneś być w stanie:

•  Zrozumieć frameworki
•  Umieć skorzystać z podstawowego frameworka
•  Pracować z TensorFlow

Po przestudiowaniu Części III powinieneś być w stanie:

•  Uzyskąć kopię Pythona
•  Zrozumieć interakcję z notatnikiem Jupyter
•  Tworzyć podstawowy kod w Pythonie
•  Poznać pracę w chmurze

Po przestudiowaniu Części II powinieneś być w stanie:

•  Rozważyć na czym polega uczenie maszynowe
•  Zrozumieć metody wykorzystywane do osiągnięcia uczenia maszynowego
•  Wykorzystywać uczenie maszynowe do właściwych powodów

Po przestudiowaniu Części I powinieneś być w stanie:

•  Zrozumieć głębokie uczenie
•  Zrozumieć pracę z głębokim uczeniem
•  Zrozumieć tworzenie aplikacji do głębokiego uczenia
•  Zrozumieć ograniczenia uczenia głębokiego

Wstęp i przegląd historyczny, czyli o co w tym wszystkim chodzi?

Algorytmy i dane

Języki programowania i paradygmaty

Metody algorytmiczne

Poprawność algorytmów

Wydajność algorytmów

Ograniczenia i wytrzymałość

Nieobliczalność i nierozstrzygalność

Uniwersalność algorytmów i ich wytrzymałość

Modele równoległości, współbieżności i alternatywne

Algorytmy probabilistyczne

Gra w pokera przez telefon

Funkcje kryptograficzne klucza publicznego mogą być używane w wielu pozornie niepowiązanych aplikacjach. Rozważ dwie osoby, Alice i Bob, którzy chcą grać w pokera przez telefon. Można założyć, że każdy gracz ma dostęp do komputera na wypadek, gdyby w trakcie gry wykonywał obliczenia, a informacje cyfrowe mogą być przesyłane linią telefoniczną. Nie ma neutralnego sędziego, który rozda karty lub który ma ogólną wiedzę na temat rąk graczy i/lub kart pozostających w talii; wszystko musi być wykonane przez samych dwóch graczy. Nietrudno wyobrazić sobie mniej zabawne sytuacje o podobnym charakterze, takie jak cyfrowe negocjacje kontraktowe. Oczywiście każdy gracz musi mieć pewne informacje, które mogą być utrzymywane w tajemnicy podczas gry, takie jak jego ręka z kartami. Teraz, w zwykłej grze twarzą w twarz, gracz nie może twierdzić, że ma asa, chyba że jest w stanie to zademonstrować, odsłaniając asa jako jedną z posiadanych kart. Elektronicznym odpowiednikiem tego jest czekanie, aż gra się skończy, a następnie umożliwienie każdemu graczowi sprawdzenie całej sekwencji ruchów drugiego, w tym jego prywatnych działań. Zapobiegnie to zwykłym oszustwom. Oszukiwanie to jednak nie jedyny problem. Trochę namysłu pokazuje, że rozdawanie kart stanowi prawdziwe wyzwanie. Musimy zaprojektować protokół, który zaczyna się od 52 (reprezentowanych cyfrowo) kart i powoduje, że każdy z dwóch graczy ma losową rękę składającą się z pięciu kart, a pozostałe 42 pozostają w stosie do wykorzystania w przyszłości. Tym, co sprawia, że problem nie jest trywialny, jest to, że musimy upewnić się, że żaden z graczy nie zna ręki drugiego gracza. Na pierwszy rzut oka wydaje się to niemożliwe. Możemy zacząć od zaszyfrowania i przetasowania kart. Ponieważ jednak przynajmniej jeden z graczy musi być w stanie odszyfrować używane szyfrowanie, wydaje się, że jeden z nich będzie wiedział, która z kart została rozdana drugiemu lub że jeden z nich będzie w stanie zaaranżować żeby mieć szczególnie dobrą rękę. Czy możemy zalecić uczciwą i losową ofertę? Odpowiedź brzmi tak. Pomysł polega na użyciu jednokierunkowych funkcji pułapek, jak w kryptografii klucza publicznego, ale w tym przypadku wymagamy, aby były przemienne; to znaczy dla każdej wiadomości M musimy mieć:

Encr_B(Encr_A (M)) = Encr_A (Encr_B (M))

Gwarantuje to, że jeśli wiadomość jest zaszyfrowana przez Alicję, a następnie przez Boba, może zostać odszyfrowana najpierw przez Alicję, a następnie przez Boba, ponieważ podwójne szyfrowanie da Encr_B (Encr_A (M)), co jest takie samo jak Encr_B (Encr_B(M )), przy czym odszyfrowanie Alicji przyniesie Decr_A (Encr_A (Encr_B (M))), co jest po prostu Encr_B (M), a na koniec odszyfrowanie Boba da Decr_B (Encr_B (M)), który jest po prostu oryginalnym M. Można wykazać, że funkcje RSA spełniają ten dodatkowy wymóg przemienności, a zatem wydają się być odpowiednie również dla niniejszego zastosowania. Jeśli chodzi o zamknięte pudełka, przemienność oznacza, że zatrzask ma wystarczająco dużo miejsca na dwie kłódki, które można zatrzasnąć obok siebie w dowolnej kolejności, a nie jedna nad drugą. W ten sposób pierwsza kłódka do założenia nie musi być usuwana jako ostatnia. Tak jak poprzednio, każdy gracz zaczyna od wybrania własnych funkcji Encr i Decr. Jednak, w przeciwieństwie do kryptografii z kluczem publicznym, żadna informacja nie jest upubliczniana przed zakończeniem gry, nawet funkcje szyfrowania. Oto jak nasi gracze Alice i Bob rozdają sobie pięć kart z 52 talii. Alice używa własnej funkcji szyfrowania EncrA do zaszyfrowania opisów 52 kart. Przypomnij sobie, że cała sekwencja gry jest później sprawdzana, gdy funkcje obu graczy są ujawnione, aby Alicja nie mogła zaszyfrować nielegalnego zestawu kart, mając, powiedzmy, 20 asów. Używając rzucania monetą lub w jakikolwiek inny sposób, Alicja tasuje zaszyfrowaną talię i wysyła wynikową listę do Boba. Mimo że dokładnie wie, jak wyglądają 52 zaszyfrowane wiadomości po odszyfrowaniu, nie ma możliwości dowiedzenia się, która karta jest która, ponieważ docierają one w nieznanej mu kolejności, a Encr_A i Decr_A są ściśle strzeżonymi tajemnicami Alicji. Teraz czas na samo rozdanie. Bob wybiera 10 zaszyfrowanych kart, z których pięć szyfruje po raz drugi za pomocą własnej funkcji Encr_B. Następnie wysyła Alice wszystkie 10. Tak więc Bob ma teraz 42 pudełka zamknięte na kłódkę Alice, a Alice ma 10 - pięć zamkniętych na własną kłódkę i pięć zamkniętych na obie kłódki. Alice odblokowuje teraz własne 10 zamków; to znaczy, Alice odszyfrowuje 10 wiadomości otrzymanych od Boba za pomocą jej funkcji deszyfrującej Decr. Pierwsze pięć z nich staje się teraz niezaszyfrowanymi opisami kart i odtąd Alicja uważa je za swoją rękę. Pozostałe pięć jest nadal zablokowanych za pomocą Encr_B (tutaj jest potrzebna przemienność - czytelnik powinien to sprawdzić), a Alicja odsyła je z powrotem do Boba. Po otrzymaniu, Bob odblokowuje je za pomocą Decr_B, odsłaniając w ten sposób własną rękę z pięcioma kartami. Ręce są oczywiście rozłączne i różnią się od pozostałych 42 kart. Co więcej, żaden z graczy nie wie, jaka jest ręka drugiego gracza. Bob nie wie nic o ręce Alicji, chociaż Bob był tym, który faktycznie rozdał karty, ponieważ wybrał 10 kart z potasowanej talii, która została zaszyfrowana za pomocą funkcji, której nie potrafi odszyfrować. Podobnie Alicja nie wie nic o ręce Boba, chociaż Alicja wie, jak odszyfrować oryginalne szyfrowanie, ponieważ pięć kart Boba zostało zaszyfrowanych po raz drugi (przez Boba) przy użyciu funkcji, której Alicja nie ma możliwości odszyfrowania. W ten sposób transakcja wydaje się być ważna, uczciwa i tak samo bezpieczna, jak każda metoda handlowania. Teraz nie powinieneś mieć trudności z ustaleniem, jak toczy się gra. Jedyną nietrywialną częścią jest sytuacja, w której gracz musi wziąć nową kartę z pozostałego stosu, procedura, którą można przeprowadzić przy użyciu dokładnie tego samego pomysłu, co przy rozdawaniu pierwszych rąk. Pomimo tych faktów okazuje się, że istnieją dość poważne problemy, jeśli chodzi o wdrożenie tego protokołu handlu. Wykazano na przykład, że funkcje szyfrowania RSA są tutaj niewystarczające. Chociaż wiadomości zaszyfrowanych przy ich użyciu nie można, o ile wiemy, faktycznie odszyfrować w rozsądnym czasie, pewne częściowe informacje można z nich wydobyć. W ten sposób można manipulować zaszyfrowaną wersją karty i ustalić pewne matematyczne właściwości jej oryginalnej (cyfrowej) wersji, które wynikają ze szczególnego sposobu definiowania funkcji RSA. Na przykład może być możliwe sprawdzenie, czy liczba kodująca kartę ma taką samą resztę po podzieleniu przez jakąś specjalną liczbę pierwszą, jak inna liczba kwadratowa. To trochę tak, jakby powiedzieć, że jeden gracz może określić kolor (czerwony lub czarny) kart drugiego - jest to oczywiście niedopuszczalny kompromis w większości gier karcianych. Jednym z doraźnych sposobów przezwyciężenia takich problemów jest opisanie przez Alicję kart przed zaszyfrowaniem w swoim własnym, nieformalnym języku, dokładna forma, jaką przybiera opis, jest nieznana Bobowi z wyprzedzeniem lub wstawienie do nich losowych liter i cyfr; podobny pomysł zostałby wykorzystany przez Boba. Wydaje się, że w ten sposób jeden gracz nie mógłby nic zyskać znając takie arytmetyczne właściwości oryginalnych, nieprzewidywalnych opisów kart drugiego gracza. Powinniśmy jednak zdać sobie sprawę, że takie podejście może nie być naprawdę bezpieczne, ponieważ nie możemy udowodnić że nie wyciekają żadne istotne informacje o kartach. Rzeczywiście odkryto inne, bezpieczniejsze protokoły rozdawania kart. Same są probabilistyczne, ale są znacznie bardziej skomplikowane niż opisana tutaj prosta i elegancka.

Kryptosystem RSA

Około rok po pojawieniu się koncepcji kryptosystemów z kluczem publicznym, znaleziono pierwszą metodę jej wdrożenia. Powstały system, nazwany Kryposystem RSA, od inicjałów jego wynalazców, jest opisany tutaj. Od tego czasu zaproponowano kilka innych definicji, z których niektóre w konsekwencji okazały się nie być bezpieczne. Podejście RSA pozostaje jednak jednym z najciekawszych z nich wszystkich i, jak wyjaśniono później, istnieją powody, by sądzić, że jest naprawdę nie do złamania. Ważne jest, aby zrozumieć, co to znaczy, że kryptosystem klucza publicznego został złamany lub scrackowany. Ponieważ integralność systemu klucza publicznego zależy od trudności obliczenia funkcji Decr bez odpowiednich kluczy, złamanie takiego systemu wiąże się ze znalezieniem szybkiego algorytmu obliczania funkcji Decr przy znajomości odpowiedniej funkcji Encr. Jeśli używane są podpisy, można posiadać również wiedzę o kilku przykładowych wiadomościach M i ich szyfrogramach Decr (M). Tak więc, chociaż złamanie pewnych konwencjonalnych metod kryptograficznych może wymagać szczęśliwych zgadnięć lub wyrafinowanych sposobów na znalezienie jakiegoś tajnego kodu lub liczby, złamanie kryptosystemów z kluczem publicznym jest tak naprawdę równoznaczne ze znalezieniem sprytnych algorytmów czasu wielomianowego dla pewnych problemów, które uważa się za możliwe. nieodłączne zachowanie superwielomianu w czasie. I to jest praca algorytmiczna par excellence. System RSA opiera się na kontraście między testowaniem pierwszości a faktoringiem. To pierwsze, jak widzieliśmy, można przeprowadzić bardzo szybko, przy użyciu algorytmu probabilistyki , a być może w przyszłości również przy użyciu szybkiej wersji nowego nieprobabilistycznego algorytmu wielomianowego. Jednak dla tych ostatnich nie ma znanych szybkich metod, nawet probabilistycznych, a faktoring jest faktycznie przypuszczalny, że nie jest nawet w probabilistycznej/randomizowanej klasie RP. Każda ze stron, powiedzmy Alice, potajemnie i losowo, wybiera dwie duże liczby pierwsze P i Q, o długości powiedzmy około 300 cyfr, i mnoży je, w wyniku czego iloczyn N = P × Q. Alicja zachowuje w tajemnicy liczby pierwsze, ale upublicznia ich iloczyn (oraz inną ilość, jak wyjaśniono później). czynniki pierwsze w rozsądnym czasie. Oto szczegóły.

Przed wybraniem dwóch liczb pierwszych Alicja musi wybrać inną liczbę, G, zwaną wykładnikiem publicznym. Powinna to być liczba nieparzysta, najlepiej pierwsza i nie musi być zbyt duża. Ta liczba może być taka sama dla wszystkich uczestników; ulubionym wyborem jest pierwszy 2¹⁶ + 1 = 65 537. Wybierając liczby pierwsze P i Q, Alicja musi upewnić się, że ani P ? 1, ani Q ? 1 nie mają żadnych wspólnych czynników z G, z wyjątkiem oczywiście trywialnego czynnika 1. Na koniec Alicja oblicza swój prywatny wykładnik K, być multiplikatywną odwrotnością G modulo (P - 1) × (Q - 1), co oznacza, że K × G daje resztę 1 po podzieleniu przez (P - 1) × (Q - 1). Symbolicznie:

K × G ≡ 1 (mod (P - 1) × (Q - 1))

To kończy proces wyjścia Alice i kupowania kłódki i klucza. Kłódką jest para G, N , która jest upubliczniana, a tajnym kluczem jest K. Czynniki pierwsze N, a mianowicie P i Q, również są utrzymywane w tajemnicy. Aby być całkiem precyzyjnym, powinniśmy wskazać, że są to wszystkie liczby Alicji, zapisując je jako P_A, Q_A, N_A, K_A i G_A. Inne strony wybierają własne numery P_B, P_C , Q_B, Q_C itd. Jak wyglądają procedury szyfrowania i deszyfrowania? Załóżmy, że Bob chce wysłać wiadomość M do Alicji. Aby go zaszyfrować, używa publicznej pary Alice (G_A, N_A) . Bob najpierw dzieli M na bloki liczb, każdy z przedziału od 0 do N_A - 1. Dalej możemy założyć, że istnieje tylko jedna taka liczba M, ponieważ cały proces jest przeprowadzany dla każdej z nich. Aby uzyskać tekst zaszyfrowany H, Bob podnosi M do potęgi G_A, modulo N_A:

H = Encr_A(M) = M^G_A (mod N_A)

Oznacza to, że H jest resztą uzyskaną po podzieleniu M^G_A przez N_A. To kończy definicję procedury szyfrowania. Zauważ, że ponieważ cała arytmetyka jest wykonywana modulo N_A, wszystkie zaangażowane liczby mieszczą się w zakresie od 0 do N_A - 1, więc zarówno wiadomość, jak i jej zaszyfrowany tekst znajdują się w tym samym zakresie liczb. Deszyfrowanie jest bardzo podobne: Alicja po otrzymaniu zaszyfrowanego tekstu H podnosi go do mocy swojego tajnego klucza K_A, również modulo N_A. Zatem:

Decr_A (H) = H^K_A (mod N_A)
v Pochodzenie terminów wykładnik publiczny i wykładnik prywatny powinno być teraz jasne. Teraz łatwo zauważyć, że:

Decr_A (Encr_A (M)) = Encr_A (Decr_A (M)) ≡ MG_^A×K_A (mod N_A)

Nie jest to takie łatwe do zauważenia, ale mimo wszystko prawdą jest, że w szczególny sposób K_A zostało wyprowadzone z G_A, P i Q, ta ostatnia liczba to po prostu M (mod N_A), więc odszyfrowanie zaszyfrowanej wiadomości daje wiadomość w swojej pierwotnej formie. Fakt, że nie tylko Decr_A (Encr_A (M)) daje M, ale także Encr_A (Decr_A (M)) i że jest to prawdą dla każdego M, sprawia, że metoda RSA pasuje również do sygnatur. Oczywiście musimy pokazać, w jaki sposób wszystkie obliczenia mogą być rzeczywiście wykonane efektywnie i że Decr_A (M) nie można obliczyć bez znajomości klucza K_A Alicji. Cały proces konfiguracji zaczyna się od tego, że każda ze stron wybiera dwie duże liczby pierwsze, co można osiągnąć bezboleśnie przy użyciu szybkiego algorytmu testowania pierwszości, wielokrotnie dla losowych 300-cyfrowych liczb, jak wyjaśniono wcześniej. Oczywiście szansa, że dwie strony wymyślą dokładnie te same liczby pierwsze, jest znikoma. Ostatnim krokiem przygotowania jest obliczenie K z G, P i Q (pomijamy tutaj indeks A dla jasności). To, jak również rzeczywiste obliczenia MG i HK modulo N, można przeprowadzić dość szybko przy użyciu stosunkowo prostych procedur dla potęgowania modulo N i dla pewnej wersji algorytmu największego wspólnego dzielnika (gcd). Pominięto szczegóły, ponieważ mają one nieco techniczny charakter. Jeśli chodzi o bezpieczeństwo systemu RSA, można wykazać, że jeśli rozłożymy duże liczby w rozsądnym czasie, system zostanie natychmiast zepsuty, ponieważ wtedy przeciwnik może wziąć produkt publiczny N, znaleźć jego czynniki (tj. dwie tajne liczby pierwsze P i Q) i użyj ich, wraz z publicznym wykładnikiem G, do obliczenia prywatnego wykładnika K. Podwójnie, wszystkie podejścia sugerowane do tej pory w celu złamania systemu RSA wykazały, że aby zadziałać, muszą dać szybkie rozwiązania problemu faktoringowego. Innymi słowy, na chwilę obecną dla każdego podejścia sugerowanego jako atak na bezpieczeństwo systemu RSA wykazano, że albo to nie zadziała, albo że jeśli w zasadzie zadziała, to skutkuje szybkim algorytmem faktoring. Ponieważ jednak faktoring jest mocno przypuszczany, że nie ma szybkiego algorytmu, nawet probabilistycznego, a żaden z proponowanych ataków na system RSA nie dał takiego algorytmu, ludzie mocno wierzą, że RSA jest bezpieczny. Istnieje nieco inna wersja systemu RSA, której bezpieczeństwo jest dowodem na to, że szybki faktoring. Innymi słowy, wykazano, że każda metoda złamania tego konkretnego kryptosystemu da szybki algorytm faktoryzacji. Oczywiście, ponieważ nie znamy dokładnego statusu problemu faktoringu, nie jest jasne, czy ten kryptosystem jest lepszy czy gorszy od oryginalnego RSA. Warto ponownie podkreślić fundamentalne aspekty algorytmiki, które są zaangażowane w takie idee, jak kryptosystem RSA. Obejmują one konwencjonalne algorytmy sekwencyjne, pozornie nierozwiązywalne problemy algorytmiczne, algorytmy probabilistyczne, a jeśli metoda ma działać w miarę szybko na dużych liczbach, to albo bardzo wydajne programowanie, albo projektowanie sprzętu specjalnego przeznaczenia.

Kryptografia klucza publicznego

W 1976 roku zaproponowano nowatorskie podejście do problemów z szyfrowaniem, deszyfrowaniem i podpisem, kryptosystem klucza publicznego. Być może najlepiej tłumaczy to wariant metafory zamkniętego pudełka. Pomysł polega na użyciu innego rodzaju kłódki, takiej, którą można zamknąć bez klucza, po prostu zatrzaśniętej. Otwarcie takiego zamka wymaga jednak klucza. Aby skonfigurować mechanizm wymiany tajnych informacji, każdy potencjalny użytkownik systemu wychodzi na własną rękę i kupuje taką kłódkę i klucz. Następnie zapisuje swoje imię na kłódce i kładzie ją na stole, w miejscu publicznym. Klucz pozostaje jednak u nabywcy. Załóżmy teraz, że strona B (powiedzmy Bob) chce wysłać wiadomość do strony A (powiedzmy Alice). Bob wkłada wiadomość do pudełka, podchodzi do stołu, podnosi kłódkę Alicji i zamyka nią pudełko. Do tego nie jest potrzebny klucz. Pudełko jest następnie wysyłane do Alice, która używa swojego klucza do otwarcia zamka i przeczytania wiadomości. Nikt poza Alicją nie ma klucza, dzięki czemu wiadomość jest bezpieczna. Zauważ, że nie jest wymagana żadna wcześniejsza komunikacja ani współpraca między Alicją i Bobem. Gdy jakakolwiek strona zdecyduje się dołączyć do gry, kupi kłódkę i upubliczni ją, ta strona może zacząć otrzymywać wiadomości. Aby zrozumieć, w jaki sposób systemy z kluczem publicznym mogą być używane w cyfrowych, skomputeryzowanych środowiskach, załóżmy, że wiadomości są (być może długimi) sekwencjami cyfr. Tak więc pewna bezpośrednia i prosta metoda tłumaczenia symboli na cyfry został już zastosowany. Kłódka Alicji to po prostu funkcja szyfrowania Encr_A, która przekształca liczby na inne liczby, a klucz Alicji jest sekretnym sposobem obliczania funkcji deszyfrowania Decr_A. W ten sposób każda ze stron upublicznia swoją procedurę szyfrowania, ale zachowuje swoją procedurę deszyfrowania jako prywatną. Aby wysłać wiadomość do Alicji, Bob używa publicznej procedury szyfrowania Alicji Encr_A i wysyła Alicji numer Encr_A(M). Teraz Alicja może to rozszyfrować, korzystając z prywatnej procedury Decr_A. Aby metoda działała, obie funkcje muszą być łatwe do obliczenia, a równanie dualności Decr_A( Encr_A(M)) = M musi być przechowywany dla każdej wiadomości M. Co jednak najważniejsze, nie powinno być możliwe wywnioskowanie metody obliczania funkcji deszyfrującej Decr_A na podstawie publicznie znanej funkcji szyfrowania Encr_A. Tutaj "niemożliwe" naprawdę oznacza "niewykonalne obliczeniowo", tak więc to, czego naprawdę potrzebujemy, to odpowiedni rodzaj jednokierunkowej funkcji zapadni; to znaczy funkcję Encr dla każdego użytkownika, którą łatwo obliczyć, powiedzmy w czasie wielomianu niższego rzędu, ale której funkcji odwrotnej Decr nie można obliczyć w czasie wielomianu, chyba że tajny klucz tego użytkownika jest znany. Analogia do zapadni jest oczywista: zapadnia nie może zostać aktywowana, dopóki nie jest znane istnienie lub położenie tajnej dźwigni lub przycisku. Później omówimy takie funkcje. Jeśli chodzi o podpisy, to oczywiste jest, że w przeciwieństwie do podpisu odręcznego, podpis cyfrowy, który ma być użyty w skomputeryzowanym kryptosystemie, musi być funkcją nie tylko strony podpisującej, ale także podpisanej wiadomości. W przeciwnym razie odbiorca może wprowadzić zmiany w podpisanej wiadomości przed pokazaniem jej neutralnemu sędziemu, a nawet dołączyć podpis do zupełnie innej wiadomości. Jeśli wiadomość jest poleceniem przelewu pieniężnego, odbiorca może po prostu dodać kilka kluczowych zer do sumy i stwierdzić, że nowa podpisana wiadomość jest autentyczna. Dlatego podpisy muszą być różne dla różnych wiadomości. Aby użyć jednokierunkowych funkcji pułapek do podpisywania wiadomości, wymagamy, aby funkcje Encr i Decr były przemienne, to znaczy, że odszyfrowanie jakiejkolwiek zaszyfrowanej wiadomości powinno dać tę wiadomość w jej oryginalnej formie, ale także szyfrowanie odszyfrowanej wiadomości musi dać oryginalną wiadomość. W związku z tym wymagamy dla każdej ze stron A zarówno: Decr_A( Encr_A(M)) = M i Encr_A (Decr_A(M)) = M Ponieważ komunikat jest tylko liczbą, a zarówno Encr_A, jak i Decr_A są funkcjami na liczbach, ma sens, przynajmniej matematycznie, zastosowanie Decr_A do komunikatu M. Ale jaki to ma sens praktyczny? Dlaczego ktokolwiek miałby być zainteresowany zastosowaniem funkcji deszyfrowania do niezaszyfrowanej wiadomości? Odpowiedź jest prosta. Aby to podpisać! Oto jak to działa



Jeśli Bob chce wysłać Alicji podpisaną wiadomość M, Bob najpierw oblicza swoją specjalną sygnaturę zależną od wiadomości S, stosując własną prywatną funkcję deszyfrującą DecrB do M. W ten sposób: S = Decr_B(M) Następnie szyfruje podpis S w zwykły sposób z kluczem publicznym, używając publicznej funkcji szyfrowania Alicji Encr_A i wysyła wynik, a mianowicie Encr_A (Decr_B(M)), do Alicji. Po otrzymaniu tego dziwnie wyglądającego numeru, Alice najpierw odszyfrowuje go za pomocą swojej prywatnej funkcji deszyfrującej Decr_A. Wynikiem jest Decr_A( Encr_A(S)), co w rzeczywistości jest Decr_A (Encr_A (Decr_B(M))). Jednak ponieważ Decr_A cofa wszystko, co Encr_A związał, wynikiem tego będzie po prostu S lub Decr_B( (M). (Zauważ, że Alicja nie może jeszcze odczytać wiadomości M, ani nie jest w żaden sposób przekonana, że Bob był naprawdę nadawcą.) Wreszcie, Alicja stosuje publiczną funkcję szyfrowania Boba EncrB do S, otrzymując Encr_B (S) = Encr_B (Decr_B (M)) = M. W ten sposób Alicja widzi wiadomość M i może być całkiem pewna, że tylko Bob mógł ją wysłać. Wynika to z faktu, że funkcje są takie, że żadna liczba nie da w wyniku M po poddaniu Encr_B, chyba że liczba ta była dokładnie Decr_B(M), i nikt poza Bobem nie mógł wytworzyć Decr_B (M), ponieważ funkcja deszyfrująca Decr_B jest Ściśle strzeżony sekret Boba. Co więcej, Alicja nie może podpisać żadnej innej wiadomości w imieniu Boba, ponieważ podpisywanie pociąga za sobą zastosowanie tajnej funkcji Boba Decr_B do nowej wiadomości. Jednak nadal istnieje możliwość, że Alicja będzie mogła wysłać tę samą wiadomość M do kogoś innego, powiedzmy Carol, ale z podpisem Boba. Powodem jest to, że podczas tego procesu Alicja jest w posiadaniu Decr_B (M), który może następnie zaszyfrować za pomocą Encr_C, wysyłając wynik do Carol, która pomyśli, że pochodzi od Boba. Może to mieć kluczowe znaczenie w przypadku, gdy komunikat M brzmi "Ja, generał Bob, niniejszym rozkazuję ci wyruszyć na następującą niebezpieczną misję: . . ". Aby zapobiec takiej sytuacji, imię i nazwisko odbiorcy wiadomości (i ewentualnie także data) powinny być zawsze podane, tak jak w "Ja, generał Bob, niniejszym rozkazuję ci, major Alice, abyś wyruszył z następującą niebezpieczną misją: . . ". Takie psoty w imieniu Alice (i na koszt Carol) stałyby się wtedy niemożliwe. Oczywiście oznacza to, że Alicja nie może obliczyć funkcji Decr_B bez odpowiedniego klucza, nawet dla nieco zmodyfikowanej wiadomości M, która jest bardzo zbliżona do wiadomości M, dla której ma dostęp do Decr_B (M). Koncepcja kryptografii klucza publicznego brzmi zatem bardzo obiecująco. Jednak aby to zadziałało, musimy znaleźć odpowiednie definicje kluczy i odpowiadające im procedury Encr i Decr, które cieszą się wszystkimi przyjemnymi właściwościami, które omówiliśmy. Innymi słowy, interesują nas jednokierunkowe funkcje zapadni, a jeśli chcemy użyć funkcji sygnatury, muszą one również spełniać właściwość wzajemnej odwrotności. Nie jest wcale jasne, czy takie funkcje istnieją. W rzeczywistości można by argumentować, że wymagania są paradoksalne, niemal wewnętrznie sprzeczne. Gdzie znajdziemy funkcję jednokierunkową z naprawdę trudną do obliczenia odwrotnością? Na przykład wzięcie pierwiastka kwadratowego nie jest o wiele trudniejsze niż jego odwrotność, podniesienie do kwadratu, a poruszanie się wstecz w alfabecie jest tak proste, jak poruszanie się do przodu. Ponadto trudny kierunek musi stać się łatwy do obliczenia, jeśli znany jest tajny klucz. Czy są takie funkcje? Zobaczymy teraz, że są, ale trudność obliczenia odwrotności bez klucza będzie polegać na domniemanej, a nie udowodnionej niewykonalności. Pytanie, czy istnieją takie funkcje z niewykonalnymi do udowodnienia odwrotnościami, jest nadal otwarte.

Kryptografia i niezawodna interakcja

Przejdźmy teraz do nowego i ekscytującego obszaru zastosowań algorytmiki. Jej nowatorską cechą jest to, że metody stosowane do rozwiązywania problemów w tym obszarze wykorzystują trudność rozwiązywania innych problemów. To samo w sobie jest dość zaskakujące, ponieważ spodziewalibyśmy się, że negatywne wyniki, które ustalają dolne granice rozwiązywania problemów algorytmicznych, nie będą miały żadnej praktycznej wartości, z wyjątkiem zapobiegania próbom poprawy tych granic. Bynajmniej. Kluczowe są tutaj problemy, dla których nie są znane żadne dobre algorytmy. Ogólnie rzecz biorąc, obszar ten dotyczy kryptografii i dotyczy potrzeby komunikowania się w bezpieczny, prywatny i niezawodny sposób. Kryptografia ma wiele różnorodnych zastosowań w kręgach wojskowych, dyplomatycznych, finansowych i przemysłowych. Zapotrzebowanie na dobre protokoły kryptograficzne znacznie wzrasta dzięki szybkiemu rozprzestrzenianiu się komputerowych systemów komunikacyjnych, w szczególności oczywiście Internetu. Coraz częściej komputery stają się odpowiedzialne za przechowywanie, manipulowanie i przesyłanie wszystkiego, od kontraktów, poleceń strategicznych i transakcji biznesowych po zwykłe poufne informacje, takie jak dane wojskowe, medyczne i osobiste. Ta sytuacja z kolei sprawia, że problemy z podsłuchiwaniem i manipulacjami są jeszcze bardziej dotkliwe. Jednym z podstawowych problemów w kryptografii jest szyfrowanie i deszyfrowanie danych. Jak zakodować ważną wiadomość tak, aby odbiorca mógł ją rozszyfrować, a nie podsłuchiwacz? Co więcej, czy wiadomość może być "podpisana" przez nadawcę, aby (1) odbiorca miał pewność, że mógł ją wysłać sam, (2) nadawca nie może później zaprzeczyć, że ją wysłał, oraz (3) odbiorca , po otrzymaniu podpisanej wiadomości, nie może podpisać w imieniu nadawcy żadnej wiadomości, nawet dodatkowych wersji samej wiadomości, która właśnie została odebrana? Kwestia podpisu dotyczy wielu aplikacji, takich jak przekazy pieniężne i umowy elektroniczne. Moglibyśmy długo kontynuować z takimi pytaniami i ich motywującymi przykładami, bo jest ich wiele, a każde rodzi nowe wyzwania. Dla niektórych z nich znaleziono eleganckie i użyteczne rozwiązania, dla innych nie ma. Zaczniemy od skoncentrowania się na problemach z szyfrowaniem i podpisem. Konwencjonalne kryptosystemy oparte są na kluczach. Są one używane do przetłumaczenia wiadomości M na jej zaszyfrowaną formę, zaszyfrowanego tekstu H, a następnie do odszyfrowania jej z powrotem do jej oryginalnej postaci. Jeśli mamy na myśli ogólną procedurę szyfrowania związaną z kluczem przez Encr i odpowiednią procedurę deszyfrowania przez Decr, możemy napisać:

H = Encr (M) i M = Decr (H)

Innymi słowy, zaszyfrowaną wersję H uzyskuje się przez zastosowanie procedury Encr do wiadomości M, a oryginalne M można pobrać z H przez zastosowanie procedury Decr do H. Prosty przykład, którego wszyscy używaliśmy w dzieciństwie, wymaga klucz K jest liczbą z zakresu od 1 do 25, aby Encr była procedurą, która zastępuje każdą literę tą, która znajduje się w K w dalszych pozycjach alfabetu, a Decr ma zamieniać każdą literę na tę znajdującą się wcześniej w K pozycji. W ten sposób Encr i Decr są wzajemnie podwójne; Decr jest odwrotnością Encr. (Dla celów liczenia liter alfabet jest uważany za cykliczny; następuje z.) To standardowe podejście można zilustrować za pomocą metafory zamkniętego pudełka. Aby wymieniać gryps z przyjacielem należy najpierw przygotować skrzynkę z bezpiecznym zatrzaskiem. Następnie kupmy kłódkę z dwoma kluczami, jeden dla nas, a drugi dla naszego przyjaciela. Następnie wysłanie wiadomości polega na włożeniu jej do pudełka, zablokowaniu pudełka za pomocą klucza i wysłaniu pudełka do miejsca przeznaczenia. Nikt nie może odczytać wiadomości po drodze, jeśli nie ma klucza, a ponieważ są tylko dwa klucze, przechowywane przez nadawcę i zamierzonego odbiorcę, system jest dość bezpieczny. Takie podejście ma kilka wad. Po pierwsze, nie odnosi się do kwestii podpisu. Odbiorcy mogą samodzielnie wymyślać fałszywe wiadomości i twierdzić, że zostały wysłane przez nadawcę, a nadawca z kolei może zaprzeczyć, że wysłał wiadomości autentyczne. Kolejna poważna wada dotyczy konieczności współpracy w doborze i bezpiecznej dystrybucji kluczy. Ogólnie rzecz biorąc, w sieć komunikacyjną zaangażowane są więcej niż dwie strony, a aby zapewnić prywatność między dowolnymi dwoma, musi istnieć jakiś bezpieczny sposób dystrybucji par kluczy, po jednym dla każdej pary stron. Biorąc pod uwagę, że główne zastosowania współczesnej kryptografii znajdują się w środowiskach skomputeryzowanych, klucze cyfrowe nie mogą być dystrybuowane tymi samymi (niebezpiecznymi) kanałami komunikacyjnymi, co zaszyfrowane wiadomości. Konieczne byłoby zatem skorzystanie z innych, znacznie droższych metod, takich jak osobiste doręczenie przez zaufanego kuriera. Jest to oczywiście niewykonalne w aplikacjach obejmujących wiele stron.

• Kluczowe Idee
• Przed startem …
• Podstawowe Zachowania
• Badania Użytkowników
• Granice naszych umysłów
• Architektura informacji
• Projektowanie zachowań
• Zasady projektowania wizualnego
• Szkielety i prototypy
• Psychologia użyteczności
• Treść
• Moment Prawdy
• Dane dla projektantów
• Znajdź pracę, ty brudny hipisie

IV Rewolucja Przemysłowa

"Czwarta rewolucja przemysłowa : uogólniająca koncepcja odnosząca się do pojęcia "rewolucji przemysłowej" w związku ze współczesnym wzajemnym wykorzystywaniem automatyzacji, przetwarzania i wymiany danych oraz technik wytwórczych."  (Wikipedia)