Démo 06 : Fonctions et modularité

(hiver 2005)

[Exercices théoriques] [Exercices pratiques] [Exercice noté]

Exercice théorique

Pas d'exercices théoriques cette semaine si ce n'est une séance de questions ouvertes.

Profitez-en pour poser n'importe quelle question petite ou grande qui vous tracasse sur Java et que vous n'avez encore jamais osez posé pour l'instant à votre démo!!! ;0)

[Retour au sommet de la page]

Exercices pratiques

Exercice 1

Prenez le temps de finir l'exercice noté à rendre pour cette semaine si ce n'est pas déjà fait.

Exercice 2

Si vous avez fini l'exercice noté à rendre cette semaine, n'hésitez pas à vous lancer à l'attaque du nouvel exercice noté!

[Retour au sommet de la page]

Exercice noté

Date de remise: Jeudi 17 février 2005 avant minuit.

Vous devez faire un programme en Java qui résout le problème décrit plus bas.

Problème: Cryptographie

La cryptographie est la science qui s'occupe (entre autres) de permettre à deux personnes de communiquer de facon confidentielle. La cryptanalyse est au contraire la science qui s'intéresse à briser les codes secrets. Pour ce tp, vous devez implémenter un mécanisme de cryptographie plusieurs fois millénaire que Jules César a utilisé pour transmettre des messages importants lors de batailles pendant l'Antiquité.

La chiffrement de César est ce qu'on appelle une méthode de chiffrement par substitution, ce qui veut dire que chaque lettre du texte original va être remplacé par une autre lettre. À chaque lettre est associée un entier entre 0 et 25 (0 pour 'a', 1 pour 'b', ..., 25 pour 'z'), on ne considèrera pour ce tp que les lettres minuscules pour le chiffrement, pas les lettres majuscules, les nombres ou tout autre caractère.

Pour chiffrer le message, on va ajouter à la valeur numérique de chacune de ces lettres la valeur d'une clé c qui est comprise entre 1 et 26. Cela revient en pratique au même que de décaler la lettre de c positions en avant dans l'alphabet. Par exemple si la lettre est 'a' (donc valeur de 0) et la clé est 6 alors on décale 'a' de 6 lettres ce qui donne 'g' (valeur 6). Si jamais on "dépasse" le chiffre 25 en appliquant la clé alors on repart à partir de 'a' (valeur 0), par exemple la lettre 'z' (valeur 25) chiffré avec la clé 4 donnerait 'd' (valeur de 3 = (25 + 4) modulo 26).

Pour déchiffrer une lettre codée dont la clé est c, on fera la méthode inverse c'est à dire qu'on va soustraire la valeur de la clé à la lettre codée pour obtenir la valeur de la lettre originale. Ainsi par exemple si la lettre chiffrée est 'r' (valeur 17) et la clé vaut 9 alors la vraie lettre décodée sera 'i' (valeur de 8 = (17 - 9)). Si jamais, on descend sous la valeur 0 (soit la lettre 'a'), on repart ensuite de 25 (soit la lettre 'z'). Encore un exemple si la lettre codée est 'h' (valeur 7) et la clé vaut 10 alors la lettre décodée sera 'x' (valeur de 23 = (7 -10) modulo 26).

Pour résumé, on peut dire que le chiffrement et le déchiffrement se font de la manière suivante:

Remarquer que le chiffrement de César est ce qu'on appelle un cryptosystème symétrique car il utilise la même clé pour le chiffrement et le déchiffrement. Si vous voulez en savoir plus si le chiffrement de César, n'hésitez pas à faire une recherche sous Google en tapant des mots clés tel que "cryptographie", "chiffrement" et/ou "César"!!!

Cet exercice consiste à écrire des fonctions qui vous permettront de chiffrer ou déchiffrer un message, ou encore de trouver la clé à partir d'un message et son texte chiffré correspondant. Vous devez écrire le fichier Crypto.java qui vous permettra de chiffrer, déchiffrer et trouver la clé à partir de votre terminal. Après avoir lancé le programme, l'utilisateur est libre d'entrer des commandes jusqu'à ce qu'il entre la commande "quitter" qui mettra fin à sa session.

Les commandes considérées valides (qui correspondent aussi à des fonctions que vous devez implémenter dans le code) sont les suivantes:

