Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00506 009008 7434577 na godz. na dobę w sumie
Jak działa oprogramowanie? Tajemnice komputerowych mechanizmów szyfrowania, obrazowania, wyszukiwania i innych powszechnie używanych technologii - ebook/pdf
Jak działa oprogramowanie? Tajemnice komputerowych mechanizmów szyfrowania, obrazowania, wyszukiwania i innych powszechnie używanych technologii - ebook/pdf
Autor: Liczba stron: 232
Wydawca: Helion Język publikacji: polski
ISBN: 978-83-283-2594-4 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> grafika komputerowa >> inne
Porównaj ceny (książka, ebook (-20%), audiobook).
Zawrotny rozwój technologii informatycznych sprawia, że coraz więcej osób chce poznać zasady działania oprogramowania, zwłaszcza tego najpopularniejszego. Bez znajomości pewnych zjawisk łatwo można paść ofiarą tych, którzy już tę wiedzę posiedli. Nie trzeba do tego ukończonych studiów technicznych!

Książka, którą trzymasz w dłoni, opisuje działanie różnych rodzajów oprogramowania. Autor w przystępny i interesujący sposób wyjaśnia trudne i złożone kwestie. Nie musisz być informatykiem ani znać podstaw programowania, aby zrozumieć procesy, które przebiegają w magicznie lśniących układach scalonych, skrytych pod obudową komputera czy smartfona. Ta książka będzie Twoim przewodnikiem!

Dowiedz się, jak działa oprogramowanie:

Sprawdź, jak bardzo fascynujące są tajniki oprogramowania!


V. Anton Spraul — od kilkunastu lat wykłada informatykę dla studentów i początkujących programistów. Jest autorem kilku bardzo popularnych książek, znakomicie ułatwiających zrozumienie zasad programowania. Spraul niezwykle chętnie dzieli się swoją wiedzą. Prowadzi bloga, publikuje filmy na YouTubie. Mieszka w Birmingham w stanie Alabama, a jego pasje, poza informatyką, to tworzenie muzyki i gry komputerowe. Do gier używa sprzętu, który sam zbudował!
Znajdź podobne książki

Darmowy fragment publikacji:

