Signification de: «Si la factorisation de grands nombres entiers est difficile, alors la rupture de RSA est difficile» n'est pas prouvé »

30

Je lisais CLRS et on me dit:

Si la factorisation de grands nombres entiers est facile, alors la rupture du cryptosystème RSA est facile.

Ce qui a du sens pour moi car avec la connaissance de et , il est facile de créer la clé secrète que la connaissance de la clé publique. Cependant, cela explique la déclaration inverse, que je ne comprends pas très bien:qpq

L'inverse, si la factorisation de grands nombres entiers est difficile, alors la rupture de RSA est difficile, n'est pas prouvée.

Que signifie formellement la déclaration ci-dessus? Si nous supposons que l'affacturage est difficile (d'une manière formelle), pourquoi cela n'implique-t-il pas que la rupture du système cryptographique RSA est difficile?

Considérez maintenant que si nous supposions que l'affacturage est difficile ... et que nous avons découvert que cela signifiait que le cryptosystème RSA est difficile à briser. Qu'est-ce que cela signifierait officiellement?

Charlie Parker
la source
3
Cela peut impliquer que la rupture du RSA est difficile, mais cela n'a pas été prouvé .
Tom van der Zanden
2
le problème du logarithme discret au cœur de la rupture du RSA alors que "très similaire" n'a pas été prouvé être équivalent à l'affacturage, c'est une question ouverte majeure du domaine (à la fois la cryptographie et le TCS)
vzn
1
Le second ne devrait-il pas utiliser un tiret au lieu de virgules? Un tiret n'est-il pas utilisé lorsqu'il y a des virgules à l'intérieur de la clause dépendante? The converse statement -- that if factoring large integers is hard, then breaking RSA is hard -- is unproven.
Czipperz
@ruakh: Oups, ouais ... Je me suis même assuré de revérifier mais je me suis toujours trompé. J'oublie toujours que vous êtes censé réduire à un problème que vous savez facile, pas un problème que vous savez être au moins aussi difficile que votre problème actuel. :-) Merci pour ça, je l'ai retiré.
Mehrdad
Argument mathématique: "si , alors " signifie la même chose que "si pas , alors pas ". Vous ne pouvez rien dire sur "sinon , alors pas ". B B A A BABBAAB
drzbir

Réponses:

50

La façon la plus simple d'y penser est de penser à la contrapositive.

La déclaration:

si la factorisation de grands nombres entiers est difficile, alors la rupture du RSA est difficile

est équivalent à ce qui suit:

si casser RSA est facile, alors factoriser de grands entiers est facile

Cette déclaration n'a pas été prouvée.

Ce qu'ils disent, c'est que nous avons un algorithme qui résout la factorisation en temps polynomial. Ensuite, nous pouvons l'utiliser pour construire un algorithme qui résout RSA en temps polynomial.

Mais, il pourrait y avoir une autre façon de casser RSA qui n'implique pas la factorisation d'entiers. Il est possible que nous découvrions que nous pouvons casser RSA d'une manière qui ne nous permet pas de factoriser les entiers en temps polynomial.

Bref, nous savons que RSA est au moins aussi simple que l'affacturage. Il y a deux résultats possibles: RSA et l'affacturage sont de difficulté équivalente, ou RSA est un problème strictement plus facile que l'affacturage. Nous ne savons pas quel est le cas.

jmite
la source
10
«au moins aussi facile» - c'est une façon d'interpréter les réductions qui devrait être enseignée plus expressément avec l'inverse.
G. Bach
Vous pouvez le faire dans les deux cas, si X est au moins aussi dur que Y, Y est au moins aussi facile que X.
jmite
2
C'est ce que je voulais dire - presque tout le monde a probablement entendu "X est au moins aussi dur que Y", mais "Y est au moins aussi facile que X" est très rarement expliqué - bien qu'il soit tout aussi utile.
G. Bach
1
Je semble me rappeler vaguement que Donald Knuth a mentionné un algorithme qui, étant donné qu'une machine capable de déchiffrer comme par magie des messages cryptés RSA arbitraires, pourrait factoriser les produits de deux grands nombres premiers. Je peux me tromper :-(
gnasher729
31

L'existence d'une voie dure ne signifie pas qu'il n'y a pas de voie facile.

Il peut y avoir un certain nombre de façons de rompre le RSA et il nous suffit d'en trouver un.


L'une de ces façons consiste à factoriser un grand entier, donc si c'est facile, nous pouvons le faire de cette façon et RSA est cassé. C'est aussi le seul moyen que nous connaissons encore. S'il est impossible de le faire, nous pouvons toujours trouver un autre moyen, moins exigeant en termes de calcul, d'effectuer notre tâche sans avoir besoin de calculer explicitement p et q à partir de n .


Pour prouver RSA est cassé, nous devons prouver que l' une façon de le faire est facile.

Pour prouver que RSA est sûr, nous devons prouver que toutes les façons de le faire sont difficiles.


