新規更新August 23, 2018 at 04:37AM
【外部リンク】
Problème RSA fort
Ϛ : création :)
En [[cryptologie]] en [[théorie des nombres]], le '''problème RSA fort'''<ref group="Note">On trouve aussi le nom ''problème RSA flexible'' (en anglais : ''flexible RSA problem'') qui est toutefois beaucoup moins utilisé dans la littérature.</ref> (''strong RSA'') consiste à calculer trouver une racine ''e''-ième d'un nombre donné dans un certain [[Anneau (mathématiques)|anneau]]<ref>Liquid error: wrong number of arguments (1 for 2)</ref><ref>Liquid error: wrong number of arguments (1 for 2)</ref>. Il a été introduit indépendamment par Barić et Pfitzmann<ref>Liquid error: wrong number of arguments (1 for 2)</ref>, et Fujisaki et Okamoto<ref>Liquid error: wrong number of arguments (1 for 2)</ref> en 1997 comme [[hypothèse calculatoire]] afin de [[Preuve de sécurité|prouver la sécurité]] de constructions cryptographiques, en particulier les [[Signature numérique|signatures numériques]]<ref>Liquid error: wrong number of arguments (1 for 2)</ref><ref name=":0">Liquid error: wrong number of arguments (1 for 2)</ref><ref>Liquid error: wrong number of arguments (1 for 2)</ref><ref>Liquid error: wrong number of arguments (1 for 2)</ref>. Cette relaxation du [[problème RSA]] donne des signatures plus efficaces et permet de se passer de certains modèles idéalisés tel que l'[[Modèle de l'oracle aléatoire|oracle aléatoire]] dans la preuve de sécurité.
== Définition ==
Soit <math>p, q</math>deux [[Nombre premier|nombres premiers]] distincts, <math>n = pq</math>, et considérons l'[[anneau quotient]] <math>R = \mathbb Z/(n)</math>. Le problème RSA fort consiste à trouver, étant donné <math>n</math> et <math>y \in R \setminus \{0\}</math>, deux entiers <math>x \in R</math>et <math>e \in \mathbb N \setminus \{0\}</math>tels que <math>x^e = y</math>.
Le problème RSA fort est a priori plus facile que le [[problème RSA]] standard, puisque l'on peut en principe choisir ''e'' librement.
À l'heure actuelle (2018) le meilleur moyen connu pour résoudre le problème RSA fort (comme pour le problème RSA standard) est d'obtenir une [[Décomposition en produit de facteurs premiers|factorisation]] de <math>n</math>. En effet, étant donné une telle factorisation, il est facile de trouver deux entiers <math>e, d</math>tels que <math>ed = 1 \bmod \varphi(n)</math>où <math>\varphi</math>est la [[Indicatrice d'Euler|fonction d'Euler]], au moyen de l'[[algorithme d'Euclide]]. On en déduit immédiatement <math>x = y^d</math>. Toutefois il n'est pas exclu qu'existent des algorithmes spécifiques résolvant le problème RSA fort sans pour autant obtenir une factorisation de <math>n</math>.
== Exemples importants ==
* La sécurité des signatures de Gennaro-Halevi-Rabin face aux contrefaçons existentielles a été réduite dans le [[Modèle standard (cryptologie)|modèle standard]] au problème RSA fort <ref>Liquid error: wrong number of arguments (1 for 2)</ref>.
* La sécurité des signatures de Cramer-Shoup est prouvable dans le modèle standard en s'appuyant sur le problème RSA fort<ref name=":0" />.
== Notes et références ==
=== Notes ===
<references group="Note" />
=== Références ===
<references />
[[Catégorie:Cryptologie]]
== Définition ==
Soit <math>p, q</math>deux [[Nombre premier|nombres premiers]] distincts, <math>n = pq</math>, et considérons l'[[anneau quotient]] <math>R = \mathbb Z/(n)</math>. Le problème RSA fort consiste à trouver, étant donné <math>n</math> et <math>y \in R \setminus \{0\}</math>, deux entiers <math>x \in R</math>et <math>e \in \mathbb N \setminus \{0\}</math>tels que <math>x^e = y</math>.
Le problème RSA fort est a priori plus facile que le [[problème RSA]] standard, puisque l'on peut en principe choisir ''e'' librement.
À l'heure actuelle (2018) le meilleur moyen connu pour résoudre le problème RSA fort (comme pour le problème RSA standard) est d'obtenir une [[Décomposition en produit de facteurs premiers|factorisation]] de <math>n</math>. En effet, étant donné une telle factorisation, il est facile de trouver deux entiers <math>e, d</math>tels que <math>ed = 1 \bmod \varphi(n)</math>où <math>\varphi</math>est la [[Indicatrice d'Euler|fonction d'Euler]], au moyen de l'[[algorithme d'Euclide]]. On en déduit immédiatement <math>x = y^d</math>. Toutefois il n'est pas exclu qu'existent des algorithmes spécifiques résolvant le problème RSA fort sans pour autant obtenir une factorisation de <math>n</math>.
== Exemples importants ==
* La sécurité des signatures de Gennaro-Halevi-Rabin face aux contrefaçons existentielles a été réduite dans le [[Modèle standard (cryptologie)|modèle standard]] au problème RSA fort <ref>Liquid error: wrong number of arguments (1 for 2)</ref>.
* La sécurité des signatures de Cramer-Shoup est prouvable dans le modèle standard en s'appuyant sur le problème RSA fort<ref name=":0" />.
== Notes et références ==
=== Notes ===
<references group="Note" />
=== Références ===
<references />
[[Catégorie:Cryptologie]]
https://ift.tt/2o25b4S
