Pourquoi les “grands nombres premiers” utilisé dans RSA/le cryptage?
J'ai appris la théorie de la clé publique de chiffrement, mais je suis absent la connexion avec le monde physique. par exemple,
J'ai été dit que la bonne cryptage RSA devrait s'appuyer sur les nombres premiers avec 300 chiffres après la virgule, mais pourquoi? qui est venu avec ce numéro? Combien de temps il faudra pour briser le cryptage (des statistiques sur des machines différentes).
J'ai essayé Google, mais ne pouvais pas trouver ce que je voulais. quelqu'un?
grâce
Veuillez questions d'orientation. J'espère que le changement de titre permettra d'éviter d'être sans pitié downvoted et fermé ..
OriginalL'auteur Yehonatan Ginzberg | 2012-08-06
Vous devez vous connecter pour publier un commentaire.
La clé de chiffrement asymétrique est d'avoir une asymétrie de fonction qui permettent de décrypter le message chiffré par la clé asymétrique, sans permettre de trouver la clé d'autres. En RSA, la fonction utilisée est basée sur la factorisation de nombres premiers, il n'est cependant pas la seule option (Courbe elliptique un d'autre par exemple).
Donc, fondamentalement, vous avez besoin de deux nombres premiers pour générer une paire de clés RSA. Si vous êtes capable de factoriser la clé publique et de trouver ces nombres premiers, vous serez alors en mesure de trouver la clé privée. L'ensemble de la sécurité de RSA est basé sur le fait qu'il n'est pas facile de factoriser de grands nombres composés, c'est pourquoi la longueur de la clé de fortement modifier la robustesse de l'algorithme RSA.
Il y a des compétitions pour factoriser de grands nombres premiers avec des calculatrices chaque années avec de beaux prix. La dernière étape de factoriser de clés RSA a été fait dans 2009 en factorisant 768 bits clés. C'est pourquoi au moins 2048 bits clés doivent être utilisés maintenant.
Comme d'habitude, Wikipedia est une bonne référence dans le RSA.
En effet, corrigé. Merci !
pas vraiment ... la sécurité de RSA est basé sur le fait que vous ne pouvez pas efficacement calculer un inverse modulaire ... dans ce cas, vous devez PHI(n) pour que le calcul lorsque vous n'avez que n avec n=p*q avec p et q inconnu ... si vous trouvez une autre façon de calculer PHI(n) ... autre que (p-1)*(q-1) ... on aurait brisé RSA sans factoriser n ... mais cette tâche est considérée comme au moins aussi difficile que de factoriser n
Je suis un peu en retard à la fête, mais cette réponse vraiment fusionné ma compréhension de RSA.
OriginalL'auteur Nibbler
Tous les algorithmes de clés publiques sont fondées sur trappe fonctions, qui est, de constructions mathématiques qui sont "faciles" à calculer, mais "dur" à l'inverse, sauf si vous avez aussi quelques informations supplémentaires (utilisé comme clé privée), là aussi l'inverse devient "facile".
"Facile" et "difficile" ne sont que qualitatives des adjectifs qui sont toujours plus formellement définie en termes de la complexité algorithmique. "En dur" très souvent fait référence à des calculs qui ne peuvent pas être résolus en temps polynomial O(nx) pour certains x et où n est l'entrée de données.
Dans le cas de RSA, la solution de "facilité" de la fonction est l'exponentiation modulaire C = Me mod N où les facteurs de N sont gardés secrets. Le "dur" problème est de trouver le e-ième racine de C (qui est, M). Bien sûr, "dur" ne signifie pas qu'il est toujours dur, mais (intuitivement) que l'augmentation de la taille de N par un certain facteur augmente la complexité par un bien plus grand facteur.
La taille du module, qui sont recommandés (2048 bits, ou 617 chiffres décimaux) ont trait à la disponibilité de la puissance de calcul à l'heure actuelle, de sorte que si vous vous en tenez à eux, vous êtes assuré qu'il sera extrêmement coûteuse pour l'attaquant de le casser. Pour plus de détails, je vous renvoie à une brillante réponse sur la cryptographie.SE (aller et upvote :-)).
Enfin, afin de disposer d'une trappe, N est construit pour être un nombre composé. C'théorie, pour améliorer les performances, N peut avoir plus de 2 facteurs, mais la règle de sécurité général est que tous les facteurs doivent être équilibrées et ont à peu près la même taille. Cela signifie que si vous avez K facteurs, et N est B bits de long, chaque facteur est à peu près B/K bits longs.
Ce problème à résoudre n'est pas le même que le la factorisation d'entiers problème. Les deux sont liés dans la mesure où si vous réussissez à le facteur N vous pouvez calculer la clé privée par re-faire ce que le parti qui a généré la clé n'. Généralement, l'exposant e utilisé est très faible (3); il ne peut être exclu qu'un jour quelqu'un conçoit un algorithme pour calculer la e-th, et sans tenir compte N.
EDIT: Corrigé le nombre de chiffres après la virgule pour le module d'une clé RSA de 2048 bits.
OriginalL'auteur SquareRootOfTwentyThree
RSA utilise la notion de fonctions mathématiques, de sorte qu'il est facile de chiffrer et de déchiffrer si vous avez la clé, mais dur (comme dans il faut beaucoup, beaucoup de cycles de CPU) pour déchiffrer si vous n'avez pas de clé. Avant même de penser à l'aide de nombres premiers, les mathématiciens ont identifié le besoin d'une fonction.
La première méthode, ils ont frappé sur l'idée que, si votre "clé" est un nombre premier, et votre message est un autre nombre, alors vous pouvez chiffrer en multipliant les deux ensemble. Quelqu'un avec la clé peut facilement diviser le nombre premier et le message, mais pour quelqu'un sans le premier numéro, essayer de comprendre le premier numéro de la clé est dur.
OriginalL'auteur Yusuf X