est to pierwszy post z 3 częściowej serii na temat podstaw kryptografii. Seria jest przedstawiona w następujący sposób:
- Szyfrowanie symetryczne
- integralność danych& Szyfrowanie uwierzytelnione
- szyfrowanie asymetryczne z parami kluczy publicznych/prywatnych
zanurzenie się w świecie informatyki może być trudnym zadaniem. Zwłaszcza sam!, W tej serii blogów chciałbym zaoferować przegląd podstaw kryptografii na wysokim poziomie dla tych, którzy chcą zagłębić się w ten temat, którzy niekoniecznie wiedzą, od czego zacząć. Ten przegląd jest oparty w szczególności na moich głównych wykładach z kursu kryptografii Stanforda i, prowadzonego przez Dana Boneha, dostępnego na Coursera.
zdecydowałem się na ten kurs, ponieważ jestem programistą blockchain, który nie pochodził z tradycyjnego środowiska comp-sci. Studiowałem ekonomię w college ' u, ale gdy zaczynałem karierę, bardziej zwróciłem się ku programowaniu komputerowemu., Odkąd zacząłem kodować, miałem misję, aby „zbliżyć się do komputera” — oderwać warstwy abstrakcji, które lubiłem jako programista stron internetowych i zrozumieć, co dzieje się pod maską. Przejście na kryptowaluty i systemy rozproszone z tworzenia stron internetowych było dzikim i wspaniałym krokiem w tym kierunku pod wieloma względami, z których nie mniej ważne było zapoznanie się z pojęciami kryptografii. Chciałem jednak solidniejszego fundamentu., Ponieważ jest to dość rozległa dziedzina, pomyślałem, że warto było upuścić $ 70, aby spożywać te informacje na forum specjalnie przygotowanym z Uniwersytetu Stanforda. Możesz również audytować ten kurs bez przekazywania zadań za darmo. Cuda Internetu!
zaczynajmy.
zasadniczo kryptografia jest praktyką bezpiecznej komunikacji w obecności potencjalnych przeciwników stron trzecich. Koncepcja bezpiecznej komunikacji składa się z 2 głównych punktów:
- Zabezpieczenie przed podsłuchem: zapewnia to poufność danych.,
- bezpieczeństwo przed manipulacją danymi: zapewnia to integralność danych, co oznacza, że nikt nie może manipulować danymi, które wysłałeś i oszukać odbiorcy, aby zaakceptował zmanipulowane dane jako ważne.
poufność danych uzyskuje się poprzez szyfrowanie, które może przybierać dwie formy: symetryczną i asymetryczną.
- Szyfrowanie symetryczne wykorzystuje jeden klucz, który musi być udostępniony wszystkim uczestnikom, którzy się komunikują.
- szyfrowanie asymetryczne wykorzystuje klucze osobiste., Każdy uczestnik ma swój własny klucz publiczny i klucz prywatny do szyfrowania i deszyfrowania wiadomości podczas komunikacji.
(Uwaga: Ten blog będzie mówił o kryptografii w kontekście szyfrowania symetrycznego. W kolejnym poście zajmiemy się szyfrowaniem asymetrycznym.)
szyfrowanie danych: dwa typy Szyfrów
szyfrowanie zapewnia poufność danych i obejmuje dwa ważne elementy:
- klucz tajny: w kontekście szyfrowania symetrycznego możemy założyć, że nasi uczestnicy, Alice i Bob, mają wspólny klucz tajny.,
- szyfr: zestaw algorytmów, jeden do szyfrowania, a drugi do deszyfrowania.
należy pamiętać, że algorytmy szyfrowania i deszyfrowania są publicznie znane. Jedyną tajemnicą jest klucz.
dwa typy szyfrów to szyfry strumieniowe i blokowe. Potencjalnym warunkiem odpowiedniego zrozumienia obu tych szyfrów jest znajomość operacji bitowych(operacji wykonywanych na bitach). Dokładniej, pojęcie wyłączności-lub (XOR). Znalazłem ten blog, aby dać bardzo jasne wyjaśnienie operacji bitowych., Możesz też spróbować zrozumieć koncepcję XOR, korzystając z poniższego zdjęcia. Zasadniczo dwa bity są połączone i jeśli są różne (jeden 0 i jeden 1), to dają 1, a jeśli są takie same, (oba 0 lub oba 1), to dają 0. Od teraz zakładam, że czytelnik rozumie pojęcie XOR i że uniwersalna notacja dla XOR to: ⊕
szyfr strumieniowy
szyfr strumieniowy jest symetrycznym szyfrem klucza, w którym tekst jawny (w postaci bajtów) jest XOR ' d bit po bitie z kluczem (również w postaci bajtów) do wytworzenia zaszyfrowanego szyfru., Ten sam proces jest używany do odszyfrowywania tekstu szyfrowego. Biorąc pod uwagę naturę operacji XOR, jeśli użyjemy XOR zaszyfrowanego tekstu z kluczem, spowoduje to powrót z oryginalnym tekstem jawnym.
bystry czytelnik może zdać sobie sprawę z tego opisu, że klucz (oznaczony na powyższej ilustracji jako „strumień szyfrów”) i tekst jawny muszą mieć coś bardzo ważnego wspólnego. Zgadza się! Klucz i tekst jawny muszą być tej samej długości., To oczywiście nie jest bardzo praktyczne.
aby uczynić szyfr strumieniowy bardziej praktycznym, wprowadzono ideę generatora pseudorandomu. Generator pseudorandomu jest deterministyczną procedurą, która pobiera dane wejściowe i wyprowadza jeszcze dłuższy wynik pseudorandomu. Jako deterministyczna procedura oznacza, że zawsze zwróci dokładnie to samo wyjście, jeśli podane zostanie to samo wejście (np.” abc123 „daje za każdym razem” 8474f24e0d72e1b949ffd2…”)., Słowo pseudorandom oznacza, że chociaż wyjście nie jest w rzeczywistości losowe (ponieważ jest określone na podstawie konkretnego wejścia), jest w rzeczywistości nie do odróżnienia od prawdziwie losowego ciągu. Innymi słowy, biorąc pod uwagę próbkę wejść i wyjść, nie ma wskazówek, które wyjście odpowiada konkretnemu wejściu i odwrotnie, dlatego jest pseudorandom. Można użyć współdzielonego klucza tajnego jako danych wejściowych, aby wytworzyć jeszcze dłuższy pseudorandomowy klucz, który będzie działał jako długi klucz XOR ' D z równie długim tekstem jawnym.,
ta specyficzna implementacja szyfru strumieniowego, którą do tej pory zilustrowaliśmy, nazywa się „one-time-pad”. Niezwykle ważną cechą podkładki jednorazowej jest to, że klawisz jednorazowy może być używany tylko jeden raz. Gdy zostanie użyty po raz drugi, bezpieczeństwo tych wiadomości jest zagrożone.
Na zdjęciu poniżej slajd z kursu. PRG (K) oznacza pseudorandomową sekwencję generowaną z naszego klucza wspólnego K. symbol ⊕ oznacza XOR. c oznacza tekst szyfrowy. m oznacza wiadomość (lub zwykły tekst).,
zasadniczo, ten slajd mówi, że gdy klucz zostanie użyty dwukrotnie, możemy XOR szyfrogramów razem, a to jest dokładnie równe XOR ' ining dwóch prostokąt razem. Ponieważ w języku angielskim istnieje wystarczająca nadmiarowość, doświadczony atakujący może wykorzystać te informacje do całkowitego odzyskania wiadomości.
aby zachować jeden wspólny klucz tajny, można użyć pojęcia nonce, aby upewnić się, że nigdy nie powtórzymy klucza jednorazowego., Nonce to dowolna liczba, która może być użyta tylko raz w komunikacji kryptograficznej. Podczas wysyłania zaszyfrowanego tekstu nadawca może również wysłać nonce do połączenia z tajnym kluczem, aby następnie użyć go jako wejścia do wytworzenia odrębnego pseudorandomowego klucza dla każdego szyfrowania.
(być może zauważyłeś powyższy slajd mówi atak 1., Na marginesie, dla tych, którzy zastanawiają się, co to jest atak 2, atakiem 2 jest fakt, że chociaż szyfr strumieniowy zapewnia poufność danych, nie zapewnia integralności danych zdefiniowanej w pierwszej sekcji)
szyfr blokowy
drugim typem szyfru jest szyfr blokowy. Szyfr blokowy przyjmuje wejście o stałej długości i iteratywnie szyfruje tekst zwykły, używając innego klucza („okrągłego klucza”) dla każdej rundy i ostatecznie wysyła tekst szyfrowy o tej samej długości. 3DES i AES to dwa przykłady szyfrów blokowych, które przyjmują wejście odpowiednio 48 bitów i 128 bitów.,
powyższy slajd pokazuje podstawową architekturę szyfru blokowego. Widać, że mechanizm rozszerzania klucza jest używany, aby mieć nowy klucz dla każdej rundy. Tekst jawny, oznaczony (m) dla wiadomości, jest zaszyfrowany wielokrotnie, aż w końcu zostanie zwrócony odpowiedni tekst szyfrowy (c) O Tej Samej długości.
ze względu na zwięzłość, będę opisywał AES w tym blogu., Chociaż DES/3DES ma znaczenie historyczne, dziś AES jest szerzej stosowany i akceptowany.
AES jest zbudowany jako sieć permutacji zastępczej. AES działa na 128-bitowym bloku, równym 16 bajtom. Jak na zdjęciu powyżej w lewym górnym rogu, zapisujemy 16 bajtów jako macierz 4 na 4. Macierz ta służy jako struktura danych dobra do tasowania danych wokół., W każdej rundzie proces wygląda następująco:
- najpierw XOR okrągły klucz (k0) z bieżącą wiadomością
- następnie przechodzimy przez proces zastępowania, w którym bloki danych są zastępowane innymi blokami bazującymi na podanej tabeli zastępowania (na zdjęciu powyżej (1) ByteSub).
- przechodzimy przez warstwę permutacji, gdzie bity są permutowane i tasowane(na zdjęciu powyżej (2) ShiftRow& (3) MixColumn).
- następnie powtarzamy ten proces przez 10 rund.,
na powyższym zdjęciu zauważysz, że ostatnia runda pomija krok kolumny Mix, XOR jest wynikiem za pomocą naszego klucza ostatniej rundy i wyświetla nasz wynikowy tekst szyfrowy. Aby odszyfrować, po prostu odwracamy proces. Kurs oferuje przegląd tego procesu szyfrowania na wysokim poziomie i zachęca uczniów do głębszego przyjrzenia się temu, jeśli jest to dla Ciebie interesujące. Dlatego zostawię w tym wewnętrzne działania AES. Polecam ludziom zajrzeć do procedury sieci Fiestel 3DES dla Zabawy porównać i kontrast różnych szyfrów blokowych.,
jeśli chodzi o sprzęt, od czasu premiery Intela Westmere, Intel zaprojektował swoje procesory ze specjalnymi instrukcjami optymalizacji AES wbudowanymi bezpośrednio w ich sprzęt, A AMD wkrótce potem podążyło za tym.
tryby działania szyfru blokowego
w przeciwieństwie do szyfru strumieniowego, szyfr blokowy przyjmuje tylko dane wejściowe o stałej długości. Oczywiście chcemy obsługiwać dane, które są większe niż 16 bajtów na raz. Więc dalej ważne jest, aby zrozumieć tryby działania, w których możemy używać szyfrów blokowych do szyfrowania dużych zbiorów danych., Aby zastosować ten szyfr blokowy do dużego zbioru danych, pierwszy tryb działania, który może przyjść na myśl, nazywa się „elektroniczna Księga kodów” (ECB). EBC po prostu dzieli dane na 16 bajtowe bloki i jednolicie wykonuje szyfrowanie AES. Można to zrobić nawet równolegle. Bardzo szybko! Ale to nie jest zbyt bezpieczne.
jest to niebezpieczne, ponieważ jeśli 16-bajtowa wiadomość się powtórzy, zaszyfrowany tekst będzie również zawierał powtarzane dane., Ujawnia to informacje o naszych danych potencjalnemu atakującemu. Tę lukę możemy zastosować do przypadku, w którym szyfrujemy obraz za pomocą ECB. Jak widać poniżej, to jasne, że nasz obraz jest headshot. W silnie czarnym obszarze widzimy sylwetkę poprzez ciemne włosy i koszulę.
ważne jest, aby nasze Schematy szyfrowania były semantycznie bezpieczne., Bezpieczeństwo semantyczne polega na tym,że jeśli mamy zaszyfrowany tekst, który odpowiada jednemu z dwóch różnych tekstów jawnych, przeciwnik nie może odgadnąć z większym prawdopodobieństwem niż 1/2, który tekst jawny odpowiada tekstowi jawnemu. Oczywiście EBC nie jest semantycznie Bezpieczny. Nasz zaszyfrowany obraz daje nam mnóstwo informacji, aby odgadnąć odpowiadający mu zwykły obraz.
EBC jest przykładem trybu pracy z kluczem jednorazowym (co oznacza, że podobnie jak klawisz jednorazowy, klucz może być użyty tylko raz). Innym bezpieczniejszym trybem działania klucza jednorazowego jest deterministyczny tryb licznika. Możesz sam się temu przyjrzeć., Przejdę do bezpiecznych trybów pracy, które umożliwiają wielokrotne klucze!
Cipher Block Chaining (CBC) to sposób działania, który łączy każdy 16-bajtowy blok tekstu jawnego razem poprzez XOR ' ING zaszyfrowany tekst poprzedniego tekstu jawnego z naszym bieżącym tekstem jawnym przed wykonaniem szyfrowania szyfru blokowego (np. AES). Poniższy obraz wyjaśnia tę koncepcję:
zaczynamy od losowego IV., IV oznacza wektor inicjalizacji, który można zdefiniować jako: wartość początkową używaną do rozpoczęcia jakiegoś iteracyjnego procesu. W przypadku CBC IV musi być losowy (a więc nieprzewidywalny), a zatem musi być unikalny dla każdej transakcji. Pierwszy blok szyfrogramu jest po prostu niezaszyfrowanym random IV. aby wytworzyć resztę szyfrogramu, najpierw losowy IV jest XOR ' D z pierwszym blokiem zwykłego tekstu (m). Wynik zostanie zaszyfrowany okrągłym kluczem k, aby zwrócić pierwszy blok zaszyfrowanego tekstu (c)., Ten tekst zaszyfrowany jest następnie XOR ' D z następnym blokiem tekstu jawnego (m), wynik jest zaszyfrowany okrągłym kluczem k i zwraca drugi blok zaszyfrowanego tekstu (c). Proces jest kontynuowany, dopóki wszystkie bloki nie zostaną zaszyfrowane.
aby odszyfrować, po prostu odwracamy proces.
ważnym elementem szyfrowania CBC jest to, że random IV jest nieprzewidywalny., Jeśli IV stanie się przewidywalny, nasz schemat szyfrowania stanie się podatny na wybrane ataki za pomocą zwykłego tekstu. Chosen Plaintext Attack (CPA) to model ataku, który zakłada, że atakujący może uzyskać ciphertext dla dowolnych Plaintext i użyć ich do ujawnienia informacji o zaszyfrowanych wiadomościach. W związku z tym nieprzewidywalny IV jest potrzebny do zapewnienia bezpieczeństwa CPA.
proszę o cierpliwość, ponieważ staram się wyjaśnić, jak ten atak będzie działał: możliwe jest wykonanie wybranego ataku tekstowego w obecności przewidywalnych IV ze względu na naturę XOR., Jeśli XOR tej samej wartości razem (0101 ⊕ 0101) będzie zawsze równe 0, więc anuluje się. Jeśli więc podejrzewasz, że zaobserwowany tekst szyfrowy c odpowiada konkretnemu tekstowi jawnemu m, Możesz przetestować swoją hipotezę za pomocą przewidywalnego IV. Jeśli tekst jawny, o którym mowa, został zaszyfrowany za pomocą IV1, tak że c = E(k, m ⊕ IV1), możesz przesłać nowy tekst jawny do zaszyfrowania i sprawdzić, czy otrzymasz pasujący wynik: c. ponieważ możesz przewidzieć, że IV będzie IV2, wysyłasz m ⊕ IV1 ⊕ IV2., Proces CBC będzie XOR tego wejścia z następnym IV, IV2 tak, że: c = E (k, m ⊕ IV1 ⊕ IV2 ⊕ IV2) stąd IV2 anuluje się, i po raz kolejny szyfrujemy E (k, IV1 ⊕ m), co spowoduje ponownie z c i jeśli tak się stanie, byliśmy w stanie odgadnąć, co było wcześniej zaszyfrowane z IV1.
naprawdę świetna robota, jeśli przez to przeszedłeś — ^
z tym chciałbym przejrzeć jeszcze jeden tryb szyfru blokowego, który zakończy pierwszy blog z tej 3 części serii. Jeśli to był duży wysiłek, aby przejść tak daleko, teraz może być dobry czas na krótką przerwę przed kontynuacją!,
Ok, więc sprawdziliśmy EBC, CBC, i ich luki, ale na koniec, i chyba najważniejsze wprowadzę Randomized Counter Mode (CTR). Jest to najnowszy, najbezpieczniejszy tryb pracy, a także bardziej wydajny niż morfologia.
tryb licznika randomizowanego również przyjmuje losowy IV. IV służy tutaj jednak innemu celowi. Nasz klucz jest łączony (np., via AES) z iterowaną wersją naszego IV: powyżej dodajemy 1 do naszego IV dla każdej iteracji, w przeciwnym razie otrzymamy powtarzający się wynik. Robimy to, dopóki nie mamy pad Tak długo, jak nasz zwykły tekst wiadomości. Podobnie jak szyfr jednokrotnego szyfru strumieniowego, teraz XOR naszej wiadomości tekstowej z naszym pseudorandomowym pad, aby uzyskać tekst szyfrowy. Jeśli twój sprzęt ma wiele silników AES, jest to bardzo wydajne, ponieważ jest równoległe. W CBC, każdy szyfertext zależał od poprzedniego bloku szyfertext, więc nie było możliwe równoległe połączenie.,
nie potrzebujemy nawet szyfru blokowego, aby połączyć nasze IV i key w pseudorandomowy pad. Szyfry blokowe muszą być odwracalne. Jeśli przyjrzysz się dokładnie mechanice randomizowanego trybu licznika, zauważysz, że odszyfrowanie nie wymaga od nas odwrócenia F(k, IV). Biorąc pod uwagę naturę XOR, wszystko, co musimy zrobić, to zregenerować ten sam pseudorandom pad i XOR go z naszym szyfrowym tekstem. Dlatego, aby odszyfrować, musimy powtórzyć operację, a nie ją odwrócić.,
mówiąc abstrakcyjnie (dotychczas unikałem abstrakcyjnych pojęć), oznacza to, że procedura, której używamy do połączenia naszego tajnego klucza i IVF(k, IV) musi być funkcją Pseudorandomową (PRF) w przeciwieństwie do permutacji Pseudorandomowej (PRP). W rzeczywistości stosujemy te koncepcje w tym blogu. Zarówno PRPs, jak i PRFs są deterministycznymi procedurami, które, biorąc pod uwagę dane wejściowe, powodują pseudorandomowe wyjście. AES, XOR). PRP jest jednak bardziej rygorystyczny w tym sensie, że musi być odwracalny., W rzeczywistości terminy PRP i block cipher (takie jak AES) są często używane synonimicznie. PRF nie musi jednak być odwracalny. Jeśli wrócisz do poprzednich slajdów wyświetlanych w tym poście, teraz zrozumiesz notację PRF i PRP.
To kończy mój przegląd szyfrowania symetrycznego! Zajęliśmy się szyframi strumieniowymi i blokowymi. Następnie, ponieważ szyfry blokowe mogą być wykonywane tylko na około 16 bajtach na raz, omówiliśmy tryby działania używane do wykonywania szyfrów blokowych na dużych tekstach. Wyjaśniliśmy również koncepcje PRPs vs PRFs.
