Université BORDEAUX 1 U.F.R. Mathématiques et Informatique
MAI 932 EX (1/2 épreuve de J.Bétréma) 19 janvier 2005


Master Crypto 2
Cryptographie appliquée : complexité

Durée totale de l'épreuve : 3 heures. Ce sujet est à traiter sur copie séparée, et il est conseillé de lui consacrer environ 1h30. Tous documents interdits pour ce sujet.

Recommandation : soignez la rédaction de vos réponses. Les développements confus et vagues sont sans intérêt ; les réponses doivent être précises, et argumentées.

Exercice 1

Un corrigé est disponible ci-dessous.

On considère un problème de décision LNPco-NP.

  1. Expliquer ce que cela signifie (donner les définitions précises).
  2. Donner un exemple, en arithmétique, d'un tel problème, qui soit en même temps difficile, c'est-à-dire qui ne semble pas appartenir à P. Prouver que ce problème appartient bien à NPco-NP ; par contre on ne demande pas de prouver qu'il est difficile : pourquoi ?
  3. Montrer que si L est NP-complet, alors NP = co-NP.
  4. Que peut-on en conclure pour le problème de la question 2 ?

Exercice 2

Un corrigé est disponible ci-dessous.

Dans cet exercice, p désigne un entier premier impair, de taille n = log2 ( p ), et g désigne un générateur du groupe multiplicatif modulo p. Tous les calculs sont effectués modulo p.

  1. Montrer que y = g x est un carré (modulo p) si et seulement si x est pair.
  2. Comment tester rapidement si y est un carré (autrement dit un résidu quadratique modulo p) ?
  3. Si y est un carré, et si z = g a est une racine carrée de y, calculer b tel que g b soit l'autre racine carrée de y.
  4. On rappelle qu'il existe un algorithme efficace (c'est-à-dire de complexité polynomiale) pour extraire une racine carrée modulo p (car p est premier). Voici un algorithme récursif qui semble calculer efficacement le logarithme discret de y, qu'on notera f ( y ) pour simplifier :

    Calcul de f (y) :
      si y = 1, retourner 0 ;
      si y est un carré alors
        z = racine carrée (y);
        retourner 2 * f (z);  
      sinon
        z = y / g;
        retourner 1 + f (z);
    

    Où est le bug ?

  5. Soit t = p / 2 ; t est une fraction, il ne s'agit pas, ici, d'une division entière. On suppose qu'on dispose d'un "oracle" permettant de calculer la fonction booléenne b ( y ) qui vaut 1 si f ( y ) < t, 0 sinon. Autrement dit :

    b ( y ) = ( f ( y ) < t )

    Modifier l'algorithme précédent, pour qu'il calcule correctement le logarithme discret f, en utilisant la fonction b.

  6. Soit γ ( y ) le nombre d'appels récursifs effectués par cet algorithme. Montrer que :

    γ ( y ) ≤ 2 n

    Rappel : n désigne la taille de p.

  7. Dans la suite, on suppose que l'oracle qui calcule b est un algorithme probabiliste, qui donne la bonne réponse avec un avantage significatif, soit, pour fixer les idées, avec une probabilité de succès supérieure à 2 / 3. On note φ ( y ) le résultat calculé par l'algorithme de la question 5. Calculer la probabilité d'avoir :

    φ ( y ) = f ( y ).

  8. Il est facile de vérifier si φ donne la bonne réponse : expliquer comment. On peut donc recommencer le calcul de φ autant de fois que nécessaire ; calculer l'espérance du nombre de calculs nécessaires pour obtenir φ ( y ) = f ( y ).
  9. Le résultat précédent prouve-t-il que la fonction booléenne b est difficile ( hard-core ) pour la fonction exponentielle modulo p ? On commencera par rappeler rigoureusement ce que cela signifie.

Corrigé.

Exercice 1