chiffrement

Cette commande chiffre un texte entré à l'aide d'une clé dont la valeur entière doit être comprise entre 1 et 26. Souvenez vous qu'on va s'intéresser seulement a chiffrer les lettres minuscules, PAS les majuscules, ni les nombres, ni tout autre caractère qui eux doivent rester non touché par le chiffrement. Cette commande a deux paramètres en entrée (le texte clair et la clé) et un paramètre en sortie (le texte chiffré):

commande: chiffrement
paramètres en entrée:
texte clair : <texte à clair à chiffrer [String]>
cle : <clé utilisée pour le chiffrement [int]>
paramètre en sortie:
texte chiffre : <texte chiffré [String]>
 

déchiffrement

Cette commande déchiffre un texte chiffré l'aide d'une clé dont la valeur entière doit être comprise entre 1 et 26. Cette commande a deux paramètres en entrée (le texte chiffré et la clé) et un paramètre en sortie (le texte clair):

commande: dechiffrement
paramètres en entrée:
texte chiffre : <texte à chiffré [String]>
cle : <clé utilisée pour le déchiffrement [int]>
paramètre en sortie:
texte clair : <texte clair [String]>
 

cryptanalyse

Cette commande calcule la clé secrète utilisée à dont la valeur entière doit être comprise entre 1 et 26 à partir d'un texte clair et de son texte chiffré correspondant. S'il n'existe pas de clé permettant de passer d'un message à l'autre la fonction devra renvoyer -1. Cette commande a deux paramètres en entrée (le texte clair et le texte chiffré) et un paramètre en sortie (la clé):

commande: cryptanalyse
paramètres en entrée:
texte clair : <texte à chiffrer (donc texte clair); [String]>
texte chiffré : <texte chiffré [String]>
paramètre en sortie:
cle : <clé utilisée pour le chiffrement [int]>
 
quitter

Indique que l'utilisateur veut quitter.

commande: quitter
 

Fonctions pouvant être (très) utiles pour résoudre le tp

Voici quelques exemples de fonctions pouvant être utiles pour programmer ce tp. Pour les trois premières vous pouvez les mettre directement dans votre code.

Comment vérifier qu'un caractère est une lettre minuscule?

Avec l'aide de la fonction suivante:

// retourne vrai si le caractere c passe en parametre est une lettre minuscule (entre 'a' et 'z')
static boolean estCaractereMinuscule(char c)
{
    return ((Character.isLetter(c)) && (Character.isLowerCase(c)));
}

Comment transformer une variable de type char contenant un caractère en sa valeur en entier representant l'ordre dans l'alphabet?

Avec l'aide de la fonction suivante:

// retourne la valeur entiere du caractere c defini en type cahr par rapport a l'ordre alphabetique si le caractere est une lettre minuscule et -1 sinon
// 'a' valant 0, 'b' valant 1, ... jusqu'a 'z' valant 25
static int conversionCaractereNumeroAlphabet(char c)
{
    int valeur_caractere;

    valeur_caractere = c - 'a';
    if ((valeur_caractere >= 0) && valeur_caractere < 26)
        return valeur_caractere;
    else
        return -1;
}

Comment transformer la valeur en entier d'un caractère representant l'ordre dans l'alphabet en une variable de type char?

Avec l'aide de la fonction suivante:

// convertit la valeur entiere par rapport a l'ordre alphabetique d'un caractere en le caractere lui-meme de type char
// remarque: la valeur entiere du caractere doit etre comprise entre 0 (pour 'a') et 25 (pour 'z')
static char conversionNumeroAlphabetCaractere(int i)
{
    char valeur_caractere='a';
    int x;

    for (x=0; x < i; x++)
        valeur_caractere++;

    return valeur_caractere;

}

Comment comparer deux variables s1 et s2 de type String?

Avec l'aide de l'expression suivante:

