[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Université de Harvard]
[C'est CS50.] [CS50.TV]
Jetons un coup d'oeil à RSA, un algorithme largement utilisé pour crypter les données.
Les algorithmes de chiffrement, comme César et chiffres Vigenère ne sont pas très sécurisé.
Avec le chiffrement de César, un attaquant n'a besoin que d'essayer 25 touches différentes
pour obtenir un texte clair du message.
Alors que le chiffrement de Vigenère est plus sûr que le chiffrement de César
en raison de la plus grand espace de recherche pour les clés, une fois un attaquant
connaît la longueur de la clé dans un chiffrement de Vigenère,
qui peut être déterminée au moyen d'une analyse des tendances dans le texte chiffré,
le chiffrement de Vigenère n'est pas beaucoup plus sûr que le chiffrement de César.
RSA, d'autre part, n'est pas vulnérable à des attaques de ce genre.
Le chiffre de César et de Vigenère chiffrement utilisent la même clé
pour chiffrer et déchiffrer un message.
Cette propriété rend ces algorithmes algorithmes de chiffrement symétriques clés.
Un problème fondamental avec algorithmes de clés symétriques
est qu'ils reposent sur le chiffrement et l'envoi du message
et l'une de réception et le décryptage du message
avoir déjà accepté dès le départ sur la touche, ils utilisent tous les deux.
Mais nous avons un petit problème de démarrage ici.
Comment puis 2 ordinateurs qui souhaitent communiquer établir une clé secrète entre eux?
Si la clé doit être secret, alors nous devons trouver un moyen pour crypter et décrypter la clé.
Si tout ce que nous avons est symétrique de cryptographie à clé
alors nous revenons au même problème.
RSA, d'autre part, utilise une paire de clés,
une pour le chiffrement et le déchiffrement de l'autre.
L'une est appelée la clé publique, et l'autre est la clé privée.
La clé publique est utilisée pour chiffrer les messages.
Comme vous pouvez le deviner par son nom, nous pouvons partager notre clé publique avec
qui nous voulons sans compromettre la sécurité d'un message chiffré.
Messages chiffrés à l'aide d'une clé publique
peut être déchiffré qu'avec la clé privée correspondante.
Alors que vous pouvez partager votre clé publique, vous devez toujours garder votre clé privée secrète.
et seule la clé privée peut être utilisée pour décrypter des messages
si 2 utilisateurs veulent envoyer des messages chiffrés avec RSA
avant et en arrière les deux utilisateurs ont besoin d'avoir leur propre paire de clés publique et privée.
Messages de l'utilisateur 1 à l'utilisateur 2
utiliser la touche 2 paires de l'utilisateur, et les messages de l'utilisateur 2 utilisateur 1
utiliser une paire de clés de l'utilisateur 1.
Le fait qu'il ya 2 touches séparées pour crypter et décrypter des messages
RSA rend un algorithme à clé asymétrique.
Nous n'avons pas besoin de crypter la clé publique afin de l'envoyer vers un autre ordinateur
car la clé publique n'est de toute façon.
Cela signifie que le RSA n'a pas le même problème de démarrage
que les algorithmes de clé symétrique.
Donc, si je veux envoyer un message en utilisant le cryptage RSA
à Rob, je vais d'abord besoin de la clé publique de Rob.
Pour générer une paire de clés, Rob doit choisir 2 grands nombres premiers.
Ces numéros seront utilisés dans les deux touches les secteurs public et privé,
mais la clé publique utilise uniquement le produit de ces 2 numéros,
pas les chiffres eux-mêmes.
Une fois que j'ai chiffré le message avec la clé publique de Rob
Je peux envoyer le message à Rob.
Pour un ordinateur, le nombre d'affacturage est un problème difficile.
La clé publique, rappelez-vous, a utilisé le produit de 2 nombres premiers.
Ce produit doit alors avoir seulement 2 facteurs,
qui se trouvent être les numéros qui composent la clé privée.
Afin de décrypter le message, RSA va utiliser cette clé privée
ou les nombres multipliés ensemble dans le processus de création de la clé publique.
Parce que c'est difficile de tenir compte de calcul du nombre
utilisé dans une clé publique dans les 2 chiffres utilisés dans la clé privée
il est difficile pour un attaquant de trouver la clé privée
qui est nécessaire pour décrypter le message.
Maintenant, nous allons entrer dans quelques détails de bas niveau du RSA.
Voyons d'abord comment nous pouvons générer une paire de clés.
Tout d'abord, nous aurons besoin de 2 nombres premiers.
Nous appellerons ces 2 nombres p et q.
Afin de choisir p et q, dans la pratique, nous pseudo-aléatoire générer
grand nombre, puis utiliser un test pour déterminer si oui ou non
ces chiffres sont probablement premier.
Nous pouvons continuer à générer des nombres aléatoires, encore et encore
jusqu'à ce que nous avons 2 nombres premiers que nous pouvons utiliser.
Ici, nous allons prendre p = 23 et q = 43.
Rappelez-vous, dans la pratique, p et q doivent être des nombres beaucoup plus grands.
Pour autant que nous savons, plus les numéros, plus il est difficile
pour casser un message crypté.
Mais il est aussi plus cher à crypter et décrypter des messages.
Aujourd'hui, il est souvent recommandé que p et q sont au moins 1024 bits,
qui met chaque nombre à plus de 300 chiffres décimaux.
Mais nous allons chercher ces petits nombres de cet exemple.
Maintenant, nous allons multiplier p et q ensemble pour obtenir un numéro de 3e,
que nous appellerons n.
Dans notre cas, n = 23 * 43, qui = 989.
Nous avons n = 989.
Ensuite, nous allons multiplier p - 1 avec q - 1
pour obtenir un numéro 4, que nous appellerons m.
Dans notre cas, m = 22 * ​​42, qui = 924.
Nous avons m = 924.
Maintenant, il nous faut un nombre e qui est relativement premier avec m
et inférieur à m.
Deux nombres sont premiers entre eux ou premiers entre eux
si le seul entier positif qui les divise à la fois uniforme est 1.
En d'autres termes, le plus grand commun diviseur de e et m
doit être 1.
Dans la pratique, il est fréquent que e soit le nombre premier 65537
aussi longtemps que ce nombre ne pas arriver à être un facteur de m.
Pour nos clés, nous allons prendre e = 5
depuis le 5 est premier avec 924.
Enfin, nous aurons besoin d'un autre numéro, que nous appellerons d.
D doit avoir une certaine valeur qui satisfait l'équation de = 1 (mod m).
Ce mod m signifie que nous allons utiliser quelque chose qui s'appelle l'arithmétique modulaire.
En arithmétique modulaire, une fois un certain nombre devient supérieur à une certaine limite supérieure
il repassera autour de 0.
Une horloge, par exemple, utilise l'arithmétique modulaire.
Une minute après 01h59, par exemple, est 2:00,
pas 1:60.
L'aiguille des minutes a enroulé autour de 0
après avoir atteint une limite supérieure de 60 ans.
Donc, nous pouvons dire 60 est équivalent à 0 (mod 60)
125 et est équivalent à 65 est équivalent à 5 (mod 60).
Notre clé publique sera la paire e et n
dans ce cas, où e est 5 et n est égal à 989.
Notre clé privée sera la paire et d n,
qui dans notre cas est de 185 et 989.
Notez que notre original nombres premiers p et q ne semblent pas
partout dans nos clés privées ou publiques.
Maintenant que nous avons notre paire de clés, nous allons jeter un oeil à la façon dont nous pouvons crypter
et déchiffrer un message.
Je veux envoyer un message à Rob,
alors il sera le seul à générer cette paire de clés.
Alors, je vais demander à Rob pour sa clé publique, que je vais utiliser
pour chiffrer un message pour lui envoyer.
Rappelez-vous, c'est tout à fait correct pour Rob de partager sa clé publique avec moi.
Mais il ne serait pas correct de partager sa clé privée.
Je n'ai pas la moindre idée de ce que sa clé privée est.
Nous pouvons briser notre message m en morceaux plusieurs
tous plus petits que n et ensuite crypter chacun de ces morceaux.
Nous allons crypter le CS50 chaîne, que l'on peut diviser en 4 morceaux,
une par lettre.
Afin de chiffrer mon message, je vais avoir besoin de le convertir en
une sorte de représentation numérique.
Nous allons concaténer les valeurs ASCII avec les personnages de mon message.
Afin de chiffrer un message m donnée
Je vais avoir besoin de calculer c = m à l'e (mod n).
Mais m doit être plus petit que n,
ou bien l'intégralité du message ne peut pas être exprimé modulo n.
Nous pouvons briser m en morceaux, plusieurs qui sont tous plus petits que n,
et crypter chacun de ces morceaux.
Chiffrement chacun de ces morceaux, on obtient c1 = 67 à la 5 (mod 989)
qui = 658.
Pour notre deuxième fragment, nous avons 83 à la 5 (mod 989)
qui = 15.
Pour notre morceau Notre troisième 53 à la 5 (mod 989)
qui = 799.
Et enfin, pour notre dernier morceau, nous avons 48 à la 5 (mod 989)
qui = 975.
Maintenant, nous pouvons envoyer plus de ces valeurs chiffrées à Rob.
Ici, vous allez, Rob.
Alors que notre message est en vol, nous allons jeter un autre regard
comment nous sommes arrivés à cette valeur pour d.
Notre nombre d nécessaire pour satisfaire 5d = 1 (mod 924).
Ce qui rend d l'inverse multiplicatif de 5 modulo 924.
Compte tenu de 2 entiers, a et b, l'algorithme d'Euclide étendu
peut être utilisé pour trouver le plus grand commun diviseur des entiers 2.
Il nous donnera également d'autres numéros 2, x et y,
qui satisfont l'équation ax + by = plus grand commun diviseur de a et b.
Comment en sommes-nous aider?
Eh bien, en branchant e = 5 pour une
et m = 924 pour b
nous savons déjà que ces nombres sont premiers entre eux.
Leur plus grand diviseur commun est 1.
Cela nous donne 5x + 924y = 1
ou 5x = 1 - 924y.
Mais si l'on ne se soucient tout modulo 924
alors nous pouvons laisser tomber le - 924y.
Pensez à l'horloge.
Si l'aiguille des minutes est sur 1, puis exactement 10 heures se sont écoulées,
nous savons que l'aiguille des minutes sera toujours sur le 1.
Ici, nous commençons à 1, puis enrouler autour de fois exactement y,
donc nous allons encore à 1.
Nous avons 5x = 1 (mod 924).
Et voici ce x est le même que celui d que nous recherchions avant,
si nous utilisons l'algorithme d'Euclide étendu
pour obtenir ce nombre x, c'est le nombre que nous devrions utiliser comme notre d.
Maintenant, nous allons exécuter l'algorithme d'Euclide étendu pour 5 =
et b = 924.
Nous allons utiliser une méthode appelée la méthode de la table.
Notre table aura 4 colonnes, x, y, d et k.
Notre table commence avec 2 rangées.
Dans la première ligne, nous avons 1, 0, puis notre valeur de a, qui est de 5,
et notre deuxième rangée est 0, 1, et notre valeur de b, qui est 924.
La valeur de la 4ème colonne, k, sera le résultat
de division de la valeur de d dans la ligne au-dessus de la valeur de d
sur la même ligne.
Nous avons 5 divisé par 924 est 0 avec quelque reste.
Cela signifie que nous avons k = 0.
Maintenant, la valeur de toutes les autres cellules sera la valeur des 2 cellules rangées au-dessus il
moins la valeur de la ligne au-dessus k fois.
Commençons par d dans la 3e rangée.
Nous avons 5 à 924 * 0 = 5.
Ensuite, nous avons 0 à 1 * 0 qui vaut 0
et 1 - 0 * 0 qui est 1.
Pas trop mal, nous allons donc passer à la ligne suivante.
Nous avons d'abord besoin de notre valeur de k.
924 divisé par 5 = 184 avec quelques autres,
si notre valeur pour k est de 184.
Maintenant 924 à 5 * 184 = 4.
1 à 0 * 184 = 1 et de 0 à 1 184 * -184 est.
Très bien, nous allons faire la rangée suivante.
Notre valeur de k sera 1 car
5 divisé par 4 = 1 avec quelques autres.
Nous allons remplir les autres colonnes.
5 à 4 * 1 = 1.
0 à 1 * 1 = -1.
Et 1 - 184 * 1 est 185.
Voyons voir ce que notre prochaine valeur de k serait.
Eh bien, il semble que nous ayons 4 divisé par 1, qui est de 4.
Dans ce cas où on divisant par 1 tel que k est égal à
la valeur de d à la ligne ci-dessus signifie que nous en avons fini avec notre algorithme.
Nous pouvons voir ici que nous avons x = 185 et y = -1 dans la dernière rangée.
Nous allons maintenant revenir à notre objectif initial.
Nous avons dit que la valeur de x en tant que résultat de l'exécution de cet algorithme
serait l'inverse multiplicatif d'un (mod b).
Qui signifie que 185 est l'inverse multiplicatif de 5 (mod 924)
ce qui signifie que nous avons une valeur de 185 pour d.
Le fait que d = 1 dans la dernière rangée
vérifie que e est premier avec m.
Si ce n'était pas 1 alors nous aurions à choisir un nouvel e.
Maintenant, nous allons voir si Rob a reçu mon message.
Quand quelqu'un m'envoie un message crypté
aussi longtemps que j'ai gardé ma clé privée secrète
Je suis le seul qui peut déchiffrer le message.
Pour déchiffrer un morceau c je peux calculer le message original
est égale à la puissance morceau de d (mod n).
Rappelez-vous que d et n sont de ma clé privée.
Pour obtenir un message plein de ses morceaux que nous déchiffrer chaque bloc
et concaténer les résultats.
Exactement comment est sécurisé RSA?
La vérité est que nous ne savons pas.
La sécurité est basée sur le temps qu'il faudrait à un pirate de se fissurer un message
chiffré avec RSA.
Rappelez-vous que l'attaquant a accès à votre clé publique,
qui contient à la fois e et n.
Si l'attaquant parvient à tenir compte dans ses 2 n nombres premiers, p et q,
alors elle pourrait calculer d en utilisant l'algorithme d'Euclide étendu.
Cela lui donne la clé privée, qui peut être utilisée pour déchiffrer n'importe quel message.
Mais comment peut-on tenir compte rapidement des entiers?
Encore une fois, nous ne savons pas.
Personne n'a trouvé un moyen rapide de le faire,
ce qui signifie que, étant donné n assez grand
il faudrait un attaquant excessivement longue
prendre en compte le nombre.
Si quelqu'un a révélé un moyen rapide d'entiers d'affacturage
RSA serait rompu.
Mais même si la factorisation des entiers est intrinsèquement lent
l'algorithme RSA peut toujours avoir une faille dans l'
qui permet le décryptage des messages facile.
Personne n'a trouvé et révélé une telle faille encore,
mais cela ne veut pas dire qu'il n'existe pas.
En théorie, quelqu'un pourrait être là la lecture de toutes les données chiffrées avec RSA.
Il ya une autre sorte de problème de confidentialité.
Si Tommy crypte quelque message en utilisant ma clé publique
et un attaquant crypte le même message en utilisant ma clé publique
l'attaquant verrez que les 2 messages sont identiques
et donc savoir ce que Tommy cryptées.
Afin d'éviter cela, les messages sont généralement complétée par des bits aléatoires
avant d'être chiffré de sorte que le même message chiffré
plusieurs fois sera différente dans la mesure où le remplissage du message est différent.
Mais rappelez-vous comment nous devons diviser en morceaux messages
de sorte que chaque bloc est plus petit que n?
Rembourrage les morceaux signifie que nous pourrions avoir à diviser les choses
en morceaux encore plus depuis le morceau rembourrée doit être inférieur à n.
Le cryptage et le décryptage sont relativement chers avec RSA,
et ainsi avoir besoin de briser un message en morceaux beaucoup peut être très coûteux.
Si un grand volume de données doivent être chiffrées et déchiffrées
nous pouvons combiner les avantages des algorithmes de clés symétriques
avec ceux de RSA pour obtenir à la fois la sécurité et l'efficacité.
Bien que nous ne pourrons pas y entrer ici,
AES est un algorithme à clé symétrique comme le Vigenère et chiffres César
mais beaucoup plus difficile à casser.
Bien sûr, nous ne pouvons pas utiliser AES sans établir une clé secrète partagée
entre les 2 systèmes, et nous avons vu le problème avec ça avant.
Mais maintenant nous pouvons utiliser RSA pour établir la clé secrète partagée entre les 2 systèmes.
Nous allons appeler l'ordinateur qui envoie les données de l'expéditeur
et l'ordinateur recevant les données du récepteur.
Le récepteur possède une paire de clés RSA et envoie
la clé publique de l'expéditeur.
L'expéditeur génère une clé AES,
le chiffre avec le récepteur RSA à clé publique,
et envoie la clé AES au récepteur.
Le récepteur déchiffre le message avec sa clé privée RSA.
L'expéditeur et le récepteur ont maintenant une clé partagée AES entre eux.
AES, ce qui est beaucoup plus rapide au chiffrement et le déchiffrement de RSA,
peut maintenant être utilisé pour chiffrer les gros volumes de données et de les envoyer au récepteur,
qui peut déchiffrer à l'aide de la même clé.
AES, ce qui est beaucoup plus rapide au chiffrement et le déchiffrement de RSA,
peut maintenant être utilisé pour chiffrer les gros volumes de données et de les envoyer au récepteur,
qui peut déchiffrer à l'aide de la même clé.
Nous avons juste besoin RSA pour transférer la clé partagée.
Nous n'avons plus besoin d'utiliser RSA du tout.
On dirait que j'ai un message.
Ce n'est pas grave si quelqu'un lire ce qui est sur l'avion en papier avant de le prendre
parce que je suis le seul à avoir la clé privée.
Nous allons décrypter chacun des segments dans le message.
Le premier morceau, 658, nous élever à la puissance d, qui est de 185,
mod n, qui est 989, est égal à 67,
qui est la lettre C en ASCII.
Maintenant, sur le morceau seconde.
Le deuxième fragment a de la valeur 15,
dont nous élever à la puissance 185e,
mod 989, et ceci est égal à 83
qui est la lettre S en ASCII.
Maintenant, pour le morceau tiers, ce qui a de la valeur 799, nous élevons à 185,
mod 989, et ceci est égal à 53,
qui est la valeur du caractère ASCII en 5.
Maintenant, pour le dernier morceau, qui a de la valeur 975,
nous élevons à 185, mod 989,
et ceci est égal à 48, qui est la valeur du 0 caractère ASCII.
Mon nom est Rob Bowden, et c'est CS50.
[CS50.TV]
RSA du tout.
RSA du tout. [Rires]
Pas du tout.