P
Q
XOR(p,Q)
Szyfrowanie i kryptografia Klasyczna cz.1 - wstęp
Kryptografia klasyczna – część kryptologii , która zajmuje się przekazywaniem informacji między dwoma stronami w bezpieczny sposób – tzn. po przejęciu informacji osoba podsłuchująca nie jest w stanie jej odczytać. Polega na szyfrowaniu tekstu jawnego przed wysłaniem, a po otrzymaniu – deszyfracji w celu odczytu. Sama kryptografia skupia się wyłącznie na wiedzy o utajnianiu informacji. Tekst został przygotowany przez KN Qubit.
Podstawowe szyfrowanie informacji w kryptografii klasycznej
Spis treści
Szyfr Podstawieniowy (Szyfr Cezara)
Jest to szyfr przypisujący każdej literze alfabetu inną literę, przypisaną tylko do niej. W najprostszym wydaniu (szyfr Cezara) „przesuwa się” daną literę o kilka pozycji w alfabecie. Jeżeli przesunięcie jest o 7 pozycji (w alfabecie łacińskim bez polskich znaków), to „a” kodujemy na „h”, „b” na „i”, natomiast „z” na „g”. Ogólniejszym sposobem jest losowe pomieszanie przypisanych liter.
Jednak tego typu szyfr jest podatny na tzw. analizę częstotliwościową. Litery w danym języku występują z różną częstotliwością i to pozwala je rozróżnić. Np. litera „a” wystąpiła w tym akapicie 50 razy, kiedy „ż” tylko 7. Każdy język ma swój charakterystyczny rozkład, który pozwala na deszyfrację, zwłaszcza dłuższych tekstów.
Szyfr z kluczem jednorazowym (ang. One Time Pad)
Szyfrowanie z kluczem jednorazowym nie jest podatne na tego typu analizę. Polega ono na kodowaniu znaków z użyciem klucza, który się nie powtarza. Jest to sekwencja znaków lub liczb, o długości co najmniej tekstu jawnego. Może być to ciąg losowych liczb, przekazany bezpiecznym kanałem, umówiona książka , której kolejne litery zamieniamy na ich miejsce w alfabecie, lub inny chaotyczny zbiór znaków. Jednak zauważmy, że książka jest napisana konkretnym językiem, której litery mają wcześniej wspomnianą charakterystykę występowania. Stąd w celu zapewnienia najwyższego bezpieczeństwa w praktyce stosuje się losowo generowane ciągi liczb. Jeżeli jest on prawdziwie losowy to mówimy o bezpieczeństwie bezwarunkowym. Obie strony mają całkowicie losowy ciąg, który może zmienić tekst jawny w losowo wybrany szyfrogram (zaszyfrowany tekst) z wszystkich możliwych do utworzenia szyfrogramów z tego tekstu. Stąd osoba podsłuchująca może jedynie zgadywać jaki był oryginał.
Szyfr polialfabetyczny
Wybieramy słowo szyfrujące i każdą z jego liter zamieniamy na miejsce porządkowe w alfabecie („a”-> 1, „b” -> 2 itd.). Dzięki tym liczbom przesuwamy kolejne litery tekstu jawnego o odpowiednią ilość miejsc (podobnie jak w szyfrze Cezara). Różnica polega na tym, że jedna litera słowa szyfrującego jest używana do jednej litery tekstu jawnego, zamiast przesuwania wszystkich liter o tę samą ilość pól.
Po użyciu każdej z liter słowa szyfrującego znowu zaczynamy od pierwszej litery. Metoda ta jest pośrednią między szyfrowaniem z kluczem jednorazowym a podstawieniowym. Jej bezpieczeństwo zależy od długości słowa i skomplikowania funkcji wiążącej szyfrowaną literę i fragment klucza do niej przypisany.
Kryptografia klucza symetrycznego i publicznego:
Kryptografia klucza symetrycznego
Metoda szyfrowania stosowana od początku powstania kryptografii, stosowana już przed naszą erą. Polega na identyczności klucza, który szyfruje i deszyfruje. Obecnie z klucza symetrycznego korzystają dwa rodzaje szyfrów.
Szyfr blokowy
Pierwszy z nich – szyfr blokowy, w zależności od poziomu skomplikowania jest mniej lub bardziej ulepszoną wersją szyfru polialfabetycznego. Na podstawie podanego bloku klucza dzieli tekst jawny na bloki takiej samej długości jak klucz i kolejno szyfruje je zadaną funkcją. Nie jest on bezwarunkowo bezpieczny, ale część protokołów nadal pozostaje w użyciu ze względu na złożoność (3DES, AES, szyfrowanie wiadomości mailowych, oprogramowania bankomatów).
Szyfry strumieniowe
Druga kategoria to szyfry strumieniowe. Rozkodowywują znaki na bity je zapisujące. Dalej z dowolnie długiego klucza, po kolei, bit po bicie oryginał jest łączony z kluczem (najczęściej alternatywą rozłączną – XOR):
0
0
0
0
1
1
1
0
1
1
1
0
Jest to szyfrowanie bardziej fundamentalne, niż szyfrowanie blokowy i metoda z kluczem jednorazowym zapewnia bardzo dobry poziom bezpieczeństwa.
Kryptografia klucza publicznego (asymetrycznego)
Kryptografia klucza publicznego (asymetrycznego) – idea tego szyfrowania jest stosunkowo nowa, pierwsze prace pojawiły się około 50 lat temu. Sama koncepcja polega na dostępności klucza szyfrującego dla wszystkich, jednak do rozszyfrowania wymagany jest klucz prywatny. Stąd nazywamy ten sposób szyfrowaniem z kluczem asymetrycznym. Oba klucze są oczywiście powiązane ze sobą w matematyczny sposób, jednak uzyskanie klucza prywatnego z publicznego jest bardzo trudne. Rozumiemy przez to długi czas przeprowadzenia obliczeń, który uniemożliwia złamanie zabezpieczenia, nawet z dużymi zasobami mocy obliczeniowej.
Do szyfrowania z kluczem publicznym korzysta się przykładowo z problemu faktoryzacji liczb. Najsłynniejszym tego typu algorytmem jest RSA.
Algorytm Rivesta-Shamira-Adlemana (RSA):
Algorytm stworzony w 1977 r. stosowany do dzisiaj. Generowanie kluczy przebiega w następujący sposób:
- Wybieramy dwie liczby pierwsze „p” i „q”. Muszą być duże (próba złamania musi być wystarczająco czasochłonna, a znane są przypadki złamania kodu z liczbami ponad 100-cyfrowymi [1][2]), niezbyt bliskie siebie (wtedy wystarczy spierwiastkować ich iloczyn, dostępny publicznie, i zacząć poszukiwania obu liczb od tego miejsca) oraz podobnego rzędu wielkości (jeżeli jedna liczba będzie miała 150 cyfr, a druga 100, to problem będzie tak prosty jakby były to dwie 100-cyfrowe liczby).
- Obliczamy iloczyn:
- Obliczamy tzw. funkcję Eulera
- Wybieramy liczbę e taką, że
i jest ona względnie pierwsza z
- Znajdujemy d z wzoru
Oznacza to, że d po wymnożeniu z e, daje resztę z dzielenia przez φ(n) równą 1.
Liczba e służy do szyfrowania informacji (ang. encryption), d do deszyfracji (ang. decryption). W ten sposób klucz publiczny zostaje udostępniony jako para liczb (n, e), natomiast prywatny to para (n, d). W jaki sposób ten skomplikowany algorytm zapewnia bezpieczeństwo?
Chodzi o problematyczność rozłożenia liczby n na czynniki pierwsze. Powszechnie używa się liczb wielkości 2048 bitów (ok. 616 cyfr) i przez to niemożliwe staje się uzyskanie pary liczb p i q, a tylko one umożliwiają uzyskanie liczby d potrzebnej do rozszyfrowania wiadomości. Stąd możemy spokojnie podawać liczbę n do informacji publicznej, bez obawy o złamanie naszego szyfru. Jedynym warunkiem jest bezpieczne dostarczenie do odbiorcy klucza prywatnego.
W jaki sposób szyfruje się wiadomości za pomocą liczb e i d?
Musimy zamienić blok wiadomości na wartość liczbową m. Nie może być ona większa niż n. Potem każdy z bloków kodujemy w c:
Żeby odkodować c:
Dlatego jako klucz publiczny traktujemy parę (n,e), a prywatny (n,d). To wszystko co potrzebne co zakodowania i odkodowania informacji. Zauważmy, że przez kod publiczny każdy może zakodować informację w ten sam sposób co nadawca klucza publicznego.
Bibliografia
[1] Cavallar, Dodson, Lenstra Factorization of a 512-bit RSA Modulus [2006]
https://eprint.iacr.org/2010/006.pdf
[2] Kleinjung, Aoki, Franke Factorization of a 512-bit RSA Modulus [2010]
https://www.iacr.org/archive/eurocrypt2000/1807/18070001-new.pdf
Na zakończenie
To pierwsza część serii poświęconej kryptografii. W najbliższym czasie pojawią się wpisy poświęcone kryptografii kwantowej i postkwantowej. Zapraszamy do zapoznania się z pozostałymi wpisami poświęconymi informatyce kwantowej.
Autorzy
- Marek Kowalik
- Urszula Lajzner
- Michał Łukomski
- Janusz Twardak