Enfin, votre déclaration n'est pas prouvée car il n'est pas prouvé qu'aucune autre méthode plus simple n'existe pour extraire des informations d'un texte crypté.

Rainer P.
la source
1
Nous pourrions prouver que RSA et l'affacturage sont tout aussi difficiles si nous pouvions produire un algorithme qui peut factoriser les produits de deux grands nombres premiers en générant des messages cryptés RSA spéciaux, en les fissurant, puis en effectuant d'autres calculs. Cela signifierait que RSA n'est pas plus facile que l'affacturage. Cela ne signifie pas que ce soit facile ou difficile.
gnasher729
@ gnasher729 Serait-ce suffisant? Si l'algorithme pouvait factoriser les produits de deux grands nombres premiers, mais pas les produits impliquant plus de 2 nombres premiers, ou les produits impliquant de petits nombres premiers?
otakucode
@Je pense que RSA ne dépend que des facteurs qui sont coprimes. Il serait donc simple de contourner les produits à facteurs multiples.
Taemyr
10

Une autre façon de voir les choses est que la rupture du RSA ne nécessite qu'un cas spécial d'affacturage, qui peut ou non être facile quelle que soit la question générale de l'affacturage.

3

A sonné.
la source
7

Cela signifie que le problème RSA semble (à l'heure actuelle) être plus spécifique que l'affacturage.

pqe,v,mvmemodpq

Le problème de l'affacturage est le suivant: connaître un semi-premier trouver à la fois et .p qpq,pq

Si vous pouvez résoudre efficacement le problème d'affacturage, alors vous pouvez résoudre efficacement le problème RSA: prenez le semi-premier, factorisez-le, utilisez certains théorèmes sur les modules premiers pour calculer un exposant inverse qui révèle tous les textes chiffrés comme . (En fait, ces théorèmes expliquent comment fonctionne la configuration pour RSA: nous connaissons les deux nombres premiers pendant la phase de configuration.)m v ddmvd

Cependant, on ne sait pas que la résolution de ce problème ci-dessus pour les messages arbitraires vous dira quoi que ce soit sur les facteurs du module ou les exposants impliqués. Cela pourrait ou non; nous ne savons pas. De nombreuses personnes intelligentes ont vraisemblablement examiné le problème, mais rien d’évident n’a sauté aux yeux. On ne sait donc pas que le problème de l'affacturage est résolu par des solutions au problème RSA (plus l'effort polynomial), mais seulement que le problème RSA est résolu par des solutions au problème de l'affacturage (plus l'effort polynomial).m

En fait, en 1998, Boneh et Venkatesan ont publié une preuve qu'une certaine classe simple d'algorithmes (plus, temps, exposants, aucun élément de type XOR / NAND) ne peut pas être utilisée pour transformer une solution à problème RSA en algorithme d'affacturage. L'argument avait une ingéniosité simple: en manipulant mathématiquement ces opérations arithmétiques, nous pouvons découvrir que "l'algorithme de réduction" (pour plus de précision: c'est l'algorithme qui utilise un "oracle" RSA pour un semi-prime pour factoriser ce semi-premier) tourne être un algorithme de factorisation à part entière, afin que nous puissions le modifier en une variante qui n'appelle pas son oracle. Nous avons donc une trichotomie: soit (a) il n'y a pas un tel algorithme de réduction, ou (b) l'algorithme de réduction n'a pas une bonne interprétation arithmétique ou (c) la factorisation est en temps polynomial, tout comme l'algorithme de réduction l'était.

CR Drost
la source
«On ne sait pas que trouver cet exposant inverse d à un e donné ne vous dira rien sur les facteurs du module» N'est-ce pas? Vous pouvez calculer et étant donné , etq n e dpqned . L'algorithme exprimé est évidemment PP, n'est-il pas connu pour être en P?
Gilles 'SO- arrête d'être méchant'
@Gilles, je pense que vous avez raison, j'ai donc corrigé ma réponse en conséquence.
CR Drost
3

RSA dépend de deux tâches mathématiques abstraites qui sont considérées comme difficiles: l'affacturage entier, comme vous le savez, mais aussi le problème du logarithme discret . Vous pouvez casser RSA si vous pouvez rapidement factoriser un nombre qui est le produit de deux grands nombres premiers inconnus; mais vous pouvez également casser RSA si vous pouvez trouver rapidement dans le groupe fini , où et sont l'exposant et le module RSA public, et est le texte chiffré.Z m e m ClogeCZmemC

Ces deux tâches mathématiques sont liées, mais (si je me souviens bien), on pense qu'une solution à l'une n'impliquerait pas une solution à l'autre. Je ne sais pas si ce sont les deux seules façons de casser RSA mathématiquement.

zwol
la source
Je pense que vous vous souvenez peut-être mal des choses. Ce ne sont pas vraiment deux problèmes différents: si vous pouvez trouver le modulo log discret , alors vous pouvez factoriser . En d'autres termes, une solution au problème de journal discret implique certainement une solution au problème de factorisation. mmm
DW