IB001 – Úvod do programování – 4. domácí úkol – prolomení šifry

Zadání

Každý e-mailem obdržel zašifrovaný text, který se liší od textu obdrženého ostatními studenty – každý má jiný.
Vaším úkolem je navrhnout a implementovat program (v jazyku C), který šifru prolomí a odhalí tak čitelnou zprávu (prostý text).

Kryptoanalýza (více na wiki) je obecně velmi složitá a náročná.
V našem případě se však jedná o úkol relativně lehký.
- Jednak šifrovaný text je produktem primitivního algoritmu,
- navíc je níže pečlivě popsán, takže nabízí přímočarou cestu, jak jej prolomit pomocí hrubé síly (brute force attack, více na wiki).
Vaším cílem je odhalit původní zprávu, která je „člověkem čitelná“ (čistý text), a to pomocí Vámi napsaného programu v jazyku C.
- Nebude uznáno řešení bez programu, který mohl rozumnou cestou vést k úspěšné kryptoanalýze.
- V komentáři programu popište, jak jste program při prolamování šifry využili.
- Odevzdat je třeba jak odhalenou zprávu, tak „prolamovací program“.
Dole jsem doplnil příklad šifrování a dešifrování krok po kroku.

Popis šifrovacího algoritmu

Pro jednoduchost se omezíme na šifrování textu, a to ješte s omezenou sadou povolených znaků:
- {abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890_,.-:?!| }
  (poslední znak je mezera ' ')
- Je kruciálně důležité, abychom používali stejnou „abecedu“, proto si její definici, prosím, stáhněte zde:
  abeceda
- Pokud by někdo použil jinou sadu povolených znaků nebo v jiném pořadí, mohl by si neúměrně ztížit práci až k nemožnosti realizace (pokud by například použil pouze její vlastní podmnožinu).
- Pro eliminaci problémů s rozdílnou interpretací znaků konce řádků (CRLF vs. CR vs. LF, více na wiki) není znak nového řádku mezi povolenými znaky a šifrovaný i čistý text je uložen na řádce jediné.

Použitý šifrovací algoritmus odpovídá mírně upravené Caesarově šifře (více na wiki), kdy posun znaků není pevně dán pro celý text, ale závisí na předchozích znacích.

Na začátku si algoritmus stanoví iniciální posun znaků vůči původní pozici.
Veškeré posuny, vzdálenosti mezi znaky či počítání modulo se vztahují vůči užité „abecedě“ odkazované výše. Nejedná se o pozici v ASCII!!!
- Takže prvním znakem s pozicí 0 (nula) je znak 'a', poslední je mezera ' ' a třeba posun znaku '1' od začátku „abecedy“ (vyjde 52) lze spočítat takto:
```
#include<stdio.h>
#include<string.h>

int main(void) {
        char *abeceda = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890_,.-:?!| ";
        size_t posun = strchr(abeceda, '1') - abeceda;
        printf("%lu\n", posun);

        return 0;
}
```
Důležité: Iniciální posun znaků je individuální pro každého studenta a jemu předaný šifrovaný text.
Iniciální posun je z rozsahu <0, strlen(abeceda)>.

Algoritmus načte první znak čistého textu a posune jej o iniciální posun v rámci užité „abecedy“.
- Kdyby byl iniciální posun 3 a první znak 'z', pak bude nahrazen znakem 'C' (velké C).
- Nahrazovaný znak se počítá modulo počet znaků v abecedě (strlen(abeceda)), abychom nepřesáhli hranici „abecedy“,
  takže je-li iniciální posun 3, tak se případná mezera ' ' nahradí znakem 'c' (malé c).
Po zašifrování prvního znaku dojde k úpravě iniciálního posunu následovně:
posunProDalsiZnak = (inicialniPosun + poziceZasifrovanehoZnakuVAbecede) % strlen(abeceda)
- Jinak řečeno, k iniciálnímu posunu se přičte pozice zašifrovaného prvního znaku v „abecedě“ modulo počet znaků v „abecedě“ (strlen(abeceda))
- Pozor, neuvažuje se pozice prvního znaku čistého textu, ale až pozice znaku zašifrovaného iniciálním posunem.

