PLAYMENDROIT

LA CRYPTOLOGIE

Lire : http://www-rocq.inria.fr/codes/Anne.Canteaut/crypto_moderne.pdf

 

Il faut distinguer cryptographie, cryptologie et cryptanalyse 

1° LA CRYPTOLOGIE

Elle comprend : 

• La cryptographie : ‘secret writing’ : chiffrement ou cryptage de messages en clair et le déchiffrement ou décryptage de messages codés, connaissant la clef. Algorithme codage/décodage avec la clef.

•  La cryptanalyse : ‘code breaking’ : art de décrypter des messages codés sans connaître la clé.

Si on trouve la clef on trouve le reste… comme une porte !

Décrypter le message :
E (m) = c, D(c) = m

Avec : C = code 
M = message
E = encodage 
D = décodage

2° LA CRYPTOGRAPHIE

Un système cryptographie ou cryptosystème est composé d’un algorithme de cryptage (chiffrement) et d’un algorithme de décryptage (déchiffrement).

·        Types de cryptosystèmes :

·          Système à usage restreint : les algorithmes de chiffrement et de déchiffrement  sont secrets. La sécurité repose sur la confidentialité.

·          Système à usage général (DES : Data encryption standard – algorithme le plus utilisé aux USA) : la confidentialité ne repose pas sur l’algorithme mais sur la clé. Tout le monde peut utiliser le système

Les cryptosystèmes modernes sont des systèmes à clé :

Ek(m) = c, Dk’(c)
Les clefs K et K’ ne sont pas forcément identiques.

·        Deux classes d’algorithmes :

·          Algorithmes à clé secrète ou algorithmes symétriques.

·          Algorithmes à clé publique.

Il existe un système sans clé et avec un message derrière chaque caractère : l’écriture.

·          Algorithmes à clef secrète : La clé de décryptage se calcule (simplement)  à partir de la clé de cryptage et vice-versa ; équivaut à une même clé. Il existe une corrélation mathématique entre la clé de cryptage et celle de décryptage.

Deux catégories :

