Problem Set #1: Top Secret

Ciele

• Osvojiť si základy dynamickej správy pamäte (alokácia a dealokácia).
• Naučiť sa pracovať s bitovými operátormi a operáciami v jazyku C.

Šifrovanie

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:

• Modul Playfair, v rámci ktorého implementujete Playfairovu šifru.
• Modul BMP, v rámci ktorého implementujete BMP šifru.

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:

• na rovnakom riadku matice 5x5, nahradia sa písmenami napravo od nich
• v rovnakom stĺpci matice 5x5, nahradia sa písmenami pod nimi
• na rozdielnych riadkoch a stĺpcoch matice 5x5, nahradia sa písmenami na priesečníkoch daných stĺpcov a riadkov

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é:

• const char* text - Odkaz na reťazec, ktorý reprezentuje text na zašifrovanie. Tento text môže pozostávať len z písmen, pričom na veľkosti písmen nezáleží, alebo zo znaku medzery. Žiadne iné znaky nie sú prípustné (nie je možné ich zašifrovať).
• const char* key - Odkaz na reťazec, ktorý reprezentuje kľúč, pomocou ktorého bude text zašifrovaný. Kľúč je reprezentovaný textom, v ktorom nezáleží na veľkosti písmen. Jednotlivé písmená sa v kľúči nemôžu opakovať (ak sa opakujú tak vo vašej implementácii zabezpečte, že duplikáty budú odstránené). Medzery v kľúči sú ignorované.

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ý:

• key - Reťazec reprezentujúci kľúč použitý na zašifrovanie aj odšifrovanie textu. Kľúč je reprezentovaný ako jedno slovo a môže pozostávať len zo znakov abecedy, pričom na veľkosti písmen nezáleží.
• text - Reťazec na zašifrovanie resp. odšifrovanie.

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’:

• Písmeno 'H’ má v ASCII tabuľke hodnotu 72. Hodnota 72 vyzerá v dvojkovej sústave nasledovne: 01001000. Prvé 4 bity sú teda 0100 a druhé 4 bity sú 1000.
• Prvá polovica bitov 0100 pozostáva z dvoch párov (01 a 00), v ktorých jednotlivé bity navzájom vymeníme (z páru 01 sa stane 10 a z páru 00 sa stane pár 00). Tým dostaneme hodnotu 1000.
• Takto upravenú podobu prvých štyroch bitov použijeme ako parameter operácie XOR spolu so zvyšnými štyrmi bitmi:

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

• Spojením oboch získaných štvoríc bitov (prvá štvorica 1000, ktorú sme získali ako výsledok v 2. kroku a druhá štvorica 0000, ktorú sme získali ako výsledok v 3. kroku) dostaneme hodnotu 10000000, ktorá predstavuje zašifrovanú podobu písmena 'H’ pomocou tejto metódy.

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:

• vstupný reťazec najprv prežeňte funkciou reverse()
• získaný reťazec následne prežeňte funkciou vigenere_encrypt()
• výsledný reťazec ešte prežeňte funkciou bit_encrypt

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ý:

• key - Reťazec reprezentujúci kľúč použitý na zašifrovanie aj odšifrovanie textu. Kľúč môže pozostávať len zo znakov, pričom na veľkosti nezáleží.
• text - Reťazec na zašifrovanie resp. odšifrovanie.

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/.

Ak vytvárate projekt prvýkrát, urobte tak na tejto stránke. Návod na to, ako si inicializovať prostredie a ako pracovať s GitLab-om, nájdete na stránkach predmetu ZAP.

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

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

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

• playfair.c, playfair.h - Zdrojový kód a hlavičkový súbor knižnice pre Playfairovu šifru.

• bmp.c, bmp.h - Zdrojový kód a hlavičkový súbor knižnice pre BMP šifru.

• main.c - Zdrojový kód obsahujúci funkciu main().

• Makefile - Makefile súbor obsahujúci minimálne tieto ciele:

  • playfair.o pre vytvorenie modulu na prácu s Playfairovou šifrou,
  • bmp.o pre vytvorenie modulu na prácu so šifrou BMP,
  • all pre vytvorenie spustiteľného programu s názvom ps1, a
  • clean pre odstránenie priebežne vytvorených objektových a spustiteľných súborov.

• README - Súbor, v ktorom bude uvedené označenie vašej skupiny, ktorú navštevujete na cvičeniach v tvare:

  GROUP : A1

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:

• playfair.h - hlavičkový súbor, v ktorom sa nachádzajú deklarácie všetkých požadovaných funkcií pre Playfairovu šifru.
• bmp.h - hlavičkový súbor, v ktorom sa nachádzajú deklarácie všetkých požadovaných funkcií pre BMP šifru.

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

$ wget https://kurzy.kpi.fei.tuke.sk/pvjc/2024/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:

• Štruktúra vášho projektu (či sa v ňom nachádzajú všetky potrebné súbory).
• Statická analýza vášho kódu pomocou nástroja cppcheck.
• Kontrola únikov v pamäti pomocou nástroja valgrind
• Prítomnosť globálnych premenných vo vašom kóde.
• Funkčnosť vašej implementácie.

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!