Takto algoritmus pokračuje dále:
1. Načte další znak a zašifruje jej (posune jej o vypočtený posun modulo počet prvků v „abecedě“).
2. Spočítá další posun:
  posunProDalsiZnak = (aktualniPosun + poziceZasifrovanehoZnakuVAbecede) % strlen(abeceda)
3. Přejde k bodu [1].
Takto algoritmus zašifruje celý vstupní čistý text.

Nápověda

Pro úspěšnou kryptoanalýzu stačí hrubou silou „uhádnout“ iniciální posun. Jak je vidět, další je již vše deterministické.
Tím se jedná o velmi slabou šifru. Pro naše účely je však dostačující.
Abyste nemuseli výstupy kontrolovat ručně, mají všechny soubory rozdané studentům společný následující text:
„NejlepsiCokoladaJeHorkaCokoladaZKakaovehoMaslaBezPalmovehoOleje“
- Pokud jej Váš program ve výstupu detekuje, máte velkou šanci, že se jedná o korektně dešifrovaný text, který je řešením problému.
Lze se spolehnout na to, že šifrované i výstupní čisté texty neobsahují žádné nepovolené znaky mimo domluvenou „abecedu“.
Zkusil jsem všechny rozeslané soubory hrubou silou dešifrovat využívaje znalosti přítomnosti výše uvedeného řetězce, který se vyskytuje ve všech šifrách v zašifrované podobě, a podařilo se – získal jsem čitelné texty.

Neopisujte, nápadně podobná řešení budou diskvalifikována.

Odevzdání

Odevzdávejte pouze nezabalený zdrojový soubor a čistý dešifrovaný text (2 soubory, nezabalené).
Do zdrojového souboru do komentáře napište, jak Vám Váš program při dešifrování pomohl a jak jste s ním pracovali.
Úkol vložte do ISu sem: https://is.muni.cz/auth/el/1433/podzim2015/IB001/ode/sk_060708/ode_u4/

Příklad prolomení šifry

Vypíšeme obsah souboru s čistým textem:

(škaredě se vypisující obsah souborů je proto, že na konci fakt není nový řádek)

[xbayer@katana-ng new]$ cat cisty_text.txt 
Kolik programovacich jazyku znas, tolikrat jsi programatorem... Nemam rad smouly! NejlepsiCokoladaJeHorkaCokoladaZKakaovehoMaslaBezPalmovehoOleje Jakou barvu ma kralicek Azurit?[xbayer@katana-ng new]$

Zašifruji čistý text do nečitelné podoby (podobnou cestou vznikly Vaše soubory):

22 odpovídá iniciálnímu posunu

[xbayer@katana-ng new]$ ./encode cisty_text.txt sifrovany_text.txt
22
[xbayer@katana-ng new]$ cat sifrovany_text.txt 
7xRmAPB5M!f.||d5RvKgesBipqQ,kidywZZAXyYK47z97J0?-5Hg:c,dbf!c5PlCzpM.|34wVt6Lfqx8uQ2afmrTwIruKfhdjp-CojvJ9g|,8SgpBI2 igA8E,_gTL?19Acu jtOqpHcEF4SmtdQxYJXD692IVK9WKi jpyYJ8dffhfvt[xbayer@katana-ng new]$

Moje implementace kryptoanalytického nástroje :D

Zkouší hrubou silou prolomit a vždy hledá ve výsledném souboru text "NejlepsiCokoladaJeHorkaCokoladaZKakaovehoMaslaBezPalmovehoOleje", až jej najde, zkusí upozornit a případně hledat dále. Je zde vidět, že se program zastavil při inicializačním posunu 22.

[xbayer@katana-ng new]$ ./decode sifrovany_text.txt prolomeny_text.txt

Nalezeno! (22)
Hledat dal? (a/n): n
[xbayer@katana-ng new]$ cat prolomeny_text.txt 
Kolik programovacich jazyku znas, tolikrat jsi programatorem... Nemam rad smouly! NejlepsiCokoladaJeHorkaCokoladaZKakaovehoMaslaBezPalmovehoOleje Jakou barvu ma kralicek Azurit?[xbayer@katana-ng new]$

