venerdì 16 gennaio 2015

Modern C++ - Esercizio - Il Cifrario di Cesare

Bentornati sulle pagine del corso di Modern C++, ospitato sulle pagine di Lubit - The Secrets of Ubuntu, diretto amabilmente da Luigi bit3lux Iannoccaro. Fin qui, abbiamo visto insieme alcuni degli elementi principali del C++: vettori, variabili, condizioni e cicli. Oggi vedremo tante, tantissime novitá, per chi si avvicina per la prima volta alla programmazione o ad un linguaggio come il C++.
Luigi ha postato un piccolo script in bash che effettua la codifica/decodifiche di stringhe usando il Cifrario di Cesare. E´ uno dei piú antichi algoritmi di crittografia ad oggi pervenuto. Perchè non realizzarlo in anche in Modern C++?
L'algoritmo (sulla carta) è molto semplice: si sostituisce ad ogni lettera contenuta in una parola, un'altra lettera dell'alfabeto, la quale ha una posizione, definita chiave, successiva a quella della lettera originale.
Ad esempio, se la chiave è 3, come quella usata da Cesare nel suo cifrario, alla lettera A corrisponde la lettera E, alla lettera B corrisponde la lettera E e così via. 

Su Wikipedia esiste giá una versione di questo algoritmo, che vi invito a testare personalmente, ma è scritto seguendo il cosídetto "C-Style", usando printf e vettori ad allocazione statica (ovvero che non si possono modificare in lunghezza) ed una chiave fissa, pari a 3.

Quella che vi presento, è una versione Modern C++ realizzata da me personalmente, che consente di utilizzare una chiave diversa ed effettuare la codifica e la decodifica di una stringa di caratteri:
Il codice è commentato nel dettaglio, spiegando riga per riga, l'operazione eseguita.

Idea di Base

Al fine di realizzare il Cifrario di Cesare, con chiave variabile, ci occorrono due elementi: la stringa da codificaree la chiave: pertanto, avremo bisogno di due parametri, che l'utente andrá ad inserire a riga di comando. In questo caso, si è scelto di inserire tali parametri come argomenti del programma (chiamato per convenienza, caesar), ovvero nel seguente modo:
caesar "stringa da codificare" chiave

Quindi, avremo bisogno di importare tali parametri nel nostro codice e analizzarli. Poichè lo spazio è usato come indicatore di fine stringa (ovvero, non è un carattere alfanumerico), ogni parola separata dallo spazio è interpretata come un parametro aggiuntivo. Al fine di prevenire ció, dovremo inserire l'intero testo delimitato dagli apici "". In tal modo, la stringa all'interno dei delimitatori è interpretata come un unico parametro. Nell'algoritmo, non vengono considerate le vocali accentate.

Come applicare il cifrario di Cesare in modo semplice?
Per prima cosa, occorre definire i limiti dell'alfabeto: la 'a' è il limite inferiore, mentre la 'z' rappresenta il limite superiore. Quando viene valutato un singolo carattere della stringa, occorre valutare le seguenti condizioni:
  1. è un carattere alfanumerico? 
  2. la chiave usata è positiva (cifratura) o negativa (decifratura)?
  3. il nuovo carattere ottenuto dalla trasformazione, è ancora un carattere contenuto tra 'a' e 'z'?
In C++, ma piú in generale in ASCII, un carattere è codificato come un valore numerico. Alla 'a' corrisponde il numero 97, alla 'z' il numero 122. Occorre pertanto valutare se il carattere codificato sia maggiore o uguale a 97 oppure minore o uguale a 122. Se queste condizioni non sono verificate, occorre calcolare la differenza tra il valore attuale e quello del limite corrispondente e ripartire dal limite stesso.
Esempio:

caesar "zorro" 3       #esegue la codifica di zorro con chiave = 3

  • z+3 = 125, ma 125 corrisponde a '}' in ASCII, quindi:
    • differenza = 125 - z  #(nuovo - valore di 'z')
    • valore_attuale = a + (differenza - 1)  #si riparte da 'a', considerando la 'a' stessa
    • quindi valore_attuale = 97 + 3 - 1 = 99 = 'c'
    • quindi z+3 = 'c'
  • o+3 = 114 ('o' = 111 in ASCII)
    • 114 <= 122, quindi o+3 = 'r' = 114
