Etude et mise en oeuvre d’une technique d’attaque sur le crypto système à clefs publiques RSA

Quelques repères historiques 

Tout au long de l’histoire, la cryptographie s’est insérée dans les différents contextes historiques, et a progressé avec les évolutions mathématiques. La plupart du temps elle est utilisée dans un milieu politique ou militaire.
Historiquement le développement de cryptographie est passé par trois âges :

Antiquité 

Jusqu’à au XXème siècle (fin de la 1ère guerre mondiale), on entend habituellement lesméthodes cryptographiques qui requièrent simplement du papier et un crayon. Il n’est pas surprenant que ces systèmes soient les plus anciens.
Les premières traces de cryptographie remontent au XVIème siècle avant J-C. On a retrouvé à cette époque sur les bords du Tigre en Irak le plus vieux document chiffré connu. Dans l’antiquité on remarque alors l’émergence de nouveaux modes de cryptographie, pour la plupart propres à un peuple. C’est pourquoi nous allons ici organiser l’étude avec ces différentes civilisations.

Hébreux (chiffre Atbesh)

La plus connue et la plus simple est sans doute le chiffre Atbesh. Datant du Vème siècle avant J-C, ce procédé consiste à faire correspondre l’alphabet classique avec l’alphabet inversé, et d’associer ainsi à chaque lettre, la lettre correspondante en position dans l’alphabet inversé. Voici un exemple pour l’alphabet latin.

Grecs (Scytale) 

A la même époque que les hébreux, les grecs commencèrent à développer quelques méthodes de codage. Parmi celles-ci : la scytale (ou scytale spartiate). La scytale est une des premières techniques de codage par transposition. Elle date du Vème siècle av J-C.
Le principe est le suivant : celui qui est l’auteur du message va préalablement enrouler une bande (de parchemin ou de cuir) en hélice autour d’un bâton régulier de diamètre fixé sur laquelle il va pouvoir écrire. Après écriture, l’auteur déroule la bande qui présente alors une succession de caractères n’ayant aucun sens logique. Celui qui veut lire le message doit alors connaître le diamètre du bâton initial puis y enrouler de nouveau la bande.

Age technique (Systèmes mécaniques et électromécaniques)

Le XXème siècle (1919 – 1975), utilisant des appareils mécaniques ont donc été mises au point. L’âge technique garde les substitutions et les permutations mais les met en oeuvre à l’aide de machines mécaniques ou électromécaniques. Les plus célèbres sont l’Enigma et la Hebern.

Machine Enigma 

La machine Enigma reste l’une des plus remarquables machines à crypter toutes périodes confondues ; elle a longtemps servi de modèle et a marqué son époque. La naissance de la machine Enigma est initiée en 1919 par un ingénieur hollandais, Hugo Alexander, qui breveté un dispositif de codage électromécanique ; ses idées sont réutilisées par le Dr Arthur Scherbius qui donne le nom Enigma à sa machine initialement développée pour les civils. Cependant, sa société fera faillite peu après, en revanche, les militaires allemands vont lui accorder un grand intérêt pendant la seconde guerre mondiale.

Machine Hebern 

En 1910, Edward H. Hebern commença à mettre au point des machines de chiffrement aux États-Unis. Au début des années 1920, il inventa la machine à code électrique qui utilisait seule roue codeuse. Il conçut aussi, en 1924, des appareils à trois et cinq roues codeuses comme prototypes pour la marine américaine. Très différentes de l’Enigma, les machines Hebern utilisaient des roues codeuses dont le filage interne pouvait facilement être changé. De plus, ces roues codeuses pouvaient fonctionner dans le sens de rotation conventionnel ou dans le sens contraire. Par contre, ces machines possédaient toutes des faiblesses du point de vue cryptanalytique. Ces faiblesses sont décrites par William Friedman.

Age scientifique 

Il a commencé en 1976 avec la prolifération des ordinateurs et l’essor de leur connectivité (méthodes modernes). Plusieurs méthodes cryptographiques utilisent maintenant des logiciels plutôt que des machines électromécaniques.
Il voit l’introduction de mécanismes donnant des réponses positives à des questions a priori hors d’atteinte :
 Comment assurer un service de confidentialité sans avoir au préalable établi une convention secrète commune ?
 Comment assurer un service d’authenticité basé sur la possession d’un secret sans révéler la moindre information sur le secret ?

