-------------------------------------------------------- BFZ#1/ Cryptologie slugg -------------------------------------------------------- CCCC RRRRR YY YY PPPPP TTTTTT OOOO LL OOOO GGGG II EEEEEE CCCCCC RR RR YY YY PP PP TTTTTT OOOOOO LL OOOOOO GGGGGG EEEEEE CC CC RR RR YY YY PP PP TT OO OO LL OO OO GG GG II EE CC RRRRR YYYY PPPPP TT OO OO LL OO OO GG II EEEE CC RR RR YY PP TT OO OO LL OO OO GG II EEEE CC CC RR RR YY PP TT OO OO LL OO OO GG GGG II EE CCCCCC RR RR YY PP TT OOOOOO LLLLLL OOOOOO GG G G II EEEEEE CCCC RR RR YY PP TT OOOO LLLLLL OOOO GGG G II EEEEEE 1. INTRODUCTION **************** La cryptologie est LA science du message secret. Elle se partage en deux parties, la CRYPTOGRAPHIE, qui est l'etude des techniques destines a assurer la confidentialite, l'integrite, et l'authentification des donnees, et la CRYPTANALYSE, qui consiste a casser ces techniques cryptographiques. On va donc voir comment proteger ses donnees en les chiffrant (avec des systemes de chiffrement classiques), et voir comment on peut casser ces chiffrages. On essaiera ensuite de creer une application en C, qui pourrai simplifier tout ce shlimblick, dans certains cas seulement, j'vais pas vous macher tout le boulot non plus :-). Enfin je tenai a dire qu'a l'heure ou les libertes numeriques (s'il y avait que celles la) ne cessent de reculer (en France en tout cas), il devient indispensable de s'interesser a ce domaine (qui plus est, fort interessant). Treve de bavardarge... LET's GO !! 2. TABLE DES MATIERES ****************** 1. Introduction 2. Table des matieres 3. Chiffrement par transposition 3.1. Transposition simple 3.2. Variantes 3.3. Cryptanalyse 4. Chiffrement par substitution 4.1 Substitution monoalphabetique 4.1.1. La substitution monoalphabetique decalee : CESAR 4.1.2. Cryptanalyse d un systeme monoalphabetique 4.2 Substitution polyalphabetique 4.2.1 Le chiffre de Vigenere 4.2.2 Cryptanalyse du chiffre de Vigenere 5. Epilogue 6. Annexe 3. LE CHIFFREMENT PAR TRANSPOSITION ************************************ Le chiffrement par transposition consiste a melanger les lettres de votre message, en utilisant un principe mathematique de permutation : 3.1.Transposition simple ======================== On ecrit le message horizontalement dans une grille predefinie (appelee matrice), puis on retrouve le message crypte en lisant la grille verticalement. Pour decrypter il suffit de realiser le procede inverse. Texte en clair : CECI EST UN EXEMPLE DE TRANSPOSITION SIMPLE PAR COLONNE utilisant une matrice [7;7]. (7 colonnes, 7 lignes) _______________ |C|E|C|I|E|S|T| |U|N|E|X|E|M|P| |L|E|D|E|T|R|A| |N|S|P|O|S|I|T| |I|O|N|S|I|M|P| |L|E|P|A|R|C|O| |L|O|N|N|E| Texte crypte : CULNILLENESOEOCEDPNPNIXEOSANEETSIRESMRIMCTPATPO ==> La cle est une matrice [7;7] 3.2.Variantes ============= Ici on commence par choisir un MOT CLE. Celui-ci doit avoir autant de lettres qu'il y a de colonnes dans notre matrice, ni plus, ni moins. De plus le mot cle ne doit surtout pas contenir 2 fois la meme lettre. Ensuite on attribue a chaque lettre du mot cle, un numero de sequence, commancant a 1 et finissant au nombre de lettre composant notre mot cle. On obtient les numeros de sequence en partant de la gauche vers la droite, et en donnant l'ordre d'apparition dans l'alphabet. Ceci fait on peut maintenant placer notre message dans la matrice, toujours horizontalement,et on lit le message crypte verticalement en suivant le numero de sequence : Notre mot cle est : CRYPTO L'ordre d'apparition dans l'alphabet est : COPRTY Texte clair : CECI EST UNE VARIANTE AVEC UN MOT CLE Matrice [6;5] C R Y P T O 1 4 6 3 5 2 _____________ |C|E|C|I|E|S| |T|U|N|E|E|X| |E|M|P|L|E|D| |E|V|A|R|I|A| |N|T|E|A|V|E| |C|U|N|M|O|T| |C|L|E| Texte crypte : ==> La cle est une matrice [6;5]transposition CRYPTO Il existe plusieurs variantes pour ameliorer la confidentialite du texte chiffre : une rotation de la grille, un ajout de lettres inutiles, etc... 3.3.Cryptanalyse du chiffrement par transposition ================================================= Un chiffrement par transposition est rarement utilise seul; il est plus souvent utilise avant ou apres un autres algorithme de cryptage. De plus, une simple analyse de frequence des caracteres(cf plus bas) est inutile, puisque les lettres avant le chiffrage sont les memes qu apres. Le nombre de possibilites augmentant avec le nombre de lettre, je vous recommande de vous armer de votre patience pour TOUTE cryptanalyse, meme avec un ordinateur puissant : ici, pour un message de "n" lettres, il y a : n!=1*2*...*(n-1)*n possibilites. Donc, le plus simple serait de retrouver le nombre de colonnes que comprend la matrice, en cherchant a prendre qu une lettre sur 2 (sur 3, sur 4,....sur 7 dans notre premier cas). Regardons ce que ca donne avec la matrice : _______________ |C|E|C|I|E|S|T| |U|N|E|X|E|M|P| |L|E|D|E|T|R|A| |N|S|P|O|S|I|T| |I|O|N|S|I|M|P| |L|E|P|A|R|C|O| |L|O|N|N|E| Texte crypte : Culnill Enesoeo Cedpnpn Ixeosan Eetsire Smrimc Tpatpo J'ai decoupe en 7 blocs, pour bien reperer les colonnes. Vous remarquerez que les premieres lettres de chaque block nous donne le debut de notre texte non chiffre. Arrivee au dernier block, on recommence en s interessant a la 2e lettres de chaque block, puis a la troisieme, et ainsi de suite. Cette methode marche tres bien, avec un petit nombre de caractere, et dans le cas d'une transposition simple. 4. LE CHIFFREMENT PAR SUBSTITUTION *********************************** Le principe de substitution consiste a remplacer un ou plusieurs caracteres par d'autres caracteres. Contrairement au chiffrement par transposition, la substitution change (totalement ou partiellement) les lettres et peut dans certains cas utiliser d autres symboles, ou alphabets. Il existe plusieurs procedes de substitution, nous n'en verrons que deux : la substitution monoalphabetique (dite simple) et la substitution polyalphabetique. 4.1.La substitution monoalphabetique ===================================== La substitution monoalphabetique se dit simple puisqu'il suffit d'attribuer a un alphabet clair un equivalent chiffre,cet alphabet chiffre sera conserve tout au long du processus de chiffrement. Ce type de chiffrement est tres peu sur. On retrouve dans cette categorie, les alphabet desordonne, ou reversible, le carre de polybe, le chiffre de "CESAR" que nous allons etudier. 4.1.1. La substitution monoalphabetique par décalage ---------------------------------------------------- "Le chiffre de CESAR" consiste a choisir une lettre (la cle) qui definira le decalage a effectuer a l ensemble du texte clair (Modulo 26 pour que ca boucle correctement). CLAIR 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 +1 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 A +2 C 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 +3 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . +23 X Y Z A B C D E F G H I J K L M N O P Q R S T U V W +24 Y Z A B C D E F G H I J K L M N O P Q R S T U V W X +25 Z 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 Par exemple, en prennant comme decalage (cle) +2, le texte clair : "La substitution monoalphabetique est simple" devient "Nc uwduvkvwvkqp oqpqcnrjcdgvkswg guv ukorng" Pour dechiffre, il faut faire le decalage OPPOSE (le signe change), c'est a dire -2. Qui a dit que la crypto etait compliquee ? Bon maintenant on va essayer d'automatiser tout ca avec un petit code. -------------8<-------------cut-------------8<-----------------cut-------------8<------------- #include #include #define TAILLE 100 /* modifie ici pour un texte de plus de 100 caracteres */ int main (int argc , char **argv) { int i , cle ; char mode [6] ; /* mode encode ou decode */ char entree[TAILLE] ; /* texte entree par l utilisateur */ char sortie[TAILLE] ; /* texte sortie apres modification */ if(argc < 4) { printf("aide : %s <\"texte\"> ",argv[0]) ; exit(0); } strcpy(entree, argv[1]) ; strcpy(mode, argv[3]) ; cle = atoi(argv[2]) ; if ((mode[0] == 'E') || (mode[0] == 'e')) { for(i=0 ; ica veut pas dire grand chose, on passe a V=A SH ZBIZAPABAPVU TVUVHSWOHILAPXBL LZA ZPTWSL ==>ca veut rien dire non plus, On continu avec v=S, puis v=I, puis v=T, jusqu a ce qu on trouve : avec v=T ==>JACKPOT, on trouve une phrase qui signifie quelque chose : LA SUBSTITUTION MONOALPHABETIQUE EST SIMPLE (le texte clair). L'analyse de frequence est plus performante avec les gros textes. Vous avez compris ? Passons au code : -------------8<-------------cut-------------8<-----------------cut-------------8<------------- #include #include #define alpha 26 #define TAILLE 100 /* modifie ici pour un texte de plus de 100 caracteres */ void init(void); /* initialisation */ char caractere[alpha][2] ; char texte[TAILLE] ; /* texte a analyser */ int compte[alpha] ; /* pour compter les differentes lettres */ float pourcent[alpha] ; /* pour calculer le pourcentage */ int total = 0 ; /* nombre total de caractere dans le texte */ int main(int argc, char **argv) { int i, j ; init() ; if(argc < 2) { printf("aide : %s <\"texte\"> ",argv[0]) ; exit(0) ; } strcpy(texte, argv[1]) ; for (i=0 ; i