ITI 1521. Introduction à l’informatique II
Hiver 2007

Devoir 1

Échéance: dimanche le 21 janvier, 2007, 23 h

[ PDF ]

Solution

Objectifs

Introduction

Le traitement sécuritaire des données dans une société d’information est essentiel aux activités politiques et économiques. L’une des façons de sécuriser la transmission des informations consiste à encoder les messages de sorte qu’ils soient indéchiffrables pour tous ceux qui n’en possèdent pas la clé. La cryptographie s’intéresse aux techniques permettant l’échange sécuritaire d’information.

Il y a deux grandes approches en cryptographie : transposition et substitution. La méthode de transposition implique changer l’ordre lettres à l’intérieur du message, par exemple on pourrait encoder le mot “word” comme ceci “owdr”.

La méthode de substitution consiste à remplacer chaque lettre du message original (plain text) par une nouvelle afin de créer la représentation encodée (cipher text). Dans ce contexte, l’ensemble des règles décrivant la transformation à partir d’un alphabet en clair vers l’alphabet chiffré s’appelle la clé.

Voici un exemple simple (Caesar shift cipher). Chaque lettre de l’alphabet en clair est remplacée par celle qui se trouve trois positions en aval.

Plain alphabet  = a b c d e f g h i j k l m n o p q r s t u v w x y z  
Cipher alphabet = d e f g h i j k l m n o p q r s t u v w x y z a b c

Lorsqu’on utilise ce code afin de chiffrer ce texte.

follow the white rabbit

On obtient le texte chiffré suivant.

iroorz wkh zklwh udeelw

À première vue, cette façon de faire semble sécuritaire puisqu’il y a 26! = 403,291,461,126,605,635,584,000,000 clés distinctes. On ne pourrait tous simplement pas toutes les essayer.

Cependant, cette méthode a son talon d’Achille. Les lettres de l’alphabet ne sont pas utilisées avec la même fréquence. Par exemple, les lettres ’a’ et ’e’ apparaissent plus fréquemment que les lettres ’k’ et ’w’. Ainsi, dans le texte chiffré les lettres qui apparaissent fréquemment correspondent probablement aux lettres ’a’ et ’e’.

Cette observation servira de fondation pour la construction d’un outil pour assister le décodage de messages chiffrés à l’aide d’un code de substitution. Voici un exemple de son utilisation.

************************************************************  
*                                                          *  
*                                                          *  
*                                                          *  
*                                                          *  
************************************************************  
 
Assignment 1, question 3:  
 
1. Select a dictionary.  
2. Select an encrypted text.  
3. Guess a key using frequency analysis.  
4. Show the current key.  
5. Show the current decoded text.  
6. Calculate words count.  
7. Modify the current key.  
8. Quit.  
 
Enter your selection and press return:

L’une des premières choses à faire pour ce devoir, c’est de modifier la classe StudentInfo afin que sa méthode display affiche vos informations (nom, numéro d’étudiant, etc.) dans la boîte. Sélectionnons l’option 1 afin de charger un dictionnaire en mémoire, ce qui nous servira au moment où nous transformerons une clé existante.

Select a dictionary.  
Enter file name and press return: dict.txt  
Enter the maximum number of words to be read and press return: 233615

Nous sommes de retour au menu principal.

1. Select a dictionary.  
2. Select an encrypted text.  
3. Guess a key using frequency analysis.  
4. Show the current key.  
5. Show the current decoded text.  
6. Calculate words count.  
7. Modify the current key.  
8. Quit.  
 
Enter your selection and press return:

Sélectionnons l’option 2.

Select an encrypted text.  
Enter file name and press return: cipher.txt  
Enter the maximum number of words to be read and press return: 121

Nous sommes de retour au menu principal, encore.

1. Select a dictionary.  
2. Select an encrypted text.  
3. Guess a key using frequency analysis.  
4. Show the current key.  
5. Show the current decoded text.  
6. Calculate words count.  
7. Modify the current key.  
8. Quit.  
 
Enter your selection and press return:

