livre-algorithmes EXo7.pdf
On retient les choses suivantes : • On affecte une valeur à une variable par le signe égal a. Page 9. ALGORITHMES ET MATHÉMATIQUES. 1. PREMIERS PAS AVEC Python
Python au lycée - tome 1
et maîtriser la programmation en s'aidant des mathématiques. Python Pour cela tu vas programmer un algorithme qui est une version simple du crible ...
Cours de mathématiques - Exo7
En plus la programmation est simple
ALGORITHME SECONDE Exercice 5.1 Ecrire un algorithme qui
Ecrire un algorithme qui demande à l'utilisateur un nombre compris entre 1 et 3 jusqu'à ce NB : cet algorithme peut être écrit d'une manière simple ...
Cours de mathématiques - Exo7
ALGORITHMES ET MATHÉMATIQUES. 1. PREMIERS PAS AVEC Python 2. 1.2. Somme des cubes. Travaux pratiques 2. 1. Pour un entier n fixé programmer le calcul de la
COURS ALGORITHMIQUE ET PROGRAMMATION INFORMATIQUE
Mar 12 2013 ALGORITHME. • Savoir expliquer comment faire un travail sans la moindre ambiguïté. • langage simple : des instructions (pas élémentaires).
LATEX pour le prof de maths !
Jan 11 2021 <b></b> \url{http://<b>math</b>.univ-lyon1.fr/irem/}. 3.8 Deux idées pour un QCM. 3.8.1 En bout de ligne. Entourer la réponse correcte. 1. <b>Premier</b> énoncé.
Cours de mathématiques - Exo7
L'attaque la plus simple pour Chloé est de tester ce que donne chacune Voici un petit algorithme qui calcule la fréquence de chaque lettre d'une phrase.
Outils Mathématiques et utilisation de Matlab
Si la mantisse est codée sur. 23 bits cela signifie que l'on peut obtenir les nombres entre 0 et 223. 1 = 8388607
Cryptographie
Vidéo"partie 1. Le chiffrement de César
Vidéo"partie 2. Le chiffrement de Vigenère
Vidéo"partie 3. La machine Enigma et les clés secrètes Vidéo"partie 4. La cryptographie à clé publiqueVidéo"partie 5. L"arithmétique pour RSA
Vidéo"partie 6. Le chiffrement RSA
1. Le chiffrement de César
1.1. César a dit...
Jules César a-t-il vraiment prononcé la célèbre phrase :DOHD MDFWD HVW
ou bien comme le disent deux célèbres Gaulois : " Ils sont fous ces romains! ».En fait César, pour ses communications importantes à son armée, cryptait ses messages. Ce que l"on appelle le
chiffrement de César est un décalage des lettres : pour crypter un message,AdevientD,BdevientE,CdevientF,...
A7!DB 7!EC 7!F...W7!ZX 7!AY 7!BZ 7!C
Voici une figure avec l"alphabet d"origine en haut et enrouge, en correspondance avec l"alphabet pour le chiffrement
en-dessous et envert.Nous adopterons la convention suivante, envertc"est la partie du message à laquelle tout le monde a accès (ou qui
pourrait être intercepté), c"est donc le message crypté. Alors qu"enrougec"est la partie du message confidentiel, c"est
le message en clair.Pour prendre en compte aussi les dernières lettres de l"alphabet, il est plus judicieux de représenté l"alphabet sur un
anneau. Ce décalage est undécalage circulairesur les lettres de l"alphabet.CRYPTOGRAPHIE1. LE CHIFFREMENT DECÉSAR2Pour déchiffrer le message de César, il suffit de décaler les lettres dans l"autre sens,Dse déchiffre enA,EenB,...
Et la célèbre phrase de César est :
ALEA JACTA EST
qui traduite du latin donne " Les dés sont jetés ».1.2. Des chiffres et des lettresIl est plus facile de manipuler des nombres que des lettres, aussi nous passons à une formulation arithmétique. Nous
associons à chacune des26lettres deAàZun nombre de0à25. En termes mathématiques, nous définissons une
bijection : f:A,B,C,...,Z!0,1,2,...,25 parA7!0B7!1C7!2 ...Z7!25
Ainsi "A L E A" devient "0 11 4 0".
Le chiffrement de César est un cas particulier desubstitution mono-alphabétique, c"est-à-dire un chiffrement lettre à
lettre.Quel est l"intérêt? Nous allons voir que le chiffrement de César correspond à une opération mathématique très simple.
Pour cela, rappelons la notion de congruence et l"ensembleZ=26Z.1.3. Modulo
Soitn>2 un entier fixé.Définition 1.
On dit queaest congru àbmodulon, sindiviseba. On note alors ab(modn). Pour nousn=26. Ce qui fait que282(mod26), car282est bien divisible par26. De même85=326+7 donc 857(mod 26).On noteZ=26Zl"ensemble de tous les éléments deZmodulo26. Cet ensemble peut par exemple être représenté par
les 26 élémentsf0,1,2,...,25g. En effet, puisqu"on compte modulo 26 :0, 1, 2, ..., 25, puis 260, 271, 282,..., 520, 531,...
et de même125,224,...Plus généralementZ=nZcontientnéléments. Pour un entiera2Zquelconque, sonreprésentantdansf0,1,2,...,n
1gs"obtient comme le restekde la division euclidienne deaparn:a=bn+k. De sorte queak(modn)et
06k De façon naturelle l"addition et la multiplication d"entiers se transposent dansZ=nZ. Poura,b2Z=nZ, on associea+b2Z=nZ.
CRYPTOGRAPHIE1. LE CHIFFREMENT DECÉSAR3Par exemple dansZ=26Z,15+13égale2. En effet15+13=282(mod26). Autre exemple : que vaut133+64?
133+64=197=726+1515(mod26). Mais on pourraitprocéderdifféremment : toutd"abord133=526+33
(mod 26)et 64=226+1212(mod 26). Et maintenant sans calculs : 133+643+1215(mod 26). On fait de même pour la multiplication : poura,b2Z=nZ, on associeab2Z=nZ. Par exemple312donne10modulo26, car312=36=126+1010(mod26). De même :327=81= 326+33(mod26). Une autre façon de voir la même opération est d"écrire d"abord27=1(mod26)puis
327313(mod 26).
1.4. Chiffrer et déchiffrer
Le chiffrement de César est simplement une addition dansZ=26Z! Fixons un entierkqui est le décalage (par exemple
k=3dans l"exemple de César ci-dessus) et définissons lafonction de chiffrement de César de décalagekqui va de
l"ensembleZ=26Zdans lui-même :C k:Z=26Z!Z=26Z x7!x+kPar exemple, pourk=3 :C3(0) =3,C3(1) =4... Pour déchiffrer, rien de plus simple! Il suffit d"aller dans l"autre sens, c"est-à-dire ici de soustraire. Lafonction de
déchiffrement de César de décalagekestD k:Z=26Z!Z=26Z x7!xk En effet, si1a été chiffré en4, par la fonctionC3alorsD3(4) =43=1. On retrouve le nombre original.
Mathématiquement,Dkest la bijection réciproque deCk, ce qui implique que pour toutx2Z=26Z:D kCk(x)=x En d"autres termes,sixest un nombre,on applique la fonction de chiffrement pourobtenirle nombre cryptéy=Ck(x);
ensuite la fonction de déchiffrement fait bien ce que l"on attend d"elleDk(y) =x, on retrouve le nombre originalx.Z=26ZZ=26ZC
kD k Une autre façon de voir la fonction de déchiffrement est de remarquer queDk(x) =Ck(x). Par exempleC3(x) =
x+(3)x+23(mod 26). Voici le principe du chiffrement : Alice veut envoyer des messages secrets à Bruno. Ils se sont d"abord mis d"accord sur
une clé secrètek, par exemplek=11. Alice veut envoyer le message "COUCOU" à Bruno. Elle transforme "COUCOU"
en "2 14 20 2 14 20". Elle applique la fonction de chiffrementC11(x) =x+11à chacun des nombres : "13 25 5 13
25 5
" ce qui correspond au mot crypté "NZFNZF". Elle transmet le mot crypté à Bruno, qui selon le même principe
applique la fonction de déchiffrementD11(x) =x11.ALICEBRUNO COUCOU
2 14 20 2 14 2013 25 5 13 25 5NZFNZFCOUCOU
2 14 20 2 14 2013 25 5 13 25 5NZFNZF
C kD k CRYPTOGRAPHIE1. LE CHIFFREMENT DECÉSAR4
Exemple 1.
Un exemple classique est le "rot13" (pour rotation par un décalage de 13) : C 13(x) =x+13et comme1313(mod26)alorsD13(x) =x+13. La fonction de déchiffrement est la même que la fonction de
chiffrement! Exemple : déchiffrez le mot "PRFNE".
Notons ici deux points importants pour la suite : tout d"abord nous avons naturellement considéré un mot comme une
succession de lettres, et chaque opération de chiffrement et déchiffrement s"effectue sur un bloc d"une seule lettre.
Ensuite nous avons vu que chiffrer un message est une opération mathématique (certes sur un ensemble un peu
spécial). 1.5. Espace des clés et attaque
Combien existe-t-il de possibilités de chiffrement par la méthode de César? Il y a26fonctionsCkdifférentes,
k=0,1,...,25. Encore une fois,kappartient àZ=26Z, car par exemple les fonctionsC29etC3sont identiques. Le
décalageks"appelle laclé de chiffrement, c"est l"information nécessaire pour crypter le message. Il y a donc26clés
différentes et l"espace des clésestZ=26Z. Il est clair que ce chiffrement de César est d"une sécurité très faible. Si Alice envoie un message secret à Bruno et que
Chloé intercepte ce message, il sera facile pour Chloé de le décrypter même si elle ne connaît pas la clé secrètek.
L"attaque la plus simple pour Chloé est de tester ce que donne chacune des26combinaisons possibles et de reconnaître
parmi ces combinaisons laquelle donne un message compréhensible. 1.6. Algorithmes
Les ordinateurs ont révolutionné la cryptographie et surtout le décryptage d"un message intercepté. Nous montrons
ici, à l"aide du langagePythoncomment programmer et attaquer le chiffrement de César. Tout d"abord la fonction de
chiffrement se programme en une seule ligne :Code 1(cesar.py (1)). def cesar_chiffre_nb(x,k): return (x+k)%26 Icixest un nombre def0,1,...,25getkest le décalage.(x+k)%26a pour valeur le reste modulo26de la somme
(x+k). Pour le décryptage, c"est aussi simple :Code 2(cesar.py (2)). def cesar_dechiffre_nb(x,k): return (x-k)%26 Pour chiffrer un mot ou une phrase, il n"y a pas de problèmes théoriques, mais seulement des difficultés techniques :
•Un mot ou une phrase est une chaîne de caractères, qui en fait se comporte comme une liste. Simotest une chaîne
alorsmot[0]est la première lettre,mot[1]la deuxième lettre... et la bouclefor␣lettre␣in␣mot:permet de
parcourir chacune des lettres. Pour transformer une lettre en un nombre, on utilise le code Ascii qui à chaque caractère associe un nombre,
ord(A)vaut65,ord(B)vaut66... Ainsi(ord(lettre)␣-␣65)renvoie le rang de la lettre entre0et25comme
nous l"avons fixé dès le départ. La transformation inverse se fait par la fonctionchr:chr(65)renvoie le caractèreA,chr(66)renvoieB...
Pour ajouter une lettre à une liste, faitesmaliste.append(lettre). Enfin pour transformer une liste de
caractères en une chaîne, faites"".join(maliste). Ce qui donne :Code 3(cesar.py (3)).
def cesar_chiffre_mot(mot,k): CRYPTOGRAPHIE2. LE CHIFFREMENT DEVIGENÈRE5␣␣␣␣message_code␣=␣[]␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣#␣Liste␣vide
for lettre in mot: Pour chaque lettre nb ord(lettre)-65 Lettre
devient nb de 0 25
nb_crypte cesar_chiffre_nb(nb,k) Chiffrement
de César
lettre_crypte chr(nb_crypte+65) Retour
aux lettres message_code.append(lettre_crypte) Ajoute
lettre au message message_code "".join(message_code) Revient
chaine caractères return(message_code)Pour l"attaque on parcourt l"intégralité de l"espace des clés :kvarie de0à25. Noter que pour décrypter les messages
on utilise ici simplement la fonction de César avec la clék.Code 4(cesar.py (4)). def cesar_attaque(mot): for k in range(26): print(cesar_chiffre_mot(mot,-k)) return None2. Le chiffrement de Vigenère
2.1. Substitution mono-alphabétique
Principe
Nous avons vu que le chiffrement de César présente une sécurité très faible, la principale raison est que l"espace des
clés est trop petit : il y a seulement26clés possibles, et on peut attaquer un message chiffré en testant toutes les clés
à la main.
Au lieu de faire correspondre circulairement les lettres, on associe maintenant à chaque lettre une autre lettre (sans
ordre fixe ou règle générale). Par exemple :ABCDEFGHIJKLMNOPQRSTUVWXYZ
FQBMXITEPALWHSDOZKVGRCNYJU
Pour crypter le message
ETRE OU NE PAS ETRE TELLE EST LA QUESTION
on regarde la correspondance et on remplace la lettreEpar la lettreX, puis la lettreTpar la lettreG, puis la lettreR
par la lettreK... Le message crypté est alors :
XGKX DR SX OFV XGKX GXWWX XVG WF ZRXVGPDS
Pour le décrypter, en connaissant les substitutions, on fait l"opération inverse. Avantage : nous allons voir que l"espace des clés est gigantesque et qu"il n"est plus question d"énumérer toutes les
possibilités. Inconvénients : la clé à retenir est beaucoup plus longue, puisqu"il faut partager la clé constituée des26lettres
"FQBMX...". Mais surtout, nous allons voir que finalement ce protocole de chiffrement est assez simple à " craquer ».
Espace des clés
Mathématiquement, le choix d"une clé revient au choix d"une bijection de l"ensembleA,B,...,Zvers le même
ensembleA,B,...,Z. Il y a26!choix possibles. En effet pour la lettre A de l"ensemble de départ, il y a26choix
possibles (nous avions choisi F), pour B il reste25choix possibles (tout sauf F qui est déjà choisi), pour C il reste
24choix... enfin pour Z il ne reste qu"une seule possibilité, la seule lettre non encore choisie. Au final il y a :
26252421soit26!choix de clés. Ce qui fait environ41026clés. Il y a plus de clés différentes que
CRYPTOGRAPHIE2. LE CHIFFREMENT DEVIGENÈRE6de grains de sable sur Terre! Si un ordinateur pouvait tester1milliard de clés par seconde, il lui faudrait alors12
milliards d"années pour tout énumérer. Attaque statistique
La principale faiblesse du chiffrement mono-alphabétique est qu"une même lettre est toujours chiffrée de la même
façon. Par exemple, iciEdevientX. Dans les textes longs, les lettres n"apparaissent pas avec la même fréquence. Ces
fréquences varient suivant la langue utilisée. En français, les lettres les plus rencontrées sont dans l"ordre :
E S A I N T R U L O D C P M V Q G F H B X J Y Z K W avec les fréquences (souvent proches et dépendant de l"échantillon utilisé) :ESAINTRULOD Voici la méthode d"attaque : dans le texte crypté, on cherche la lettre qui apparaît le plus, et si le texte est assez
long cela devrait être le chiffrement duE, la lettre qui apparaît ensuite dans l"étude des fréquences devrait être le
chiffrement duS, puis le chiffrement duA... On obtient des morceaux de texte clair sous la forme d"une texte à trous
et il faut ensuite deviner les lettres manquantes. Par exemple, déchiffrons la phrase :
LHLZ HFQ BC HFFPZ WH YOUPFH MUPZH
On compte les apparitions des lettres :
H: 6F: 4P: 3Z: 3
On suppose donc que leHcrypte la lettreE, leFla lettreS, ce qui donne *E**ES* **ESS** *E***SE****E D"après les statistiquesPetZdevraient se décrypter enAetI(ouIetA). Le quatrième mot "HFFPZ", pour l"instant
décrypté en "ESS**", se complète donc en "ESSAI" ou "ESSIA". La première solution semble correcte! AinsiPcrypte
A, etZcrypteI. La phrase est maintenant :
*E*IES * **ESSAI*E***ASE**AIE En réfléchissant un petit peu, on décrypte le message : CECI EST UN ESSAI DE PHRASE VRAIE
2.2. Le chiffrement de Vigenère
Blocs L"espace des clés du chiffrement mono-alphabétique est immense, mais le fait qu"une lettre soit toujours cryptée de la
même façon représente une trop grande faiblesse. Le chiffrement de Vigenère remédie à ce problème. On regroupe les
lettres de notre texte par blocs, par exemple ici par blocs de longueur 4 : CETTE PHRASE NE VEUT RIEN DIRE
devient CETT EPHR ASEN EVEU TRIE NDIR E
(les espaces sont purement indicatifs, dans la première phrase ils séparent les mots, dans la seconde ils séparent les
blocs). Sikest la longueurd"un bloc,alors on choisit une clé constituée deknombres de0à25:(n1,n2,...,nk). Le chiffrement
consiste à effectuer un chiffrement de César, dont le décalage dépend du rang de la lettre dans le bloc :
un décalage den1pour la première lettre de chaque bloc, un décalage den2pour la deuxième lettre de chaque bloc, un décalage denkpour lak-ème et dernière lettre de chaque bloc. Pour notre exemple, si on choisit comme clé(3,1,5,2)alors pour le premier bloc "CETT" : un décalage de 3 pourCdonneF,quotesdbs_dbs46.pdfusesText_46
Poura,b2Z=nZ, on associea+b2Z=nZ.
CRYPTOGRAPHIE1. LE CHIFFREMENT DECÉSAR3Par exemple dansZ=26Z,15+13égale2. En effet15+13=282(mod26). Autre exemple : que vaut133+64?
133+64=197=726+1515(mod26). Mais on pourraitprocéderdifféremment : toutd"abord133=526+33
(mod 26)et 64=226+1212(mod 26). Et maintenant sans calculs : 133+643+1215(mod 26). On fait de même pour la multiplication : poura,b2Z=nZ, on associeab2Z=nZ. Par exemple312donne10modulo26, car312=36=126+1010(mod26). De même :327=81=326+33(mod26). Une autre façon de voir la même opération est d"écrire d"abord27=1(mod26)puis
327313(mod 26).
1.4. Chiffrer et déchiffrer
Le chiffrement de César est simplement une addition dansZ=26Z! Fixons un entierkqui est le décalage (par exemple
k=3dans l"exemple de César ci-dessus) et définissons lafonction de chiffrement de César de décalagekqui va de
l"ensembleZ=26Zdans lui-même :C k:Z=26Z!Z=26Z x7!x+kPar exemple, pourk=3 :C3(0) =3,C3(1) =4...Pour déchiffrer, rien de plus simple! Il suffit d"aller dans l"autre sens, c"est-à-dire ici de soustraire. Lafonction de
déchiffrement de César de décalagekestD k:Z=26Z!Z=26Z x7!xkEn effet, si1a été chiffré en4, par la fonctionC3alorsD3(4) =43=1. On retrouve le nombre original.
Mathématiquement,Dkest la bijection réciproque deCk, ce qui implique que pour toutx2Z=26Z:D kCk(x)=xEn d"autres termes,sixest un nombre,on applique la fonction de chiffrement pourobtenirle nombre cryptéy=Ck(x);
ensuite la fonction de déchiffrement fait bien ce que l"on attend d"elleDk(y) =x, on retrouve le nombre originalx.Z=26ZZ=26ZC
kD kUne autre façon de voir la fonction de déchiffrement est de remarquer queDk(x) =Ck(x). Par exempleC3(x) =
x+(3)x+23(mod 26).Voici le principe du chiffrement : Alice veut envoyer des messages secrets à Bruno. Ils se sont d"abord mis d"accord sur
une clé secrètek, par exemplek=11. Alice veut envoyer le message "COUCOU" à Bruno. Elle transforme "COUCOU"
en "2 14 20 2 14 20". Elle applique la fonction de chiffrementC11(x) =x+11à chacun des nombres : "13 25 5 13
25 5" ce qui correspond au mot crypté "NZFNZF". Elle transmet le mot crypté à Bruno, qui selon le même principe
applique la fonction de déchiffrementD11(x) =x11.ALICEBRUNOCOUCOU
2 14 20 2 14 2013 25 5 13 25 5NZFNZFCOUCOU
2 14 20 2 14 2013 25 5 13 25 5NZFNZF
C kD kCRYPTOGRAPHIE1. LE CHIFFREMENT DECÉSAR4
Exemple 1.
Un exemple classique est le "rot13" (pour rotation par un décalage de 13) : C13(x) =x+13et comme1313(mod26)alorsD13(x) =x+13. La fonction de déchiffrement est la même que la fonction de
chiffrement!Exemple : déchiffrez le mot "PRFNE".
Notons ici deux points importants pour la suite : tout d"abord nous avons naturellement considéré un mot comme une
succession de lettres, et chaque opération de chiffrement et déchiffrement s"effectue sur un bloc d"une seule lettre.
Ensuite nous avons vu que chiffrer un message est une opération mathématique (certes sur un ensemble un peu
spécial).1.5. Espace des clés et attaque
Combien existe-t-il de possibilités de chiffrement par la méthode de César? Il y a26fonctionsCkdifférentes,
k=0,1,...,25. Encore une fois,kappartient àZ=26Z, car par exemple les fonctionsC29etC3sont identiques. Le
décalageks"appelle laclé de chiffrement, c"est l"information nécessaire pour crypter le message. Il y a donc26clés
différentes et l"espace des clésestZ=26Z.Il est clair que ce chiffrement de César est d"une sécurité très faible. Si Alice envoie un message secret à Bruno et que
Chloé intercepte ce message, il sera facile pour Chloé de le décrypter même si elle ne connaît pas la clé secrètek.
L"attaque la plus simple pour Chloé est de tester ce que donne chacune des26combinaisons possibles et de reconnaître
parmi ces combinaisons laquelle donne un message compréhensible.1.6. Algorithmes
Les ordinateurs ont révolutionné la cryptographie et surtout le décryptage d"un message intercepté. Nous montrons
ici, à l"aide du langagePythoncomment programmer et attaquer le chiffrement de César. Tout d"abord la fonction de
chiffrement se programme en une seule ligne :Code 1(cesar.py (1)). def cesar_chiffre_nb(x,k): return (x+k)%26Icixest un nombre def0,1,...,25getkest le décalage.(x+k)%26a pour valeur le reste modulo26de la somme
(x+k). Pour le décryptage, c"est aussi simple :Code 2(cesar.py (2)). def cesar_dechiffre_nb(x,k): return (x-k)%26Pour chiffrer un mot ou une phrase, il n"y a pas de problèmes théoriques, mais seulement des difficultés techniques :
•Un mot ou une phrase est une chaîne de caractères, qui en fait se comporte comme une liste. Simotest une chaîne
alorsmot[0]est la première lettre,mot[1]la deuxième lettre... et la bouclefor␣lettre␣in␣mot:permet de
parcourir chacune des lettres.Pour transformer une lettre en un nombre, on utilise le code Ascii qui à chaque caractère associe un nombre,
ord(A)vaut65,ord(B)vaut66... Ainsi(ord(lettre)␣-␣65)renvoie le rang de la lettre entre0et25comme
nous l"avons fixé dès le départ.La transformation inverse se fait par la fonctionchr:chr(65)renvoie le caractèreA,chr(66)renvoieB...
Pour ajouter une lettre à une liste, faitesmaliste.append(lettre). Enfin pour transformer une liste de
caractères en une chaîne, faites"".join(maliste).Ce qui donne :Code 3(cesar.py (3)).
def cesar_chiffre_mot(mot,k):CRYPTOGRAPHIE2. LE CHIFFREMENT DEVIGENÈRE5␣␣␣␣message_code␣=␣[]␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣#␣Liste␣vide
for lettre in mot: Pour chaque lettre nb ord(lettre)-65Lettre
devient nb de 0 25nb_crypte cesar_chiffre_nb(nb,k)
Chiffrement
deCésar
lettre_crypte chr(nb_crypte+65)Retour
aux lettres message_code.append(lettre_crypte)Ajoute
lettre au message message_code "".join(message_code)Revient
chaine caractèresreturn(message_code)Pour l"attaque on parcourt l"intégralité de l"espace des clés :kvarie de0à25. Noter que pour décrypter les messages
on utilise ici simplement la fonction de César avec la clék.Code 4(cesar.py (4)). def cesar_attaque(mot): for k in range(26): print(cesar_chiffre_mot(mot,-k)) returnNone2. Le chiffrement de Vigenère
2.1. Substitution mono-alphabétique
Principe
Nous avons vu que le chiffrement de César présente une sécurité très faible, la principale raison est que l"espace des
clés est trop petit : il y a seulement26clés possibles, et on peut attaquer un message chiffré en testant toutes les clés
à la main.
Au lieu de faire correspondre circulairement les lettres, on associe maintenant à chaque lettre une autre lettre (sans
ordre fixe ou règle générale).Par exemple :ABCDEFGHIJKLMNOPQRSTUVWXYZ
FQBMXITEPALWHSDOZKVGRCNYJU
Pour crypter le message
ETRE OU NE PAS ETRE TELLE EST LA QUESTION
on regarde la correspondance et on remplace la lettreEpar la lettreX, puis la lettreTpar la lettreG, puis la lettreR
par la lettreK...Le message crypté est alors :
XGKX DR SX OFV XGKX GXWWX XVG WF ZRXVGPDS
Pour le décrypter, en connaissant les substitutions, on fait l"opération inverse.Avantage : nous allons voir que l"espace des clés est gigantesque et qu"il n"est plus question d"énumérer toutes les
possibilités.Inconvénients : la clé à retenir est beaucoup plus longue, puisqu"il faut partager la clé constituée des26lettres
"FQBMX...". Mais surtout, nous allons voir que finalement ce protocole de chiffrement est assez simple à " craquer ».
Espace des clés
Mathématiquement, le choix d"une clé revient au choix d"une bijection de l"ensembleA,B,...,Zvers le même
ensembleA,B,...,Z. Il y a26!choix possibles. En effet pour la lettre A de l"ensemble de départ, il y a26choix
possibles (nous avions choisi F), pour B il reste25choix possibles (tout sauf F qui est déjà choisi), pour C il reste
24choix... enfin pour Z il ne reste qu"une seule possibilité, la seule lettre non encore choisie. Au final il y a :
26252421soit26!choix de clés. Ce qui fait environ41026clés. Il y a plus de clés différentes que
CRYPTOGRAPHIE2. LE CHIFFREMENT DEVIGENÈRE6de grains de sable sur Terre! Si un ordinateur pouvait tester1milliard de clés par seconde, il lui faudrait alors12
milliards d"années pour tout énumérer.Attaque statistique
La principale faiblesse du chiffrement mono-alphabétique est qu"une même lettre est toujours chiffrée de la même
façon. Par exemple, iciEdevientX. Dans les textes longs, les lettres n"apparaissent pas avec la même fréquence. Ces
fréquences varient suivant la langue utilisée. En français, les lettres les plus rencontrées sont dans l"ordre :
E S A I N T R U L O D C P M V Q G F H B X J Y Z K W avec les fréquences (souvent proches et dépendant de l"échantillon utilisé) :ESAINTRULODVoici la méthode d"attaque : dans le texte crypté, on cherche la lettre qui apparaît le plus, et si le texte est assez
long cela devrait être le chiffrement duE, la lettre qui apparaît ensuite dans l"étude des fréquences devrait être le
chiffrement duS, puis le chiffrement duA... On obtient des morceaux de texte clair sous la forme d"une texte à trous
et il faut ensuite deviner les lettres manquantes.Par exemple, déchiffrons la phrase :
LHLZ HFQ BC HFFPZ WH YOUPFH MUPZH
On compte les apparitions des lettres :
H: 6F: 4P: 3Z: 3
On suppose donc que leHcrypte la lettreE, leFla lettreS, ce qui donne *E**ES* **ESS** *E***SE****ED"après les statistiquesPetZdevraient se décrypter enAetI(ouIetA). Le quatrième mot "HFFPZ", pour l"instant
décrypté en "ESS**", se complète donc en "ESSAI" ou "ESSIA". La première solution semble correcte! AinsiPcrypte
A, etZcrypteI. La phrase est maintenant :
*E*IES * **ESSAI*E***ASE**AIE En réfléchissant un petit peu, on décrypte le message :CECI EST UN ESSAI DE PHRASE VRAIE
2.2. Le chiffrement de Vigenère
BlocsL"espace des clés du chiffrement mono-alphabétique est immense, mais le fait qu"une lettre soit toujours cryptée de la
même façon représente une trop grande faiblesse. Le chiffrement de Vigenère remédie à ce problème. On regroupe les
lettres de notre texte par blocs, par exemple ici par blocs de longueur 4 :CETTE PHRASE NE VEUT RIEN DIRE
devientCETT EPHR ASEN EVEU TRIE NDIR E
(les espaces sont purement indicatifs, dans la première phrase ils séparent les mots, dans la seconde ils séparent les
blocs).Sikest la longueurd"un bloc,alors on choisit une clé constituée deknombres de0à25:(n1,n2,...,nk). Le chiffrement
consiste à effectuer un chiffrement de César, dont le décalage dépend du rang de la lettre dans le bloc :
un décalage den1pour la première lettre de chaque bloc, un décalage den2pour la deuxième lettre de chaque bloc, un décalage denkpour lak-ème et dernière lettre de chaque bloc. Pour notre exemple, si on choisit comme clé(3,1,5,2)alors pour le premier bloc "CETT" : un décalage de 3 pourCdonneF,quotesdbs_dbs46.pdfusesText_46[PDF] algorithme simulation lancer de dé PDF Cours,Exercices ,Examens
[PDF] algorithme somme des carrés des n premiers entiers PDF Cours,Exercices ,Examens
[PDF] algorithme somme des n premiers entiers PDF Cours,Exercices ,Examens
[PDF] algorithme somme des termes d'une suite PDF Cours,Exercices ,Examens
[PDF] algorithme somme suite PDF Cours,Exercices ,Examens
[PDF] algorithme somme suite arithmétique PDF Cours,Exercices ,Examens
[PDF] algorithme somme suite géométrique PDF Cours,Exercices ,Examens
[PDF] algorithme suite 1es PDF Cours,Exercices ,Examens
[PDF] Algorithme suite algo 1ère Mathématiques
[PDF] algorithme suite algobox PDF Cours,Exercices ,Examens
[PDF] algorithme suite arithmétique PDF Cours,Exercices ,Examens
[PDF] algorithme suite casio PDF Cours,Exercices ,Examens
[PDF] algorithme suite casio graph 35+ PDF Cours,Exercices ,Examens
[PDF] Algorithme suite et limites Terminale Mathématiques
