Chiffre de César

tbowan
(in english)
11 juin 2017

Divulgâchage : Le Chiffre de César est un classique de la cryptographie. Très simple à utiliser mais aussi à cryptanalyser, il a été vu et revu par toute la littérature du domaine.

Le chiffre de César (ou Chiffrement par décalage) est l’algorithme de cryptographie connu le plus ancien. Il est rendu célèbre par Jules César pour l’usage qu’il en fit pendant ses campagnes (et via ses ouvrage d’auto-promotion, comme quoi le personnal branding n’est pas si nouveau que ça).

Mais je m’égare… Cet algorithme remplace chaque lettre du message en clair par la lettre qui la suit d’exactement $n$ places dans l’alphabet ; et si ça déborde, on continue depuis le début.

Le décalage de référence, qu’on nomme souvent abusivement chiffre décalé de Caesar consiste à décaler de trois lettres. Par exemple, le chiffré de bonjour est erqmrxu. On peut l’assimiler à un chiffrement par bloc de 4.7 bits en ECB, autant dire que ça se casse plus vite d’un bibelot.

Mathématiquement

Cet algorithme est un automorphisme pour le groupe cyclique $(Z_{26},+)$ , avouez que ça claque. En associant chaque lettre (de $a$ à $z$ ) avec un nombre (de $0$ à $25$ ), on décrit « très simplement » l’opération de chiffrement $E_k(c)$ d’un caractère $c$ après un décalage $k$ par l’équation suivante :

$\begin{align} E_k(c) & = c + k \mod n \\ & = c + k \end{align}$

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
Chiffré : 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

Puisque nous sommes dans un groupe cyclique, et qu’il est évident que toutes les opérations se feront modulo n, nous allons systématiquement l’omettre dans la suite pour simplifier les notations.

Le déchiffrement $D_k(c)$ est l’opération inverse, au sens mathématique, il s’agit, connaissant le chiffré et le décalage, de trouver le texte clair.

$\begin{align} D_k(c) & = c - k \\ & = c + k^{-1} \\ & = E_{k^{-1}}(c) \end{align}$

Et c’est ici que le chiffrement de César prend tout son sens moderne en tant que premier chiffrement asymétrique de l’histoire… Pour toute clé de chiffrement $k$ , il existe une clé inverse $k^{-1}$ , au sens du groupe $(Z_{26}, +)$ , qui en annule les effets.

Le chiffrement est alors considéré comme un chiffrement par bloc de 4.7 bits (un caractère alphabétique) en mode ECB (chaque bloc est chiffré indépendamment des autres).

Implémentation

L’implémentation du chiffrement de César ne comporte aucune difficulté particulière. L’arithmétique sur les caractères nous évite l’utilisation de table de correspondance et rendent le code plus court.

L’implémentation suivante, en C, chiffre un caractère seul ou une chaine complète.

char code_char(int k, char c)
{
    if (c >= 'a' && c <= 'z') {
        return 'a' + (c - 'a' + k) % 26 ;
    } else if (c >= 'A' && c <= 'Z') {
        return 'A' + (c - 'A' + k) % 26 ;
    } else{
        return c ;
    }
}

void code_string(int k, char * message)
{
    for (char * ptr = message; *ptr != '\0'; ++ptr) {
        *ptr = code_char(k, *ptr) ;
    }
}

Exemple

Sécurité de l’algorithme

Comme vous pouvez vous en douter, cet algorithme n’est pas sûr. Les premières traces d’attaques remontent au IX^e siècle par Analyse fréquentielle. Nous allons maintenant voir pourquoi et à quel point.

Version Asymétrique

La version asymétrique de l’algorithme, utilisant une clé publique et une clé privée n’est pas sûre pour deux raisons : l’opération choisie et la taille du groupe.

L’opération choisie. La sécurité de ce cryptosystème est basée sur la difficulté d’inverser une addition, c’est à dire de calculer une soustraction (programme de CP/CE1) dans un groupe cyclique (programme de Terminale).
La taille du groupe. Avec seulement 26 éléments, il est très rapide de calculer toutes les possibilités, même si l’opération était plus complexe.

Pour rendre cet algorithme plus sûr, il faudrait alors augmenter la taille du groupe et dans le même temps utiliser une opération plus difficile à inverser. Vous obtiendrez alors naturellement des algorithmes modernes comme RSA ou encore El Gamal.

Version symétrique

Vu la facilité à trouver l’inverse de la clé, on comprend pourquoi cet algorithme a été utilisé de manière symétrique, les correspondants étant d’accord à priori sur un couple de clés qu’ils gardent secrètes.

Le problème, cette fois est du à la taille de la clé et au mode opératoire ECB qui chiffre toujours les blocs de la même manière.

La taille des clés. Encore une fois, leur faible nombre permet de tester toutes les clés et de confronter les résultats avec les informations sur le texte clair (i.e. un dictionnaire).
Le mode ECB. Qui, en chiffrant les mêmes combinaisons de la même manière, conserve la structure du texte dans sa version chiffrée et qui permet des analyse directement sur le texte chiffré pour le cryptanalyser.

C’est sur ce point que le chiffrement de César a été et reste attaqué. Il est possible de retrouver le décalage via la comparaison entre la fréquence d’apparition des lettres dans le texte chiffré et dans un corpus de référence.

Point de vue régalien

Concernant la cryptographie, la France proposes deux points de vue complémentaires et somme toute cohérents. La loi, via la Loi n°2004-575 du 21 juin 2004 et son Décret n°2007-663 du 2 mai 2007 d’un côté qui fixent des maximum autorisés et l’ANSSI de l’autre qui fixe des minimum pour être considérés comme sûrs dans son Référentiel Général de Sécurité, Annexe B1…

pour la version asymétrique. L’ANSSI recommande l’utilisation, d’un groupe multiplicatif et des clés de 2048 bits. Le maximum légal étant de 112 bits, également pour les groupes multiplicatifs.
pour la version symétrique. L’ANSSI recommande l’utilisation de clé de 128 bits tout en déconseillant le mode ECB. Le maximum légal étant de 56 bits.

Le chiffrement de César, est donc tout à fait légal puisqu’il respecte les maxima. Pour la même raison, l’ANSSI ne le considère pas sûr.

Conclusion

Comparé aux standards cryptographiques modernes, le chiffrement de César, n’est pas seulement obsolète, mais carrément à la ramasse. Les clés sont ridiculement faibles en regard des normes mais les opérations ne sont mêmes pas dignes d’apparaître dans les textes.

Et c’est justement là que réside son intérêt. Sa simplicité en fait le candidat idéal pour débuter en cryptographie, découvrir les principes de base avant de poursuivre avec des algorithmes plus complexes.