C’est ici que le déchiffrage commence. Nous utiliserons un texte en clair connu afin de calculer la fréquence des 26 lettres de l’alphabet, dans ce texte. Nous calculerons aussi la fréquence des 26 lettres de l’alphabet, mais cette fois dans le message chiffré. La lettre qui apparaît le plus fréquemment dans le message chiffré correspond probablement à la lettre qui apparaît le plus fréquemment dans le texte en clair. La lettre dont la fréquence apparaît au second rang dans le texte chiffré correspond probablement à la lettre qui apparaît au second rang dans le texte en clair, et ainsi de suite pour les 26 lettres de l’alphabet.

Pour que cette technique fonctionne bien, il faut que les fréquences des lettres du message original (non chiffré) soient les mêmes que celles du texte en clair utilisé pour l’analyse. Si l’on a des raisons de croire qu’il s’agit d’un texte militaire, il serait judicieux que l’on utilise un texte militaire pour l’analyse. S’il s’agit d’un texte scientifique alors, on utilisera un texte scientifique pour l’analyse des fréquences.

Commençons cette analyse par le meilleur scénario possible, celui où les fréquences des lettres dans les deux textes (texte original non chiffré et le texte en claire utilisé pour l’analyse) sont les mêmes. Pour ce faire, nous utiliserons le texte original ! Sélectionnons l’option 3.

Guess a key using frequency analysis.  
Enter file name and press return: plain.txt  
Enter the maximum number of words to be read and press return: 121

De retour au menu principal.

1. Select a dictionary.  
2. Select an encrypted text.  
3. Guess a key using frequency analysis.  
4. Show the current key.  
5. Show the current decoded text.  
6. Calculate words count.  
7. Modify the current key.  
8. Quit.  
 
Enter your selection and press return:

Jetons un coup d’oeil à la clé ainsi générée (option 4). Est-ce que cette clé vous semble familière ?

Key is  
a -> d  
b -> e  
c -> f  
d -> g  
e -> h  
f -> i  
g -> j  
h -> k  
i -> l  
j -> a  
k -> n  
l -> o  
m -> p  
n -> q  
o -> r  
p -> s  
q -> m  
r -> u  
s -> v  
t -> w  
u -> x  
v -> y  
w -> z  
x -> t  
y -> b  
z -> c  
 
Press return.

De retour vous savez où.

1. Select a dictionary.  
2. Select an encrypted text.  
3. Guess a key using frequency analysis.  
4. Show the current key.  
5. Show the current decoded text.  
6. Calculate words count.  
7. Modify the current key.  
8. Quit.  
 
Enter your selection and press return:

Sélectionnons l’option 5 afin de visualiser le texte déchiffré à l’aide de la clé obtenue à l’étape précédente.

Cipher text: ndupd srolfh duuhvw wklv pdq kh wdonv lq pdwkv kh excchv olnh d iulgjh k hv olnh d ghwxqhg udglr ndupd srolfh duuhvw wklv jluo khu klwohu kdlugr lv pdnlqj ph ihho loo dqg zh kdyh fudvkhg khu sduwb wklv lv zkdw brx jhw wklv lv zkdw brx jhw wklv lv zkdw brx jhw zkhq brx phvv zlwk xv ndupd srolfh l yh jlyhq doo l fdq lwv qrw hqrxjk l yh jlyhq doo l fdq exw zhuh vwloo rq wkh sdburoo wklv lv zkdw brx jhw wklv lv zkdw brx jhw wklv lv zkdw brx jhw zkhq brx phvv zlwk xv dqg iru d plqxwh wkhuh l orvw pbvhoi l orvw pbvhoi dqg iru d plqxwh wkhuh l orvw pbvhoi  
Plain text:  faoma prlice aooest this man he talfs in maths he buzzes life a koidge h es life a detuned oadir faoma prlice aooest this giol heo hitleo haiodr is mafing me keel ill and we have coashed heo paoty this is what yru get this is what yru get this is what yru get when yru mess with us faoma prlice i ve given all i can its nrt enrugh i ve given all i can but weoe still rn the payorll this is what yru get this is what yru get this is what yru get when yru mess with us and kro a minute theoe i lrst myselk i lrst myselk and kro a minute theoe i lrst myselk  
 
