Ćwiczenia 15A, 15B i 15C mogą być wykonane w dowolnej kolejności.
Kryptografia to sztuka i nauka ukrywania znaczenia informacji w taki sposób, aby tylko niektórzy ludzie ją widzieli. W tej lekcji wprowadzimy jedną z najprostszych metod kryptograficznych, Szyfr Cezara (znany również jako szyfr podstawieniowy), a także napiszemy program, który go złamie. Zaprojektujesz każdy aspekt swojego rozwiązania (w przeciwieństwie do lekcji 15A, w której podzieliliśmy rozwiązywanie problemu na podzadania).
Szyfr Cezara zastępuje każdą literę alfabetu inną literą. Działa tak, gdy chcesz zakodować jakiś tekst, musisz wybrać wartość przesunięcia S, które może wynosić od 0 do 25. Następnie zamienić każdą literę w tekście na literę, która jest o S liter dalej w alfabecie, a po osiągnięciu Z na końcu alfabetu wraca na początek.
Przykład
Załóżmy, że chcemy zakodować sekretną wiadomość
JOIN ME AT EIGHT BY THE ZOO
używając przesunięcia S=2.
Reguła szyfrowania mówi, że każda litera jest zastąpiona literą, która występuje w dalszej części alfabetu. Na przykład, ponieważ alfabet ma postać ABCDEFGHIJKL ..., pierwsza litera J zostanie zastąpiona literą L. Kontynuując, O zastępuje się literą Q, I zastępuje się literą K, itd. Aby zakodować literę Y, musimy na początek alfabetu: po Y pochodzi Z, a następnie A, więc Y jest zastępowane przez A. Podobnie Z zastąpione jest przez B. Więc zakodowana wersja naszego tajnego komunikatu to:
LQKP OG CV GKIJV DA VJG BQQ
Gdyby jakiś szpieg zobaczył tę wiadomość, nie byłby dla niego oczywiste, jaka jest jej treść.
SPY CODER przy wartości przesunięcia S=5? (Używaj dużych liter.) Jeśli chcesz, napisz program w konsoli, który to obliczy — może się on przydać później.Deszyfracja
Gdy Twój przyjaciel dostanie wiadomość, to jeśli zna wartość tajnego przesunięcia S, to łatwo odszyfruje wiadomość: każda litera jest zastępowana przez literę umieszczoną w alfabecie o S pozycji wcześniej. Na przykład, popatrzy na L, cofnie się o dwie pozycje w alfabecie i znajdzie literę J, o której teraz wie, że jest pierwszą literą twojej tajnej wiadomości. Znowu należy traktować alfabet w sposób cykliczny, zakładając, że Z przechodzi na A.
HUD, a wartość przesunięcia wynosi S=6, to jaka była pierwotna wiadomość? (Użyj wielkich liter.)Pracuję dla Złych Facetów
Zostałeś zatrudniony przez szpiega, aby pomóc odszyfrować wiadomość zaszyfrowaną przy użyciu szyfru podstawieniowego. Niestety, szpieg nie zna wartości S. Do napisania programu będziesz musiał używać statystyk, które dają duże szanse na automatyczne znalezienie odpowiedniej wartości S.
Nasza metoda polega na analizie częstotliwości literowej. W języku angielskim niektóre litery są bardzo powszechne (np. E), a niektóre występują rzadko (np. J). Oto tabela częstotliwości, oparta na liczeniu częstotliwości wystąpień w dużym obszarze tekstu.
| A | B | C | D | E | F | G | H | I |
|---|---|---|---|---|---|---|---|---|
| .0817 | .0149 | .0278 | .0425 | .1270 | .0223 | .0202 | .0609 | .0697 |
| J | K | L | M | N | O | P | Q | R |
| .0015 | .0077 | .0402 | .0241 | .0675 | .0751 | .0193 | .0009 | .0599 |
| S | T | U | V | W | X | Y | Z | |
| .0633 | .0906 | .0276 | .0098 | .0236 | .0015 | .0197 | .0007 |
Na przykład, częstotliwość L wynosi 0,0402=4,02%, co oznacza, że tekst angielski średnio zawiera 4,02% L liter.
Wywołanie goodness dla litery daje wartość zawartą w powyższej tabeli. Teraz, dla naszej metody statystycznej, określamy goodness dla zdania jako sumę goodness każdej z jej liter. Na przykład, goodness łańcucha GOOD wynosi
goodness("GOOD") = .0202 + .0751 + .0751 + .0425 = .2129
Idea analizy częstotliwości polega na tym, że łańcuchy o wyższej częstotliwości goodness z większym prawdopodobieństwem reprezentują tekst w języku angielskim. Na przykład, jeśli szpieg widzi zaszyfrowaną wiadomość "JRRG", to oryginalny tekst może być "GOOD z przesunięciem S = 3 lub "IQQF" z S = 1. Ale goodness "IQQF" jest
goodness("IQQF") = .0697 + .0009 + .0009 + .0223 = .0938
i skoro 0,0938 < 0,2129, to twój program powinien wywnioskować, że GOOD jest bardziej prawdopodobną prawidłową wiadomością niż IQQF.
 | Ocenianie łańcuchów poprzez goodness nie jest doskonałe. Dajmy na to, że sekretna wiadomość to JAZZ, a wartość tajnego przesunięcia to S = 10, więc rozszyfrowany tekst to TKJJ. Kiedy wprowadzisz TKJJ do swojego programu i sprawdzisz dla S = 10, wtedy goodness dla JAZZ wyniesie 0,0846, ale lepszą wartość uzyskasz dla S = 5 i otrzymanej wiadomości OFEE z goodness 0,3514 jako najlepszego proponowanego wyniku tego programu. Twój program powinien iść dalej i wyświetlić to nieangielskie słowo OFEE. (Analiza częstotliwości tego typu działa lepiej, jeśli zakodowana wiadomość jest dłuższa). |
