Question:
L'exposant public RSA doit-il être uniquement dans {3, 5, 17, 257 ou 65537} pour des raisons de sécurité?
Vladislav Rastrusny
2011-03-01 14:59:16 UTC
view on stackexchange narkive permalink

Dans mon projet, j'utilise la valeur d'exposant public de 4451h. Je pensais que c'était sûr et correct jusqu'à ce que je commence à utiliser une bibliothèque de chiffrement RSA commerciale. Si j'utilise cet exposant avec cette bibliothèque, cela lève une exception.

J'ai contacté les développeurs de cette bibliothèque et j'ai obtenu la réponse suivante: "Cette fonctionnalité est destinée à empêcher certaines attaques sur les clés RSA. La conséquence est que l'exposant la valeur est limitée à {3, 5, 17, 257 ou 65537}. La désactivation de cette vérification fait toujours l'objet d'une enquête, car les risques peuvent être importants. "

C'est la première fois de ma vie que j'entends ces valeurs autres que {3, 5, 17, 257 ou 65537} sont utilisés pour interrompre RSA. Je savais seulement que l'utilisation de 3 avec un remplissage incorrect était vulnérable.

Est-ce vraiment le cas? Je peux sûrement utiliser une autre bibliothèque, mais après une telle réponse, je me suis inquiété de la sécurité de ma solution.

Six réponses:
#1
+69
Thomas Pornin
2011-03-01 18:13:06 UTC
view on stackexchange narkive permalink

qui divise le module).

Si vous utilisez un petit exposant et vous n'utilisez aucun remplissage pour le chiffrement et vous cryptez exactement le même message avec plusieurs clés publiques distinctes, alors votre message est en danger: si e = 3 , et vous cryptez le message m avec des clés publiques n1 , n2 et n3 , alors vous avez c i = m 3 mod ni pour i = 1 à 3 . Par le théorème du reste chinois, vous pouvez ensuite reconstruire m3 mod n 1 n 2 n 3 , qui s'avère être m3 (sans aucun modulo) car n 1n2n3 est un entier supérieur. Une extraction de racine cubique (non modulaire) suffit alors pour extraire m.

La faiblesse, ici, n'est pas le petit exposant; il s'agit plutôt de l'utilisation d'un rembourrage inapproprié (à savoir, aucun remplissage) pour le chiffrement. Le remplissage est très important pour la sécurité de RSA, que ce soit le cryptage ou la signature; si vous n'utilisez pas un rembourrage approprié (comme ceux décrits dans PKCS # 1), alors vous avez de nombreuses faiblesses, et celle décrite dans le paragraphe ci-dessus n'est pas de loin la plus importante. Néanmoins, chaque fois que quelqu'un se réfère à une faiblesse liée à la taille de l'exposant, il se réfère plus ou moins directement à cet événement. C'est un peu une tradition ancienne et incorrecte, qui est parfois inversée en une interdiction contre les grands exposants (puisque c'est un mythe, le mythe inversé est aussi un mythe et n'est ni plus ni moins - - justifié); Je crois que c'est ce que vous observez ici.

Cependant, on peut trouver quelques raisons pour lesquelles un grand exposant public doit être évité:

  • Les petits exposants publics favorisent l'efficacité (pour les opérations à clé publique).

  • Le fait d'avoir un petit exposant privé pose des problèmes de sécurité ; une attaque de récupération de clé a été décrite lorsque la longueur de l'exposant privé ne dépasse pas 29% de la longueur de l'exposant public. Lorsque vous voulez forcer l'exposant privé à être court (par exemple pour accélérer les opérations de clé privée), vous devez plus ou moins utiliser un grand exposant public (aussi grand que le module); exiger que l'exposant public soit court peut alors être considéré comme une sorte de contre-mesure indirecte.

  • Certaines implémentations RSA largement déployées s'étouffent sur les grands exposants publics RSA. Par exemple. le code RSA sous Windows (CryptoAPI, utilisé par Internet Explorer pour HTTPS) insiste sur l'encodage de l'exposant public dans un seul mot de 32 bits; il ne peut pas traiter une clé publique avec un exposant public plus grand.

Pourtant, "les risques peuvent être grands" ressemble à la justification générique ("c'est un problème de sécurité" est le façon habituelle de dire "nous ne l'avons pas implémenté mais nous ne voulons admettre aucune sorte de paresse").

