Jump to content
  • entries
    20
  • comments
    161
  • views
    24,045

[sssh, no words now]Czyli krótka rozprawa o szyfrowaniu kluczem jednorazowym

Sign in to follow this  
Hakken

749 views

Przedsłowie

Ten wpis jest pierwszym (i mam nadzieję, że nie ostatnim) wpisem poświęconym kryptologii, czyli w skrócie nauką o tworzeniu i łamaniu szyfrów.

Zacznę od prostych szyfrów, następnie planuję przejść przez bardziej skomplikowane, a później zajmę się hashami (czy jak to w naszym języku się mówi "skrótami").

Niestety ze względu na wysokie skomplikowanie większości zagadnień, nie będę w stanie przedstawić pełnej matematycznej aparatury stojącej za każdym z omawianych zagadnień.

Abstrakt

One-time pad, zwany po Polsku szyfrem z kluczem jednorazowym jest bardzo łatwym do zrozumienia, ale niemożliwym do złamania szyfrem.

Jego siła opiera się na pełnej losowości klucza. Niestety, jest niepraktyczny, więc obecnie nie jest szeroko używany.

Kryptografia - zasada działania

Sposób działania tego szyfru jest bardzo prosty. Jest to funkcja, która przyjmuje dwa ciągi jedynek i zer - pierwszy będący szyfrowaną wiadomością, a drugi kluczem.

Wynikiem jest ciąg jedynek i zer powstały poprzez wykonanie operacji xor (czyli alternatywy wykluczającej) na ciągach wejściowych.

Należy jednak pamiętać, że klucz musi być całkowicie losowy, a także nie może on być użyty więcej niż jeden raz.

Musi też być tej samej długości, co szyfrowana wiadomość.

Deszyfrowanie wiadomośći przeprowadza się dokładnie tak samo, jak szyfrowanie (xoruje się tekst zaszyfrowany i klucz).

Jak działa xor

xor jest funkcją, która przyjmuje dwa argumenty. Każdy z nich jest zerem lub jedynką. Wynikiem xor-a jest 1, jeżeli podane znaki są różne, natomaist gdy znaki są równe, to wynikiem jest 0.

1 xor 0 = 0 xor 1 = 1

0 xor 0 = 1 xor 1 = 0

Określimy funkcję xor na ciągach zer i jedynek tak, że będzie to działanie zdefiniowanej wyżej funkcji na kolejnych parach z obu ciągów.

Przykład:


10110010
01100111
________ xor
11010101

Uwaga

Mówię tutaj cały czas o ciągach zer i jedynek - jak to ma się do szyfrowania tekstu?

Wystarczy sobie uświadomić, że w pamięci komputera tekst jest kodowany jako ciąg wartości binarnych (czyli właśnie zer i jedynek), a więc to takie wartości musimy de facto szyfrować.

Kryptoanaliza - rozważania na temat łamania tego szyfru

Przy zachowaniu warunków o których pisałem wcześniej szyfru tego nie da się złamać. Oznacza to, że jeśli komuś uda się przechwycić naszą zaszyfrowaną wiadomość (ale nie klucz), to jedyne co jest w stanie o niej powiedzieć, to jej długość.

Dlaczego? Przyjmijmy, że przechwyciliśmy następującą zaszyfrowaną wiadomość: "011101010100011101". Teraz dla każdego ciągu binarnego o długości 18 (bo tyle znaków ma przechwycona wiadomość) możemy dobrać taki klucz, żeby po deszyfracji otrzymać właśnie tę wiadomość którą wybraliśmy.

Przykładowo możemy przyjąć, że wiadomość jawna to "110100100101101001". Wtedy kluczem byłoby "101001110001110100" (xor obu wiadomości). Ale równie dobrze (z równym prawdopodobieństwem) wiadomością może być "000100100101101001", a wtedy kluczem byłby ciąg "11001110001110100".

Nawet przy nieskończonej mocy obliczeniowej napastnik nie jest w stanie stwierdzić, który klucz jest poprawny. Ma on zbyt mało danych.

To tak, jakbyśmy mieli rozwiązać równanie a+b=7 nie znając wartości a ani b. Jest nieskończenie wiele równie dobrych rozwiązań.

Stosując ten szyfr jesteśmy podatni na zmianę wiadomości przez atakującego.

Przyjmijmy, że ktoś przechwycził zaszyforwaną wiadomość, której tekstem jawnym jest "Spotkajmy się jutro o 15:30."

Jeśli osoba przechwytująca wie, że ostatnimi znakami jest godzina spotkania, to może je łatwo zastąpić przez cokolwiek innego (skoro zna tekst jawny i zaszyforwany, to może obliczyć klucz).

Odbiorca nie jest w stanie zweryfikować, czy wiadomość nie została gdzieś zmieniona.

Podsumowanie

Poważnymi wadami tego szyfru jest rozmiar klucza (przesłane dane muszą być dwa razy większe) oraz podatność na modyfikację wiadomości. Co więcej, klucz musi być przekazany w sposób bezpieczny, a jego generacja musi być w pełni losowa.

Generowanie dużych losowych danych nie jest łatwe z programistycznego punktu widzenia, a ponowne użycie tego samego klucza może być tragiczne w skutkach (szyfr może wtedy zostać złamany).

Osiągnięcie sprzyjających warunków jest zazwyczaj bardzo trudne, dlatego też szyfr ten nie jest powszechnie stosowany.

Mimo to, jest to szyfr, którego nie da się złamać, wiec samo to zasługuje na uwagę.

Jak zawsze zachęcam do komentowania, dyskutowania i zadawania pytań.

Sign in to follow this  


2 Comments


Recommended Comments

Ciekawostką jest, że Rosjanie jeszcze na początku XXw używali często szyfru Cezara, bo ich niewykształceni sztabowcy byli wstanie pojąć tylko ten właśnie szyfr.

Pytanie do Hakkena: miałeś kryptografie na studiach, czy sam ogarniasz temat hobbystycznie?

Share this comment


Link to comment

Ciekawostką jest, że Rosjanie jeszcze na początku XXw używali często szyfru Cezara

Wiele organizacji którym zależało na bezpieczeństwie używało własnych, autorskim (i tajnych) systemów zabezpieczeń.

Dziwnym trafem po ujawnieniu metody działania zwykle okazywało się, że dany szyfr jest o wiele gorszy niż otwarte, popularne szyfry ;).

miałeś kryptografie na studiach, czy sam ogarniasz temat hobbystycznie?

Jeszcze nie miałem, ale mieć będę.

To, co umiem nauczyłem się we własnym zakresie (z książek, artykułów etc).

Share this comment


Link to comment
Guest
Add a comment...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...