§         Stream ciphers : travaillent bit à bit ou octet par octet. Ex. : XOR, time pad. (xor calcule sur des bits : raisonnement logique « ou exclusif » : l’un exclut l’autre : Vrai->1, Faux->0 (0 0 donne 0 ; 1 1 donne 0, 1 0 donne 1, 0 1 donne 1)

§         Block ciphers : travaillent sur des groupes de bits (par ex. 64 bits, DES).

·          Algorithmes à clé publique : La clé de cryptage est publique, la clé de décryptage est secrète et non calculable en temps raisonnable.

·        Objectifs :

·          Confidentialité : le message crypté doit rester secret, ne peut être déchiffrer par un tiers.

·          Authentification : assurance de l’authenticité, notamment de l’expéditeur ou de l’origine.

·          Intégrité : assurance que le message n’a pas été modifié durant la transmission. (Entre deux ordinateurs : ‘communication’, Dans un ordinateur : ‘informatique’).

·          Non-répudiation : l’expéditeur ne peut nier, ultérieurement, avoir envoyé le message.

·        Techniques :

·          Signature : Signature : moyen d’associer l’expéditeur à un message

·          Certificat : attestation qui corrobore (confirme) une affirmation

·          Tiers de confiance : c’est lui qui délivre les certificats.

·          Estampillage : apposition de dates ou autres signes assurant l’unicité du message.

3° LA CRYPTANALYSE :

C’est une logique militaire : espionnage/contre-espionnage. La cryptanalyse est la science du décryptage sans connaissance de la clé. Une tentative d’analyse est une attaque. Une attaque n’est pas générale, mais exploite des situations particulières.

·        Attaque à texte chiffré :

L’analyse dispose de textes chiffrés c1, …., cn.

Il doit retrouver la clef pour trouver le message.

·        Attaque à texte connu :

L’analyste dispose de textes en clair  m1, …., mn et l’autre chiffrement c1, …, cn.

Il manque la clef.

·        Attaque à texte clair choisi :

L’analyste peut choisir les textes

M1,…,mn

Et obtenir c1,…,cn

Un cas particulier , l’analyste peut choisir mi en fonction de m1,…., m(n-1) et c1,….,c(i-1). C’est le cas des systèmes à clés publiques. i-1 : étape –1

·        Attaque biaisée :

L’analyste achète la clé, ou force quelqu’un à la lui fournir. C’est souvent l’attaque la plus efficace.

4° LA SECURITE :

La sécurité mesure la difficulté de casser l’algorithme. Mais cette mesure est relative.

·        Un algorithme est sûr :

si le coût pour casser l’algorithme est supérieur au temps est supérieur à la valeur des données cryptées ;

+

si le temps nécessaire pour casser l’algorithme est supérieur au temps pendant lequel le message doit rester secret.

·        Un algorithme est inconditionnellement sûr :

si le cryptanalyste ne peut trouver le texte en clair, quel que soit la quantité de messages chiffrés dont il dispose.

·        Un algorithme algorithmiquement sûr :

s’il ne peut être cassé par les ressources disponibles (vague) (cf : défis RSA).
Remarque, la complexité d’une attaque est mesurée par la place et le temps requis. Rappel : Clefs de 512 bits = 2 exposant 512 (2 car binaire (0/1)). Mémoire impossible pour un ordinateur actuel.

Exemples :

·        Mesure de la sécurité d’un algorithme

Complexité en temps : 2 exposant 128 = 10 exposant opérations.

Moyens : un million de stations travaillant à un milliard d’opération par secondes.

Temps requis : avec 10 exposant 15 opérations par secondes, il faut 10 exposant 25 secondes, cad de l’ordre d’un milliard de milliard d’années !!!

·        Sténographie

Le message à transmettre est caché à l’intérieur d’un texte beaucoup plus grand.

·        Exemples historiques :

L’encre invisible, petits points sur des caractères particuliers, grille masquant des portions du texte.

·        Exemples plus récents :

Les tatouages: on cache un message dans un image graphique en modifiant le dernier bit de la couleur de chaque pixel. Une version plus efficace est le waterlarking, qui estampille (en principe invisible) ajouté à une image et qui en certifie l’origine (donc le copyright).

·        Transposition :

Une transposition ou anagramme du texte

T = a1… an
Est le texte
A t(1) …. At(n)
Où t est la permutation de {1,….,n}
La transposition de permutation t-1 redonne le texte original.

5. LES DIFFERENTES METHODES :

Pour crypter :
K -> T (permutation)
1 donne 3
2 donne 1
3 donne 2
 

Donc pour décrypter :
K’-> T-1 (permutation inverse)
1 donne 2
2 donne 3
3 donne 1
 

La clé de codage K est différente de la clé de décodage K’.

·          La Technique de César : cryptage par décalage

K : Permutation en décalant de 3 lettres :
Z devient b,
A devient c…
26 ! = 26*25*24*…*2*1

Factoriel de 26 possibilités pour découvrir tout cela (manque de temps, de matériel pour tout tester)
Tous les moyens sont bons pour transmettre la clé !

 

La substitution :
C’est une permutation sigma de l’alphabet. Une substitution doit augmenter la ‘confusion’ d’un texte.

Les textes :
M = a1….an
Donne
C= sigma (a1) …..sigma(an)

La substitution de permutation sigma puissance –1 redonne le texte original.

Exemple :

·          code de César :
Sigma(a) = a + 1mod26     IBM->HAL
rot13 : sigma(a)=a+13mod26

·          Code Vigénère :

On choisit un clé k = k1….kp.
On répète la clé jusqu’à obtenir la longueur du message du message m = a1…an.
Le message crypté est :
Ci =ki + ai mod26

Ou encore
C =k + m mod26
Le décodage est par soustraction

Exemple :
Clé : k = (2,4,5)
IBM :
I devient K (I + 2 caractères),
B devient F (B + 4 caractères),
M devient . (M et décalage de 5 caractères)

·          Xor simple « ou exclusif » 

Clef secrète codage/décodage est la même. C’est un algorithme de codage utilisé dans de nombreux logiciels commerciaux et autorisé par la NSA pour l’industrie des téléphones cellulaires aux Etats unis.

La clé est un chaîne de caractères k et le codage est
M xor k = c
Le décodage
C xor k = m

Ce système n’est pas sûr! 
Attention avec les échanges commerciaux aux USA.

·          One time pad ou à masque jetable :

Ex. : carte téléphonique prépayée.
Données :
·          le message  m  à crypter
·          n masque ou pad est tiré au hasard et de même longueur que m

Cryptage :
Par addition modulo 26 ou xor

Décryptage : le destinataire possède une copie du masque et fait l’opération inverse :
M = c xor k

 

·          Si le masque est parfaitement aléatoire, le texte crypté est parfaitement aléatoire ; il n’y a pas de moyen d’attaque.

·          Le destinataire doit connaître le masque.

·          On doit savoir engendrer des séquences aléatoires, le problème est qu’il nous est impossible de générer réellement du hasard.  

·          8 chaînage

Donnée : un cryptosystème (E,D) par bloc de tailles N

? Cela peut être RSA ou DES

Objectif : envoyer un message m long.

Méthode :

·          on le découpe en segments de taille n :
      m = m1…. Mk
·          on crypte chaque segment
·          On chaîne les segments en faisant interagir, en clair ou cryptés, pour augmenter la diffusion.

 

Quatre mode de chaînage existent :
·          ECB (Electronic codebook)
·          CBC (Cipher block chaining)
·          CFB (Cipher feedback)
·          OFB (Output feedback)

·        ELECTRONIC CODEBOOK (ECB)

C’est l’absence de chaînage.

On calcule 

Ci =E(mi)

Et on envoie

C = Ci....Ck

On décrypte par :

Mi = D(Ci)

·          Ce chaînage expose à des attaques statistiques, car deux blocs égaux de la source donnent deux blocs chiffrés égaux.
·          Peut être vu comme une substitution l’alphabet étant formé des blocs de taille n.

Se porte bien à l’attaque stat. (ce que l’on connaît on le réutilise).
Ce mode de codage est le plus facile à casser, il est préférable de ne pas l’utiliser.

·        CIPHER CLOCK CHAINING (CBC)

On choisit un premier bloc C0

On crypte par

Ci=E(mi xor Ci-1)
Et on envoie
Co et les Ci

On déchiffre par

Mi= C(i-1) xor D(ci)

Les erreurs de transmissions sur les Ci ne se propagent pas.

·        CIPHER FEEDBACK (CFB)

·          On prend une taille t<n
·          On découpe le message en blocs de taille t
M=m1….mk

Un registre de décalage à n bits initialisés à s0.
Cryptage en 3 morceaux
Il faut connaître So et t au départ

·          Chiffrage par :

Pi = E (si-1)t     prendre s1-1(t bits de gauche)
Ci = mi xor Pi
Si = (2 puissance t s(i-1) + Ci) mod 2 exposant n (décalage et addition)

On recommence k fois.

·          Déchiffrage : changer la formule du milieu en

Mi = ci xor Pi

NB : il faut une clé secrète.

Quand augmentation de la complexité de l’algorithme, augmentation de la sécurité.

·        OUTPUT FEEDBACK (OFB)

Les CFB ET OFB sont utlisés lorsque l’unité de transmission est de taille t (=1 ou =8  souvent) est inférieure à la taille d’un bloc crypté (n=64).

Pour OFB, on a t inférieur ou égal n. Le calcul des si est modifié en

                        Si = (2exposant t (Si-1) + Pi) mod2 exposant n.

Cas fréquent : t = n.
Dans ce cas, Pi=Si et
Si = E(Si-1).