Chiffre de César

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).

wajari @ pixabay

Mais je m’égare… Cet algorithme remplace chaque lettre du message en clair par la lettre qui la suit d’exactement nn 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 (Z26,+)(Z_{26},+), avouez que ça claque. En associant chaque lettre (de aa à zz) avec un nombre (de 00 à 2525), on décrit « très simplement » l’opération de chiffrement Ek(c)E_k(c) d’un caractère cc après un décalage kk par l’équation suivante :

Ek(c)=c+kmodn=c+k \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 Dk(c)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.

Dk(c)=ck=c+k1=Ek1(c) \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 kk, il existe une clé inverse k1k^{-1}, au sens du groupe (Z26,+)(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 IXe 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.

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.

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

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.