e così via.

Se eseguiamo invece:

caesar "acqua" -3      #esegue la codifica di acqua con chiave = -3 (al contrario) 

  • a-3 = 94 = '^' in ASCII, ma 94 < 97, quindi:
    • differenza = 97 - 94 (valore di 'a' - valore del nuovo carattere)
    • valore_attuale = z - (differenza + 1) #si riparte da z, considerando la z stessa
    • quindi valore_attuale = 122 - 3 + 1 = 120 = 'x'
    • quindi, a-3 = 'x'
  • c-3 = 96 = '`', ma 96 < 97, quindi:
    • differenza = 97 - 96 = 1
    • valore_attuale =  122 -1 +1 = 'z'
    • quindi c-3 = 'z'
e cosí via.

Analizziamo il codice sorgente

Per prima cosa, noterete che includo gli header files cctype e algorithm: sono librerie STL che contengono alcune funzioni utili per l'esecuzione delle operazioni a noi utili: std::isalnum(char x) è una funzione che ha come risultato true se il carattere contenuto in x è un carattere alfanumerico, altrimenti restituisce false; std::transform ci permette di eseguire una operazione in sequenza su ognuno degli elementi di un array. Un array, poichè una stringa è un array di caratteri, dove l'elemento 0 (il primo) corrisponde al primo carattere e l'ultimo elemento del vettore corrisponde all'ultimo elemento della stringa. ATTENZIONE: std::string non è da confondersi con char stringa[], poichè quest'ultimo è un array di tipo char, il cui ultimo elemento è il carattere '\0', indicante il termine di una stringa. Modern C++ usa in modo quasi esclusivo std::string, poichè gli array di tipo char costituiscono una fonte di errori notevoli e non sono espandibili, se non mediante una nuova dichiarazione e allocazione di memoria.

Ho dichiarato la variabile key come variabile globale, ovvero è possibile accedere al valore contenuto nella variabile, da qualsiasi funzione del programma. Ho fatto questo, per poter usare key all'interno della funzione codifica(char &x).

La funzione char codifica(char &x) consente di eseguire l'algoritmo sul singolo carattere della stringa usata come parametro della nostra applicazione.
Essa valuta il valore di x: la notazione char &x indica che come parametro della funzione codifica, occorre fornire un valore di tipo char il cui dato è quello che fa riferimento al valore di x. Vedremo meglio questo aspetto nelle prossime lezioni: basti solo pensare che il parametro &x è passato per riferimento e puó esser modificato, modificando il valore originario del parametro stesso, anche quando la funzione termina. L'alternativa è il passaggio per valore, ovvero si effettua una copia della variabile e al termine della funzione, la copia viene distrutta, mentre il valore originale di x viene preservato.

Tale funzione, poi, restituisce un valore di tipo char, ovvero il carattere codificato con chiave positiva o negativa. Il corpo della funzione è documentato nel codice sorgente stesso e l'algoritmo è stato giá esaminato precedentemente.

La nota importante è la conversione implicita da char ad int. Questo è possibile che avvenga poichè char è rappresentato da 1 byte (=8 bit) e assume valori da -2^8 a (2^8)-1, ovvero da -128 a +127. Il tipo di dato int invece è rappresentato da 4 byte (=8*4=32 bit), ma varia da macchina a macchina (alcune architetture usano il tipo di dato int da 2 byte) e assume valori da -2^32 fino (2^32)- 1, ovvero puó contenere valori molto piú ampi. La conversione da int a char è possibile finchè il vaore di int rientra tra -128 e 127, altrimenti si ottengono risultati disastrosi ed inaspettati.

La funzione mostraHelp() permette di visualizzare un messaggio di testo in uscita, in caso di errori durante l'immissione dei parametri da passare al programma. È di tipo void, ovvero non restituisce alcun valore al termine della sua esecuzione.