Tytuł oryginału: How Software Works: The Magic Behind Encryption, CGI, Search Engines, and Other Everyday Technologies Tłumaczenie: Zdzisław Płoski ISBN: 978-83-283-2593-7 Copyright © 2015 by V. Anton Spraul Title of English-language original: How Software Works, ISBN 978-1-59327-666-9, published by No Starch Press. Polish-language edition copyright © 2016 by Helion S.A. All rights reserved. All rights reserved. No part of this book may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage retrieval system, without permission from the Publisher. Wszelkie prawa zastrzeżone. Nieautoryzowane rozpowszechnianie całości lub fragmentu niniejszej publikacji w jakiejkolwiek postaci jest zabronione. Wykonywanie kopii metodą kserograficzną, fotograficzną, a także kopiowanie książki na nośniku filmowym, magnetycznym lub innym powoduje naruszenie praw autorskich niniejszej publikacji. Wszystkie znaki występujące w tekście są zastrzeżonymi znakami firmowymi bądź towarowymi ich właścicieli. Autor oraz Wydawnictwo HELION dołożyli wszelkich starań, by zawarte w tej książce informacje były kompletne i rzetelne. Nie biorą jednak żadnej odpowiedzialności ani za ich wykorzystanie, ani za związane z tym ewentualne naruszenie praw patentowych lub autorskich. Autor oraz Wydawnictwo HELION nie ponoszą również żadnej odpowiedzialności za ewentualne szkody wynikłe z wykorzystania informacji zawartych w książce. Wydawnictwo HELION ul. Kościuszki 1c, 44-100 GLIWICE tel. 32 231 22 19, 32 230 98 63 e-mail: helion@helion.pl WWW: http://helion.pl (księgarnia internetowa, katalog książek) Drogi Czytelniku! Jeżeli chcesz ocenić tę książkę, zajrzyj pod adres http://helion.pl/user/opinie/jakdzo Możesz tam wpisać swoje uwagi, spostrzeżenia, recenzję. Printed in Poland. • Kup książkę • Poleć książkę • Oceń książkę • Księgarnia internetowa • Lubię to! » Nasza społeczność Spis tre(cid:258)ci O autorze .................................................................................................................................9 O recenzencie technicznym .....................................................................................................9 Podzi(cid:218)kowania .......................................................................................................................11 Wst(cid:218)p .....................................................................................................................................13 1 SZYFROWANIE ......................................................................................... 17 Cel szyfrowania ......................................................................................................................18 Przestawianie — te same dane, ró(cid:285)ny porz(cid:200)dek ...................................................................19 Klucze szyfrów ...................................................................................................................20 (cid:146)amanie szyfrów ................................................................................................................22 Podstawianie — zast(cid:218)powanie danych ..................................................................................23 Zmienianie wzorca podstawiania .......................................................................................23 Poszerzanie klucza .............................................................................................................25 Zaawansowany standard szyfrowania ....................................................................................26 Podstawy dwójkowe ..........................................................................................................27 Szyfrowanie AES w uj(cid:218)ciu ogólnym ...................................................................................29 Poszerzanie klucza w AES ..................................................................................................30 Rundy szyfrowania AES ......................................................................................................31 (cid:146)a(cid:241)cuchowanie bloków .....................................................................................................33 Dlaczego AES jest bezpieczny ............................................................................................33 Mo(cid:285)liwe ataki na AES .........................................................................................................35 Ograniczenia szyfrowania z kluczem symetrycznym .............................................................36 2 HAS(cid:146)A ..................................................................................................... 37 Przekszta(cid:239)canie has(cid:239)a w liczb(cid:218) ................................................................................................38 Cechy dobrych funkcji haszowania ....................................................................................38 Funkcja skrótu MD5 ...............................................................................................................39 Kodowanie has(cid:239)a ................................................................................................................39 Operacje bitowe ................................................................................................................40 Poleć książkęKup książkę Rundy haszowania MD5 .................................................................................................... 42 Spe(cid:239)nienie kryteriów dobrej funkcji haszowania ............................................................... 43 Podpisy cyfrowe .................................................................................................................... 43 Problem to(cid:285)samo(cid:258)ci .......................................................................................................... 44 Ataki z wykorzystaniem kolizji .......................................................................................... 44 Has(cid:239)a w systemach uwierzytelniania ...................................................................................... 45 Zagro(cid:285)enia dotycz(cid:200)ce tablic hase(cid:239) ..................................................................................... 45 Haszowanie hase(cid:239) .............................................................................................................. 46 Ataki s(cid:239)ownikowe .............................................................................................................. 47 Tablice haszowania ............................................................................................................ 48 (cid:146)a(cid:241)cuchowanie haszowania ............................................................................................... 48 Haszowanie iteracyjne ....................................................................................................... 51 Solenie hase(cid:239) ...................................................................................................................... 52 Czy tablice hase(cid:239) s(cid:200) bezpieczne ......................................................................................... 53 Us(cid:239)uga przechowywania hase(cid:239) ............................................................................................... 54 Przemy(cid:258)lenia ko(cid:241)cowe .......................................................................................................... 55 3 BEZPIECZE(cid:148)STWO W SIECI ...................................................................... 57 Jak kryptografia z kluczem publicznym rozwi(cid:200)zuje problem wspólnego klucza ................... 58 Matematyczne narz(cid:218)dzia kryptografii z kluczem publicznym ............................................... 59 Funkcje odwracalne ........................................................................................................... 59 Funkcje jednokierunkowe ................................................................................................. 60 Funkcje z bocznym wej(cid:258)ciem ............................................................................................ 60 Metoda szyfrowania RSA ....................................................................................................... 63 Tworzenie kluczy .............................................................................................................. 63 Szyfrowanie danych za pomoc(cid:200) RSA ................................................................................. 65 Efektywno(cid:258)(cid:202) RSA ............................................................................................................... 66 Zastosowanie szyfru RSA w rzeczywistym (cid:258)wiecie ........................................................... 68 U(cid:285)ycie RSA do uwierzytelniania ........................................................................................ 71 Bezpiecze(cid:241)stwo w Sieci — protokó(cid:239) HTTPS ........................................................................ 73 Wymiana potwierdze(cid:241) ...................................................................................................... 74 Przesy(cid:239)anie danych protoko(cid:239)em (cid:43)(cid:55)(cid:55)(cid:51)(cid:54) ............................................................................(cid:3)75 Czy problem wspólnego klucza zosta(cid:239) rozwi(cid:200)zany? .............................................................. 77 4 FILM CGI .................................................................................................. 79 Oprogramowanie tradycyjnej animacji .................................................................................. 81 Jak dzia(cid:239)aj(cid:200) obrazy cyfrowe ............................................................................................... 81 Sposoby definiowania kolorów .......................................................................................... 83 Jak oprogramowanie wykonuje animacje celuloidowe ...................................................... 84 Od oprogramowania animacji celuloidowej do renderowanej grafiki 2D ......................... 91 Oprogramowanie trójwymiarowej grafiki CGI ..................................................................... 92 Jak opisuje si(cid:218) sceny trójwymiarowe ................................................................................. 92 Kamera wirtualna .............................................................................................................. 93 4 S p i s t r e (cid:258) c i Poleć książkęKup książkę O(cid:258)wietlenie bezpo(cid:258)rednie .................................................................................................93 O(cid:258)wietlenie ca(cid:239)ego planu ...................................................................................................98 Jak (cid:258)ledzi(cid:202) (cid:258)wiat(cid:239)o ...............................................................................................................99 Wyg(cid:239)adzanie kraw(cid:218)dzi w ca(cid:239)ej scenie ..............................................................................103 (cid:146)(cid:200)czenie rzeczywistego ze sztucznym .................................................................................104 Idea(cid:239) renderowania z jako(cid:258)ci(cid:200) filmow(cid:200) .................................................................................105 5 GRAFIKA GIER ....................................................................................... 107 Sprz(cid:218)t do grafiki tworzonej w czasie rzeczywistym ............................................................108 Dlaczego w grach nie stosuje si(cid:218) (cid:258)ledzenia promieni ...........................................................109 Same odcinki i (cid:285)adnych krzywych ........................................................................................110 Rzutowanie bez (cid:258)ledzenia promieni .....................................................................................110 Renderowanie trójk(cid:200)tów .....................................................................................................112 Algorytm malarza .............................................................................................................113 Buforowanie g(cid:239)(cid:218)boko(cid:258)ci ...................................................................................................113 O(cid:258)wietlanie w czasie rzeczywistym .....................................................................................115 Cienie ...................................................................................................................................117 (cid:165)wiat(cid:239)o otaczaj(cid:200)ce i jego poch(cid:239)anianie ..................................................................................118 Nanoszenie tekstur ..............................................................................................................120 Próbkowanie metod(cid:200) najbli(cid:285)szego s(cid:200)siada .......................................................................121 Filtrowanie dwuliniowe ....................................................................................................123 Mipmapy ..........................................................................................................................124 Filtrowanie trójliniowe .....................................................................................................125 Odbicia .................................................................................................................................126 Fabrykowanie krzywizn .......................................................................................................128 Oszukiwanie na du(cid:285)ych odleg(cid:239)o(cid:258)ciach .............................................................................129 Odwzorowywanie wypuk(cid:239)o(cid:258)ci .........................................................................................129 Mozaikowanie ..................................................................................................................130 Wyg(cid:239)adzanie kraw(cid:218)dzi w czasie rzeczywistym ....................................................................132 Superpróbkowanie ...........................................................................................................132 Wielopróbkowanie ...........................................................................................................134 Poprocesowe wyg(cid:239)adzanie kraw(cid:218)dzi ...............................................................................135 Bud(cid:285)et obrazowania .............................................................................................................136 Co jeszcze w zwi(cid:200)zku z grafik(cid:200) gier .....................................................................................137 6 KOMPRESJA DANYCH ........................................................................... 139 Kodowanie d(cid:239)ugo(cid:258)ci serii ......................................................................................................141 Kompresja s(cid:239)ownikowa ........................................................................................................142 Podstawowa metoda .......................................................................................................143 Kod Huffmana ..................................................................................................................144 Reorganizacja danych w celu lepszej kompresji ...................................................................146 Kodowanie z przewidywaniem ........................................................................................146 Kwantyzacja .....................................................................................................................147 S p i s t r e (cid:258) c i 5 Poleć książkęKup książkę Obrazy w formacie JPEG ..................................................................................................... 148 Inny sposób zapami(cid:218)tywania kolorów ............................................................................. 148 Dyskretna transformacja kosinusowa .............................................................................. 149 DCT w dwóch wymiarach .............................................................................................. 152 Kompresowanie wyników ............................................................................................... 156 Jako(cid:258)(cid:202) obrazów JPEG ...................................................................................................... 159 Kompresja wideo wysokiej rozdzielczo(cid:258)ci .......................................................................... 162 Nadmiarowo(cid:258)(cid:202) czasowa .................................................................................................. 162 Wideokompresja MPEG-2 ............................................................................................... 163 Jako(cid:258)(cid:202) wideo z kompresj(cid:200) czasow(cid:200) ................................................................................. 166 Tera(cid:283)niejszo(cid:258)(cid:202) i przysz(cid:239)o(cid:258)(cid:202) wideokompresji ....................................................................... 168 7 WYSZUKIWANIE .................................................................................... 169 Zdefiniowanie problemu wyszukiwania .............................................................................. 170 Porz(cid:200)dkowanie danych ........................................................................................................ 170 Sortowanie przez wybór ................................................................................................. 170 Sortowanie szybkie .......................................................................................................... 171 Wyszukiwanie binarne ......................................................................................................... 175 Indeksowanie ....................................................................................................................... 176 Haszowanie ......................................................................................................................... 178 Przeszukiwanie Sieci ............................................................................................................ 181 Klasyfikacja wyników ....................................................................................................... 182 Efektywne zastosowanie indeksów ................................................................................. 184 Co dalej w zwi(cid:200)zku z wyszukiwaniem w Sieci .................................................................... 185 8 WSPÓ(cid:146)BIE(cid:191)NO(cid:165)(cid:109) ................................................................................... 187 Po co ta wspó(cid:239)bie(cid:285)no(cid:258)(cid:202)? ...................................................................................................... 187 Wydajno(cid:258)(cid:202) ....................................................................................................................... 188 (cid:165)rodowiska z wieloma u(cid:285)ytkownikami ............................................................................ 188 Wielozadaniowo(cid:258)(cid:202) ........................................................................................................... 188 Kiedy wspó(cid:239)bie(cid:285)no(cid:258)(cid:202) zawodzi ............................................................................................. 189 Jak dzia(cid:239)a(cid:202) wspó(cid:239)bie(cid:285)nie i bezpiecznie ................................................................................. 192 Dane tylko do czytania .................................................................................................... 192 Przetwarzanie transakcyjne ............................................................................................. 193 Semafory .......................................................................................................................... 194 Problem niesko(cid:241)czonego oczekiwania ................................................................................ 196 Kolejki uporz(cid:200)dkowane ................................................................................................... 196 G(cid:239)odzenie wynikaj(cid:200)ce z czekania cyklicznego ................................................................. 196 Kwestie sprawno(cid:258)ci semaforów .......................................................................................... 199 Co jeszcze w zwi(cid:200)zku ze wspó(cid:239)bie(cid:285)no(cid:258)ci(cid:200) .......................................................................... 200 6 S p i s t r e (cid:258) c i Poleć książkęKup książkę 9 TRASY NA MAPACH ............................................................................. 203 Czym jest mapa w rozumieniu oprogramowania ................................................................203 Wyszukiwanie najpierw najlepszej ...................................................................................205 Ponowne wykorzystanie wcze(cid:258)niejszych wyników wyszukiwania ..................................209 Jednoczesne znajdowanie wszystkich najlepszych tras ........................................................211 Algorytm Floyda ...............................................................................................................212 Zapami(cid:218)tywanie kierunków tras ......................................................................................215 Przysz(cid:239)o(cid:258)(cid:202) wytyczania tras ...................................................................................................218 SKOROWIDZ .......................................................................................... 219 S p i s t r e (cid:258) c i 7 Poleć książkęKup książkę 8 S p i s t r e (cid:258) c i Poleć książkęKup książkę 1 Szyfrowanie LICZYMY, (cid:191)E OPROGRAMOWANIE W KA(cid:191)DEJ CHWILI OCHRONI NASZE DANE, LECZ WI(cid:125)KSZO(cid:165)(cid:109) Z NAS NIE BARDZO SI(cid:125) ORIEN- TUJE, NA CZYM TA OCHRONA POLEGA. DLACZEGO IKONA „k(cid:239)ódki” w rogu Twojej przegl(cid:200)darki oznacza, (cid:285)e mo(cid:285)esz bez- piecznie wprowadzi(cid:202) numer swojej karty kredytowej? Jak to si(cid:218) dzieje, (cid:285)e opatrzenie Twojego telefonu has(cid:239)em rzeczywi(cid:258)cie chroni zawarte w nim dane? Co w istocie zapobiega logowaniu si(cid:218) kogo(cid:258) innego na Twoich kontach online? Bezpiecze(cid:241)stwo komputerowe (ang. computer security) jest nauk(cid:200) o ochronie danych. W pewnym sensie bezpiecze(cid:241)stwo komputerowe reprezentuje technolo- gi(cid:218) rozwi(cid:200)zuj(cid:200)c(cid:200) problem spowodowany przez ni(cid:200) sam(cid:200). Jeszcze nie tak dawno wi(cid:218)kszo(cid:258)(cid:202) danych nie by(cid:239)a przechowywana cyfrowo. Mieli(cid:258)my w biurach szafy z kartotekami, a pod (cid:239)ó(cid:285)kami przechowywali(cid:258)my pude(cid:239)ka po butach pe(cid:239)ne foto- grafii. Oczywi(cid:258)cie w tamtych czasach nie by(cid:239)o (cid:239)atwo podzieli(cid:202) si(cid:218) fotografiami z przyjació(cid:239)mi na (cid:258)wiecie, nie mówi(cid:200)c ju(cid:285) o sprawdzeniu stanu konta na komórce, lecz nikt nie móg(cid:239) ukra(cid:258)(cid:202) Twoich prywatnych danych bez fizycznego ich zagarni(cid:218)- cia. Dzi(cid:258) nie tylko mo(cid:285)na Ci(cid:218) zdalnie obrabowa(cid:202), lecz mo(cid:285)esz nawet nie wiedzie(cid:202), (cid:285)e do tej kradzie(cid:285)y dosz(cid:239)o — przynajmniej do czasu otrzymania z banku zapytania, dlaczego wydajesz tysi(cid:200)ce dolarów na karty podarunkowe1. 1 Ang. gift cards, rodzaj bonu towarowego o kszta(cid:239)cie typowej karty bankomatowej — przyp. t(cid:239)um. Poleć książkęKup książkę W pierwszych trzech rozdzia(cid:239)ach omówimy wi(cid:218)kszo(cid:258)(cid:202) wa(cid:285)nych koncepcji le(cid:285)(cid:200)- cych u podstaw bezpiecze(cid:241)stwa komputerowego. W tym rozdziale opowiemy o szyfrowaniu. Z natury rzeczy szyfrowanie umo(cid:285)liwia zamykanie danych w ten sposób, aby tylko nam wolno je by(cid:239)o otworzy(cid:202). Omówione w nast(cid:218)pnych dwóch rozdzia(cid:239)ach dodatkowe metody s(cid:200) potrzebne do zapewnienia pe(cid:239)nego repertu- aru (cid:258)rodków bezpiecze(cid:241)stwa, na którym opieramy swoje zaufanie, lecz szyfro- wanie jest podstaw(cid:200) bezpiecze(cid:241)stwa komputerowego. Cel szyfrowania Pomy(cid:258)l o pliku w swoim komputerze. Mo(cid:285)e on zawiera(cid:202) tekst, fotografi(cid:218), arkusz elektroniczny, nagranie d(cid:283)wi(cid:218)kowe lub wideo. Chcesz mie(cid:202) dost(cid:218)p do tego pliku, a jednocze(cid:258)nie trzyma(cid:202) go w sekrecie przed innymi. Tak przedstawia si(cid:218) pod- stawowy problem bezpiecze(cid:241)stwa komputerowego. W celu zachowania pliku w tajemnicy mo(cid:285)esz si(cid:218) pos(cid:239)u(cid:285)y(cid:202) szyfrowaniem (ang. encryption), aby nada(cid:202) pli- kowi nowy format, nieczytelny dopóty, dopóki plik nie zostanie przywrócony do pierwotnej postaci za pomoc(cid:200) deszyfrowania (ang. decryption). Plik pierwotny jest zwany tekstem jawnym (ang. plaintext, nawet je(cid:258)li nie zawiera tekstu), a plik zaszy- frowany to kryptogram (ang. ciphertext)2. Atakuj(cid:200)cy (ang. attacker) to kto(cid:258), kto próbuje odszyfrowa(cid:202) kryptogram, nie b(cid:218)d(cid:200)c do tego upowa(cid:285)nionym. Celem szyfrowania jest utworzenie kryptogramu (cid:239)atwego do odszyfrowania przez upowa(cid:285)nionych u(cid:285)ytkowników, a jednocze(cid:258)nie praktycznie niemo(cid:285)liwego do odszyfrowania przez intruzów. Owo „praktycznie” przyprawia o ból g(cid:239)owy specjalistów od bezpiecze(cid:241)stwa. Tak jak (cid:285)aden zamek nie jest nie do pokonania, nie ma szyfru absolutnie niemo(cid:285)liwego do odszyfrowania. Maj(cid:200)c do dyspozycji dostatecznie du(cid:285)o czasu i mocy obliczeniowej, teoretycznie mo(cid:285)na z(cid:239)ama(cid:202) ka(cid:285)dy schemat szyfrowania. Celem bezpiecze(cid:241)stwa komputerowego jest utrudnienie roboty w(cid:239)amywaczowi w takim stopniu, (cid:285)eby udane ataki by(cid:239)y w praktyce niemo(cid:285)liwe, gdy(cid:285) wymaga(cid:239)yby mocy obliczeniowych dla niego nie- dost(cid:218)pnych. Zamiast skaka(cid:202) na g(cid:239)ówk(cid:218) w odm(cid:218)ty szyfrowania opartego na oprogramowa- niu, rozpoczn(cid:218) ten rozdzia(cid:239) od prostych przyk(cid:239)adów z czasów przedkomputero- wych, gdy w gr(cid:218) wchodzi(cid:239)y kody i zainteresowani nimi szpiedzy. Mimo (cid:285)e si(cid:239)a szyfrowania z biegiem lat niepomiernie wzros(cid:239)a, u podstaw ka(cid:285)dego szyfrowania le(cid:285)(cid:200) te same klasyczne sposoby. Pó(cid:283)niej zobaczymy, jak te pomys(cid:239)y s(cid:200) wplecione w nowoczesny schemat szyfrowania cyfrowego. 2 Tu i wielu innych miejscach stosujemy terminy zgodne z ksi(cid:200)(cid:285)k(cid:200) Kryptografia Douglasa R. Stinsona (WNT, Warszawa 2005, przek(cid:239). W. Bartol); kryptografia w obu j(cid:218)zykach ma ich w nadmiarze — przyp. t(cid:239)um. 18 R o z d z i a (cid:239) 1 Poleć książkęKup książkę Przestawianie — te same dane, ró(cid:285)ny porz(cid:200)dek Jeden z najprostszych sposobów szyfrowania danych nazywa si(cid:218) przestawianiem (transpozycj(cid:200), ang. transposition) i polega po prostu na „zmienianiu pozycji”. Prze- stawianie jest rodzajem szyfrowania, którego moi koledzy i ja u(cid:285)ywali(cid:258)my, prze- kazuj(cid:200)c sobie li(cid:258)ciki w czasach szkolnych. Poniewa(cid:285) te li(cid:258)ciki przechodzi(cid:239)y przez niepewne r(cid:218)ce, trzeba si(cid:218) by(cid:239)o postara(cid:202), aby by(cid:239)y niezrozumia(cid:239)e dla wszystkich prócz nas. Aby zapewni(cid:202) naszym wiadomo(cid:258)ciom tajemnic(cid:218), zmieniali(cid:258)my w nich kolejno(cid:258)(cid:202) liter, u(cid:285)ywaj(cid:200)c prostego, (cid:239)atwego do odwrócenia schematu. Przypu(cid:258)(cid:202)my, (cid:285)e chcia- (cid:239)em si(cid:218) podzieli(cid:202) jak(cid:285)e istotnym doniesieniem, (cid:285)e KA(cid:165)KA LUBI KEITHA (imiona zosta(cid:239)y zmienione, gdy(cid:285) moi rówie(cid:258)nicy niczego tu nie zawinili). (cid:191)eby zaszyfro- wa(cid:202) t(cid:218) wiadomo(cid:258)(cid:202), skopiowa(cid:239)em ka(cid:285)d(cid:200) co trzeci(cid:200) liter(cid:218) tekstu jawnego (pomi- jaj(cid:200)c spacje). W rezultacie po pierwszym przej(cid:258)ciu przez wiadomo(cid:258)(cid:202) skopiowa- (cid:239)em pi(cid:218)(cid:202) liter, co uwidacznia rysunek 1.1. Rysunek 1.1. Pierwszy etap transpozycji przyk(cid:239)adowej wiadomo(cid:258)ci Po dotarciu do ko(cid:241)ca wiadomo(cid:258)ci wróci(cid:239)em do pocz(cid:200)tku i kontynuowa(cid:239)em wybieranie ka(cid:285)dej co trzeciej litery z pozosta(cid:239)ych. W drugim etapie otrzyma(cid:239)em stan przedstawiony na rysunku 1.2. Rysunek 1.2. Drugi etap transpozycji W ostatnim etapie skopiowa(cid:239)em pozosta(cid:239)e litery, co pokazano na rysunku 1.3. Wynikowy kryptogram ma posta(cid:202) KKUKTAABEH(cid:165)LIIA. Moi koledzy mogli odczyta(cid:202) t(cid:218) wiadomo(cid:258)(cid:202), odwracaj(cid:200)c proces transpozycji. Pierwszy krok jest poka- zany na rysunku 1.4. Przywrócenie wszystkich liter na ich pierwotne pozycje odkrywa tekst jawny. S z y f r o w a n i e 19 Poleć książkęKup książkę Rysunek 1.3. Ostatni etap transpozycji Rysunek 1.4. Pierwszy etap odwracania transpozycji w celu odszyfrowania Ta elementarna metoda przestawie(cid:241) by(cid:239)a zabawna w u(cid:285)yciu, lecz jest ona okropnie s(cid:239)abym szyfrowaniem. Najwi(cid:218)kszym problemem jest przeciek — jeden z moich kolegów wypapla(cid:239) zasad(cid:218) szyfrowania komu(cid:258) spoza naszej paczki. Odt(cid:200)d wysy(cid:239)anie zaszyfrowanych wiadomo(cid:258)ci przesta(cid:239)o by(cid:202) bezpieczne; wystarczy(cid:239)o tylko wi(cid:218)cej popracowa(cid:202). Przecieków nie da si(cid:218), niestety, unikn(cid:200)(cid:202) — i nie dotyczy to tylko dzieci w wieku szkolnym. Ka(cid:285)da metoda jest podatna na przecieki, a im wi(cid:218)- cej ludzi korzysta z danej metody, tym wi(cid:218)ksze prawdopodobie(cid:241)stwo, (cid:285)e zosta- nie wyjawiona. Z tego powodu wszystkie dobre systemy szyfrowania spe(cid:239)niaj(cid:200) regu(cid:239)(cid:218) okre(cid:258)lon(cid:200) przez jednego z pierwszych kryptografów, Du(cid:241)czyka Auguste’a Kerckhoffsa, znan(cid:200) jako zasada Kerckhoffsa: bezpiecze(cid:241)stwo danych nie powinno zale(cid:285)e(cid:202) od utrzy- mywania metody szyfrowania w tajemnicy. Klucze szyfrów Rodzi to oczywiste pytanie: w jaki sposób, je(cid:258)li metoda szyfrowania nie jest tajem- nic(cid:200), mo(cid:285)emy bezpiecznie szyfrowa(cid:202) dane? Odpowied(cid:283) polega na nast(cid:218)puj(cid:200)cej ogólnej i powszechnie znanej metodzie szyfrowania, w której jednak szyfrowa- nie poszczególnych wiadomo(cid:258)ci zmienia si(cid:218) przez zastosowanie klucza szyfru (ang. cipher key), czyli po prostu — klucza. Aby zrozumie(cid:202), czym jest klucz, przyj- rzyjmy si(cid:218) ogólniejszej metodzie transpozycji. W tej metodzie nadawcy i odbiorcy, zanim zaczn(cid:200) przesy(cid:239)a(cid:202) jakiekolwiek komunikaty, wchodz(cid:200) w posiadanie wspólnej tajnej liczby. Powiedzmy, (cid:285)e moi koledzy i ja umówili(cid:258)my si(cid:218), (cid:285)e b(cid:218)dzie to 374. Liczby tej u(cid:285)yjemy do zmiany 20 R o z d z i a (cid:239) 1 Poleć książkęKup książkę wzorca przestawiania w naszych kryptogramach, Dla wiadomo(cid:258)ci KA(cid:165)KA LUBI KEITHA wzorzec ten pokazano na rysunku 1.5. Cyfry naszej tajnej liczby wska- zuj(cid:200), któr(cid:200) liter(cid:218) nale(cid:285)y skopiowa(cid:202) z tekstu jawnego do kryptogramu. Poniewa(cid:285) pierwsz(cid:200) cyfr(cid:200) jest 3, trzecia litera tekstu jawnego, czyli (cid:165), staje si(cid:218) pierwsz(cid:200) liter(cid:200) kryptogramu. Nast(cid:218)pn(cid:200) cyfr(cid:200) jest 7, wi(cid:218)c nast(cid:218)pn(cid:200) liter(cid:200) b(cid:218)dzie siódma litera po (cid:165), czyli K. Dalej wybieramy czwart(cid:200) liter(cid:218), rozpoczynaj(cid:200)c odliczanie od nast(cid:218)pnej po K. Pierwszymi trzema literami kryptogramu b(cid:218)d(cid:200) (cid:165)KH. Rysunek 1.5. Pierwszy etap transpozycji z u(cid:285)yciem klucza 374 Na rysunku 1.6 pokazano, jak wygl(cid:200)da przekopiowanie dwóch nast(cid:218)pnych liter do kryptogramu. Zaczynaj(cid:200)c od miejsca, w którym przebywali(cid:258)my (to jest od pozycji zaznaczonej na rysunku jedynk(cid:200) w kó(cid:239)ku), odliczamy trzy pozycje, przy czym po doj(cid:258)ciu do ko(cid:241)ca tekstu jawnego wracamy na jego pocz(cid:200)tek, gdzie wybieramy A jako czwart(cid:200) liter(cid:218) kryptogramu. Nast(cid:218)pnie wybieramy liter(cid:218) z siódmej pozycji po A, przeskakuj(cid:200)c litery ju(cid:285) skopiowane — b(cid:218)dzie ni(cid:200) E. Kontynuujemy to post(cid:218)- powanie, a(cid:285) wszystkie litery z tekstu jawnego zostan(cid:200) przestawione. Rysunek 1.6. Drugi etap transpozycji z u(cid:285)yciem klucza 374 Tajna liczba 374 sta(cid:239)a si(cid:218) zatem naszym kluczem szyfrowania. Gdyby kto(cid:258) prze- chwyci(cid:239) t(cid:218) wiadomo(cid:258)(cid:202), nie zdo(cid:239)a(cid:239)by jej zdeszyfrowa(cid:202) bez tego klucza — nawet gdyby wiedzia(cid:239), (cid:285)e u(cid:285)ywamy metody przestawie(cid:241). Klucz mo(cid:285)na regularnie zmie- nia(cid:202), aby ustrzec si(cid:218) przed ujawnieniem szyfrowania w wyniku niedyskrecji lub zdrady. S z y f r o w a n i e 21 Poleć książkęKup książkę (cid:146)amanie szyfrów Atakuj(cid:200)cy, nawet nie maj(cid:200)c klucza, mog(cid:200) próbowa(cid:202) odtworzy(cid:202) jawn(cid:200) posta(cid:202) tekstu innymi sposobami. Mo(cid:285)na zaatakowa(cid:202) zaszyfrowane dane metod(cid:200) si(cid:239)ow(cid:200) (ang. brute force), próbuj(cid:200)c u(cid:285)y(cid:202) do kryptogramu metody szyfrowania wszystkimi mo(cid:285)- liwymi sposobami. W przypadku wiadomo(cid:258)ci zaszyfrowanej za pomoc(cid:200) przesta- wiania atak si(cid:239)owy polega(cid:239)by na sprawdzeniu wszystkich permutacji kryptogramu. Poniewa(cid:285) atak si(cid:239)owy jest prawie zawsze mo(cid:285)liwy, liczba prób, któr(cid:200) atakuj(cid:200)cy b(cid:218)dzie musia(cid:239) wykona(cid:202), aby znale(cid:283)(cid:202) tekst jawny, jest dobrym wska(cid:283)nikiem odpor- no(cid:258)ci szyfrowania. W naszym przyk(cid:239)adzie wiadomo(cid:258)(cid:202) KA(cid:165)KA LUBI KEITHA ma oko(cid:239)o 40 miliardów permutacji. Jest to wielka liczba, wi(cid:218)c zamiast dzia(cid:239)ania si(cid:239)owego sprytny atakuj(cid:200)cy móg(cid:239)by do szybszego odtworzenia tekstu jawnego pos(cid:239)u(cid:285)y(cid:202) si(cid:218) odrobin(cid:200) zdrowego roz- s(cid:200)dku. Gdyby atakuj(cid:200)cy za(cid:239)o(cid:285)y(cid:239), (cid:285)e tekst jawny jest po polsku, wi(cid:218)kszo(cid:258)(cid:202) per- mutacji mo(cid:285)na by wykluczy(cid:202) jeszcze przed testowaniem. Na przyk(cid:239)ad atakuj(cid:200)cy móg(cid:239)by za(cid:239)o(cid:285)y(cid:202), (cid:285)e tekst jawny nie zaczyna si(cid:218) od grupy liter HT, poniewa(cid:285) (cid:285)adne polskie s(cid:239)owo nie zaczyna si(cid:218) od tej grupy liter3. To zaoszcz(cid:218)dzi(cid:239)oby atakuj(cid:200)cemu sprawdzania miliarda permutacji. Atakuj(cid:200)cy, który ma jaki(cid:258) pomys(cid:239) odno(cid:258)nie do s(cid:239)ów w wiadomo(cid:258)ci, mo(cid:285)e by(cid:202) jeszcze sprytniejszy w dochodzeniu do tekstu jawnego. W naszym przyk(cid:239)adzie atakuj(cid:200)cy móg(cid:239)by zgadn(cid:200)(cid:202), (cid:285)e wiadomo(cid:258)(cid:202) zawiera imi(cid:218) kogo(cid:258) z klasy. Mo(cid:285)na by sprawdzi(cid:202), jakie imiona da si(cid:218) utworzy(cid:202) z liter kryptogramu, a potem ustali(cid:202), jakie s(cid:239)owa mo(cid:285)na utworzy(cid:202) z pozosta(cid:239)ych liter. Odgadni(cid:218)te informacje dotycz(cid:200)ce zawarto(cid:258)ci tekstu jawnego zw(cid:200) si(cid:218) krypto- analitycznymi (cid:258)ci(cid:200)gami lub krybami4. Najmocniejszym krybem jest atak ze zna- nym tekstem jawnym (ang. known-plaintext attack). Aby go dokona(cid:202), atakuj(cid:200)cy musi mie(cid:202) dost(cid:218)p do tekstu jawnego A, odpowiadaj(cid:200)cego A kryptogramu i krypto- gramu B, w którym u(cid:285)yto tego samego klucza szyfrowania co w kryptogramie A. Okoliczno(cid:258)ci te, cho(cid:202) wygl(cid:200)daj(cid:200) na ma(cid:239)o prawdopodobne, zdarzaj(cid:200) si(cid:218). Ludzie cz(cid:218)sto zostawiaj(cid:200) bez nadzoru dokumenty, co do których zak(cid:239)adaj(cid:200), (cid:285)e straci(cid:239)y status poufno(cid:258)ci, nie u(cid:258)wiadamiaj(cid:200)c sobie, (cid:285)e mog(cid:200) pomóc w atakach na inne dokumenty. Ataki ze znanym tekstem jawnym s(cid:200) silne; odkrycie wzorca transpo- zycji jest (cid:239)atwe, gdy masz przed oczami zarówno tekst jawny, jak i kryptogram. Najlepsz(cid:200) obron(cid:200) przed atakami ze znanym tekstem jawnym s(cid:200) dobre prak- tyki bezpiecze(cid:241)stwa, takie jak regularne zmienianie hase(cid:239). Niemniej nawet prze- strzeganie najlepszych zasad bezpiecze(cid:241)stwa nie zapobiegnie temu, (cid:285)e atakuj(cid:200)cy zawsze b(cid:218)d(cid:200) mieli pewne wyobra(cid:285)enie o zawarto(cid:258)ci tekstu jawnego (to dlatego w(cid:239)a(cid:258)nie s(cid:200) tak zainteresowani jego odczytaniem). W wielu przypadkach znaj(cid:200) 3 W oryginale jest oczywi(cid:258)cie mowa o j(cid:218)zyku angielskim, ale równie(cid:285) w j(cid:218)zyku polskim (cid:285)adne s(cid:239)owo nie zaczyna si(cid:218) od „ht” — przyp. t(cid:239)um. 4 Punktami zaczepienia, wskazówkami, (cid:258)ci(cid:200)gami (ang. crib — dos(cid:239). (cid:239)ó(cid:285)eczko, (cid:285)(cid:239)óbek, oszalowanie, (cid:258)ci(cid:200)ga, bryk); nazwa u(cid:285)ywana przez kryptologów z czasów Enigmy, zostawiamy j(cid:200) w transkrypcji fonetycznej, bez przypisania — przyp. t(cid:239)um. 22 R o z d z i a (cid:239) 1 Poleć książkęKup książkę oni wi(cid:218)kszo(cid:258)(cid:202) tekstu jawnego i mog(cid:200) mie(cid:202) dost(cid:218)p do znanych par tekst jawny – kryptogram. Dobry system kryptograficzny powinien sprawia(cid:202), (cid:285)e kryby i znane teksty jawne stan(cid:200) si(cid:218) dla atakuj(cid:200)cych bezu(cid:285)yteczne. Podstawianie — zast(cid:218)powanie danych Drugi podstawowy sposób szyfrowania jest odporniejszy na kryby. Zamiast prze- suwania danych w metodach podstawieniowych (ang. substitution methods) poszczególne fragmenty danych s(cid:200) systematycznie zast(cid:218)powane innymi. W przy- padku komunikatów tekstowych najprostsz(cid:200) postaci(cid:200) podstawiania jest zamiana ka(cid:285)dego wyst(cid:200)pienia jednej litery na inn(cid:200). Na przyk(cid:239)ad ka(cid:285)de A staje si(cid:218) D, ka(cid:285)de B — H itd. Klucz tego typu szyfrowania wygl(cid:200)da tak, jak w tabeli 1.1. Tabela 1.1. Klucz szyfrowania podstawieniowego Orygina(cid:239) Zast(cid:200)pienie M N B C D E C A V B F G H L X Z I K J F K H G L M N O P Q R P O D S A J S I T T U V W X U Y Z E W Q R Y Cho(cid:202) prosty szyfr podstawieniowy, jak zw(cid:200) t(cid:218) metod(cid:218), jest ulepszeniem trans- pozycji, równie(cid:285) przysparza problemów. Podstawie(cid:241) jest niezbyt wiele, wi(cid:218)c ata- kuj(cid:200)cy mo(cid:285)e niekiedy odszyfrowa(cid:202) kryptogram metod(cid:200) si(cid:239)ow(cid:200). Proste podstawienie jest równie(cid:285) podatne na analiz(cid:218) frekwencyjn(cid:200) (ang. frequ- ency analysis), w której atakuj(cid:200)cy wykorzystuje wiedz(cid:218) o cz(cid:218)sto(cid:258)ci wyst(cid:218)powania liter lub ich kombinacji w danym j(cid:218)zyku. Ujmuj(cid:200)c ogólnie: znajomo(cid:258)(cid:202) cz(cid:218)sto(cid:258)ci wyst(cid:218)powania w tek(cid:258)cie jawnym jednostek danych daje atakuj(cid:200)cemu przewag(cid:218). Na przyk(cid:239)ad litera E wyst(cid:218)puje w tekstach angielskich najcz(cid:218)(cid:258)ciej, a TH jest naj- popularniejsz(cid:200) w tym j(cid:218)zyku par(cid:200) liter. Dlatego litera najcz(cid:218)(cid:258)ciej wyst(cid:218)puj(cid:200)ca w d(cid:239)ugim kryptogramie b(cid:218)dzie prawdopodobnie reprezentowa(cid:239)a liter(cid:218) E, a naj- cz(cid:218)(cid:258)ciej wyst(cid:218)puj(cid:200)ca para liter b(cid:218)dzie odpowiada(cid:239)a TH. Si(cid:239)a analizy frekwencyjnej polega na tym, (cid:285)e szyfr podstawieniowy staje si(cid:218) coraz bardziej podatny na z(cid:239)amanie wraz ze zwi(cid:218)kszaniem obj(cid:218)to(cid:258)ci tekstu. Ataki s(cid:200) równie(cid:285) (cid:239)atwiejsze po zgromadzeniu zbioru kryptogramów zaszyfrowanych tym samym kluczem; unikanie takiego ponownego u(cid:285)ycia klucza (ang. key reuse) jest wa(cid:285)nym zaleceniem z punktu widzenia bezpiecze(cid:241)stwa. Zmienianie wzorca podstawiania Aby uodporni(cid:202) szyfrowanie na analiz(cid:218) frekwencyjn(cid:200), mo(cid:285)emy zmienia(cid:202) wzorzec podstawiania w trakcie szyfrowania. Tak wi(cid:218)c pierwsze E w tek(cid:258)cie jawnym mog(cid:239)oby by(cid:202) zast(cid:200)pione przez A, lecz drugie E w tek(cid:258)cie jawnym mo(cid:285)na by ju(cid:285) zast(cid:200)pi(cid:202) przez T. Ten sposób jest okre(cid:258)lany jako podstawianie wieloalfabetowe (ang. polyalphabetic substitution). W jednej z metod podstawiania wieloalfabetowego korzysta si(cid:218) z siatki alfabetów zwanej tabula recta, pokazanej na rysunku 1.7. W tej S z y f r o w a n i e 23 Poleć książkęKup książkę Rysunek 1.7. Tabula recta (zacieniowane pierwsza kolumna i pierwszy wiersz zawieraj(cid:200) etykiety) tabeli ka(cid:285)dy wiersz i kolumna s(cid:200) poetykietowane liter(cid:200) alfabetu, która rozpoczyna dany wiersz lub kolumn(cid:218). Ka(cid:285)de oczko w siatce jest lokalizowane za pomoc(cid:200) dwóch liter, na przyk(cid:239)ad w wierszu D i kolumnie H wyst(cid:218)puje litera K. Z zastosowaniem tabuli recty klucz ma posta(cid:202) tekstow(cid:200): zamiast liczb, których u(cid:285)ywali(cid:258)my w przyk(cid:239)adzie z przestawianiem, do zmiany szyfrowania s(cid:200) tutaj u(cid:285)y- wane litery. Litery tekstu jawnego identyfikuj(cid:200) wiersze w tabuli rekcie, a litery klucza wskazuj(cid:200) kolumny. Za(cid:239)ó(cid:285)my na przyk(cid:239)ad, (cid:285)e tekst jawny ma posta(cid:202) SECRET, a naszym kluczem szyfrowania jest s(cid:239)owo TOUGH. Poniewa(cid:285) pierwsz(cid:200) liter(cid:200) tekstu jawnego jest S, a pierwsz(cid:200) liter(cid:200) klucza jest T, pierwsza litera kryptogramu znajduje si(cid:218) w tabuli rekcie w wierszu S i kolumnie T — jest ni(cid:200) litera L. Nast(cid:218)pnie pos(cid:239)ugujemy si(cid:218) kolumn(cid:200) O tabeli do zaszyfrowania drugiej litery tekstu jawnego, to jest E (w wyniku otrzymujemy S) itd., jak pokazano na rysunku 1.8. Poniewa(cid:285) tekst jawny jest d(cid:239)u(cid:285)szy ni(cid:285) klucz, musimy ponownie u(cid:285)y(cid:202) pierwszej litery klucza. Deszyfrowanie polega na odwróceniu tego post(cid:218)powania, co pokazano na rysunku 1.9. Litery klucza wskazuj(cid:200) kolumny przegl(cid:200)dane w celu znalezienia odpo- wiedniej litery w kryptogramie. Wiersz z odnalezion(cid:200) liter(cid:200) kryptogramu wska- zuje liter(cid:218) tekstu jawnego. W naszym przyk(cid:239)adzie pierwsz(cid:200) liter(cid:200) klucza jest T, 24 R o z d z i a (cid:239) 1 Poleć książkęKup książkę Rysunek 1.8. Szyfrowanie z u(cid:285)yciem tabuli recty i klucza szyfru TOUGH Rysunek 1.9. Deszyfrowanie z u(cid:285)yciem tabuli recty i klucza szyfru TOUGH a pierwsz(cid:200) liter(cid:200) kryptogramu jest L. Przegl(cid:200)damy kolumn(cid:218) T tabuli recty w poszu- kiwaniu L; poniewa(cid:285) L wyst(cid:218)puje w wierszu S, liter(cid:200) tekstu jawnego jest S. Pro- ces powtarza si(cid:218) dla ka(cid:285)dej litery kryptogramu. Podstawianie wieloalfabetowe jest efektywniejsze ni(cid:285) proste podstawianie, gdy(cid:285) w trakcie szyfrowania komunikatu zmienia si(cid:218) w nim wzorzec podstawiania. W naszym przyk(cid:239)adzie dwa wyst(cid:200)pienia E w tek(cid:258)cie jawnym przybra(cid:239)y postaci ró(cid:285)nych liter, a dwa wyst(cid:200)pienia L w kryptogramie reprezentuj(cid:200) ró(cid:285)ne litery tekstu jawnego. Poszerzanie klucza Cho(cid:202) podstawianie wieloalfabetowe jest znacznym ulepszeniem prostego szyfru podstawieniowego, skutkuje tylko wówczas, gdy klucz nie jest zbyt cz(cid:218)sto powta- rzany. W przeciwnym razie wyst(cid:218)puj(cid:200) w nim te same problemy co w prostym podstawianiu. Na przyk(cid:239)ad w przypadku klucza o d(cid:239)ugo(cid:258)ci 5 ka(cid:285)da litera tekstu S z y f r o w a n i e 25 Poleć książkęKup książkę jawnego by(cid:239)aby reprezentowana tylko przez pi(cid:218)(cid:202) ró(cid:285)nych liter w kryptogramie, co wystawia(cid:239)oby d(cid:239)ugie kryptogramy na niebezpiecze(cid:241)stwo analizy frekwencyj- nej i kryby. Atakuj(cid:200)cy musia(cid:239)by si(cid:218) wi(cid:218)cej napracowa(cid:202), lecz maj(cid:200)c do czynienia z dostatecznie du(cid:285)(cid:200) ilo(cid:258)ci(cid:200) tekstu zaszyfrowanego, nadal móg(cid:239)by z(cid:239)ama(cid:202) szyfr. W celu maksymalizacji efektywno(cid:258)ci musimy u(cid:285)ywa(cid:202) kluczy szyfrowania tak d(cid:239)ugich jak tekst jawny. T(cid:218) technik(cid:218) nazywa si(cid:218) podk(cid:239)adk(cid:200) jednorazow(cid:200) (ang. one-time pad). W wi(cid:218)kszo(cid:258)ci sytuacji nie jest to jednak rozwi(cid:200)zanie praktyczne. Zamiast tego metoda zwana poszerzaniem klucza (ang. key expansion) umo(cid:285)li- wia osi(cid:200)ganie efektu u(cid:285)ycia d(cid:239)u(cid:285)szych kluczy za pomoc(cid:200) krótkich kluczy. Jedno z odzwierciedle(cid:241) tego pomys(cid:239)u cz(cid:218)sto pojawia si(cid:218) w powie(cid:258)ciach szpiegowskich. Zamiast wspó(cid:239)u(cid:285)ytkowania superd(cid:239)ugiego klucza dwóch szpiegów chc(cid:200)cych wymie- nia(cid:202) meldunki uzgadnia ksi(cid:200)(cid:285)k(cid:218) kodow(cid:200) (ang. code book) s(cid:239)u(cid:285)(cid:200)c(cid:200) jako magazyn d(cid:239)ugich kluczy. Aby unikn(cid:200)(cid:202) podejrze(cid:241), ksi(cid:200)(cid:285)ka kodowa jest zwyk(cid:239)ym egzem- plarzem jakiej(cid:258) literatury, na przyk(cid:239)ad specjalnym wydaniem sztuk Szekspira. Za(cid:239)ó(cid:285)my, (cid:285)e wed(cid:239)ug tego schematu ma by(cid:202) przes(cid:239)any 50-literowy komunikat. Oprócz kryptogramu nadawca do(cid:239)(cid:200)cza równie(cid:285) nierozwini(cid:218)ty klucz. Z u(cid:285)yciem dzie(cid:239) Szekspira jako ksi(cid:200)(cid:285)ki kodowej nierozwini(cid:218)ty klucz mo(cid:285)e przyj(cid:200)(cid:202) posta(cid:202) 2.2.4.9. Pierwsza dwójka wskazuje drug(cid:200) sztuk(cid:218) Szekspira w uk(cid:239)adzie alfabetycz- nym (As You Like It5). Druga dwójka oznacza akt II tej sztuki. Czwórka oznacza czwart(cid:200) scen(cid:218) tego aktu. Dziewi(cid:200)tka symbolizuje dziewi(cid:200)te zdanie tej sceny w okre(cid:258)lonym wydaniu: „When I was at home, I was in a better place, but travelers must be content”6. Liczba liter w tym zdaniu przekracza liczb(cid:218) liter w tek(cid:258)cie jawnym, mo(cid:285)na wi(cid:218)c jej u(cid:285)y(cid:202) do szyfrowania i deszyfrowania za pomoc(cid:200) tabuli recty — jak poprzednio. W ten sposób stosunkowo krótki klucz mo(cid:285)e by(cid:202) poszerzony tak, aby pasowa(cid:239) do konkretnego komunikatu. Zauwa(cid:285)my, (cid:285)e tego schematu nie kwalifikujemy jako podk(cid:239)adki jednorazowej, gdy(cid:285) ksi(cid:200)(cid:285)ka kodowa jest sko(cid:241)czona, dlatego zda(cid:241) kluczy trzeba b(cid:218)dzie w ko(cid:241)cu u(cid:285)y(cid:202) powtórnie. Oznacza to jednak, (cid:285)e nasi szpiedzy musz(cid:200) pami(cid:218)ta(cid:202) tylko krótkie klucze cyfrowe, bezpieczniej szyfruj(cid:200)c swoje meldunki d(cid:239)u(cid:285)szymi kluczami. Jak si(cid:218) przekonamy, pomys(cid:239) poszerzania klucza jest wa(cid:285)ny w szyfrowaniu komputero- wym, poniewa(cid:285) wymagane klucze szyfrowania s(cid:200) wielkie, lecz musz(cid:200) by(cid:202) pami(cid:218)- tane w mniejszych postaciach. Zaawansowany standard szyfrowania Skoro zobaczyli(cid:258)my ju(cid:285) z osobna, jak dzia(cid:239)a transpozycja, podstawianie i posze- rzanie klucza, przyjrzyjmy si(cid:218), jak ze starannego po(cid:239)(cid:200)czenia wszystkich tych trzech technik uzyskuje si(cid:218) bezpieczne szyfrowanie cyfrowe. 5 Czyli Jak wam si(cid:218) podoba — przyp. t(cid:239)um. 6 Z ang.: „[...] kiedym by(cid:239) w domu, lepiej mi by(cid:239)o; ale podró(cid:285)ny musi przesta(cid:202) na ma(cid:239)ym” (przek(cid:239). L. Urlich. W. Szekspir, Dzie(cid:239)a dramatyczne, tom II, Komedie. PIW, Warszawa 1958) — przyp. t(cid:239)um. 26 R o z d z i a (cid:239) 1 Poleć książkęKup książkę Zaawansowany standard szyfrowania (AES, ang. Advanced Encryption Stan- dard) jest standardem otwartym, co oznacza, (cid:285)e jego specyfikacja mo(cid:285)e by(cid:202) urze- czywistniona przez ka(cid:285)dego bez op(cid:239)acania licencji. Czy sobie z tego zdajesz spraw(cid:218), czy nie, wi(cid:218)kszo(cid:258)(cid:202) Twoich danych jest chroniona z u(cid:285)yciem AES. Je(cid:258)li w domu lub w pracy masz bezpieczn(cid:200) sie(cid:202) bezprzewodow(cid:200), je(cid:258)li kiedykolwiek zdarzy(cid:239)o Ci si(cid:218) zabezpiecza(cid:202) has(cid:239)em plik w archiwum .zip lub je(cid:258)li u(cid:285)ywasz karty kredy- towej w sklepie albo pobierasz pieni(cid:200)dze z bankomatu — prawdopodobnie pole- gasz (przynajmniej cz(cid:218)(cid:258)ciowo) na AES. Podstawy dwójkowe Jak dot(cid:200)d ucieka(cid:239)em si(cid:218) do przyk(cid:239)adów szyfrowania tekstów w trosce o ich pro- stot(cid:218). Jednak(cid:285)e dane szyfrowane przez komputery s(cid:200) przedstawiane w postaci liczb dwójkowych. Je(cid:258)li wcze(cid:258)niej nie mia(cid:239)e(cid:258) z nimi do czynienia, tutaj przedsta- wiam ma(cid:239)y wst(cid:218)p. System dziesi(cid:218)tny a system dwójkowy System liczbowy, do którego wszyscy nawykli(cid:258)my od dziecka, jest nazywany dziesi(cid:218)tnym (ang. de- cimal, „deci” z (cid:239)aciny znaczy „dziesi(cid:218)(cid:202)”), gdy(cid:285) u(cid:285)ywa si(cid:218) w nim dziesi(cid:218)ciu cyfr, od 0 do 9. Ka(cid:285)da cyfra w zapisie liczby reprezentuje liczb(cid:218) jednostek 10-krotnie wi(cid:218)ksz(cid:200) ni(cid:285) cyfra s(cid:200)siadu- j(cid:200)ca z ni(cid:200) z prawej strony. Jednostki i wielko(cid:258)ci okre(cid:258)lane liczb(cid:200) 23 065 pokazano na rysunku 1.10. Na przyk(cid:239)ad dwójka na pi(cid:200)tej pozycji po lewej oznacza, (cid:285)e mamy dwie „dziesi(cid:200)tki tysi(cid:218)cy”, a szóstka oznacza sze(cid:258)(cid:202) „dziesi(cid:200)tek”. W dwójkowym (binarnym, ang. binary) sys- temie liczbowym istniej(cid:200) tylko dwie cyfry: 0 i 1, nazywane bitami od angielskiego binary digits (cyfry dwójkowe). Ka(cid:285)dy bit w liczbie dwójkowej reprezentuje wielko(cid:258)(cid:202) dwa razy wi(cid:218)ksz(cid:200) ni(cid:285) bit po prawej. Jednostki i wielko(cid:258)ci w liczbie dwój- kowej 110101 pokazano na rysunku 1.11. Jak wida(cid:202), mamy tu po jednej z nast(cid:218)puj(cid:200)cych wiel- ko(cid:258)ci: 32, 16, 4 i 1. Wobec tego liczba dwójkowa reprezentuje sum(cid:218) tych czterech warto(cid:258)ci, co daje dziesi(cid:218)tnie liczb(cid:218) 53. Liczby dwójkowe s(cid:200) zazwyczaj zapisywane z u(cid:285)yciem sta(cid:239)ej liczby bitów. Najpopularniejsz(cid:200) d(cid:239)ugo(cid:258)ci(cid:200) liczby dwójkowej jest osiem bitów okre- (cid:258)lanych jako bajt (ang. byte). Cho(cid:202) dziesi(cid:218)tn(cid:200) liczb(cid:218) 53 mo(cid:285)na zapisa(cid:202) dwójkowo w postaci Rysunek 1.10. Ka(cid:285)da cyfra w zapisie pozycyjnym liczby dziesi(cid:218)tnej 23 065 reprezentuje inn(cid:200) liczb(cid:218) jedno(cid:258)ci Rysunek 1.11. Ka(cid:285)da cyfra w zapisie pozycyjnym liczby dwójkowej 110101 reprezentuje inn(cid:200) liczb(cid:218) jedno(cid:258)ci S z y f r o w a n i e 27 Poleć książkęKup książkę 110101, zapisanie jej w postaci bajta wymaga o(cid:258)miu bitów, tote(cid:285) pocz(cid:200)tkowe bity wype(cid:239)nia si(cid:218) zerami — otrzymujemy wi(cid:218)c zapis 00110101. Bajt o najmniejszej warto(cid:258)ci, 00000000, reprezentuje dziesi(cid:218)tne 0; najwi(cid:218)kszy mo(cid:285)liwy bajt, 11111111, przedstawia liczb(cid:218) 255. Operacje na bitach Oprócz zwyk(cid:239)ych operacji matematycznych, jak dodawanie i mno(cid:285)enie, oprogra- mowanie u(cid:285)ywa pewnych operacji charakterystycznych dla liczb dwójkowych. Nazywa si(cid:218) je operacjami bitowymi (ang. bitwise operations), poniewa(cid:285) s(cid:200) wyko- nywane z osobna na ka(cid:285)dym bicie, a nie na liczbie dwójkowej traktowanej jako ca(cid:239)o(cid:258)(cid:202). W szyfrowaniu powszechnie u(cid:285)ywa si(cid:218) operacji bitowej zwanej alternatyw(cid:200) wykluczaj(cid:200)c(cid:200) (ang. exclusive-or, XOR). Podczas wykonywania na dwóch liczbach dwójkowych operacji XOR jedynki drugiej liczby prze(cid:239)(cid:200)czaj(cid:200)7 warto(cid:258)ci odpowied- nich bitów pierwszej liczby, jak pokazano na rysunku 1.12. Rysunek 1.12. Operacja alternatywy wykluczaj(cid:200)cej (XOR). Bity 1 w drugim bajcie wskazuj(cid:200), które bity s(cid:200) „prze(cid:239)(cid:200)czane” w pierwszym bajcie, co pokazano w zacieniowanych kolumnach Pami(cid:218)tamy, (cid:285)e szyfrowanie musi by(cid:202) odwracalne. XOR zmienia wzorce bitowe w sposób niemo(cid:285)liwy do przewidzenia bez znajomo(cid:258)ci u(cid:285)ytych liczb dwójkowych, lecz jest to (cid:239)atwe do odwrócenia. XOR-owanie wyniku za pomoc(cid:200) drugiej liczby prze(cid:239)(cid:200)cza te same bity do ich pierwotnego stanu, jak pokazano na rysunku 1.13. Zamiana danych na posta(cid:202) dwójkow(cid:200) Komputery u(cid:285)ywaj(cid:200) liczb dwójkowych do reprezentowania wszelkich danych. Plik z tekstem jawnym móg(cid:239)by by(cid:202) wiadomo(cid:258)ci(cid:200) tekstow(cid:200), arkuszem kalkulacyjnym, obrazem, wideoplikiem lub czymkolwiek innym, lecz koniec ko(cid:241)ców ka(cid:285)dy plik jest ci(cid:200)giem bajtów. Wi(cid:218)kszo(cid:258)(cid:202) danych komputerowych od pocz(cid:200)tku ma posta(cid:202) numeryczn(cid:200), mo(cid:285)e wi(cid:218)c by(cid:202) bezpo(cid:258)rednio zamieniona na liczby dwójkowe. Jed- nak w pewnych przypadkach trzeba zastosowa(cid:202) specjalny system kodowania do zamiany danych nienumerycznych na posta(cid:202) dwójkow(cid:200). 7 To znaczy zmieniaj(cid:200) na przeciwne — przyp. t(cid:239)um. 28 R o z d z i a (cid:239) 1 Poleć książkęKup książkę Rysunek 1.13. Je(cid:258)li potraktujemy dwukrotnie bajt operacj(cid:200) XOR z u(cid:285)yciem tego samego bajta, otrzymamy to, co mieli(cid:258)my na pocz(cid:200)tku Aby zobaczy(cid:202), jak komunikat tekstowy staje si(cid:218) ci(cid:200)giem bajtów, rozwa(cid:285)my wiadomo(cid:258)(cid:202): Send more money! 8 Ta wiadomo(cid:258)(cid:202) sk(cid:239)ada si(cid:218) z 16 znaków, licz(cid:200)c litery, spacje i wykrzyknik. Ka(cid:285)dy znak mo(cid:285)emy wyrazi(cid:202) za pomoc(cid:200) bajta, korzystaj(cid:200)c na przyk(cid:239)ad z systemu o nazwie American Standard Code for Information Interchange9, znanego równie(cid:285) pod postaci(cid:200) skrótu ASCII (wym. „aski”), W systemie ASCII du(cid:285)a litera A jest repre- zentowana liczb(cid:200) 65, B ma przypisan(cid:200) warto(cid:258)(cid:202) 66 itd. a(cid:285) do 90 dla Z. W tabeli 1.2 pokazano gar(cid:258)(cid:202) wybranych pozycji z tabeli (kodu) ASCII. Szyfrowanie AES w uj(cid:218)ciu ogólnym Zanim przyjrzymy si(cid:218) szczegó(cid:239)om szyfrowania AES, omówimy ten proces pobie(cid:285)nie. Klucze szyfrowania w AES s(cid:200) liczbami dwójkowymi. D(cid:239)ugo(cid:258)(cid:202) klucza mo(cid:285)e si(cid:218) zmienia(cid:202), lecz omówimy najprostsz(cid:200) wersj(cid:218) AES, w której jest stosowany klucz 128-bitowy. Za pomoc(cid:200) matematycznego poszerzania klucza AES przekszta(cid:239)ca pierwotny 128-bitowy klucz w jedena(cid:258)cie kluczy 128-bitowych. Tekst jawny jest dzielony w AES na bloki po 16 bajtów w siatce 4(cid:117)4; siatk(cid:218) dla przyk(cid:239)adowego komunikatu Send more money! przedstawiono na rysunku 1.14. Grube linie oddzielaj(cid:200) szesna(cid:258)cie bajtów, a cienkie linie oddzielaj(cid:200) bity w bajtach. Dane tekstu jawnego s(cid:200) dzielone na tyle 16-bajtowych bloków, ile trzeba. Je(cid:258)li ostatni blok nie jest pe(cid:239)ny, jego reszt(cid:218) uzupe(cid:239)nia si(cid:218) losowymi liczbami dwójkowymi. 8 Z ang. przy(cid:258)lijcie wi(cid:218)cej pieni(cid:218)dzy! — przyp. t(cid:239)um. 9 Z ang. standardowy ameryka(cid:241)ski kod wymiany informacji — przyp. t(cid:239)um. S z y f r o w a n i e 29 Poleć książkęKup książkę Tabela 1.2. Wybrane pozycje z tabeli ASCII Znak (spacja) ! , . A B C D E a b c d e Liczba dziesi(cid:218)tna Bajt dwójkowy 32 33 44 46 65 66 67 68 69 97 98 99 100 101 01000000 01000001 00101100 00101110 01000001 01000010 01000011 01000100 01000101 01100001 01100010 01100011 01100100 01100101 Rysunek 1.14. Przyk(cid:239)adowy komunikat „Send more money!” przekszta(cid:239)cony na siatk(cid:218) bajtów, gotowy do szyfrowania metod(cid:200) AES AES poddaje nast(cid:218)pnie ka(cid:285)dy 16-bajtowy blok 10 rundom (ang. rounds) szy- frowania. W jednej rundzie bajty s(cid:200) przestawiane wewn(cid:200)trz bloku i podstawiane z u(cid:285)yciem tabeli. Potem za pomoc(cid:200) operacji XOR bajty bloku s(cid:200) (cid:239)(cid:200)czone ze sob(cid:200) i z jednym ze 128-bitowych kluczy. Tak wygl(cid:200)da szyfr AES w najwi(cid:218)kszym skrócie. Przyjrzyjmy si(cid:218) teraz jego kilku krokom bardziej szczegó(cid:239)owo. Poszerzanie klucza w AES Poszerzanie klucza w systemie szyfrowania cyfrowego ró(cid:285)ni si(cid:218) nieco od omówio- nego przez nas wcze(cid:258)niej z „ksi(cid:200)(cid:285)k(cid:200) kodow(cid:200)”. Zamiast po prostu zagl(cid:200)da(cid:202) po d(cid:239)u(cid:285)szy klucz do ksi(cid:200)(cid:285)ki, AES poszerza klucz za pomoc(cid:200) tych samych narz(cid:218)dzi, których pó(cid:283)niej u(cid:285)yje do samego szyfrowania: operacji XOR, transpozycji i pro- stego podstawiania. Rysunek 1.15 przedstawia kilka pierwszych faz procesu poszerzania klucza. Ka(cid:285)dy blok na rysunku ma 32 bity, a jeden wiersz na tym rysunku przedstawia jeden klucz 128-bitowy. Oryginalny 128-bitowy klucz sk(cid:239)ada si(cid:218) z pierwszych czte- 30 R o z d z i a (cid:239) 1 Poleć książkęKup książkę Rysunek 1.15. Proces poszerzania klucza w AES rech bloków zacieniowanych na rysunku. Ka(cid:285)dy inny blok jest wynikiem operacji XOR na dwu poprzednich blokach; operacja XOR jest przedstawiona za pomoc(cid:200) znaku plus w kó(cid:239)ku. Na przyk(cid:239)ad blok 6 powstaje z wykonania XOR na blo- kach 2 i 5. Jak wida(cid:202) na rysunku, po prawej stronie, co czwarty blok jest poddawany zabie- gowi oznaczonemu etykiet(cid:200) „dodatkowe zniekszta(cid:239)canie”. Ten proces obejmuje przestawianie bajtów w bloku i podstawianie w ka(cid:285)dym bajcie warto(cid:258)ci zgodnie z tablic(cid:200) o nazwie S-boks (ang. S-box). Tablica S-boks, u(cid:285)ywana zarówno w poszerzaniu klucza, jak i pó(cid:283)niej, w samym szyfrowaniu, jest starannie zaprojektowana z my(cid:258)l(cid:200) o wzmocnieniu ró(cid:285)nic w tek- (cid:258)cie jawnym. Oznacza to, (cid:285)e dwa podobne do siebie bajty tekstu jawnego b(cid:218)d(cid:200) mia(cid:239)y z regu(cid:239)y zupe(cid:239)nie ró(cid:285)ne podstawienia w S-boksie. Pierwszych osiem pozy- cji tej tabeli pokazano w tabeli 1.3. Tabela 1.3. Wyj(cid:200)tki z tablicy S-boks Oryginalny wzorzec bitowy Zast(cid:218)puj(cid:200)cy wzorzec bitowy 00000000 00000001 00000010 00000011 00000100 00000101 00000110 00000111 00001000 00001001 01100011 01111100 01110111 01111011 11110010 01101111 01101111 11000101 00110000 00000001 Rundy szyfrowania AES Kiedy AES utworzy wszystkie potrzebne klucze, mo(cid:285)na rozpocz(cid:200)(cid:202) faktyczne szy- frowanie. Przypomnijmy, (cid:285)e binarny tekst jawny jest pami(cid:218)tany w siatce 16 bajtów, czyli na 128 bitach, to znaczy ma tak(cid:200) sam(cid:200) d(cid:239)ugo(cid:258)(cid:202) jak pierwotny klucz. Nie jest to przypadek. Pierwszy krok rzeczywistego szyfrowania polega na wykonaniu XOR S z y f r o w a n i e 31 Poleć książkęKup książkę 128-bitowej siatki danych z pierwotnym 128-bitowym kluczem. Teraz robota rusza na dobre, jako (cid:285)e siatka danych jest poddawana 10 rundom cyfrowego zniekszta(cid:239)- cania. Ka(cid:285)da runda sk(cid:239)ada si(cid:218) z czterech kroków. 1. Podstawianie Ka(cid:285)dy z 16 bajtów w siatce jest zast(cid:218)powany z u(cid:285)yciem tej samej tablicy S-boks, która by(cid:239)a u(cid:285)yta do poszerzania klucza. 2. Transpozycja wiersza Nast(cid:218)pnie bajty s(cid:200) przesuwane na ró(cid:285)ne pozycje w obr(cid:218)bie swojego wiersza w siatce. 3. Kombinacja kolumn Dalej dla ka(cid:285)dego bajta w siatce jest obliczany nowy bajt na podstawie kombinacji wszystkich czterech bajtów w danej kolumnie. W tym obliczeniu znów wyst(cid:218)puje operacja XOR, a tak(cid:285)e binarna odmiana przestawiania. Aby da(cid:202) posmak tego procesu, na rysunku 1.16 ukazujemy obliczenie skrajnego lewego bajta w najni(cid:285)szym wierszu. Cztery bajty skrajnej lewej kolumny s(cid:200) XOR-owane razem po uprzednim przestawieniu bitów w górnym i dolnym bajcie kolumny. Ten rodzaj przestawienia nosi nazw(cid:218) rotacji bitowej (ang. bitwise rotation)10: bity s(cid:200) przesuwane o jedn(cid:200) pozycj(cid:218) w lewo, a „wypadaj(cid:200)cy” skrajny bit z lewej trafia na skrajn(cid:200) pozycj(cid:218) po prawej stronie. Rysunek 1.16. Jedna cz(cid:218)(cid:258)(cid:202) kroku zniekszta(cid:239)cania kolumnowego w rundzie AES 10 Inna nazwa: przesuwanie cykliczne — przyp. t(cid:239)um. 32 R o z d z i a (cid:239) 1 Poleć książkęKup książkę Ka(cid:285)dy bajt w nowej siatce jest obliczany podobnie, przez kombinacj(cid:218) bajtów w kolumnie za pomoc(cid:200) XOR; jedyna ró(cid:285)nica dotyczy wyboru bajtów, których bity s(cid:200) rotowane przed wykonaniem XOR. 4. Wykonanie XOR z kluczem szyfru Na koniec siatka powsta(cid:239)a w poprzednim kroku jest XOR-owana z kluczem tej rundy. Dlatego w(cid:239)a(cid:258)nie trzeba poszerzy(cid:202) klucz, aby w ka(cid:285)dej rundzie operacja XOR by(cid:239)a wykonywana z innym kluczem. Podczas deszyfrowania AES s(cid:200) wykonywane te same kroki, co podczas szyfro- wania, tylko w odwrotnej kolejno(cid:258)ci. Poniewa(cid:285) jedynymi operacjami w szyfro- waniu s(cid:200) XOR-y, proste podstawianie z S-boksu i przestawienia bitów i bajtów, wszystko jest odwracalne, je(cid:258)li klucz jest znany. (cid:146)a(cid:241)cuchowanie bloków Szyfrowanie AES mo(cid:285)na by stosowa(cid:202) z osobna do ka(cid:285)dego 16-bajtowego bloku pliku, lecz nara(cid:285)a(cid:239)oby to kryptogram na niebezpiecze(cid:241)stwa. Jak powiedzieli(cid:258)my, im cz(cid:218)(cid:258)ciej jest u(cid:285)ywany klucz szyfrowania, tym wi(cid:218)ksza mo(cid:285)liwo(cid:258)(cid:202), (cid:285)e atakuj(cid:200)cy odkryj(cid:200) i wykorzystaj(cid:200) wzorce. Pliki komputerowe s(cid:200) niejednokrotnie olbrzymie, wi(cid:218)c u(cid:285)ywan
Pobierz darmowy fragment (pdf)

Gdzie kupić całą publikację:

Jak działa oprogramowanie? Tajemnice komputerowych mechanizmów szyfrowania, obrazowania, wyszukiwania i innych powszechnie używanych technologii
Autor:

Opinie na temat publikacji:


Inne popularne pozycje z tej kategorii:


Czytaj również:


Prowadzisz stronę lub blog? Wstaw link do fragmentu tej książki i współpracuj z Cyfroteką: