Problem Set #2: Top Secret

Ciele

Deadline

Toto zadanie je potrebné odovzdať do polnoci (23:59:59) nedele 25.mar.2018.

Šifrovanie

Obr. 1: Kryptografia v praxi (objasnenie princípu dešifrovania pomocou metódy gumennej hadice)
Obr. 1: Kryptografia v praxi (objasnenie princípu dešifrovania pomocou metódy gumennej hadice)

Videli ste filmy National Treasure alebo National Treasure II.? Nicolas Cage v roli Benjamina F. Gatesa tu ako novodobý Indiana Jones lúšti rozličné logické hádanky, ktoré mu zanechali americkí predkovia pri ceste za pokladom. Niektoré z nich spočívali v rozlúštení zakódovaného odkazu, pre rozlúštenie ktorého musel Gates poznať šifru a kľúč pre jej rozlúštenie.

Šifrovanie zohralo v histórii už mnohokrát dôležitú úlohu. Či už to bol Cézar, ktorý nechával správy vojenského významu šifrovať jednoduchou substitučnou šifrou dnes známou práve ako Cézarova šifra, alebo nacistický šifrovací prístroj Enigma, rozlúštenie ktorého pomohlo ukončiť druhú svetovú vojnu odhadom o dva roky skôr.

V rámci tohto zadania bude vašou úlohou vyriešiť niekoľko úloh týkajúcich sa práve šifrovania textu v jazyku C. Implementujete dva moduly:

V rámci oboch modulov si samozrejme môžete vytvoriť aj ďalšie pomocné funkcie. Nesmiete však nijako meniť a upravovať hlavičkové súbory oboch modulov!

Modul Playfair

Tento modul je zameraný na šifrovanie a dešifrovanie textu prostredníctvom Playfairovej šifry, ktorú vo filme National Treasure II. lúštil aj Nicolas Cage. Modul bude obsahovať dve funkcie playfair_encrypt() a playfair_decrypt() pre zašifrovanie a rozšifrovanie textu a makro ALPHA, ktoré bude obsahovať abecedu na šifrovanie s vynechaným písmenom 'W'.

Úloha #1: Playfairova šifra

Princípom Playfairovej šifry je rozdelenie textu do dvojíc znakov. Ak sú obidva znaky dvojice:

Jedno písmeno z abecedy, ktoré sa málo vyskytuje, resp. nemení sémantiku slov jazyka, zameníme za iné (v našom prípade W za V). Túto zámenu realizujte pre kľúč pri šifrovaní a dešifrovaní, pre text iba pri šifrovaní.

K šifrovaniu je potrebné poznať kľúč, ktorého znaky sa nesmú opakovať a nachádzajú sa na prvých miestach matice (ak sa opakujú tak vo vašej implementácii zabezpečte, že duplikáty budú odstránené). V prípade, že kľúč je "belfast", matica 5x5 je rozdelená nasledovne (v našom prípade bol úmyselne vynechaný znak 'W'):

B E L F A
S T C D G
H I J K M
N O P Q R
U V X Y Z

Ak s týmto kľúčom zašifrujeme slovo KRYPTOGRAFIA, výsledkom bude šifrovaný text MQXQIVMZBAME, pre MANAGER to bude RGRBTAPZ.

Vašou úlohou je vytvoriť funkcie char* playfair_encrypt(const char* key, const char* text) a char* playfair_decrypt(const char* key, const char* text), pomocu ktorých zašifrujete a odšifrujete text aplikovaním Playfairovej šifry. Jednotlivé parametre funkcií sú nasledovné:

Funkcia vráti referenciu na zašifrovaný reťazec, ak bolo šifrovanie alebo dešifrovanie úspešné. Výsledný reťazec vypisujte v podobe dvojíc veľkých písmen oddelených medzerami.