Voir l'énoncé ci-dessus.

  1. (2 points). LNP signifie qu'il existe un vérifieur V, de complexité polynomiale, tel que :

    L (u) ⇔ ∃x V (u, x)

    Lco-NP signifie que ¬LNP, ou encore qu'il existe un vérifieur V', de complexité polynomiale, tel que :

    L (u) ⇔ ∀x V' (u, x)

  2. (3 points). Le problème HAS-FACTOR (n, k) consiste à savoir si l'entier n possède un facteur non trivial inférieur à k. Ce problème appartient clairement à NP, car un certificat est un diviseur inférieur à k.

    Le problème complémentaire (ou dual) appartient aussi à NP : pour prouver que n ne possède pas de facteur non trivial inférieur à k, on peut produire comme certificat la liste des facteurs premiers pi de n, avec pour chacun leur certificat de primalité. Le vérifieur vérifie les certificats de primalité, puis divise n successivement par chacun des pi (en itérant la division si pi est un facteur multiple) pour vérifier que chaque pi est bien un facteur de n, et que la liste est complète. Enfin le vérifieur répond "oui" si k est inférieur à chacun des pi .

    Le problème de décision HAS-FACTOR est aussi difficile que le problème de la factorisation, qui peut être résolu par dichotomie en faisant appel à un oracle pour HAS-FACTOR. On ne connaît donc pas d'algorithme polynomial pour résoudre ce problème, sans qu'on sache démontrer qu'il n'en existe pas.

  3. (Questions 3 + 4 : 3 points). Supposons que L est NP-complet, et soit A un problème quelconque dans co-NP. Alors il existe une fonction de complexité polynomiale qui permet de réduire ¬A à L :

    ¬A (u) ⇔ L ( f (u) )

    soit :

    A (u) ⇔ ¬L ( f (u) )

    ce qui réduit A à ¬L. Comme ¬LNP, on en déduit ANP. Ceci montre qu'on a : co-NPNP. En passant au dual, on obtient : NPco-NP, d'où l'égalité demandée.

  4. Il est donc très vraisemblable que le problème HAS-FACTOR n'est pas NP-complet, sinon on aurait NP = co-NP, ce que personne ne conjecture.

Exercice 2

Voir l'énoncé ci-dessus.

  1. (Questions 1 + 2 : 2 points). Si x = 2 a, g x = ( g a ) 2, et vice-versa.
  2. Pour tester rapidement si y est un résidu quadratique modulo p, le plus efficace est de calculer récursivement son symbole de Legendre en utilisant la loi de réciprocité quadratique. Mais on peut aussi, plus simplement, calculer :

    y u mod p , avec u = ( p - 1 ) / 2

    et tester si le résultat vaut 1.

  3. (2 points). Si y est un carré, et si z = g a est une racine carrée de y, l'autre racine carrée de y vaut :

    - z = g u g a , avec u = ( p - 1 ) / 2

    donc b = a + u si l'on suppose a < b. Pour la suite, il est important de remarquer qu'une seule des deux racines carrées de y est de la forme g a, avec a < u.

  4. (Questions 4 + 5 : 4 points). L'algorithme présenté cherche à inverser l'algorithme d'exponentitation rapide. Pour qu'il soit correct, lorsque y = g 2 a , il faut calculer la bonne racine z = g a — et non z = g a + u , ce qu'on ne sait pas faire.

  5. Les questions 3 et 4 montrent qu'on peut corriger l'algorithme en utilisant un oracle pour calculer b, et ainsi choisir la bonne racine carrée :

    Calcul de f (y) :
      si y = 1, retourner 0 ;
      si y est un carré alors
        z = racine carrée (y);
        si ¬ b (z) alors z = -z;
        retourner 2 * f (z);  
      sinon
        z = y / g;
        retourner 1 + f (z);
    

    En effet, le test b (z) est positif si z = g a , avec a < p / 2 ; sinon, il faut changer de racine carrée.

  6. (2 points). Soit y = g x ; si x est impair, on fait un appel récursif, x est décrémenté, et sa taille est inchangée ; si x est pair, on fait un appel récursif, x est divisé par deux, donc sa taille est décrémentée. D'où le résultat.

  7. (2 points). On a : φ ( y ) = f ( y ) si l'algorithme qui calcule b donne la bonne réponse à chaque appel ; or le calcul de b est effectué n fois (chaque fois qu'on divise l'exposant par 2), donc la probabilité demandée est de l'ordre de (2 / 3) n .

  8. (2 points). Il est facile de vérifier si φ donne la bonne réponse, en calculant g φ ( y ) et en comparant le résultat avec y. L'espérance du nombre de calculs nécessaires pour obtenir la bonne réponse est l'inverse de la probabilité calculée à la question précédente, en supposant les appels de b indépendants. Elle est donc de l'ordre de (3 / 2) n .
  9. (2 points). Dire que b est difficile pour la fonction e : xg x mod p signifie qu'il n'existe pas d'algorithme polynomial B permettant de prédire b ( e (x) ) avec un avantage significatif, c'est-à-dire avec une probabilité de succès supérieure à 1 / 2 + 1 / π (n), où π désigne une fonction polynomiale. En itérant le calcul de B, et en choisissant le résultat majoritaire, on peut convenir que la probabilité de succès est supérieure à 2 / 3.

    Les questions précédentes ont montré que si un tel algorithme B existe, on peut construire un algorithme probabiliste pour calculer le logarithme discret ; cet algorithme, lorsqu'il termine, donne toujours la bonne réponse, mais son temps moyen d'exécution est exponentiel. Il reste du travail pour améliorer cet algorithme, prouver ainsi que B permet de construire un algorithme polynomial pour calculer le logarithme discret, et en conclure que si ce dernier problème est difficile (ce que tout le monde conjecture), alors B n'existe pas, et b est un bit (autrement dit une fonction booléeene) difficile pour e.