Très bien dit. IIRC, à un moment donné dans ses nombreuses incarnations, PGP avait l'habitude de générer un exposant public aléatoire de 16 bits pendant la génération de clé.
Dans un développement époustouflant, cet article est maintenant utilisé pour justifier l'utilisation de 1 comme exposant public https://github.com/saltstack/salt/commit/5dd304276ba5745ec21fc1e6686a0b28da29e6fc#commitcomment-3525158
Pour le bien de la postérité.L'attaque de récupération de clé qui s'applique lors de l'utilisation d'un petit exposant privé (ou d'un grand exposant public) est appelée [attaque de Wiener] (https://en.wikipedia.org/wiki/Wiener's_attack).
#2
+22
D.W.
2011-03-02 12:11:52 UTC
view on stackexchange narkive permalink

Les développeurs sont tout simplement incorrects. Il n'y a rien de mal avec l'exposant 0x4451 (décimal 17489); cela ne crée aucun problème de sécurité.

Il y a longtemps, les gens pensaient que les petits exposants étaient un problème, à cause d'une attaque que Thomas Pornin expliquait en envoyant le même message à plusieurs destinataires. Mais aujourd'hui, nous comprenons que les exposants n'avaient rien à voir avec cela; le problème était un rembourrage inapproprié. Ces attaques sont évitées par une utilisation appropriée du rembourrage. Toute bibliothèque de crypto digne de ce nom ferait bien mieux d'utiliser un rembourrage approprié (sinon vous avez des problèmes bien pires).

Il n'y a donc aucune bonne raison pour une bibliothèque de crypto d'interdire catégoriquement l'utilisation de cet exposant.

Cela dit, du point de vue des performances, plus l'exposant est petit, meilleures sont les performances. Le meilleur choix est e = 3, car cela donne les meilleures performances et ne présente aucun problème de sécurité connu. (En fait, e = 2 est encore un peu mieux. Il est également connu sous le nom de cryptage Rabin. Cependant, ce schéma n'est pas aussi connu et nécessite un code légèrement différent, il n'est donc pas largement utilisé.)

Etes-vous sûr que "e = 2 est encore un peu meilleur" s'applique à RSA? Avec e = 2, il n'y a pas d'inverse car phi (N) est pair.
@Yifan,, vous pouvez commencer par lire https://en.wikipedia.org/wiki/Rabin_cryptosystem.
Pour Rabin, le décryptage est: m = sqrt (c) mod N, étant donné c = m ^ 2 mod N.Pour RSA, le décryptage est: m = c ^ d mod N, étant donné c = m ^ e mod N. Dans le cas de e = 2, il n'y a pas de mod inverse phi (N) (puisque 2 et phi (N) ne sont pas relativement premiers) donc vous ne pouvez pas trouver une annonce telle que e * d = 1 mod phi (N).
@Yifan, oui, je comprends tout cela. Je ne sais pas trop où vous voulez en venir. Je dis que Rabin avec e = 2 est encore un peu meilleur que RSA avec e = 3. Non, Rabin avec e = 2 n'est pas le même que RSA, mais les différences sont un détail qui dépasse le cadre de cette question particulière.
D'accord, c'est la clarification que je voulais. Pour l'œil non averti, votre réponse implique que vous pouvez choisir e = 2 pour RSA.
#3
+19
aaz
2011-03-01 00:39:39 UTC
view on stackexchange narkive permalink

Ces cinq nombres sont des nombres premiers de Fermat.

Comme ils sont de la forme 2 k + 1, chiffrement est me = m · (( m 2 sup>) 2 ... k fois ...) 2 , qui est plus simple et plus rapide que l'exponentiation avec un exposant de taille similaire dans le cas général.

Comme ce sont des nombres premiers, le test que e est coprime à ( p - 1) ( q - 1) est juste un test qui e ne le divise pas.

C'est donc plus probable sur la vitesse ou la convention que sur la sécurité. Non pas qu'il n'y ait rien de mal à être efficace. Mais pour être sûr, demandez une référence comme l ' autre réponse suggérée.

Voir également ce message.

#4
+8
Accipitridae
2011-02-28 23:56:07 UTC
view on stackexchange narkive permalink

Je ne connais aucune raison pour laquelle l'exposant public d'une clé RSA doit être uniquement dans l'ensemble {3,5,17,257,65537}. Comme vous l'avez mentionné, les petits exposants tels que 3 ou 5 sont plus risqués à utiliser, car les effets négatifs des erreurs d'implémentation (comme un remplissage incorrect) peuvent être plus importants. NIST n'autorise que les exposants publics supérieurs à 2 ^ 16, mais je ne connais pas la raison de leur décision.

