Przejdź bezpośrednio do zadań

Co to jest “Cipher”?

Czy kiedykolwiek chciałeś napisać tajną wiadomość do przyjaciela, tak aby nikt inny nie mógł jej zrozumieć? W takim razie potrzebujesz Cipher, czyli szyfru! Szyfr to po prostu metoda, która przekształca zwykły tekst w “kod” poprzez zamianę znaków (często liter) na inne znaki. Wynik wygląda jak bełkot dla osób, które nie wiedzą, jak działa kod. Chodzi o to, że tylko osoby znające klucz (zasadę zamiany liter) mogą ponownie uczynić kod zrozumiały. Innymi słowy: szyfry umożliwiają tajne wiadomości, niezależnie od tego, czy jest to dziecięca zabawa z tajnym językiem, czy prawdziwi szpiedzy wysyłający zaszyfrowane wiadomości. 😄

Istnieje wiele rodzajów szyfrów – niektóre używają liczb, niektóre symboli, a nowoczesna kryptografia danych wykorzystuje bardzo skomplikowane algorytmy. Te skomplikowane algorytmy wymagają bardzo skomplikowanej matematyki, więc przyjrzyjmy się najpierw kilku prostszym algorytmom!

Monoalfabetowe Szyfry

Przyjrzyjmy się najpierw niektórym z najprostszych (i najstarszych) metod kodowania, jakie istnieją: monoalfabetowym szyfrom.

Monoalfabetowe brzmi może jak trudne słowo, ale możemy je rozłożyć: mono oznacza „jeden”, a alfabetowe dotyczy alfabetu.

Zatem monoalfabetowe szyfry to kody, w których używa się pojedynczego „alfabetu szyfrującego” dla całej wiadomości. Oznacza to, że każda litera w oryginalnym tekście jest zawsze zamieniana na tę samą literę w całej zaszyfrowanej wiadomości.

Na przykład, jeśli zdecydowałeś, że A ma być zamienione na X, wtedy wszystkie A w tekście są zamieniane na X.

Szyfr Cezara

Klasycznym przykładem szyfru monoalfabetycznego jest szyfr Cezara (nazwany na cześć Juliusza Cezara). Jest to zasadniczo reguła „przesuwania” wszystkich liter o pewną liczbę pozycji w alfabecie. Podobno sam Cezar używał przesunięcia o 3 litery w swoich tajnych wiadomościach. Działa to tak, że A staje się D, B staje się E, C staje się F i tak dalej przez cały alfabet. (Kiedy przechodzi się obok Z, zaczyna się od A ponownie.) Wiadomość, która brzmi ABC, stałaby się DEF, jeśli użylibyśmy metody Cezara.

Jak działa szyfr Cezara w praktyce:

• Wybierz klucz: Zdecyduj się na tajną liczbę (na przykład 3), która określa, o ile miejsc należy przesunąć każdą literę.
• Zamień każdą literę: Dla każdej litery w oryginalnej wiadomości znajdź literę, która znajduje się tyle miejsc po niej w alfabecie (dla klucza 3, A staje się D, B staje się E, itd. – pamiętaj, aby wrócić do A po Z, jeśli to konieczne). Możesz również uwzględnić Æ, Ø i Å, ale to będzie trochę bardziej skomplikowane.
• Zaszyfrowana wiadomość: Zastąp litery i napisz nową wiadomość z „przesuniętymi” literami. I voila – masz nieczytelny, tajny tekst, który tylko ci z kluczem mogą zrozumieć!
• Aby odszyfrować (czyli zamienić go z powrotem na czytelny tekst), wykonaj po prostu odwrotne przesunięcie. Jeśli znasz klucz (np. 3), odczytanie wiadomości jest równie łatwe, przesuwając litery 3 miejsca wstecz w alfabecie.

Szyfry monoalfabetyczne to fantastyczny sposób na poznanie zasady działania szyfrowania. Są proste i pokazują, jak możemy użyć prostej reguły (klucza) do przekształcenia zrozumiałego tekstu w coś tajemniczego i niezrozumiałego – i z powrotem. Więc następnym razem, gdy chcesz wysłać przyjacielowi tajną wiadomość, możesz użyć szyfru Cezara! Może spróbujecie stworzyć własną wersję tajnego alfabetu Cezara? 🔐✨

Zadania

