1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [RSA]

2
00:00:02,000 --> 00:00:04,000
[Rob Bowden] [Tommy MacWilliam] [Université de Harvard]

3
00:00:04,000 --> 00:00:07,000
[C'est CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:11,000
Jetons un coup d'oeil à RSA, un algorithme largement utilisé pour crypter les données.

5
00:00:11,000 --> 00:00:16,000
Les algorithmes de chiffrement, comme César et chiffres Vigenère ne sont pas très sécurisé.

6
00:00:16,000 --> 00:00:20,000
Avec le chiffrement de César, un attaquant n'a besoin que d'essayer 25 touches différentes

7
00:00:20,000 --> 00:00:22,000
pour obtenir un texte clair du message.

8
00:00:22,000 --> 00:00:25,000
Alors que le chiffrement de Vigenère est plus sûr que le chiffrement de César

9
00:00:25,000 --> 00:00:28,000
en raison de la plus grand espace de recherche pour les clés, une fois un attaquant

10
00:00:28,000 --> 00:00:30,000
connaît la longueur de la clé dans un chiffrement de Vigenère,

11
00:00:30,000 --> 00:00:34,000
qui peut être déterminée au moyen d'une analyse des tendances dans le texte chiffré,

12
00:00:34,000 --> 00:00:38,000
le chiffrement de Vigenère n'est pas beaucoup plus sûr que le chiffrement de César.

13
00:00:38,000 --> 00:00:42,000
RSA, d'autre part, n'est pas vulnérable à des attaques de ce genre.

14
00:00:42,000 --> 00:00:45,000
Le chiffre de César et de Vigenère chiffrement utilisent la même clé

15
00:00:45,000 --> 00:00:47,000
pour chiffrer et déchiffrer un message.

16
00:00:47,000 --> 00:00:51,000
Cette propriété rend ces algorithmes algorithmes de chiffrement symétriques clés.

17
00:00:51,000 --> 00:00:54,000
Un problème fondamental avec algorithmes de clés symétriques

18
00:00:54,000 --> 00:00:57,000
est qu'ils reposent sur le chiffrement et l'envoi du message

19
00:00:57,000 --> 00:00:59,000
et l'une de réception et le décryptage du message

20
00:00:59,000 --> 00:01:03,000
avoir déjà accepté dès le départ sur la touche, ils utilisent tous les deux.

21
00:01:03,000 --> 00:01:06,000
Mais nous avons un petit problème de démarrage ici.

22
00:01:06,000 --> 00:01:10,000
Comment puis 2 ordinateurs qui souhaitent communiquer établir une clé secrète entre eux?

23
00:01:10,000 --> 00:01:16,000
Si la clé doit être secret, alors nous devons trouver un moyen pour crypter et décrypter la clé.

24
00:01:16,000 --> 00:01:18,000
Si tout ce que nous avons est symétrique de cryptographie à clé

25
00:01:18,000 --> 00:01:21,000
alors nous revenons au même problème.

26
00:01:21,000 --> 00:01:25,000
RSA, d'autre part, utilise une paire de clés,

27
00:01:25,000 --> 00:01:28,000
une pour le chiffrement et le déchiffrement de l'autre.

28
00:01:28,000 --> 00:01:32,000
L'une est appelée la clé publique, et l'autre est la clé privée.

29
00:01:32,000 --> 00:01:34,000
La clé publique est utilisée pour chiffrer les messages.

30
00:01:34,000 --> 00:01:38,000
Comme vous pouvez le deviner par son nom, nous pouvons partager notre clé publique avec

31
00:01:38,000 --> 00:01:43,000
qui nous voulons sans compromettre la sécurité d'un message chiffré.

32
00:01:43,000 --> 00:01:45,000
Messages chiffrés à l'aide d'une clé publique

33
00:01:45,000 --> 00:01:49,000
peut être déchiffré qu'avec la clé privée correspondante.

34
00:01:49,000 --> 00:01:53,000
Alors que vous pouvez partager votre clé publique, vous devez toujours garder votre clé privée secrète.

61
00:01:55,000 --> 00:01:58,000
et seule la clé privée peut être utilisée pour décrypter des messages

62
00:01:58,000 --> 00:02:02,000
si 2 utilisateurs veulent envoyer des messages chiffrés avec RSA

63
00:02:02,000 --> 00:02:07,000
avant et en arrière les deux utilisateurs ont besoin d'avoir leur propre paire de clés publique et privée.

64
00:02:07,000 --> 00:02:10,000
Messages de l'utilisateur 1 à l'utilisateur 2

65
00:02:10,000 --> 00:02:15,000
utiliser la touche 2 paires de l'utilisateur, et les messages de l'utilisateur 2 utilisateur 1

66
00:02:15,000 --> 00:02:17,000
utiliser une paire de clés de l'utilisateur 1.

67
00:02:17,000 --> 00:02:21,000
Le fait qu'il ya 2 touches séparées pour crypter et décrypter des messages

68
00:02:21,000 --> 00:02:24,000
RSA rend un algorithme à clé asymétrique.

69
00:02:24,000 --> 00:02:28,000
Nous n'avons pas besoin de crypter la clé publique afin de l'envoyer vers un autre ordinateur

70
00:02:28,000 --> 00:02:31,000
car la clé publique n'est de toute façon.

71
00:02:31,000 --> 00:02:33,000
Cela signifie que le RSA n'a pas le même problème de démarrage

72
00:02:33,000 --> 00:02:36,000
que les algorithmes de clé symétrique.

73
00:02:36,000 --> 00:02:39,000
Donc, si je veux envoyer un message en utilisant le cryptage RSA

74
00:02:39,000 --> 00:02:42,000
à Rob, je vais d'abord besoin de la clé publique de Rob.

75
00:02:42,000 --> 00:02:47,000
Pour générer une paire de clés, Rob doit choisir 2 grands nombres premiers.

76
00:02:47,000 --> 00:02:50,000
Ces numéros seront utilisés dans les deux touches les secteurs public et privé,

77
00:02:50,000 --> 00:02:54,000
mais la clé publique utilise uniquement le produit de ces 2 numéros,

78
00:02:54,000 --> 00:02:56,000
pas les chiffres eux-mêmes.

79
00:02:56,000 --> 00:02:59,000
Une fois que j'ai chiffré le message avec la clé publique de Rob

80
00:02:59,000 --> 00:03:01,000
Je peux envoyer le message à Rob.

81
00:03:01,000 --> 00:03:05,000
Pour un ordinateur, le nombre d'affacturage est un problème difficile.

82
00:03:05,000 --> 00:03:09,000
La clé publique, rappelez-vous, a utilisé le produit de 2 nombres premiers.

83
00:03:09,000 --> 00:03:12,000
Ce produit doit alors avoir seulement 2 facteurs,

84
00:03:12,000 --> 00:03:16,000
qui se trouvent être les numéros qui composent la clé privée.

85
00:03:16,000 --> 00:03:20,000
Afin de décrypter le message, RSA va utiliser cette clé privée

86
00:03:20,000 --> 00:03:25,000
ou les nombres multipliés ensemble dans le processus de création de la clé publique.

87
00:03:25,000 --> 00:03:28,000
Parce que c'est difficile de tenir compte de calcul du nombre

88
00:03:28,000 --> 00:03:32,000
utilisé dans une clé publique dans les 2 chiffres utilisés dans la clé privée

89
00:03:32,000 --> 00:03:36,000
il est difficile pour un attaquant de trouver la clé privée

90
00:03:36,000 --> 00:03:39,000
qui est nécessaire pour décrypter le message.

91
00:03:39,000 --> 00:03:43,000
Maintenant, nous allons entrer dans quelques détails de bas niveau du RSA.

92
00:03:43,000 --> 00:03:46,000
Voyons d'abord comment nous pouvons générer une paire de clés.

93
00:03:46,000 --> 00:03:49,000
Tout d'abord, nous aurons besoin de 2 nombres premiers.

94
00:03:49,000 --> 00:03:52,000
Nous appellerons ces 2 nombres p et q.

95
00:03:52,000 --> 00:03:56,000
Afin de choisir p et q, dans la pratique, nous pseudo-aléatoire générer

96
00:03:56,000 --> 00:03:59,000
grand nombre, puis utiliser un test pour déterminer si oui ou non

97
00:03:59,000 --> 00:04:02,000
ces chiffres sont probablement premier.

98
00:04:02,000 --> 00:04:05,000
Nous pouvons continuer à générer des nombres aléatoires, encore et encore

99
00:04:05,000 --> 00:04:08,000
jusqu'à ce que nous avons 2 nombres premiers que nous pouvons utiliser.

100
00:04:08,000 --> 00:04:15,000
Ici, nous allons prendre p = 23 et q = 43.

101
00:04:15,000 --> 00:04:19,000
Rappelez-vous, dans la pratique, p et q doivent être des nombres beaucoup plus grands.

102
00:04:19,000 --> 00:04:22,000
Pour autant que nous savons, plus les numéros, plus il est difficile

103
00:04:22,000 --> 00:04:25,000
pour casser un message crypté.

104
00:04:25,000 --> 00:04:29,000
Mais il est aussi plus cher à crypter et décrypter des messages.

105
00:04:29,000 --> 00:04:33,000
Aujourd'hui, il est souvent recommandé que p et q sont au moins 1024 bits,

106
00:04:33,000 --> 00:04:37,000
qui met chaque nombre à plus de 300 chiffres décimaux.

107
00:04:37,000 --> 00:04:40,000
Mais nous allons chercher ces petits nombres de cet exemple.

108
00:04:40,000 --> 00:04:43,000
Maintenant, nous allons multiplier p et q ensemble pour obtenir un numéro de 3e,

109
00:04:43,000 --> 00:04:45,000
que nous appellerons n.

110
00:04:45,000 --> 00:04:55,000
Dans notre cas, n = 23 * 43, qui = 989.

111
00:04:55,000 --> 00:04:58,000
Nous avons n = 989.

112
00:04:58,000 --> 00:05:02,000
Ensuite, nous allons multiplier p - 1 avec q - 1

113
00:05:02,000 --> 00:05:05,000
pour obtenir un numéro 4, que nous appellerons m.

114
00:05:05,000 --> 00:05:15,000
Dans notre cas, m = 22 * ​​42, qui = 924.

115
00:05:15,000 --> 00:05:18,000
Nous avons m = 924.

116
00:05:18,000 --> 00:05:22,000
Maintenant, il nous faut un nombre e qui est relativement premier avec m

117
00:05:22,000 --> 00:05:25,000
et inférieur à m.

118
00:05:25,000 --> 00:05:28,000
Deux nombres sont premiers entre eux ou premiers entre eux

119
00:05:28,000 --> 00:05:33,000
si le seul entier positif qui les divise à la fois uniforme est 1.

120
00:05:33,000 --> 00:05:37,000
En d'autres termes, le plus grand commun diviseur de e et m

121
00:05:37,000 --> 00:05:39,000
doit être 1.

122
00:05:39,000 --> 00:05:44,000
Dans la pratique, il est fréquent que e soit le nombre premier 65537

123
00:05:44,000 --> 00:05:48,000
aussi longtemps que ce nombre ne pas arriver à être un facteur de m.

124
00:05:48,000 --> 00:05:53,000
Pour nos clés, nous allons prendre e = 5

125
00:05:53,000 --> 00:05:57,000
depuis le 5 est premier avec 924.

126
00:05:57,000 --> 00:06:01,000
Enfin, nous aurons besoin d'un autre numéro, que nous appellerons d.

127
00:06:01,000 --> 00:06:11,000
D doit avoir une certaine valeur qui satisfait l'équation de = 1 (mod m).

128
00:06:11,000 --> 00:06:17,000
Ce mod m signifie que nous allons utiliser quelque chose qui s'appelle l'arithmétique modulaire.

129
00:06:17,000 --> 00:06:21,000
En arithmétique modulaire, une fois un certain nombre devient supérieur à une certaine limite supérieure

130
00:06:21,000 --> 00:06:24,000
il repassera autour de 0.

131
00:06:24,000 --> 00:06:27,000
Une horloge, par exemple, utilise l'arithmétique modulaire.

132
00:06:27,000 --> 00:06:31,000
Une minute après 01h59, par exemple, est 2:00,

133
00:06:31,000 --> 00:06:33,000
pas 1:60.

134
00:06:33,000 --> 00:06:36,000
L'aiguille des minutes a enroulé autour de 0

135
00:06:36,000 --> 00:06:39,000
après avoir atteint une limite supérieure de 60 ans.

136
00:06:39,000 --> 00:06:46,000
Donc, nous pouvons dire 60 est équivalent à 0 (mod 60)

137
00:06:46,000 --> 00:06:57,000
125 et est équivalent à 65 est équivalent à 5 (mod 60).

138
00:06:57,000 --> 00:07:02,000
Notre clé publique sera la paire e et n

139
00:07:02,000 --> 00:07:09,000
dans ce cas, où e est 5 et n est égal à 989.

140
00:07:09,000 --> 00:07:15,000
Notre clé privée sera la paire et d n,

141
00:07:15,000 --> 00:07:22,000
qui dans notre cas est de 185 et 989.

142
00:07:22,000 --> 00:07:25,000
Notez que notre original nombres premiers p et q ne semblent pas

143
00:07:25,000 --> 00:07:29,000
partout dans nos clés privées ou publiques.

144
00:07:29,000 --> 00:07:33,000
Maintenant que nous avons notre paire de clés, nous allons jeter un oeil à la façon dont nous pouvons crypter

145
00:07:33,000 --> 00:07:36,000
et déchiffrer un message.

146
00:07:36,000 --> 00:07:38,000
Je veux envoyer un message à Rob,

147
00:07:38,000 --> 00:07:42,000
alors il sera le seul à générer cette paire de clés.

148
00:07:42,000 --> 00:07:46,000
Alors, je vais demander à Rob pour sa clé publique, que je vais utiliser

149
00:07:46,000 --> 00:07:48,000
pour chiffrer un message pour lui envoyer.

150
00:07:48,000 --> 00:07:53,000
Rappelez-vous, c'est tout à fait correct pour Rob de partager sa clé publique avec moi.

151
00:07:53,000 --> 00:07:56,000
Mais il ne serait pas correct de partager sa clé privée.

152
00:07:56,000 --> 00:08:00,000
Je n'ai pas la moindre idée de ce que sa clé privée est.

153
00:08:00,000 --> 00:08:03,000
Nous pouvons briser notre message m en morceaux plusieurs

154
00:08:03,000 --> 00:08:07,000
tous plus petits que n et ensuite crypter chacun de ces morceaux.

155
00:08:07,000 --> 00:08:12,000
Nous allons crypter le CS50 chaîne, que l'on peut diviser en 4 morceaux,

156
00:08:12,000 --> 00:08:14,000
une par lettre.

157
00:08:14,000 --> 00:08:17,000
Afin de chiffrer mon message, je vais avoir besoin de le convertir en

158
00:08:17,000 --> 00:08:20,000
une sorte de représentation numérique.

159
00:08:20,000 --> 00:08:25,000
Nous allons concaténer les valeurs ASCII avec les personnages de mon message.

160
00:08:25,000 --> 00:08:28,000
Afin de chiffrer un message m donnée

161
00:08:28,000 --> 00:08:37,000
Je vais avoir besoin de calculer c = m à l'e (mod n).

162
00:08:37,000 --> 00:08:40,000
Mais m doit être plus petit que n,

163
00:08:40,000 --> 00:08:45,000
ou bien l'intégralité du message ne peut pas être exprimé modulo n.

164
00:08:45,000 --> 00:08:49,000
Nous pouvons briser m en morceaux, plusieurs qui sont tous plus petits que n,

165
00:08:49,000 --> 00:08:52,000
et crypter chacun de ces morceaux.

166
00:08:52,000 --> 00:09:03,000
Chiffrement chacun de ces morceaux, on obtient c1 = 67 à la 5 (mod 989)

167
00:09:03,000 --> 00:09:06,000
qui = 658.

168
00:09:06,000 --> 00:09:15,000
Pour notre deuxième fragment, nous avons 83 à la 5 (mod 989)

169
00:09:15,000 --> 00:09:18,000
qui = 15.

170
00:09:18,000 --> 00:09:26,000
Pour notre morceau Notre troisième 53 à la 5 (mod 989)

171
00:09:26,000 --> 00:09:30,000
qui = 799.

172
00:09:30,000 --> 00:09:39,000
Et enfin, pour notre dernier morceau, nous avons 48 à la 5 (mod 989)

173
00:09:39,000 --> 00:09:43,000
qui = 975.

174
00:09:43,000 --> 00:09:48,000
Maintenant, nous pouvons envoyer plus de ces valeurs chiffrées à Rob.

175
00:09:54,000 --> 00:09:58,000
Ici, vous allez, Rob.

176
00:09:58,000 --> 00:10:01,000
Alors que notre message est en vol, nous allons jeter un autre regard

177
00:10:01,000 --> 00:10:07,000
comment nous sommes arrivés à cette valeur pour d.

178
00:10:07,000 --> 00:10:17,000
Notre nombre d nécessaire pour satisfaire 5d = 1 (mod 924).

179
00:10:17,000 --> 00:10:24,000
Ce qui rend d l'inverse multiplicatif de 5 modulo 924.

180
00:10:24,000 --> 00:10:28,000
Compte tenu de 2 entiers, a et b, l'algorithme d'Euclide étendu

181
00:10:28,000 --> 00:10:33,000
peut être utilisé pour trouver le plus grand commun diviseur des entiers 2.

182
00:10:33,000 --> 00:10:37,000
Il nous donnera également d'autres numéros 2, x et y,

183
00:10:37,000 --> 00:10:47,000
qui satisfont l'équation ax + by = plus grand commun diviseur de a et b.

184
00:10:47,000 --> 00:10:49,000
Comment en sommes-nous aider?

185
00:10:49,000 --> 00:10:52,000
Eh bien, en branchant e = 5 pour une

186
00:10:52,000 --> 00:10:56,000
et m = 924 pour b

187
00:10:56,000 --> 00:10:59,000
nous savons déjà que ces nombres sont premiers entre eux.

188
00:10:59,000 --> 00:11:03,000
Leur plus grand diviseur commun est 1.

189
00:11:03,000 --> 00:11:09,000
Cela nous donne 5x + 924y = 1

190
00:11:09,000 --> 00:11:17,000
ou 5x = 1 - 924y.

191
00:11:17,000 --> 00:11:22,000
Mais si l'on ne se soucient tout modulo 924

192
00:11:22,000 --> 00:11:25,000
alors nous pouvons laisser tomber le - 924y.

193
00:11:25,000 --> 00:11:27,000
Pensez à l'horloge.

194
00:11:27,000 --> 00:11:31,000
Si l'aiguille des minutes est sur 1, puis exactement 10 heures se sont écoulées,

195
00:11:31,000 --> 00:11:35,000
nous savons que l'aiguille des minutes sera toujours sur le 1.

196
00:11:35,000 --> 00:11:39,000
Ici, nous commençons à 1, puis enrouler autour de fois exactement y,

197
00:11:39,000 --> 00:11:41,000
donc nous allons encore à 1.

198
00:11:41,000 --> 00:11:49,000
Nous avons 5x = 1 (mod 924).

199
00:11:49,000 --> 00:11:55,000
Et voici ce x est le même que celui d que nous recherchions avant,

200
00:11:55,000 --> 00:11:58,000
si nous utilisons l'algorithme d'Euclide étendu

201
00:11:58,000 --> 00:12:04,000
pour obtenir ce nombre x, c'est le nombre que nous devrions utiliser comme notre d.

202
00:12:04,000 --> 00:12:07,000
Maintenant, nous allons exécuter l'algorithme d'Euclide étendu pour 5 =

203
00:12:07,000 --> 00:12:11,000
et b = 924.

204
00:12:11,000 --> 00:12:14,000
Nous allons utiliser une méthode appelée la méthode de la table.

205
00:12:14,000 --> 00:12:21,000
Notre table aura 4 colonnes, x, y, d et k.

206
00:12:21,000 --> 00:12:23,000
Notre table commence avec 2 rangées.

207
00:12:23,000 --> 00:12:28,000
Dans la première ligne, nous avons 1, 0, puis notre valeur de a, qui est de 5,

208
00:12:28,000 --> 00:12:37,000
et notre deuxième rangée est 0, 1, et notre valeur de b, qui est 924.

209
00:12:37,000 --> 00:12:40,000
La valeur de la 4ème colonne, k, sera le résultat

210
00:12:40,000 --> 00:12:45,000
de division de la valeur de d dans la ligne au-dessus de la valeur de d

211
00:12:45,000 --> 00:12:49,000
sur la même ligne.

212
00:12:49,000 --> 00:12:56,000
Nous avons 5 divisé par 924 est 0 avec quelque reste.

213
00:12:56,000 --> 00:12:59,000
Cela signifie que nous avons k = 0.

214
00:12:59,000 --> 00:13:05,000
Maintenant, la valeur de toutes les autres cellules sera la valeur des 2 cellules rangées au-dessus il

215
00:13:05,000 --> 00:13:09,000
moins la valeur de la ligne au-dessus k fois.

216
00:13:09,000 --> 00:13:11,000
Commençons par d dans la 3e rangée.

217
00:13:11,000 --> 00:13:19,000
Nous avons 5 à 924 * 0 = 5.

218
00:13:19,000 --> 00:13:25,000
Ensuite, nous avons 0 à 1 * 0 qui vaut 0

219
00:13:25,000 --> 00:13:30,000
et 1 - 0 * 0 qui est 1.

220
00:13:30,000 --> 00:13:33,000
Pas trop mal, nous allons donc passer à la ligne suivante.

221
00:13:33,000 --> 00:13:36,000
Nous avons d'abord besoin de notre valeur de k.

222
00:13:36,000 --> 00:13:43,000
924 divisé par 5 = 184 avec quelques autres,

223
00:13:43,000 --> 00:13:46,000
si notre valeur pour k est de 184.

224
00:13:46,000 --> 00:13:54,000
Maintenant 924 à 5 * 184 = 4.

225
00:13:54,000 --> 00:14:05,000
1 à 0 * 184 = 1 et de 0 à 1 184 * -184 est.

226
00:14:05,000 --> 00:14:07,000
Très bien, nous allons faire la rangée suivante.

227
00:14:07,000 --> 00:14:10,000
Notre valeur de k sera 1 car

228
00:14:10,000 --> 00:14:15,000
5 divisé par 4 = 1 avec quelques autres.

229
00:14:15,000 --> 00:14:17,000
Nous allons remplir les autres colonnes.

230
00:14:17,000 --> 00:14:21,000
5 à 4 * 1 = 1.

231
00:14:21,000 --> 00:14:25,000
0 à 1 * 1 = -1.

232
00:14:25,000 --> 00:14:33,000
Et 1 - 184 * 1 est 185.

233
00:14:33,000 --> 00:14:35,000
Voyons voir ce que notre prochaine valeur de k serait.

234
00:14:35,000 --> 00:14:40,000
Eh bien, il semble que nous ayons 4 divisé par 1, qui est de 4.

235
00:14:40,000 --> 00:14:43,000
Dans ce cas où on divisant par 1 tel que k est égal à

236
00:14:43,000 --> 00:14:50,000
la valeur de d à la ligne ci-dessus signifie que nous en avons fini avec notre algorithme.

237
00:14:50,000 --> 00:14:58,000
Nous pouvons voir ici que nous avons x = 185 et y = -1 dans la dernière rangée.

238
00:14:58,000 --> 00:15:00,000
Nous allons maintenant revenir à notre objectif initial.

239
00:15:00,000 --> 00:15:04,000
Nous avons dit que la valeur de x en tant que résultat de l'exécution de cet algorithme

240
00:15:04,000 --> 00:15:08,000
serait l'inverse multiplicatif d'un (mod b).

241
00:15:08,000 --> 00:15:15,000
Qui signifie que 185 est l'inverse multiplicatif de 5 (mod 924)

242
00:15:15,000 --> 00:15:20,000
ce qui signifie que nous avons une valeur de 185 pour d.

243
00:15:20,000 --> 00:15:23,000
Le fait que d = 1 dans la dernière rangée

244
00:15:23,000 --> 00:15:26,000
vérifie que e est premier avec m.

245
00:15:26,000 --> 00:15:30,000
Si ce n'était pas 1 alors nous aurions à choisir un nouvel e.

246
00:15:30,000 --> 00:15:33,000
Maintenant, nous allons voir si Rob a reçu mon message.

247
00:15:33,000 --> 00:15:35,000
Quand quelqu'un m'envoie un message crypté

248
00:15:35,000 --> 00:15:38,000
aussi longtemps que j'ai gardé ma clé privée secrète

249
00:15:38,000 --> 00:15:41,000
Je suis le seul qui peut déchiffrer le message.

250
00:15:41,000 --> 00:15:46,000
Pour déchiffrer un morceau c je peux calculer le message original

251
00:15:46,000 --> 00:15:53,000
est égale à la puissance morceau de d (mod n).

252
00:15:53,000 --> 00:15:57,000
Rappelez-vous que d et n sont de ma clé privée.

253
00:15:57,000 --> 00:16:01,000
Pour obtenir un message plein de ses morceaux que nous déchiffrer chaque bloc

254
00:16:01,000 --> 00:16:04,000
et concaténer les résultats.

255
00:16:04,000 --> 00:16:08,000
Exactement comment est sécurisé RSA?

256
00:16:08,000 --> 00:16:10,000
La vérité est que nous ne savons pas.

257
00:16:10,000 --> 00:16:14,000
La sécurité est basée sur le temps qu'il faudrait à un pirate de se fissurer un message

258
00:16:14,000 --> 00:16:16,000
chiffré avec RSA.

259
00:16:16,000 --> 00:16:19,000
Rappelez-vous que l'attaquant a accès à votre clé publique,

260
00:16:19,000 --> 00:16:21,000
qui contient à la fois e et n.

261
00:16:21,000 --> 00:16:26,000
Si l'attaquant parvient à tenir compte dans ses 2 n nombres premiers, p et q,

262
00:16:26,000 --> 00:16:30,000
alors elle pourrait calculer d en utilisant l'algorithme d'Euclide étendu.

263
00:16:30,000 --> 00:16:35,000
Cela lui donne la clé privée, qui peut être utilisée pour déchiffrer n'importe quel message.

264
00:16:35,000 --> 00:16:38,000
Mais comment peut-on tenir compte rapidement des entiers?

265
00:16:38,000 --> 00:16:41,000
Encore une fois, nous ne savons pas.

266
00:16:41,000 --> 00:16:43,000
Personne n'a trouvé un moyen rapide de le faire,

267
00:16:43,000 --> 00:16:46,000
ce qui signifie que, étant donné n assez grand

268
00:16:46,000 --> 00:16:49,000
il faudrait un attaquant excessivement longue

269
00:16:49,000 --> 00:16:51,000
prendre en compte le nombre.

270
00:16:51,000 --> 00:16:54,000
Si quelqu'un a révélé un moyen rapide d'entiers d'affacturage

271
00:16:54,000 --> 00:16:57,000
RSA serait rompu.

272
00:16:57,000 --> 00:17:01,000
Mais même si la factorisation des entiers est intrinsèquement lent

273
00:17:01,000 --> 00:17:04,000
l'algorithme RSA peut toujours avoir une faille dans l'

274
00:17:04,000 --> 00:17:07,000
qui permet le décryptage des messages facile.

275
00:17:07,000 --> 00:17:10,000
Personne n'a trouvé et révélé une telle faille encore,

276
00:17:10,000 --> 00:17:12,000
mais cela ne veut pas dire qu'il n'existe pas.

277
00:17:12,000 --> 00:17:17,000
En théorie, quelqu'un pourrait être là la lecture de toutes les données chiffrées avec RSA.

278
00:17:17,000 --> 00:17:19,000
Il ya une autre sorte de problème de confidentialité.

279
00:17:19,000 --> 00:17:23,000
Si Tommy crypte quelque message en utilisant ma clé publique

280
00:17:23,000 --> 00:17:26,000
et un attaquant crypte le même message en utilisant ma clé publique

281
00:17:26,000 --> 00:17:29,000
l'attaquant verrez que les 2 messages sont identiques

282
00:17:29,000 --> 00:17:32,000
et donc savoir ce que Tommy cryptées.

283
00:17:32,000 --> 00:17:36,000
Afin d'éviter cela, les messages sont généralement complétée par des bits aléatoires

284
00:17:36,000 --> 00:17:39,000
avant d'être chiffré de sorte que le même message chiffré

285
00:17:39,000 --> 00:17:44,000
plusieurs fois sera différente dans la mesure où le remplissage du message est différent.

286
00:17:44,000 --> 00:17:47,000
Mais rappelez-vous comment nous devons diviser en morceaux messages

287
00:17:47,000 --> 00:17:50,000
de sorte que chaque bloc est plus petit que n?

288
00:17:50,000 --> 00:17:52,000
Rembourrage les morceaux signifie que nous pourrions avoir à diviser les choses

289
00:17:52,000 --> 00:17:57,000
en morceaux encore plus depuis le morceau rembourrée doit être inférieur à n.

290
00:17:57,000 --> 00:18:01,000
Le cryptage et le décryptage sont relativement chers avec RSA,

291
00:18:01,000 --> 00:18:05,000
et ainsi avoir besoin de briser un message en morceaux beaucoup peut être très coûteux.

292
00:18:05,000 --> 00:18:09,000
Si un grand volume de données doivent être chiffrées et déchiffrées

293
00:18:09,000 --> 00:18:12,000
nous pouvons combiner les avantages des algorithmes de clés symétriques

294
00:18:12,000 --> 00:18:16,000
avec ceux de RSA pour obtenir à la fois la sécurité et l'efficacité.

295
00:18:16,000 --> 00:18:18,000
Bien que nous ne pourrons pas y entrer ici,

296
00:18:18,000 --> 00:18:23,000
AES est un algorithme à clé symétrique comme le Vigenère et chiffres César

297
00:18:23,000 --> 00:18:25,000
mais beaucoup plus difficile à casser.

298
00:18:25,000 --> 00:18:30,000
Bien sûr, nous ne pouvons pas utiliser AES sans établir une clé secrète partagée

299
00:18:30,000 --> 00:18:34,000
entre les 2 systèmes, et nous avons vu le problème avec ça avant.

300
00:18:34,000 --> 00:18:40,000
Mais maintenant nous pouvons utiliser RSA pour établir la clé secrète partagée entre les 2 systèmes.

301
00:18:40,000 --> 00:18:43,000
Nous allons appeler l'ordinateur qui envoie les données de l'expéditeur

302
00:18:43,000 --> 00:18:46,000
et l'ordinateur recevant les données du récepteur.

303
00:18:46,000 --> 00:18:49,000
Le récepteur possède une paire de clés RSA et envoie

304
00:18:49,000 --> 00:18:51,000
la clé publique de l'expéditeur.

305
00:18:51,000 --> 00:18:54,000
L'expéditeur génère une clé AES,

306
00:18:54,000 --> 00:18:57,000
le chiffre avec le récepteur RSA à clé publique,

307
00:18:57,000 --> 00:19:00,000
et envoie la clé AES au récepteur.

308
00:19:00,000 --> 00:19:04,000
Le récepteur déchiffre le message avec sa clé privée RSA.

309
00:19:04,000 --> 00:19:09,000
L'expéditeur et le récepteur ont maintenant une clé partagée AES entre eux.

310
00:19:09,000 --> 00:19:14,000
AES, ce qui est beaucoup plus rapide au chiffrement et le déchiffrement de RSA,

311
00:19:14,000 --> 00:19:18,000
peut maintenant être utilisé pour chiffrer les gros volumes de données et de les envoyer au récepteur,

312
00:19:18,000 --> 00:19:21,000
qui peut déchiffrer à l'aide de la même clé.

313
00:19:21,000 --> 00:19:26,000
AES, ce qui est beaucoup plus rapide au chiffrement et le déchiffrement de RSA,

314
00:19:26,000 --> 00:19:30,000
peut maintenant être utilisé pour chiffrer les gros volumes de données et de les envoyer au récepteur,

315
00:19:30,000 --> 00:19:32,000
qui peut déchiffrer à l'aide de la même clé.

316
00:19:32,000 --> 00:19:36,000
Nous avons juste besoin RSA pour transférer la clé partagée.

317
00:19:36,000 --> 00:19:40,000
Nous n'avons plus besoin d'utiliser RSA du tout.

318
00:19:40,000 --> 00:19:46,000
On dirait que j'ai un message.

319
00:19:46,000 --> 00:19:49,000
Ce n'est pas grave si quelqu'un lire ce qui est sur l'avion en papier avant de le prendre

320
00:19:49,000 --> 00:19:55,000
parce que je suis le seul à avoir la clé privée.

321
00:19:55,000 --> 00:19:57,000
Nous allons décrypter chacun des segments dans le message.

322
00:19:57,000 --> 00:20:07,000
Le premier morceau, 658, nous élever à la puissance d, qui est de 185,

323
00:20:07,000 --> 00:20:18,000
mod n, qui est 989, est égal à 67,

324
00:20:18,000 --> 00:20:24,000
qui est la lettre C en ASCII.

325
00:20:24,000 --> 00:20:31,000
Maintenant, sur le morceau seconde.

326
00:20:31,000 --> 00:20:35,000
Le deuxième fragment a de la valeur 15,

327
00:20:35,000 --> 00:20:41,000
dont nous élever à la puissance 185e,

328
00:20:41,000 --> 00:20:51,000
mod 989, et ceci est égal à 83

329
00:20:51,000 --> 00:20:57,000
qui est la lettre S en ASCII.

330
00:20:57,000 --> 00:21:06,000
Maintenant, pour le morceau tiers, ce qui a de la valeur 799, nous élevons à 185,

331
00:21:06,000 --> 00:21:17,000
mod 989, et ceci est égal à 53,

332
00:21:17,000 --> 00:21:24,000
qui est la valeur du caractère ASCII en 5.

333
00:21:24,000 --> 00:21:30,000
Maintenant, pour le dernier morceau, qui a de la valeur 975,

334
00:21:30,000 --> 00:21:41,000
nous élevons à 185, mod 989,

335
00:21:41,000 --> 00:21:51,000
et ceci est égal à 48, qui est la valeur du 0 caractère ASCII.

336
00:21:51,000 --> 00:21:57,000
Mon nom est Rob Bowden, et c'est CS50.

337
00:21:57,000 --> 00:22:00,000
[CS50.TV]

338
00:22:06,000 --> 00:22:08,000
RSA du tout.

339
00:22:08,000 --> 00:22:14,000
RSA du tout. [Rires]

340
00:22:14,000 --> 00:22:17,000
Pas du tout.