All'interno dei main, abbiamo interessanti novitá: per prima cosa, all'interno del blocco switch, importiamo i parametri: come commentato nel codice sorgente, argc indica il numero di parametri (parole) scritte a riga di comando, dove argc=1 rappresenta la posizione e argv[0] rappresenta il nome nome dell'eseguibile che stiamo lanciando, mentre argc > 1 e argv[1], argv[2], ecc. indicano successivi parametri passati al nostro eseguibile.
Il tipo di dato di argv[] è char*, ovvero si tratta di un array di caratteri di dimensione non specificata, che viene definita solamente in base al numero di parametri immessi. È un retaggio del C, che è rimasto in adozione anche in C++.
La funzione atoi, al rigo 85, effettua la conversione da valore alfanumerico a intero (alphanumeric to integer), ovvero converte il parametro della chiave, ovvero il 3, da char a int, questo perchè i parametri sono passati come caratteri a riga di comando.

Al rigo 103, creo una nuova stringa, contente il carattere " da eliminare dall'input (in C++, il caratter ", al fine di usarlo come carattere di I/O, va anticipato dal carattere di escape \, quindi \" = "), al fine di non eseguire l'algoritmo anche su tale carattere: avrei potuto eliminarlo grazie a std::isalnum, ma l'ho lasciato per dimostrare il funzionamento di std::erase: tale funzione infatti, elimina ogni occorrenza di " dalla stringa di input e salva il risultato nella stessa stringa. Quindi, per ogni simbolo della stringa chars, si esegue erase, la quale rimuove iterativamente (remove) dall'inizio della stringa source (source.begin()) fino alla fine della stessa (source.end()) ogni occorrenza del simbolo symbol.
Le funzioni erase e remove (ma anche tante altre funzioni della STL) usano gli iteratori, ovvero un oggetto che punta a determinati elementi di un array: begin() rappresenta l'elemento 0, end() rappresenta la posizione N (con N-1 = ultimo elemento del vettore).
Si usano ancora gli iteratori per la funzione transform, prima per convertire la stringa in lower case (tutti i caratteri in minuscolo), grazie a ::tolower e poi per eseguire la codifica col cifrario di Cesare. Nel caso di transform, si specificano come parametri:
  • inizio della stringa di origine = target.begin()
  • fine della stringa di origine = target.end()
  • inizio della stringa di destinazione = target.begin() -- sovrascrivo la stringa target!
  • funzione che effettua la trasformazione = codifica()
A questo punto, alla funzione codifica viene passato il parametro contente il riferimento al carattere della stringa che si sta valutando: nel caso di "zorro", verranno chiamati codifica('z'), codifica('o'), codifica('r'), codifica('r'), codifica('o').

L'output del nostro programma è il seguente:



Per compilare il progetto, create un nuovo progetto con QtCreator come mostrato qui e nel file CMakeLists.txt cambiate il nome del progetto in Caesar.

Buona codifica!

PS. Tra la mia versione e quella fornita da Wikipedia, quale risulta piú chiara, la versione C++ o quella in Modern C++? Scrivetelo nei commenti!

2 commenti:

  1. Credo che la chiamata isalnum() vada sostituita con isalpha().
    isalnum() ritorna true per ogni carattere alfanumerico (a,b,c..z e 0,1,2..9). Mentre il tuo algoritmo funziona solo con le lettere:
    ghigo@venice:~/c++-contest$ ./cesare "abc3" +16
    Stringa immessa: abc3 con chiave k = 16
    Risultato: qrsC
    ghigo@venice:~/c++-contest$ ./cesare "qrsC" -16
    Stringa immessa: qrsC con chiave k = -16
    Risultato: abcm
    Invertendo il segno della chiave riesco a riconvertire le lettere ma non le cifre.

    Approfitto di questa nota per suggerire una forma un pelo più compatta per converti():
    char codificai(char &x) {
    const int delta{1+'z'-'a'};
    return isalpha(x) ? 'a' + (delta+x-'a'+key)%delta : x;
    }

    RispondiElimina
    Risposte
    1. Ciao grazie per la segnalazione.
      E' vero, avrei potuto usare isalpha(), ma il cifrario di cesare non tiene conto deila conversione dei numeri, quindi anche io non l'ho considerata.

      Per la versione compatta, va benissimo, ma poiché non tutta l'audience è esperta, la spiegazione dell'algoritmo diventa un pochino piú "oscura". Ad ogni modo, grazie mille :)

      Elimina