Zadanie 1.1 - Szyfrowanie Cezara

Teraz napiszemy trochę kodu! Zacznijmy prosto od stworzenia szyfrowania, bazując na teorii powinno być dość proste.

Zaimplementuj szyfrowanie za pomocą szyfru Cezara, używając funkcji, która przyjmuje tekst i liczbę będącą “kluczem”, czyli o ile alfabet ma być przesunięty.

def caesar_cipher(text, shift):
    result = ""
    for char in text:
        if char.isalpha():
        # znajdź punkt startowy na podstawie wielkich i małych liter
        start = ord('A') if char.isupper() else ord('a')
        # Trudne obliczenia przesunięcia
        result += chr((ord(char) - start + shift) % 26 + start)
    else:
        result += char
    return result

Zadanie 1.2 - Dekryptacja Szyfru Cezara

Dekryptacja to po prostu wykonanie odwrotnego obliczenia do szyfrowania. Odejmujesz przesunięcie zamiast dodawać.

def caesar_decrypt(text, shift):
    return caesar_cipher(text, 26 - shift)

Inne Monoalfabetyczne Szyfry/Ciphers (np. Atbash)

Istnieją również inne monoalfabetyczne szyfry! Jednym z prostszych jest ten zwany szyfrem „Atbash”.

Jak działa Atbash?

Jest to bardzo proste, zamiast rotacji litery są mapowane na przeciwne litery alfabetu. Poniżej znajduje się tabela pokazująca mapowanie:

Zadanie 1.3 - Szyfrowanie i deszyfrowanie Atbash

Wygodą Atbash jest to, że ponieważ szyfrowanie jest transformacją 1 do 1, działa ono bezpośrednio w odwrotnej kolejności. Oznacza to, że jeśli utworzyłeś szyfrowanie, automatycznie utworzyłeś również deszyfrowanie.

Jak to można zrobić w praktyce?

Możesz albo odjąć literę w odniesieniu do Z, albo stworzyć tabelę “Look-up”. Oznacza to, tabelę lub słownik, który zawiera wszystkie litery od a do z i co z nich ma powstać. Może to być dobre rozwiązanie, jeśli chcecie stworzyć inny rodzaj szyfrowania.

letters = {
    'a': 'z'
    'b': 'y'
    'c': 'x'
    'd': 'w'
    # ... dodaj pozostałe litery w dół
}

Korzystając z tej tabeli, możesz przejść przez nią literę po literze, pobrać wartość dla każdej litery z tabeli odniesienia, a następnie ją wypisać. Co musisz zrobić w przypadku wielkich i małych liter?

Część 2 - Kryptoanaliza Szyfrów Monoalfabetycznych

W tej części spróbujecie stworzyć algorytm do “złamania” szyfru Cezara, czyli pobrać zaszyfrowany tekst, a następnie odzyskać oryginalny tekst bez znajomości klucza.

Można to zrobić w miarę ręcznie, lub spróbować wykorzystać prostą “kryptoanalizę”. Jest to koncepcja, którą przyjrzymy się głębiej później, ale na razie zajmiemy się jedną z najprostszych metod: analizą częstotliwości (frequency analysis). Możesz przeczytać więcej o tej koncepcji tutaj: Frequency Analysis lub tutaj Wikipedia - frequency analysis.

Metodę tę można stosować nie tylko w szyfrach Cezara, ale także w bardziej skomplikowanych algorytmach, jednak szyfr Cezara jest tak prosty, że analiza częstotliwości jest trywialna.

In cryptanalysis, frequency analysis is the study of the frequency of letters or groups of letters in a ciphertext. The method is used as an aid to breaking classical ciphers.

Frequency analysis is based on the fact that, in any given stretch of written language, certain letters and combinations of letters occur with varying frequencies. Moreover, there is a characteristic distribution of letters that is roughly the same for almost all samples of that language. For instance, given a section of English language, E, T, A and O are the most common, while Z, Q, X and J are rare. Likewise, TH, ER, ON, and AN are the most common pairs of letters termed bigrams or digraphs), and SS, EE, TT, and FF are the most common repeats. The nonsense phrase ETAOIN SHRDLU represents the 12 most frequent letters in typical English language text.

In some ciphers, such properties of the natural language plaintext are preserved in the ciphertext, and these patterns have the potential to be exploited in a ciphertext-only attack.