Vous ne devriez pas être satisfait de la réponse donnée par les développeurs de la bibliothèque que vous utilisez et demandez pour une référence concrète. Trop souvent, il s'avère que certains papiers ont été mal compris. Je pourrais par exemple imaginer qu'un développeur lise la section 4 de l'article «Pouvons-nous faire confiance aux logiciels cryptographiques? Failles cryptographiques dans GNU Privacy Guard v1.2.3» de Phong Nguyen et parvient à une conclusion incorrecte, comme celle ci-dessus. Cet article remarque que lorsque la clé publique générée par GnuPG s'avère être une valeur inhabituelle telle que 65539, l'attaquant apprend alors un peu d'informations sur la clé secrète.La conclusion est que l'algorithme de génération de clé de GnuPG pourrait être amélioré, mais pas que 65539 est une mauvaise clé publique.

#5
+7
Andreas Arnold
2011-03-01 15:43:26 UTC
view on stackexchange narkive permalink

Je n'ai trouvé aucune référence indiquant que les autres valeurs de l'exposant public sont vulnérables. L'utilisation difficile d'un exposant public proche d'une puissance de 2 est recommandée pour des raisons de performances, selon le guide RSA.com de l'algorithme RSA

D'après Wikipedia, NIST n'autorise pas un exposant public inférieur à 65537, car les exposants plus petits posent problème s'ils ne sont pas correctement remplis.

Il s'avère que le dernier paragraphe de cette réponse est carrément faux. (Wikipédia a tort; imaginez ça!) Le problème n'a rien à voir avec les petits exposants. Si vous n'utilisez pas un rembourrage approprié, vous êtes tellement foutu (et cela est vrai quel que soit l'exposant que vous utilisez). Si vous utilisez un rembourrage approprié, les petits exposants sont tout aussi bons que les grands. C'est donc une idée fausse de penser que cela a quelque chose à voir avec la taille de l'exposant, par opposition à la présence / absence de remplissage approprié.
Comme je l'ai dit, avec un rembourrage approprié. Mais j'ai vérifié la source de la déclaration Wikipédia, et c'est partiellement faux. Selon SP 800-78-3 (http://csrc.nist.gov/publications/nistpubs/800-78-3/sp800-78-3.pdf), page 6: "Cette spécification limite également la taille du Exposant RSA qui peut être associé aux clés PIV. Les implémentations de cette spécification doivent choisir un exposant qui est un entier positif impair supérieur ou égal à 65 537 et inférieur à 2256, comme spécifié dans le Tableau 3-2 ". Donc uniquement pour les clés PIV (vérification d'identité personnelle) selon FIPS 201.
#6
-2
FaST4
2018-02-01 15:39:26 UTC
view on stackexchange narkive permalink

Pour citer l'article de Don Coppersmith de 1997 "Petites solutions aux équations polynomiales et vulnérabilités RSA à faible exposant":

Le chiffrement RSA avec l'exposant 3 est vulnérable si l'adversaire connaît les deux tiers du message .

Bien que cela ne pose pas de problème si le schéma de remplissage RSA-OAEP est utilisé, le schéma de remplissage PKCS # 1 (qui est donné comme schéma de remplissage approprié dans les réponses ci-dessous) est vulnérable si l'exposant public 3 est utilisé.

Ce n’est pas tout à fait une réponse.Vous ne vous adressez qu'à un seul exposant, et il y a d'autres réponses publiées des années avant la vôtre qui semblent déjà aborder ce problème de manière beaucoup plus détaillée.Les votes négatifs ne signifient pas nécessairement que vous vous trompez.Les votes négatifs peuvent simplement signifier que votre réponse n'est "pas utile" (selon l'info-bulle), ce avec quoi je serais d'accord dans ce cas.
La réponse précédente indique qu '"il n'y a aucune faiblesse connue pour un exposant public court ou long pour RSA", ce qui est factuellement incorrect.C'est ce que ma réponse essaie de souligner.
Alors, ceci est une réponse à une autre réponse?
Si vous pensez que la réponse acceptée est fausse, veuillez poster un commentaire sur cette réponse.Je suis sûr que Pornin est plus que suffisamment expert pour évaluer.


Ce Q&R a été automatiquement traduit de la langue anglaise.Le contenu original est disponible sur stackexchange, que nous remercions pour la licence cc by-sa 2.0 sous laquelle il est distribué.
Loading...