Press return.

Plusieurs mots sont reconnaissables. Cependant, il y a quelques erreurs, telles que “prlice”. C’est sans doute parce certaines lettres à l’intérieur d’un même texte ont la même fréquence ce qui donne lieu à de multiples solutions.

1. Select a dictionary.  
2. Select an encrypted text.  
3. Guess a key using frequency analysis.  
4. Show the current key.  
5. Show the current decoded text.  
6. Calculate words count.  
7. Modify the current key.  
8. Quit.  
 
Enter your selection and press return:

Pour nous aider dans notre analyse, il serait utile de connaître le nombre de mots du message déchiffré qui se retrouvent aussi dans le dictionnaire. Ainsi, lorsque nous apporterons des changements à la clé, nous saurons si ces changements vont dans la bonne direction. Choisissons l’option 6.

In the current decoded text, of 121 words, 109 were found in the dictionary.  
Press return.

De retour à l’écran principal.

1. Select a dictionary.  
2. Select an encrypted text.  
3. Guess a key using frequency analysis.  
4. Show the current key.  
5. Show the current decoded text.  
6. Calculate words count.  
7. Modify the current key.  
8. Quit.  
 
Enter your selection and press return:

Regardons maintenant ce qui arrive si l’on utilise un texte différent du message original pour l’analyse ; ce qui correspond mieux à une situation réelle. J’utilise ici le texte “Alice’s Adventures in Wonderland” de Lewis Carroll. J’ai obtenu ce texte du projet Gutenberg, qui regroupe plusieurs textes dont les droits d’auteurs sont expirés.

Guess a key using frequency analysis.  
Enter file name and press return: alice.txt  
Enter the maximum number of words to be read and press return: 27340

Menu principal.

1. Select a dictionary.  
2. Select an encrypted text.  
3. Guess a key using frequency analysis.  
4. Show the current key.  
5. Show the current decoded text.  
6. Calculate words count.  
7. Modify the current key.  
8. Quit.  
 
Enter your selection and press return:

Jetons un oeil à cette clé.

Key is  
a -> w  
b -> y  
c -> j  
d -> q  
e -> h  
f -> n  
g -> z  
h -> k  
i -> d  
j -> m  
k -> s  
l -> x  
m -> i  
n -> o  
o -> v  
p -> f  
q -> e  
r -> u  
s -> r  
t -> l  
u -> p  
v -> c  
w -> b  
x -> t  
y -> g  
z -> a  
 
Press return.

De retour au menu principal.

1. Select a dictionary.  
2. Select an encrypted text.  
3. Guess a key using frequency analysis.  
4. Show the current key.  
5. Show the current decoded text.  
6. Calculate words count.  
7. Modify the current key.  
8. Quit.  
 
Enter your selection and press return:

Regardez le texte résultant, option 5.

Cipher text: ndupd srolfh duuhvw wklv pdq kh wdonv lq pdwkv kh excchv olnh d iulgjh khv olnh d ghwxqhg udglr ndupd srolfh duuhvw wklv jluo khu klwohu kdlugr lv pdnlqj ph ihho loo dqg zh kdyh fudvkhg khu sduwb wklv lv zkdw brx jhw wklv lv zkdw brx jhw wklv lv zkdw brx jhw zkhq brx phvv zlwk xv ndupd srolfh lyh jlyhq doo l fdq lwv qrw hqrxjk lyh jlyhq doo l fdq exw zhuh vwloo rq wkh sdburoo wklv lv zkdw brx jhw wklv lv zkdw brx jhw wklv lv zkdw brx jhw zkhq brx phvv zlwk xv dqg iru d plqxwh wkhuh l orvw pbvhoi l orvw pbvhoi dqg iru d plqxwh wkhuh l orvw pbvhoi l orvw pbvhoi  
Plain text:  firui ksntpe irreoa ahto uid he ainfo td uiaho he qlvveo ntfe i mrtyce heo ntfe i yealdey riyts firui ksntpe irreoa ahto ctrn her htaner hitrys to uiftdc ue meen tnn idy ge hibe priohey her kiraw ahto to ghia wsl cea ahto to ghia wsl cea ahto to ghia wsl cea ghed wsl ueoo gtah lo firui ksntpe tbe ctbed inn t pid tao dsa edslch tbe ctbed inn t pid qla gere oatnn sd ahe kiwrsnn ahto to ghia wsl cea ahto to ghia wsl cea ahto to ghia wsl cea ghed wsl ueoo gtah lo idy msr i utdlae ahere t nsoa uwoenm t nsoa uwoenm idy msr i utdlae ahere t nsoa uwoenm t nsoa uwoenm  
 