Algorithme de chiffrement symétrique DES 

Les principes des algorithmes symétriques commerciaux modernes, principalement le DES (Data Encryption Standard), ont été mis au point dans les années 1970 par IBM avec l’aide de la NSA (National Security Agency). Ils sont basés sur des réseaux de substitution et de de transposition. DES n’est plus à présent sûrs compte tenu de la longueur faible des blocs clairs (64 bits) et des clés (56 bits). Cependant, il y’a l’avènement d’algorithmes plus sûr comme AES dont les clés sont de longueur de 128 bits à 256 bits. Leur cryptanalyse a fait des progrès (cryptanalyse linéaire et différentielle), ce qui permet de mieux cerner leur sûreté cryptologique.

Algorithme de chiffrement asymétrique RSA 

L’algorithme à clés publiques le plus répandu est l’algorithme RSA (Rivest-Shamir & Adleman), publié en 1978. Il est fondé sur les propriétés des nombres premiers. Pour casser l’algorithme, il faut factoriser un grand nombre entier (fourni par la clé publique).
L’algorithme RSA est malheureusement beaucoup plus coûteux à mettre en oeuvre que le DES, et son usage est généralement utilisé pour le codage de données de taille limitée.
C’est en particulier une excellente solution pour la diffusion des clés du DES.

Objectifs Fondamentaux et Qualités d’un cryptosystème

Dès que plusieurs entités sont impliquées dans un échange de messages sécurisés, il est nécessaire de faire appel aux protocoles cryptographiques afin de sécuriser la communication.
Lorsque l’on parle de “sécuriser un échange”, on souhaite prêter attention aux 3 services de sécurité suivants : la confidentialité, l’intégrité et l’authentification :

Intégrité des données 

C’est la prévention d’une modification non autorisée de l’information. L’intégrité du système et de l’information garantit que ceux-ci ne sont modifiés que par une action volontaire et légitime. Les attaques contre l’intégrité sont appelées « substitutions ».

Confidentialité 

La confidentialité est la propriété qu’une information n’est ni disponible ni divulguée aux personnes, entités ou processus non autorisés (selon la norme ISO 7498-2). La confidentialité se définit également comme le caractère réservé d’une information dont l’accès est limité aux personnes autorisées à la connaitre pour accomplir leurs missions.

Authentification 

L’authentification consiste à vérifier l’identité des différentes parties impliquées dans le dialogue. Concrètement, lorsque de l’information est échangée, l’authentification du message garantit son origine et sa destination. Les attaques contre l’authenticité sont appelées « mascarades ».

Non-Répudiation 

La non-répudiation consiste à prouver qu’un message a bien été émis par son expéditeur ou reçu par son destinataire. Plus généralement, la non-répudiation consiste à garantir que l’auteur d’un message ou d’un document ne peut pas nier l’avoir écrit ou transmis.
Elle se décompose comme suit :
– Non-répudiation d’originel : l’émetteur ne peut nier avoir écrit le message.
– Non-répudiation de réception : Le receveur ne peut nier avoir reçu le message.
– Non-répudiation de transmission : l’émetteur du message ne peut nier avoir reçu le message.

Les principaux concepts cryptographiques 

Introduction 

On se placera dans la problématique d’un émetteur et d’un récepteur désirant échanger un message sur un canal de transmission public (donc ouvert à la possibilité qu’une tierce personne intercepte le message). Le but est de décrire et d’analyser des procédés (cela inclus leurs implémentations concrètes) permettant de transformer le message original, que l’on désignera par message clair (ou texte clair), en un message chiffré. Ce procédé sera appelé chiffrement).
Une fois que le message est chiffré, il transite via un canal non sécurisé vers son destinataire.
Afin de déchiffrer le message, le destinataire doit lui faire subir l’opération inverse du chiffrement qui est le déchiffrement. Cela permet d’assurer la confidentialité du message. On parlera alors de message chiffré. En pratique, nous ne considérerons que des messages de type texte. Les méthodes que nous décrirons devront éventuellement être adaptées si l’on souhaite chiffrer du son ou/et de l’image, même si du point de vue de l’ordinateur ce sera une suite de nombres binaires.

