Exponentielle modulaire et cryptographie

   

La fonction exponentielle croissant très rapidement, on dépasse facilement les limites de l'arithmétique entière de la machine, et on ne profite guère de cette accélération. Calculons plutôt , de façon à rester dans ces limites. Il suffit de placer un %m après chaque opération. Voici la version récursive terminale de cette fonction :

static int expmod_fastrec_aux(int x, int y, int e, int m) {
  if (e == 0) {
    return y;
  } else if (e % 2 == 1) {
    return expmod_fastrec_aux(x, x*y % m, e-1, m);
  } else {
    return expmod_fastrec_aux(x*x % m, y, e/2, m);
  }
}

int expmod_fastrec(int x, int e, int m) {
  return expmod_fastrec_aux(x, 1, e, m);
}

La version itérative s'obtient facilement par dérécursivation de cette définition récursive terminale :

int expmod_iter(int x, int e, int m) {
  int y = 1;
  while (e != 0) {
    if (e%2 == 1) {
      y = (x*y) % m;
      e = e-1;
    } else {
      x = (x*x) % m;
      e = e/2;
    }
  }
  return y;
}

 

L'exponentielle modulaire intervient dans les algorithmes de la cryptographie à clé publique, car l'exponentielle modulaire est considérablement plus facile à calculer que son inverse, le logarithme modulaire (donc chiffrer est plus facile que déchiffrer). Le système de chiffrement à clé publique RSA a été proposé en 1977 par Ron Rivest, Adi Shamir et Leonard Adleman.

Pour construire ses clés, chaque utilisateur de RSA

• choisit deux grands nombres premiers p et q
• calcule n=pq
• choisit un entier e<n qui est premier avec (p-1)(q-1)
• calcule l'inverse d de e modulo (p-1)(q-1)
• publie sa clé publique, qui est formée des deux entiers e et n
• conserve sa clé privée d
• détruit les entiers p et q qui ne doivent pas être divulgués.

Les fonctions de chiffrage et de déchiffrage sont respectivement:

Quand A veut communiquer un entier m (0<m<n) à B, il calcule à l'aide de la clé publique de B, qu'il envoie à B ; à la réception d'un message chiffré c, B calcule à l'aide de sa clé privée. Il s'agit bien d'un déchiffrage car , grâce au théorème d'Euler si m est premier avec n, et au fait que .

La sécurité provient de la difficulté à factoriser de grands entiers. En effet, déterminer d à partir de e demande la connaissance de (p-1)(q-1); or la publication de n=pq n'est en aucune façon une aide pour calculer (p-1)(q-1), qui ne peut être obtenu qu'à partir de p et q. D'autre part, on ne sait pas calculer efficacement des racines e-ièmes, ce qui permettrait d'avoir le texte clair m à partir du texte chiffré C(m).