Press return.

Il semble que Thom Yorke (du groupe Radiohead et auteur du texte original) et Lewis Carroll utilisent un vocabulaire assez différent puisque cette clé semble produire un mauvais résultat.

 
1. Select a dictionary.  
2. Select an encrypted text.  
3. Guess a key using frequency analysis.  
4. Show the current key.  
5. Show the current decoded text.  
6. Calculate words count.  
7. Modify the current key.  
8. Quit.  
 
Enter your selection and press return:

Combien de mots du texte déchiffré se retrouvent aussi dans le dictionnaire ? Option 6.

In the current decoded text, of 121 words, 28 were found in the dictionary.  
Press return.

Menu principal.

1. Select a dictionary.  
2. Select an encrypted text.  
3. Guess a key using frequency analysis.  
4. Show the current key.  
5. Show the current decoded text.  
6. Calculate words count.  
7. Modify the current key.  
8. Quit.  
 
Enter your selection and press return:

C’est maintenant le début d’un travail fastidieux où l’on transforme la clé à l’aide d’indices obtenus à partir de mots partiellement décodés. Option 7.

Enter plain letter and press return: l  
Enter cipher letter and press return: i

Menu principal.

1. Select a dictionary.  
2. Select an encrypted text.  
3. Guess a key using frequency analysis.  
4. Show the current key.  
5. Show the current decoded text.  
6. Calculate words count.  
7. Modify the current key.  
8. Quit.  
 
Enter your selection and press return:

Jetez un oeil au résultat. Option 5.

Cipher text: ndupd srolfh duuhvw wklv pdq kh wdonv lq pdwkv kh excchv olnh d iulgjh khv olnh d ghwxqhg udglr ndupd srolfh duuhvw wklv jluo khu klwohu kdlugr lv pdnlqj ph ihho loo dqg zh kdyh fudvkhg khu sduwb wklv lv zkdw brx jhw wklv lv zkdw brx jhw wklv lv zkdw brx jhw zkhq brx phvv zlwk xv ndupd srolfh lyh jlyhq doo l fdq lwv qrw hqrxjk lyh jlyhq doo l fdq exw zhuh vwloo rq wkh sdburoo wklv lv zkdw brx jhw wklv lv zkdw brx jhw wklv lv zkdw brx jhw zkhq brx phvv zlwk xv dqg iru d plqxwh wkhuh l orvw pbvhoi l orvw pbvhoi dqg iru d plqxwh wkhuh l orvw pbvhoi l orvw pbvhoi  
Plain text:  firui ksntpe irreoa ahto uid he ainfo td uiaho he q!vveo ntfe i lrtyce heo ntfe i yea!dey riyts firui ksntpe irreoa ahto ctrn her htaner hitrys to uiftdc ue leen tnn idy ge hibe priohey her kiraw ahto to ghia ws! cea ahto to ghia ws! cea ahto to ghia ws! cea ghed ws! ueoo gtah !o firui ksntpe tbe ctbed inn t pid tao dsa eds!ch tbe ctbed inn t pid q!a gere oatnn sd ahe kiwrsnn ahto to ghia ws! cea ahto to ghia ws! cea ahto to ghia ws! cea ghed ws! ueoo gtah !o idy lsr i utd!ae ahere t nsoa uwoenl t nsoa uwoenl idy lsr i utd!ae ahere t nsoa uwoenl t nsoa uwoenl  
 