xcrgneipcpanhxhugtfjtcrnpcpanhxhxhiwthijsnduiwtugtfjtcrnduatiitghdgvgdjehduatiitghxcprxewtgitmiiwtbtiwdsxhjhtsphpcpxsidqgtpzxcvraphhxrparxewtghugtfjtcrnpcpanhxhxhqphtsdciwtupriiwpixcpcnvxktchigtirwdulgxiitcapcvjpvtrtgipxcatiitghpcsrdbqxcpixdchduatiitghdrrjglxiwkpgnxcvugtfjtcrxthbdgtdktgiwtgtxhprwpgpritgxhixrsxhigxqjixdcduatiitghiwpixhgdjvwaniwthpbtudgpabdhipaahpbeathduiwpiapcvjpvtudgxchipcrtvxktcphtrixdcdutcvaxhwapcvjpvttippcsdpgtiwtbdhirdbbdclwxatofmpcsypgtgpgtaxztlxhtiwtgdcpcspcpgtiwtbdhirdbbdcepxghduatiitghitgbtsqxvgpbhdgsxvgpewhpcshhttiipcsuupgtiwtbdhirdbbdcgtetpihiwtcdchtchtewgphttipdxchwgsajgtegthtcihiwtbdhiugtfjtciatiitghxcinexrpatcvaxhwapcvjpvtitmixchdbtrxewtghhjrwegdetgixthduiwtcpijgpaapcvjpvteapxcitmipgtegthtgktsxciwtrxewtgitmipcsiwthtepiitgchwpktiwteditcixpaidqttmeadxitsxcprxewtgitmidcanpiiprz

Zadanie 2.1 - Tworzenie tabeli częstości

W pliku python, utwórz tabelę częstości występowania liter w języku angielskim. Możesz spróbować znaleźć ją samodzielnie, ale jeśli nie chcesz tego robić, rozumiemy to!

Jeśli absolutnie chcesz znaleźć ją samodzielnie, możesz postąpić jak w Zadaniu 2.2, ale na bardzo dużym tekście.

english_letter_frequency = {
    'E': 12.70, 
    'T': 9.06, 
    'A': 8.17, 
    'O': 7.51, 
    'I': 6.97, 
    'N': 6.75, 
    'S': 6.33, 
    'H': 6.09, 
    'R': 5.99, 
    'D': 4.25, 
    'L': 4.03, 
    'C': 2.78, 
    'U': 2.76, 
    'M': 2.41, 
    'W': 2.36, 
    'F': 2.23, 
    'G': 2.02, 
    'Y': 1.97, 
    'P': 1.93, 
    'B': 1.29, 
    'V': 0.98, 
    'K': 0.77, 
    'J': 0.15, 
    'X': 0.15, 
    'Q': 0.10, 
    'Z': 0.07
}

Zadanie 2.2 - Zliczanie częstotliwości występowania liter w tekście

Teraz stworzymy algorytm, który znajdzie częstotliwość występowania liter w danym tekście.

Zadanie 2.3 - Porównanie częstotliwości tekstu z rzeczywistą częstotliwością

Kiedy już znajdziesz częstotliwość wszystkich liter w tekście, możesz stworzyć funkcję, która znajdzie „odległość”. Co to? Co przez to rozumiesz?!

Możesz sobie wyobrazić, że częstotliwość na przykład E w tekście będzie liczbą. Możesz znaleźć „odległość”, jaką ma od rzeczywistej częstotliwości, która wynosi 12.70. Przykład: Częstotliwość wynosi 9.63, jaka jest odległość? Odległość będzie wartością bezwzględną (liczby ujemne stają się dodatnie) między tymi dwiema wartościami: \(12.70 - 9.63 = 3.07\).

Stwórz funkcję, która przechodzi przez każdą z liter i znajduje odległość. Następnie zsumuj wszystkie odległości do „całkowitej” odległości.

Zadanie 2.4 - “Złamanie” szyfru Cezara

Teraz podsumujmy wszystko, co do tej pory zrobiliśmy! Teraz “złamiemy” szyfr Cezara.

Stwórz program, który “złamie” szyfr Cezara! Bez interakcji z użytkownikiem, program powinien być w stanie przyjąć zaszyfrowany tekst i odzyskać odszyfrowany tekst bez potrzeby klucza.