Fonction trappe - Trapdoor function

Cet article concerne la fonction de cryptographie mathématique. Pour la méthode de contournement de la sécurité, voir Backdoor (informatique) .
L'idée de la fonction trappe. Une fonction trappe f avec sa trappe t peut être générée par un algorithme Gen . f peut être calculé efficacement, c'est-à-dire en temps polynomial probabiliste . Cependant, le calcul de l'inverse de f est généralement difficile, sauf si la trappe t est donnée.

Une fonction trappe est une fonction qui est facile à calculer dans une direction, mais difficile à calculer dans la direction opposée (trouver son inverse ) sans information spéciale, appelée « trappe ». Les fonctions de trappe sont largement utilisées en cryptographie .

En termes mathématiques, si f est une fonction trappe, alors il existe une information secrète t , telle qu'étant donné f ( x ) et t , il est facile de calculer x . Considérez un cadenas et sa clé. Il est facile de changer le cadenas d'ouvert à fermé sans utiliser la clé, en poussant la manille dans le mécanisme de verrouillage. L'ouverture facile du cadenas nécessite cependant l'utilisation de la clé. Ici la clé est la trappe et le cadenas est la fonction trappe.

Un exemple de trappe mathématique simple est « 6895601 est le produit de deux nombres premiers. Quels sont ces nombres ? » Une solution typique de " force brute " serait d'essayer de diviser 6895601 par plusieurs nombres premiers jusqu'à trouver la réponse. Cependant, si l'on dit que 1931 est l'un des nombres, on peut trouver la réponse en entrant "6895601 ÷ 1931" dans n'importe quelle calculatrice. Cet exemple n'est pas une fonction de trappe solide - les ordinateurs modernes peuvent deviner toutes les réponses possibles en une seconde - mais cet exemple de problème pourrait être amélioré en utilisant le produit de deux nombres premiers beaucoup plus grands .

Les fonctions de trappe ont pris de l'importance dans la cryptographie au milieu des années 1970 avec la publication de techniques de cryptage asymétriques (ou à clé publique) par Diffie , Hellman et Merkle . En effet, Diffie & Hellman (1976) ont inventé le terme. Plusieurs classes de fonctions avaient été proposées, et il est vite devenu évident que les fonctions de trappe sont plus difficiles à trouver qu'on ne le pensait initialement. Par exemple, une des premières suggestions a été d'utiliser des schémas basés sur le problème de la somme des sous - ensembles . Cela s'est avéré – assez rapidement – ​​inadapté.

En 2004, les candidats de fonction (famille) de trappe les plus connus sont les familles de fonctions RSA et Rabin . Les deux sont écrits sous forme d'exponentiation modulo un nombre composé, et les deux sont liés au problème de la factorisation en nombres premiers .

Les fonctions liées à la dureté du problème du logarithme discret (soit modulo un nombre premier, soit dans un groupe défini sur une courbe elliptique ) ne sont pas connues pour être des fonctions de trappe, car il n'y a pas d'information connue de " trappe " sur le groupe qui permet le calcul efficace de logarithmes discrets.

Une trappe en cryptographie a la signification très spécifique susmentionnée et ne doit pas être confondue avec une porte dérobée (ceux-ci sont fréquemment utilisés de manière interchangeable, ce qui est incorrect). Une porte dérobée est un mécanisme délibéré qui est ajouté à un algorithme cryptographique (par exemple, un algorithme de génération de paires de clés, un algorithme de signature numérique, etc.) le système d'une certaine manière.

Définition

Une fonction trappe est un ensemble de fonctions unidirectionnelles { f k  : D k → R k } ( k ∈ K ), dans lesquelles K , D k , R k sont des sous-ensembles de chaînes binaires {0, 1} * , satisfaisant aux conditions suivantes :

  • Il existe un temps polynomial probabiliste (PPT) échantillonnage algorithme Gen st Gen (1 n ) = ( k , t k ) avec k ∈ K ∩ {0, 1} n et t k ∈ {0, 1} * satisfait | t k | < p ( n ), dans lequel p est un polynôme. Chaque t k est appelée la trappe correspondant à k . Chaque trappe peut être échantillonnée efficacement.
  • Étant donné l'entrée k , il existe également un algorithme PPT qui génère x ∈ D k . C'est, chaque D k peut échantillonner efficacement.
  • Pour tout k ∈ K , il existe un algorithme PPT qui correctement calcule f k .
  • Pour tout k ∈ K , il existe un algorithme PPT A st pour tout x ∈ D k , soit y = A ( k , f k ( x ), t k ), et alors on a f k ( y ) = f k ( x ). Autrement dit, étant donné la trappe, il est facile à inverser.
  • Pour tout k ∈ K , sans trappe t k , pour tout algorithme PPT, la probabilité d'inverser correctement f k (c'est-à-dire, étant donné f k ( x ), trouver une pré-image x' telle que f k ( x' ) = f k ( x )) est négligeable.

Si chaque fonction de la collection ci-dessus est une permutation à sens unique, la collection est également appelée permutation trappe .

Exemples

Dans les deux exemples suivants, nous supposons toujours qu'il est difficile de factoriser un grand nombre composé (voir Factorisation d'entiers ).

Hypothèse RSA

Dans cet exemple, ayant l'inverse de e modulo ( n ), la fonction totient d'Euler de n , est la trappe :

Si la factorisation est connue, φ( n ) peut être calculé, donc l'inverse d de e peut être calculé d = e −1 mod φ( n ), puis étant donné y = f ( x ) on peut trouver x = y d mod n = x ed mod n = x mod n . Sa dureté découle de l'hypothèse RSA.

Hypothèse de résidus quadratiques de Rabin

Soit n un grand nombre composé tel que n = pq , où p et q sont de grands nombres premiers tels que p 3 mod 4, q 3 mod 4, et gardés confidentiels à l'adversaire. Le problème consiste à calculer z donné une telle manière que un ≡ z 2 mod n . La trappe est la factorisation de n . Avec la trappe, les solutions de z peuvent être données comme cx + dy , cx − dy , − cx + dy , − cx − dy , où a ≡ x 2 mod p , a ≡ y 2 mod q , c ≡ 1 mod p , c 0 mod q , d ≡ 0 mod p , d ≡ 1 mod q . Voir le théorème des restes chinois pour plus de détails. Notez qu'étant donné les nombres premiers p et q , nous pouvons trouver x ≡ a ( p +1)/4 mod p et y ≡ a ( q +1)/4 mod q . Ici les conditions p 3 mod 4 et q 3 mod 4 garantissent que les solutions x et y peuvent être bien définies.

Voir également

Remarques

Les références