Ak pred šifrovaním zistíte, že sú v texte dve po sebe idúce písmená rovnaké, medzi tieto dve písmená pridajte písmeno 'X‘. Písmeno 'X’ rovnako pridajte na koniec vstupného textu v prípade, ak je jeho dĺžka nepárna (po pridaní 'X‘medzi dvojité znaky a odstránení medzier). Znak 'X’ sa nepridáva medzi 2 rovnaké znaky 'X’ a šifruje sa podľa stĺpca matice.

Pri dešifrovaní sa výskyt znaku 'W’ pri vstupnom texte považuje za chybu a funkcia na dešifrovanie má v takomto prípade vrátiť NULL.

V prípade, že niektoré z pravidiel týkajúce sa vstupných parametrov bolo porušené alebo funkcia na vstupe dostane miesto ktoréhokoľvek parametra hodnotu NULL, funkcia hodnotu NULL aj vráti.

Použitie funkcie na zašifrovanie/dešifrovaonie sú ilustrované na nasledujúcich príkladoch:

char *encrypted, *decrypted;

// even length of string
encrypted = playfair_encrypt("SeCReT", "Hello world");
printf("%s", encrypted);
// "Hello world" --> "HELXLOVORLDX"
// IS JZ JQ XN TK JC
decrypted = playfair_decrypt("SeCReT", encrypted);
printf("%s", decrypted);
// HELXLOVORLDX
free(encrypted);
free(decrypted);

// odd length of string
encrypted = playfair_encrypt("world", "Hello");
printf("%s", encrypted);
// "Hello" --> "HELXLO"
// JB RY DR
decrypted = playfair_decrypt("world", encrypted);
printf("%s", decrypted);
// HELXLO
free(encrypted);
free(decrypted);

// letter 'X' in message
encrypted = playfair_encrypt("Password", "Taxi please");
printf("%s", encrypted);
// "Taxi please" --> "TAXIPLEASE"
// UP YH AK DO OB
decrypted = playfair_decrypt("Password", encrypted);
printf("%s", decrypted);
// TAXIPLEASE
free(encrypted);
free(decrypted);

// multi 'X's in message
encrypted = playfair_encrypt("please", "Taxxxiii");
printf("%s", encrypted);
// "Taxxxiii" --> "TAXXXIIXIX"
// RS EE VJ JV JV
decrypted = playfair_decrypt("please", encrypted);
printf("%s", decrypted);
// TAXXXIIXIX
free(encrypted);
free(decrypted);

Modul BMP

Keďže nám na bezpečnosti našich riešení záleží, v našom tíme kladieme bezpečnosť na druhé miesto (hneď po odstránení každej ryže, ktorú zistíme). A keďže všetky súčasné krypto algoritmy považujeme za nedostatočné (Enigma šuvix) a v tíme prevláda názor, že čo je jednoduché, to je geniálne, zvolili sme prístup kombinácie a variácie viacerých jednoduchých prístupov súčasne. A keďže ľudová múdrosť hovorí, že viac čiar - viac adidas, môžeme povedať rovnako, že úroveň bezpečnosti sa zvyšuje použitím viacerých jednoduchých (rozumej - geniálnych) postupov.

Šifra BMP nesie názov zložený z prvých písmen priezvisk trojice zakladateľov nášho kryptografického tímu (Biňas-Madeja-Pietriková). Výhodou oproti Playfairovej šifre je fakt, že pomocou BMP je možné zašifrovať ľubovoľný text (teda - až na niekoľko výnimiek spomenutých nižšie).

Úloha #2: Reverz

Vašou úlohou je vytvoriť funkciu char* reverse(const char* text), vráti kópiu vstupného reťazca v obrátenom poradí (UPPERCASE).

V prípade, že funkcia miesto reťazca dostane hodnotu NULL, funkcia túto hodnotu NULL aj vráti.

char* reversed = reverse("Hello world!");
printf("%s\n", reversed);
// "!DLROW OLLEH"

Úloha #3: Vigenèrova šifra

Vigenèrova šifra predstavuje rozšírenie cézarovej šifry o kľúč, ktorý bude pri šifrovaní a dešifrovaní použitý.

Vašou úlohou je vytvoriť funkciu char* vigenere_encrypt(const char* key, const char* text) na zašifrovanie a funkciu char* vigenere_decrypt(const char* key, const char* text) na dešifrovanie textu pomocou Vénierovej šifry. Výsledný text reprezentujte veľkými písmenami (UPPERCASE)

Význam jednotlivých parametrov funkcií je nasledovný:

Funkcia vráti adresu kópie reťazca zašifrovanú resp. odšifrovanú pomocou Venierovej šifry alebo NULL, ak zašifrovanie resp. odšifrovanie nebolo úspešné.

char* encrypted;

// basic test with long text
encrypted = vigenere_encrypt("CoMPuTeR", "Hello world!");
printf("%s\n", encrypted);
// "JSXAI PSINR!"

Úloha #4: Bitový chaos

Táto metóda šifrovania ešte nie je nikde publikovaná a v našom tíme bola predmetom dlhých diskusií, počas ktorých sme v blízkych aj vzdialených podnikoch stiahli litre kofoly. Nakoľko je však metodika veľmi jednoduchá, je výsledný efekt úplne geniálny.

Pri šifrovaní postupujte nasledovne: Znak, ktorý má byť zašifrovaný, si rozdeľte na polovicu (4 bity + 4 bity). Následne bity v prvej polovici rozdeľte do párov a ich hodnoty v páre navzájom vymeňte. Takto vytvorenú štvoricu bitov použite pre operáciu XOR nad zvyšnými 4 bitmi.

Tento jednoduchý a pritom geniálny princíp si predstavíme na nasledovnom príklade. Reťazec, ktory je potrebné zašifrovať, je Hello world!. Zašifrovať je potrebné každé jedno písmeno, takže pri šifrovaní budeme postupovať od prvého písmena - 'H’:

    1000  // druhá polovica
XOR 1000  // prvá polovica po výmene bitov v dvojici
--------
    0000

V prípade dešifrovania využite opačný postup.

Vašou úlohou je teda vytvoriť funkcie unsigned char* bit_encrypt(const char* text) a char* bit_decrypt(const unsigned char* text), pomocou ktorých budete vedieť zašifrovať a dešifrovať zadanú postupnosť bytov.

Použitie tejto funkcie je ilustrované na nasledujúcom príklade:

unsigned char* encrypted;

// basic test with long text
encrypted = bit_encrypt("Hello world!");
for(int i=0; i < 12;i++) {
    printf("%x ", encrypted[i]);
    //80 9c 95 95 96 11 bc 96 b9 95 9d 10
}
free(encrypted);

Úloha #5: Šifra BMP

Ako už bolo uvedené vyššie, za šifrou BMP stojí (niekedy aj sedí) trojica mladých kryptológov Biňas, Madeja a Pietriková a jej jednoduchosť a z nej vyplývajúca genialita vychádza v kombinácii niekoľkých metód súčasne.

Ak chcete reťazec zašifrovať, postupujte nasledovne:

Pre rozšifrovanie zadanej postupnosti bytov postupujte presne opačne.

Vašou úlohou je teda vytvoriť funkcie unsigned char* bmp_encrypt(const char* key, const char* text) a char* bmp_decrypt(const char* key, const unsigned char* text), pomocou ktorých budete vedieť text zakódovať a dekódovať prostredníctvom šifry BMP.

Význam jednotlivých parametrov funkcií je nasledovný:

Funkcia vráti adresu kópie reťazca zašifrovanú resp. odšifrovanú pomocou BMP šifry alebo NULL, ak zašifrovanie resp. odšifrovanie nebolo úspešné.

Odovzdávanie projektu

Zadanie sa odovzdáva prostredníctvom systému na správu verzií Git na serveri http://git.kpi.fei.tuke.sk/. Riešenie tejto úlohy odovzdáte ako súčasť vášho projektu s názvom prog-2018.

Štruktúra vášho projektu bude vyzerať nasledovne:

├── ps2/
│   ├── playfair.c
│   ├── playfair.h
│   ├── bmp.c
│   ├── bmp.h
│   ├── main.c
│   └── Makefile
└── README

kde význam súborov v priečinku ps2/ je nasledovný:

Upozornenie

Je dôležité, aby vaše súbory zachovali uvedenú štruktúru. Ak sa niektorý zo súborov síce v repozitári nachádza, ale v inom priečinku, bude to považované za chybu a takýto projekt nebude považovaný za správny! Ak sa naopak vo vašom projekte nachádzajú súbory alebo priečinky navyše, tieto nebudú považované za chybu.

Upozornenie

Pri názvoch priečinkov, súborov a obsahu súboru README záleží na veľkosti písmen!

Kostra projektu

Z nasledujúceho odkazu si stiahnite súbor top.secret.zip, ktorý obsahuje kostru projektu. Tento balíček obsahuje nasledujúce súbory:

V prostredí OS Linux môžete pre stiahnutie použiť príkaz wget v tvare:

wget http://it4kt.cnl.sk/c/pvjc/2018/download/top.secret.zip

Hodnotenie a testovanie

V rámci tohto zadania nie je predpísaná grafická podoba výstupu ani dialóg medzi používateľom a počítačom. V tom máte voľnú ruku.

Vaše hodnotenie sa bude odvíjať od výsledku testov, ktorými vaše zadanie úspešne prejde. Overovať sa bude:

Váš kód sa bude prekladať prekladačom gcc s nasledovnými prepínačmi a knižnicami:

$ gcc -std=c11 -Werror -Wall -lm

Testovanie vašich riešení sa bude vykonávať automaticky každé 3 hodiny a to konkrétne o 0300, 0600, 0900, 1200, 1500, 1800, 2100 a 2400.

Vaše riešenia opäť prejdú kontrolou originality. Preto sa pri práci na vašom zadaní správajte podľa pravidiel etického kódexu! V prípade, že odovzdáte zadanie, ktoré nie je vaše, budete vylúčení z predmetu!