A Method for Obtaining Digital Signatures and Public-Key
A Method for Obtaining Digital Signatures and Public-Key Cryptosystems R L Rivest, A Shamir, and L Adleman Abstract An encryption method is presented with the novel property that publicly re-
TD 2 : Le cryptosyst eme RSA 1 Example de protocole RSA
TD 2 : Le cryptosyst eme RSA 1 Example de protocole RSA 1 1 G en eration des cl es Alice choisit : deux entiers premiers p et q et fait leur produit n = pq un entier e premier avec ’(n) = (p 1)(q 1) Alice calcule : la cl e d de d echi rage (c’est sa clef priv ee) qui doit satisfaire l’ equation de = 1 (mod ’(n))
Mathématiques - Le chiffrement RSA
Chiffrement RSA3 - Le cryptage RSA H Schyns3 1 3 Le cryptage RSA 3 1 Principe Le cryptage RSA repose sur le choix d'un couple de deux nombres premiers généralement appelés [ p ] et [ q ] que l'on doit absolument garder secrets Les nombres premiers choisis doivent être les plus grands possible afin de
A FULLY HOMOMORPHIC ENCRYPTION SCHEME A DISSERTATION
Rivest, Adleman and Dertouzous [120] shortly after the invention of RSA by Rivest, Shamir, and Adleman [121] Basic RSA is a multiplicatively homomorphic encryption scheme { i e , given RSA public key pk = (N;e) and ciphertexts fˆi ˆ e i mod Ng, one can e–ciently compute Q i ˆi = (Q i i) e mod N, a ciphertext that encrypts the
Cryptographie
4 Exemple d'algorithme à clés publiques Cryptage RSA 4 1 Généralités L'algorithme R S A (du nom des trois auteurs RIVEST, SHAMIR, ADLEMEN) est un exemple d'algorithme à clés publiques utilisé par les services secrets On choisit deux nombres premiers distincts « très grands »p etq et on considère le nombreN=pq
S5 - Cryptographie - arnoldonomie
Cryptage RSA Cryptage RSA Le système RSA a été inventé par les informaticiens et mathématiciens Rivest, Shamir et Adelman en 1978 Le principe est le suivant : • Si Colbert veut utiliser ce système, il doit d’abord s’inscrire dans un annuaire Il commence par choisir
Un exemple de chiffrement à clé publique: le codage
connu est le système RSA utilisé aujourd'hui dans une multitude d'applications, notamment les transactions sécurisées via internet L'objectif de cette activité est la mise en œuvre d'un chiffrement à clé publique 1ère partie : un peu de math pour commencer
Algorithmes de chiffrement symétrique par bloc (DES et AES)
• RC6 (RSA Labs) • Twofish (USA) 43 AES • Le 2 octobre 2000, l’algorithme belge Rijndael est retenu par le NIST • FIPS 197 • Taille de bloc de 128 bits
1 Le chiffrement de César - Exo7
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
[PDF] chiffrement asymétrique et symétrique
[PDF] chiffrement asymétrique exemple
[PDF] cryptographie exercices corrigés pdf
[PDF] les nombres en lettres pdf
[PDF] les nombres en lettres de 0 ? 1000
[PDF] ap seconde chiffres significatifs
[PDF] chiffres significatifs excel
[PDF] les chiffres significatifs cours
[PDF] chiffres significatifs sinus
[PDF] precision d une mesure et chiffres significatifs
[PDF] chiffres significatifs exacts
[PDF] chiffres significatifs exos
[PDF] exercices chiffres significatifs 2nde
[PDF] les nombres cardinaux en anglais pdf
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, un décalage de 1 pourEdonneF, un décalage de 5 pour le premierTdonneY, un décalage de 2 pour le deuxièmeTdonneV. Ainsi "CETT" de vient "FFYV". Vous remarquez que les deux lettresTne sont pas cryptées par la même lettre et que
les deuxFne cryptent pas la même lettre. On continue ensuite avec le deuxième bloc... CRYPTOGRAPHIE2. LE CHIFFREMENT DEVIGENÈRE7
MathématiquesL"élément de base n"est plus une lettre mais unbloc, c"est-à-dire un regroupement de lettres. La fonction de chiffrement
associe à un bloc de longueurk, un autre bloc de longueurk, ce qui donne en mathématisant les choses :C
(x1,x2,...,xk)7!(x1+n1,x2+n2,...,xk+nk) Chacune des composantes de cette fonction est un chiffrement de César. La fonction de déchiffrement est juste
Cn1,n2,...,nk.
Espace des clés et attaque
Il y a26kchoix possibles de clés, lorsque les blocs sont de longueurk. Pour des blocs de longueurk=4cela en donne
déjà456 976, et même si un ordinateur teste toutes les combinaisons possibles sans problème, il n"est pas aisé de
parcourir cette liste pour trouver le message en clair, c"est-à-dire celui qui est compréhensible!
Il persiste tout de même une faiblesse du même ordre que celle rencontrée dans le chiffrement mono-alphabétique :
la lettreAn"est pas toujours cryptée par la même lettre, mais si deux lettresAsont situées à la même position dans
deux blocs différents (comme par exemple "ALPH ABET") alors elles seront cryptées par la même lettre.
Une attaque possible est donc la suivante : on découpe notre message en plusieurs listes, les premières lettres de
chaque bloc, les deuxièmes lettres de chaque bloc... et on fait une attaque statistique sur chacun de ces regroupements.
Ce type d"attaque n"est possible que si la taille des blocs est petite devant la longueur du texte. 2.3. Algorithmes
Voici un petit algorithme qui calcule la fréquence de chaque lettre d"une phrase.Code 5(statistiques.py).
def statistiques(phrase): liste_stat [0 for x in range(26)] Une liste avec des 0 for lettre in phrase: On parcourt la phrase i ord(lettre)-65 if 0 i 26:
Si c"est␣une␣vraie␣lettre liste_stat[i] liste_stat[i] 1 return(liste_stat)Et voici le chiffrement de Vigenère. Code 6(vigenere.py).
def vigenere(mot,cle): Clé
est du type n_1 n_k message_code k len(cle) Longueur
de la clé i 0 Rang dans le bloc for lettre in mot: Pour chaque lettre nomb ord(lettre)-65 Lettre
devient nb de 0 25
nomb_code (nomb+cle[i]) 26
Vigenère
on ajoute n_i lettre_code chr(nomb_code+65) On repasse aux lettres i=(i+1) k On passe au rang suivant message_code.append(lettre_code) Ajoute
lettre au message message_code "".join(message_code) Revient
chaine caractères return(message_code) CRYPTOGRAPHIE3. LA MACHINEENIGMA ET LES CLÉS SECRÈTES8 3. La machine Enigma et les clés secrètes
3.1. Un secret parfaitL"inconvénient des chiffrements précédents est qu"une même lettre est régulièrement chiffrée de la même façon, car
la correspondance d"un alphabet à un ou plusieurs autres est fixée une fois pour toutes, ce qui fait qu"une attaque
statistique est toujours possible. Nous allons voir qu"en changeant la correspondance à chaque lettre, il est possible de
créer un chiffrement parfait! Expliquons d"abord le principe à l"aide d"une analogie : j"ai choisi deux entiersmetctels quem+c=100. Que vaut
m? C"est bien sûr impossible de répondre car il y a plusieurs possibilités :0+100,1+99,2+98,... Par contre, si je
vous donne aussicalors vous trouvezmimmédiatementm=100c. Voici le principe du chiffrement : Alice veut envoyer à Bruno le message secretMsuivant : ATTAQUE LE CHATEAU
Alice a d"abord choisi une clé secrèteCqu"elle a transmise à Bruno. Cette clé secrète est de la même longueur que le
message (les espaces ne comptent pas) et composée d"entiers de 0 à 25, tirés au hasard. Par exempleC:
[4, 18, 2, 0, 21, 12, 18, 13, 7, 11, 23, 22, 19, 2, 16, 9] Elle crypte la première lettre par un décalage de César donné par le premier entier :Aest décalé de4lettres et devient
doncE. La seconde lettre est décalée du second entier : le premierTdevientL. Le secondTest lui décalé de2lettres, il
devientV. LeAsuivant est décalé de0lettre, il resteA... Alice obtient un message chiffréXqu"elle transmet à Bruno :
ELVALGW YL NEWMGQD
Pour le décrypter, Bruno, qui connaît la clé, n"a qu"à faire le décalage dans l"autre sens.
Notez que deux lettres identiques (par exemples lesT) n"ont aucune raison d"être cryptées de la même façon. Par
exemple, lesTdu message initial sont cryptés dans l"ordre par unL, unVet unM. Formalisons un peu cette opération. On identifieAavec0,Bavec1, ...,Zavec25. Alors le message cryptéXest juste
la "somme" du messageMavec la clé secrèteC, la somme s"effectuant lettre à lettre, terme à terme, modulo 26.
Notons cette opérationMC=X.
A T T A Q U E L E C H A T E A U 0 19 19 0 16 20 4 11 4 2 7 0 19 4 0 20 4 18 2 0 21
12 18 13 7 11 23
22
19 2 16 9 =411 21 0 11 6 22 24 11 13 4 22 12 6 16 3
E L V A L G W Y L Nquotesdbs_dbs29.pdfusesText_35
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, un décalage de 1 pourEdonneF, un décalage de 5 pour le premierTdonneY, un décalage de 2 pour le deuxièmeTdonneV.Ainsi "CETT" de vient "FFYV". Vous remarquez que les deux lettresTne sont pas cryptées par la même lettre et que
les deuxFne cryptent pas la même lettre. On continue ensuite avec le deuxième bloc...CRYPTOGRAPHIE2. LE CHIFFREMENT DEVIGENÈRE7
MathématiquesL"élément de base n"est plus une lettre mais unbloc, c"est-à-dire un regroupement de lettres. La fonction de chiffrement
associe à un bloc de longueurk, un autre bloc de longueurk, ce qui donne en mathématisant les choses :C
(x1,x2,...,xk)7!(x1+n1,x2+n2,...,xk+nk)Chacune des composantes de cette fonction est un chiffrement de César. La fonction de déchiffrement est juste
Cn1,n2,...,nk.
Espace des clés et attaque
Il y a26kchoix possibles de clés, lorsque les blocs sont de longueurk. Pour des blocs de longueurk=4cela en donne
déjà456 976, et même si un ordinateur teste toutes les combinaisons possibles sans problème, il n"est pas aisé de
parcourir cette liste pour trouver le message en clair, c"est-à-dire celui qui est compréhensible!
Il persiste tout de même une faiblesse du même ordre que celle rencontrée dans le chiffrement mono-alphabétique :
la lettreAn"est pas toujours cryptée par la même lettre, mais si deux lettresAsont situées à la même position dans
deux blocs différents (comme par exemple "ALPH ABET") alors elles seront cryptées par la même lettre.
Une attaque possible est donc la suivante : on découpe notre message en plusieurs listes, les premières lettres de
chaque bloc, les deuxièmes lettres de chaque bloc... et on fait une attaque statistique sur chacun de ces regroupements.
Ce type d"attaque n"est possible que si la taille des blocs est petite devant la longueur du texte.2.3. Algorithmes
Voici un petit algorithme qui calcule la fréquence de chaque lettre d"une phrase.Code 5(statistiques.py).
def statistiques(phrase): liste_stat [0 for x in range(26)] Une liste avec des 0 for lettre in phrase: On parcourt la phrase i ord(lettre)-65 if 0 i 26:Si c"est␣une␣vraie␣lettre liste_stat[i] liste_stat[i] 1 return(liste_stat)Et voici le chiffrement de Vigenère.
Code 6(vigenere.py).
def vigenere(mot,cle):Clé
est du type n_1 n_k message_code k len(cle)Longueur
de la clé i 0 Rang dans le bloc for lettre in mot: Pour chaque lettre nomb ord(lettre)-65Lettre
devient nb de 0 25nomb_code (nomb+cle[i]) 26
Vigenère
on ajoute n_i lettre_code chr(nomb_code+65) On repasse aux lettres i=(i+1) k On passe au rang suivant message_code.append(lettre_code)Ajoute
lettre au message message_code "".join(message_code)Revient
chaine caractères return(message_code) CRYPTOGRAPHIE3. LA MACHINEENIGMA ET LES CLÉS SECRÈTES83. La machine Enigma et les clés secrètes
3.1. Un secret parfaitL"inconvénient des chiffrements précédents est qu"une même lettre est régulièrement chiffrée de la même façon, car
la correspondance d"un alphabet à un ou plusieurs autres est fixée une fois pour toutes, ce qui fait qu"une attaque
statistique est toujours possible. Nous allons voir qu"en changeant la correspondance à chaque lettre, il est possible de
créer un chiffrement parfait!Expliquons d"abord le principe à l"aide d"une analogie : j"ai choisi deux entiersmetctels quem+c=100. Que vaut
m? C"est bien sûr impossible de répondre car il y a plusieurs possibilités :0+100,1+99,2+98,... Par contre, si je
vous donne aussicalors vous trouvezmimmédiatementm=100c. Voici le principe du chiffrement : Alice veut envoyer à Bruno le message secretMsuivant :ATTAQUE LE CHATEAU
Alice a d"abord choisi une clé secrèteCqu"elle a transmise à Bruno. Cette clé secrète est de la même longueur que le
message (les espaces ne comptent pas) et composée d"entiers de 0 à 25, tirés au hasard. Par exempleC:
[4, 18, 2, 0, 21, 12, 18, 13, 7, 11, 23, 22, 19, 2, 16, 9]Elle crypte la première lettre par un décalage de César donné par le premier entier :Aest décalé de4lettres et devient
doncE. La seconde lettre est décalée du second entier : le premierTdevientL. Le secondTest lui décalé de2lettres, il
devientV. LeAsuivant est décalé de0lettre, il resteA... Alice obtient un message chiffréXqu"elle transmet à Bruno :
ELVALGW YL NEWMGQD
Pour le décrypter, Bruno, qui connaît la clé, n"a qu"à faire le décalage dans l"autre sens.
Notez que deux lettres identiques (par exemples lesT) n"ont aucune raison d"être cryptées de la même façon. Par
exemple, lesTdu message initial sont cryptés dans l"ordre par unL, unVet unM.Formalisons un peu cette opération. On identifieAavec0,Bavec1, ...,Zavec25. Alors le message cryptéXest juste
la "somme" du messageMavec la clé secrèteC, la somme s"effectuant lettre à lettre, terme à terme, modulo 26.
Notons cette opérationMC=X.
A T T A Q U E L E C H A T E A U 0 19 19 0 16 20 4 11 4 2 7 0 19 4 0 20 4 18 2 0 2112 18 13 7 11 23
22
19 2 16