Press return.

Menu principal.

1. Select a dictionary.  
2. Select an encrypted text.  
3. Guess a key using frequency analysis.  
4. Show the current key.  
5. Show the current decoded text.  
6. Calculate words count.  
7. Modify the current key.  
8. Quit.  
 
Enter your selection and press return:

Est-ce un pas dans la bonne direction ? Option 6.

In the current decoded text, of 121 words, 26 were found in the dictionary.  
Press return.

Menu principal.

1. Select a dictionary.  
2. Select an encrypted text.  
3. Guess a key using frequency analysis.  
4. Show the current key.  
5. Show the current decoded text.  
6. Calculate words count.  
7. Modify the current key.  
8. Quit.  
 
Enter your selection and press return:

Éventuellement, l’usager souhaitera sortir du système. Il sélectionnera alors l’option 8.

Bye!

Voilà ! Ceci vous donne une bonne idée du produit final. J’ai implémenté plusieurs classes et méthodes pour vous. Les instructions qui suivent vous aideront à compléter l’outil.

Au cours du semestre, nous verrons les mécanismes qui s’offrent à nous pour le traitement des erreurs en Java. D’ici là, faites l’hypothèse que les valeurs des paramètres sont valides.

1 Key (30 points)

La classe Key définit les attributs et comportements communs à l’ensemble des clés. En particulier, l’interface de cette classe contient les méthodes qui suivent.

public char encodeChar( char c ) :
Une méthode d’instance qui retourne le caractère chiffré correspondant à la valeur de c ;
public char decodeChar( char c ) :
Une méthode d’instance qui retourne le caractère en clair correspondant à la lettre chiffrée c ;
public void remap( char src, char dst ) :
Une méthode d’instance servant à modifier la substitution associée à la lettre src, qui sera maintenant associée à la lettre dst ;
public String encodeWord( String w ) :
Une méthode d’instance servant au chiffrage du mot en clair w ;
public String decodeWord( String w ) :
Une méthode d’instance servant au déchiffrage du mot chiffré w.

Le constructeur Key( char[] table ) sert à initialiser cette clé à l’aide du code spécifié par la table de substitutions. La lettre à la position i du tableau est la lettre chiffrée correspondant à la lettre se trouvant à la position i de l’alphabet, donc table[ 0 ] est la substitution associée à la lettre ’a’.

Vous devez modifier les deux classes existantes suivantes, Key et A1Q1, afin d’y ajouter les méthodes qui suivent.

  1. public String toString() : Ajoutez à la classe Key une méthode qui retourne une représentation sous forme de chaîne de caractères de cette clé. Utilisez le format des exemples ci-haut, aussi reproduit à la fin du fichier contenant la classe A1Q1 ; (10 points)
  2. public boolean equals( Key other ) : Toujours à l’intérieur de la classe Key, vous devez créer une méthode d’instance boolean equals( Key other ) servant à comparer le contenu de cette clé à celui de l’objet désigné par la variable other ; il s’agit d’une comparaison logique. La méthode retournera la valeur true si les deux objets ont le même contenu, et false sinon ; (10 points)
  3. Dans la class A1AQ1, vous devez implémenter la méthode de classe (static) suivante boolean static equal( String[] m1, String[] m2 ). Cette dernière fait une comparaison logique de deux messages. Ici, un message est représenté à l’aide d’un tableau de mots (des chaînes de caractères). Les références m1 et m2 désignent des tableaux de chaînes de caractères, donc deux messages. (10 points)

La classe A1Q1 contient quelques tests pour ces trois méthodes.

2 Dictionary (20 points)