s1.equals(s2);
Cette commande renvoie 'true' si les deux chaînes sont égales et 'false' autrement (voir l'API de Java pour plus de détails).

Comment récupérer la taille d'une variable s de type String?

Avec l'aide de l'expression suivante:

s.length();
Cette commande retourne le nombre de caractères dans la chaîne (voir l'API de Java pour plus de détails).

Comment récupérer le caractère c de type d'une variable s de type String se trouvant à la position pos (remarque pos étant un entier qui vaut 0 pour la première position de la chaîne)?

Avec l'aide de l'expression suivante:

char c = s.charAt(pos);
Cette commande retourne le caractère dans la chaîne s se trouvant à la position pos(voir l'API de Java pour plus de détails).

Comment rajouter des caractères au fur et à mesure dans une chaîne de caractères?

Avec utilisant l'opérateur de concaténation '+'. Par exemple:

String s = new String("");
s = s + 'a';
s = s + 'b';
s = s + 'c';
// s contient maintenant la chaine "abc"
// remarque: on aurait pu ecrire aussi
// s += 'a' au lieu de s = s + 'a'
// car les deux expressions sont equivalentes

Indice sur comment chiffrer en quelques mots.

Une des facons les plus simples de chiffrer est de prendre chacun des caractères du texte clair un à un et de les chiffrer en utilisant la cle (si ce sont des lettres minuscules) puis de les concaténer au fur et à mesure avec une chaîne de caractères qui est vide au départ.

Indice sur comment déchiffrer en quelques mots.

Une des facons les plus simples de déchiffrer est de prendre chacun des caractères du texte chiffré un à un et de les déchiffrer en utilisant la cle (si ce sont des lettres minuscules) puis de les concaténer au fur et à mesure avec une chaîne de caractères qui est vide au départ.

Remarquez comme la fonction de chiffrement et celle de déchiffrement fonctionnent vraiment de manière symétrique.

Indice sur comment faire "cryptanalyse" en quelques mots.

Pour trouver la clé à partir d'un texte clair et d'un texte chiffré, on peut essayer par exemple de déchiffrer le texte chiffré en essayant les clés de manière exhaustive et de comparer le résultat avec le texte clair jusqu'à ce qu'on trouve une correspondance ou qu'on est essayé toutes les clés.

S'il n'y a pas de correspondance exacte possible entre le texte clair et le texte chiffré, le programme doit s'en rendre compte et afficher (voir prototype pour plus détails):

il n'existe pas de cle valide permettant de passer du message chiffre au texte clair

Exemple d'éxécution

Voici un exemple d'exécution du programme

commande: chiffrement
texte clair : cesar utilisait deja la cryptographie
cle : 19
message chiffre : vxltk nmbebltbm wxct et vkrimhzktiabx
commande: dechiffrement
message chiffre : vxltk nmbebltbm wxct et vkrimhzktiabx
cle : 19
texte clair : cesar utilisait deja la cryptographie
commande: cryptanalyse
texte clair : cesar utilisait deja la cryptographie
message chiffre : vxltk nmbebltbm wxct et vkrimhzktiabx
cle trouvee: 19
commande: quitter
Remise

Votre devoir doit être remis le jeudi 17 février 2005 avant minuit. À moins d'excuses irréfutables, tout devoir remis après cette date méritera la note 0.
La remise est faite avec la commande:

remise ift1010 ex05 Crypto.java


Vous pouvez voir ce que vous avez remis avec la commande:

remise -v ift1010 ex05


Remarque: remettre un fichier une deuxieme fois écrase la version précédente.



Barême de correction

  • Le format de sortie tel que implémenté par le prototype doit être respecté à la lettre sous peine de sanctions sévère au niveau des points.
  • La qualité du code est tenu en ligne de compte pour la correction. Attention aux commentaires, à l'indentation et la logique de votre programme!!! (0.5) Il est particulièrement important que vous implémentiez le chiffrement, le déchiffrement et la cryptanalyse sous forme de fonctions et pas tout en bloc directement dans le main, sous peine de quoi des points vous serons enlevés.
  • Des points sont accordés selon certains tests que nous ferons sur le chiffrement (0.2 points), le déchiffrement (0.2) et la cryptanalyse (0.1).
  • Nous vous conseillons très fortement de vérifier que la sortie de votre programme donne la même que celle de notre prototype car c'est sur cette comparaison que nous baserons pour évaluer l'exécution. Ce n'est donc pas une perte de temps que de prendre le temps de jouer avec le prototype et voir comment il réagit.
  • Si le programme ne compile pas, aucun point relatif à l'exécution ne sera accordé.

[Retour au sommet de la page]