Příklad zašifrování a dešifrování krok po kroku

Abeceda s poradim (desitky a na dalsim radku jednotky)
		 0         1         2         3         4         5         6         7
                 01234567890123456789012345678901234567890123456789012345678901234567890
char *abeceda = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890_,.-:?!| ";

=================================================================================================
Zacatek kodovani textu: "Kolik programovacich jazyku znas..."
posun P nastavime na inicialni hodnotu 22 treba:

P = 22
'K' (pozice 36) + P (22) => pozice 58, 58 je mensi nez 71 => '7' ('7' jde na vystup)
	pozice '7' je 58, upravime P, P += 58 == 80 (22 + 58)
	jeste udelame modulo pres delku abecedy (max. index je 70, takze % 71)
		P %= 71, P == 9

zakodujeme dalsi znak 'o'
'o' (pozice 14) + P (9) => pozice 23, 23 je mensi nez 71 => 'x' ('x' jde na vystup)
	'x' ma pozici 23, P += 23, P == 32 (9 + 23)
	P %= 71, P == 32
	
zakodujeme dalsi znak 'l'
'l' (pozice 11) + P (32) => pozice 43, 43 je mensi nez 71, => 'R' ('R' jde na vystup)
	'R' ma pozici 33, P += 33, P == 65
	P %= 71, P == 65
atd.
 - ven tedy zatim slo "7xR" (coz odpovida prikladu vyse)

poznamka -- vyse nam vzdycky vychazelo po pricteni pozice kodovaneho znaku a P cisla < 71,
            pokud by se tak nestalo, staci zase pozici vzit % 71, napr.:
            
            kodujeme "K9" s inicialnim posunem 65:
            K (36) + P (65) => 101, 101 % 71 == 30, na pozici 30 je 'E'
	            P += 30, P == 65 + 30 == 95, P %= 71, P = 24
            9 (60) + P (24) => 84, 84 % 71 == 13, na pozici 13 je 'n'
            => Takze se to zakoduje do "En"
=================================================================================================
Priklad kousku zakodovaneho textu: "7xR"
	- musite zkouset vsechny mozne inicialni posuny, dalsi lze dopocitat
	- "trefime", ze inicialni posun je P = 22
	
P = 22
'7' (pozice 58), 58 - P (22) == 36, 36 >= 0 => na pozici 36 je 'K' ('K' jde na vystup)
	P += 58 (pozor, musime pricist pozici zasifrovaneho znaku pred jeho desifrovanim)
	P == 22 + 58 == 80
	P %= 71, P == 9

	
'x' (pozice 23), 23 - P (9) == 14, 14 >= 0 => na pozici 14 je 'o' ('o' jde na vystup)
	P += 23, P == (23 + 9)  % 71 == 32
	
'R' (pozice 43), 43 - P (32) == 11, 11 >= 0 => na pozici 11 je 'l' ('l' jde na vystup)
atd.
 - ven tedy slo "Kol", coz odpovida prefixu sifrovaneho textu
 
poznamka -- pokud se stane, ze po odecteni od pozice zasifrovaneho znaku posun P vyjde < 0,
	    pak treba pricist delku abecedy (abychom jakoby sly od jejiho konce), napr.:
	    
	    dekodujeme "En" z vyse uvedeneho s inicialnim posunem P == 65:
	    E (30) - P(65) => 30 - 65 == -35, to je < 0, proto vezmeme pozici -35 + 71 == 36, na pozici 36 je 'K'
		P += 30, P == 65 + 30 == 95, P %= 71, P == 95 % 71 == 24, P == 24
	    n (13) - P(24) => 13 - 24 < 0 => 13 - 24 + 71 = 60, na pozici 60 je '9'
	    => takze jsme dekodovali "K9", coz je to, co jsme zakodovali
	    
	    (alternativne by asi slo vzdycky pricist 71 a vzdycky udelat % 71, protoze z prikladu dekodovani "7xR":
	    	23 - 9 == 14
	    	(23 - 9 + 71) % 71 = 14
	     - ale nezkousel jsem to implementovat, jen me to tak tedka napadlo
	    )
=================================================================================================