Afin d’assister le déchiffrage du texte, vous allez créer un dictionnaire. Suivez ces directives.

  1. Il faut créer une classe nommée Dictionary. Toutes ses variables d’instance sont privées. Un dictionnaire utilise un tableau de chaînes de caractères afin de garder en mémoire les mots qu’il représente ; (5 points)
  2. Le constructeur Dictionary( String fileName, int size ) initialise le contenu de ce dictionnaire à l’aide des mots qu’il trouve dans le fichier fileName. Les mots du fichier sont déjà en ordre alphabétique. La méthode String[] Utilities.getText( String fileName, int size ) peut être utilisée afin de lire le contenu d’un fichier. Le paramètre formel size représente le nombre de mots à lire ;(5 points)
  3. Un dictionnaire possède une méthode d’accès nommée lookup. La signature de cette méthode est lookup( String word ). Cette dernière retourne la valeur true si la chaîne word se trouve dans ce dictionnaire, et false sinon. Puisqu’un dictionnaire peut avoir une taille considérable, cette méthode doit être rapide. Par exemple, le dictionnaire Webster, que vous trouverez sur la page du devoir, contient 233,615 mots. En conséquence, 1 point sera attribué pour l’efficacité (rapidité) de la méthode. (10 points)

3 Cryptography (30 points)

La classe Cryptography fournit une liste de méthodes pour assister le déchiffrage de messages. Pour ce devoir, il n’y aura qu’une seule méthode publique, dont voici la signature et la valeur de retour Key suggestKey( String[] plain, String[] cipher ) ; cette classe peut aussi contenir des méthodes privées additionnelles (c’est un détail d’implémentation caché).

Vous pouvez utiliser l’interface usager textuelle afin de tester vos méthodes. Dans une fenêtre de commande, tapez java Run (à partir du répertoire où se trouve le ficher Run.class).

Fraude scolaire

Cette partie du devoir a pour but de sensibiliser les étudiants face au problème de fraude scolaire (plagiat). Lisez les deux documents qui suivent :

Les règlements de l’université seront appliqués pour tout cas de plagiat. En soumettant ce devoir, vous signifiez avoir lu les documents ci-haut, et vous comprenez les conséquences de la fraude scolaire.

Consignes

Vous devez préférablement faire le travail en équipe de deux, mais vous pouvez aussi faire le travail individuellement. Veuillez suivre les consignes disponibles sur la page des consignes aux devoirs. Tous les devoirs doivent être soumis à l’aide de maestro.

Fichiers

Vous devez remettre les fichiers suivants.

Voici quelques fichiers supplémentaires qui pourraient être utiles lors du développement de vos programmes. Ne soumettez pas ces fichiers lors de la remise du devoir, certains de ces fichiers sont très gros.

Références

[1]   Simon Singh. The Code Book : The Science of Secrecy from Ancient Egypt to Quantum Cryptography. Fourth Estate, 1999.

Foire Aux Questions (FAQ)

  1. “Lorsque l’usager modifie une clé en utilisant l’option 7, la méthode remap change l’affectation d’un caractère source vers une nouvelle destination, ainsi l’ancien caractère destination n’a plus de source, ce que fait en sorte que lorsque j’affiche le texte déchiffré à l’aide de cette nouvelle clé, l’ancien caractère destination n’a plus de source, la méthode decodeChar retourne le symbole “ !”. Est-ce le résultat attendu ?”

    Oui, c’est bien le résultat espéré. Afin de garder l’implémentation des méthodes assez simple, c’est la responsabilité de l’utilisateur du système d’effectuer toutes les modifications nécessaires à la clé.

  2. ‘Oui, c’est bien le résultat espéré. Afin de garder l’implémentation des méthodes assez simple, c’est la responsabilité de l’utilisateur du système d’effectuer toutes les modifications nécéssaires à la clé. ?”

    En effet, certains étudiants m’ont dit que DrJava éprouvait certaines difficultés avec l’exécution de cette méthode. Cela semble lié à un problème connu de la version courante de DrJava. Je vous suggère d’utiliser la ligne de commande, telle que vue au laboratoire 1.

    java Run

Modifié le : 1er février 2016