DES 

Le D.E.S. (Data Encryption Standard, c’est-à-dire Standard de Chiffrement de Données) est un standard mondial depuis plus de 35 ans. Bien qu’il soit un peu vieillissant, il résiste toujours très bien à la cryptanalyse et reste un algorithme très sûr.
Au début des années 70, le développement des communications entre ordinateurs a nécessité la mise en place d’un standard de chiffrement de données pour limiter la prolifération d’algorithmes différents ne pouvant pas communiquer entre eux. Pour résoudre ce problème, l’Agence Nationale de Sécurité américaine (N.S.A.) a lancé des appels d’offres. La société I.B.M. a développé alors un algorithme nommé Lucifer,relativement complexe et sophistiqué. Après quelques années de discussions et de modifications, cet algorithme, devenu alors D.E.S., fut adopté au niveau fédéral le 23 novembre 1976.

Fonctionnement 

L’algorithme prend en entrée un bloc de 128 bits (16 octets), la clé fait 128, 192 ou 256 bits.
Les 16 octets en entrée sont permutés selon une table définie au préalable. Ces octets sont ensuite placés dans une matrice de 4×4 éléments et ses lignes subissent une rotation vers la droite. L’incrément pour la rotation varie selon le numéro de la ligne. Une transformation linéaire est ensuite appliquée sur la matrice, elle consiste en la multiplication binaire de chaque élément de la matrice avec des polynômes issus d’une matrice auxiliaire, cette multiplication est soumise à des règles spéciales selon GF (28) (groupe de Galois ou corps fini). La transformation linéaire garantit une meilleure diffusion (propagation des bits dans la structure) sur plusieurs tours.
Finalement, un OU exclusif XOR entre la matrice et une autre matrice permet d’obtenir une matrice intermédiaire. Ces différentes opérations sont répétées plusieurs fois et définissent un « tour ». Pour une clé de 128, 192 ou 256, AES nécessite respectivement 10, 12 ou 14 tours.
Une même clef secrète est utilisée pour les opérations de chiffrement et de déchiffrement (c’est un secret partagé entre l’expéditeur et le destinataire du message). AES est un algorithme de chiffrement par blocs, les données sont traitées par blocs de 128 bits pour le texte clair et le chiffré. La clef secrète a une longueur de 128 bits, d’où le nom de version : AES 128 (il existe deux autres variantes dont la clef fait respectivement 192 et 256 bits).

Certificats

La cryptographie asymétrique est également utilisée pour générer des- certificats numériques,ceux-ci contenant la clef publique de l’entité associée aux certificats. La clef privée est quant à elle stockée au niveau de cette dernière entité. Une application des certificats est par exemple la mise en oeuvre d’une infrastructure à clefs publiques (PKI) pour gérer l’authentification et la signature numérique d’une entité, par exemple un serveur web (Apache avec le module SSL par exemple), ou simplement un client souhaitant signer et chiffrer des informations à l’aide de son certificat de la façon décrite dans les sections précédentes.

Sécurité 

Un chiffrement symétrique au moyen d’une clef de 128 bits propose 2128 (~ 3,4 1038) façons de chiffrer un message. Un pirate qui essaierait de déchiffrer le message par la force brute devrait les essayer une par une.
Pour les systèmes à clef publique, il en va autrement. Tout d’abord les clefs sont plus longues (par exemple 1 024 bits minimum pour RSA) ; en effet, elles possèdent une structure mathématique très particulière (on ne peut pas choisir une suite de bits aléatoire comme clef secrète, par exemple dans le cas du RSA, seuls les nombres premiers sont utilisés). Certains algorithmes exploitant cette structure sont plus efficaces qu’une recherche exhaustive sur, par exemple, 1 024 bits. Ainsi, dans le cas de RSA, le crible général des corps de nombres est une méthode plus efficace que la recherche exhaustive pour la factorisation.