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] [Πανεπιστήμιο του Χάρβαρντ]

3
00:00:04,000 --> 00:00:07,000
[Αυτό είναι CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:11,000
Ας ρίξουμε μια ματιά στο RSA, ένα ευρέως χρησιμοποιούμενο αλγόριθμο για την κρυπτογράφηση των δεδομένων.

5
00:00:11,000 --> 00:00:16,000
Αλγόριθμους κρυπτογράφησης, όπως Καίσαρα και Vigenere αλγόριθμους κρυπτογράφησης δεν είναι πολύ ασφαλείς.

6
00:00:16,000 --> 00:00:20,000
Με την Caesar cipher, ένας εισβολέας θα πρέπει μόνο να δοκιμάσετε 25 διαφορετικά κλειδιά

7
00:00:20,000 --> 00:00:22,000
για να πάρει μορφή απλού κειμένου του μηνύματος.

8
00:00:22,000 --> 00:00:25,000
Ενώ η κρυπτογράφηση Vigenere είναι πιο ασφαλής από ό, τι το Caesar cipher

9
00:00:25,000 --> 00:00:28,000
λόγω του μεγαλύτερου χώρου αναζήτησης για τα κλειδιά, όταν ένας εισβολέας

10
00:00:28,000 --> 00:00:30,000
γνωρίζει το μήκος του κλειδιού κρυπτογράφησης σε ένα Vigenere,

11
00:00:30,000 --> 00:00:34,000
η οποία μπορεί να προσδιοριστεί μέσω μιας ανάλυσης των προτύπων στο κρυπτογραφημένο κείμενο,

12
00:00:34,000 --> 00:00:38,000
το κρυπτογράφημα Vigenere δεν είναι ότι πολύ πιο ασφαλή από ό, τι το Caesar cipher.

13
00:00:38,000 --> 00:00:42,000
RSA, από την άλλη πλευρά, δεν είναι ευάλωτα σε επιθέσεις όπως αυτό.

14
00:00:42,000 --> 00:00:45,000
Το Caesar cipher και Vigenere κρυπτογράφησης χρησιμοποιούν το ίδιο κλειδί

15
00:00:45,000 --> 00:00:47,000
τόσο για την κρυπτογράφηση και αποκρυπτογράφηση ενός μηνύματος.

16
00:00:47,000 --> 00:00:51,000
Αυτή η ιδιότητα κάνει τις ciphers αλγόριθμους συμμετρικού κλειδιού.

17
00:00:51,000 --> 00:00:54,000
Ένα βασικό πρόβλημα με αλγόριθμους συμμετρικού κλειδιού

18
00:00:54,000 --> 00:00:57,000
είναι ότι στηρίζονται σε εκείνη την κρυπτογράφηση και την αποστολή του μηνύματος

19
00:00:57,000 --> 00:00:59,000
και η μία υποδοχή και την αποκρυπτογράφηση του μηνύματος

20
00:00:59,000 --> 00:01:03,000
να έχουν ήδη συμφωνήσει εκ των προτέρων για το κλειδί που θα χρησιμοποιήσει και τα δύο.

21
00:01:03,000 --> 00:01:06,000
Έχουμε, όμως, ένα κομμάτι από ένα πρόβλημα εκκίνησης εδώ.

22
00:01:06,000 --> 00:01:10,000
Πώς 2 υπολογιστές που θέλουν να επικοινωνήσουν δημιουργήσει ένα μυστικό κλειδί μεταξύ τους;

23
00:01:10,000 --> 00:01:16,000
Εάν το κλειδί πρέπει να είναι μυστική, τότε χρειάζεστε έναν τρόπο για να κρυπτογραφήσει και να αποκρυπτογραφήσει το κλειδί.

24
00:01:16,000 --> 00:01:18,000
Αν το μόνο που έχουμε είναι συμμετρικό κλειδί κρυπτογράφησης

25
00:01:18,000 --> 00:01:21,000
τότε έχουμε μόλις έρθει και πάλι στο ίδιο πρόβλημα.

26
00:01:21,000 --> 00:01:25,000
RSA, από την άλλη πλευρά, χρησιμοποιεί ένα ζεύγος κλειδιών,

27
00:01:25,000 --> 00:01:28,000
ένα για κρυπτογράφηση και ένα άλλο για αποκρυπτογράφηση.

28
00:01:28,000 --> 00:01:32,000
Ένα ονομάζεται το δημόσιο κλειδί, και το άλλο είναι το ιδιωτικό κλειδί.

29
00:01:32,000 --> 00:01:34,000
Το δημόσιο κλειδί χρησιμοποιείται για την κρυπτογράφηση μηνυμάτων.

30
00:01:34,000 --> 00:01:38,000
Όπως μπορείτε να μαντέψετε από το όνομα του, μπορούμε να μοιραστούμε το δημόσιο κλειδί μας με

31
00:01:38,000 --> 00:01:43,000
κάποιος που θέλουμε χωρίς να θέτει σε κίνδυνο την ασφάλεια του ένα κρυπτογραφημένο μήνυμα.

32
00:01:43,000 --> 00:01:45,000
Μηνύματα κρυπτογραφούνται χρησιμοποιώντας ένα δημόσιο κλειδί

33
00:01:45,000 --> 00:01:49,000
μπορεί να αποκρυπτογραφηθεί μόνο με το αντίστοιχο ιδιωτικό κλειδί του.

34
00:01:49,000 --> 00:01:53,000
Ενώ μπορείτε να μοιραστείτε το δημόσιο κλειδί σας, θα πρέπει να έχετε πάντα μυστικό ιδιωτικό κλειδί σας.

61
00:01:55,000 --> 00:01:58,000
και μόνο το ιδιωτικό κλειδί μπορεί να χρησιμοποιηθεί για αποκρυπτογράφηση μηνυμάτων

62
00:01:58,000 --> 00:02:02,000
2 χρήστες αν θέλετε να στείλετε κρυπτογραφημένα μηνύματα με RSA

63
00:02:02,000 --> 00:02:07,000
εμπρός και πίσω και οι δύο χρήστες πρέπει να έχουν τη δική δημόσιου και ιδιωτικού κλειδιού τους.

64
00:02:07,000 --> 00:02:10,000
Μηνύματα από το χρήστη 1 έως χρήστη 2

65
00:02:10,000 --> 00:02:15,000
χρησιμοποιείτε μόνο ζεύγος κλειδιών 2 του χρήστη, και τα μηνύματα από τον χρήστη 2 στο χρήστη 1

66
00:02:15,000 --> 00:02:17,000
χρησιμοποιείτε μόνο το ζεύγος κλειδιών του χρήστη 1.

67
00:02:17,000 --> 00:02:21,000
Το γεγονός ότι υπάρχουν 2 ξεχωριστά κλειδιά για την κρυπτογράφηση και την αποκρυπτογράφηση μηνυμάτων

68
00:02:21,000 --> 00:02:24,000
κάνει ένα ασύμμετρο RSA κλειδί αλγόριθμο.

69
00:02:24,000 --> 00:02:28,000
Δεν χρειάζεται να κρυπτογραφήσετε το δημόσιο κλειδί για να το στείλετε σε άλλο υπολογιστή

70
00:02:28,000 --> 00:02:31,000
δεδομένου ότι το δημόσιο κλειδί είναι ούτως ή άλλως.

71
00:02:31,000 --> 00:02:33,000
Αυτό σημαίνει ότι η RSA δεν έχει το ίδιο πρόβλημα εκκίνησης

72
00:02:33,000 --> 00:02:36,000
οι αλγόριθμοι συμμετρικού κλειδιού.

73
00:02:36,000 --> 00:02:39,000
Έτσι, αν θέλετε να στείλετε ένα μήνυμα χρησιμοποιώντας RSA κρυπτογράφησης

74
00:02:39,000 --> 00:02:42,000
να Rob, θα πρέπει πρώτα δημόσιο κλειδί του Rob.

75
00:02:42,000 --> 00:02:47,000
Για να δημιουργήσετε ένα ζευγάρι κλειδιά, Rob πρέπει να πάρει 2 μεγάλα πρώτων αριθμών.

76
00:02:47,000 --> 00:02:50,000
Οι αριθμοί αυτοί θα χρησιμοποιηθούν τόσο στο δημόσιο όσο και ιδιωτικά κλειδιά,

77
00:02:50,000 --> 00:02:54,000
αλλά το δημόσιο κλειδί θα χρησιμοποιήσει μόνο το προϊόν αυτών των 2 αριθμών,

78
00:02:54,000 --> 00:02:56,000
όχι οι ίδιοι οι αριθμοί.

79
00:02:56,000 --> 00:02:59,000
Μόλις έχω το μήνυμα κρυπτογραφείται χρησιμοποιώντας το δημόσιο κλειδί του Rob

80
00:02:59,000 --> 00:03:01,000
Μπορώ να στείλετε το μήνυμα σε Rob.

81
00:03:01,000 --> 00:03:05,000
Για έναν υπολογιστή, οι αριθμοί factoring είναι ένα δύσκολο πρόβλημα.

82
00:03:05,000 --> 00:03:09,000
Το δημόσιο κλειδί, να θυμάστε, χρησιμοποιείται το προϊόν των 2 πρώτων αριθμών.

83
00:03:09,000 --> 00:03:12,000
Αυτό το προϊόν πρέπει να έχει τότε μόνο 2 παράγοντες,

84
00:03:12,000 --> 00:03:16,000
τα οποία τυχαίνει να είναι οι αριθμοί που συνθέτουν το ιδιωτικό κλειδί.

85
00:03:16,000 --> 00:03:20,000
Για να αποκρυπτογραφήσει το μήνυμα, RSA θα χρησιμοποιήσει αυτό το ιδιωτικό κλειδί

86
00:03:20,000 --> 00:03:25,000
ή οι αριθμοί πολλαπλασιάζονται μαζί με τη διαδικασία της δημιουργίας του δημόσιου κλειδιού.

87
00:03:25,000 --> 00:03:28,000
Επειδή είναι υπολογιστικά δύσκολο να συνυπολογίσει τον αριθμό

88
00:03:28,000 --> 00:03:32,000
χρησιμοποιείται σε ένα δημόσιο κλειδί στις 2 αριθμοί που χρησιμοποιούνται στο ιδιωτικό κλειδί

89
00:03:32,000 --> 00:03:36,000
Είναι δύσκολο για έναν εισβολέα να καταλάβω το ιδιωτικό κλειδί

90
00:03:36,000 --> 00:03:39,000
που θα είναι αναγκαία για να αποκρυπτογραφήσει το μήνυμα.

91
00:03:39,000 --> 00:03:43,000
Τώρα ας πάμε σε μερικά χαμηλότερο επίπεδο λεπτομέρειες της RSA.

92
00:03:43,000 --> 00:03:46,000
Ας δούμε πρώτα πώς μπορούμε να δημιουργήσουμε ένα ζευγάρι κλειδιά.

93
00:03:46,000 --> 00:03:49,000
Κατ 'αρχάς, θα χρειαστείτε 2 πρώτοι αριθμοί.

94
00:03:49,000 --> 00:03:52,000
Θα καλέσετε αυτά τα 2 αριθμούς p και q.

95
00:03:52,000 --> 00:03:56,000
Για να πάρει p και q, στην πράξη θα δημιουργήσει ψευδοτυχαία

96
00:03:56,000 --> 00:03:59,000
μεγάλους αριθμούς και στη συνέχεια χρησιμοποιήστε μια δοκιμή για να καθοριστεί εάν ή όχι

97
00:03:59,000 --> 00:04:02,000
αυτοί οι αριθμοί είναι κατά πάσα πιθανότητα prime.

98
00:04:02,000 --> 00:04:05,000
Μπορούμε να κρατήσει την παραγωγή τυχαίων αριθμών ξανά και ξανά

99
00:04:05,000 --> 00:04:08,000
μέχρι να έχουμε 2 primes που μπορούμε να χρησιμοποιήσουμε.

100
00:04:08,000 --> 00:04:15,000
Εδώ ας πάρει p = 23 και q = 43.

101
00:04:15,000 --> 00:04:19,000
Θυμηθείτε, στην πράξη, τα ρ και q πρέπει να είναι πολύ μεγαλύτερο αριθμό.

102
00:04:19,000 --> 00:04:22,000
Σε ό, τι γνωρίζουμε, όσο μεγαλύτερες είναι οι αριθμοί, τόσο πιο δύσκολο είναι

103
00:04:22,000 --> 00:04:25,000
για να σπάσουμε ένα κρυπτογραφημένο μήνυμα.

104
00:04:25,000 --> 00:04:29,000
Αλλά είναι επίσης πιο ακριβά για να κρυπτογραφήσει και να αποκρυπτογραφήσει τα μηνύματα.

105
00:04:29,000 --> 00:04:33,000
Σήμερα είναι συχνά συνιστάται ότι p και q είναι τουλάχιστον 1024 bits,

106
00:04:33,000 --> 00:04:37,000
που θέτει κάθε αριθμό σε πάνω από 300 δεκαδικά ψηφία.

107
00:04:37,000 --> 00:04:40,000
Αλλά θα πάρει αυτά τα μικρά τους αριθμούς για αυτό το παράδειγμα.

108
00:04:40,000 --> 00:04:43,000
Τώρα θα πολλαπλασιάσει p και q μαζί για να πάρει ένα 3ο αριθμό,

109
00:04:43,000 --> 00:04:45,000
το οποίο θα καλέσουμε n.

110
00:04:45,000 --> 00:04:55,000
Στην περίπτωσή μας, η = 23 * 43, η οποία = 989.

111
00:04:55,000 --> 00:04:58,000
Έχουμε n = 989.

112
00:04:58,000 --> 00:05:02,000
Στη συνέχεια θα πολλαπλασιαστούν p - 1 με q - 1

113
00:05:02,000 --> 00:05:05,000
να αποκτήσουν ένα τέταρτο αριθμό, ο οποίος θα καλέσει m.

114
00:05:05,000 --> 00:05:15,000
Στην περίπτωσή μας, m = 22 * ​​42, η οποία = 924.

115
00:05:15,000 --> 00:05:18,000
Έχουμε m = 924.

116
00:05:18,000 --> 00:05:22,000
Τώρα θα χρειαστείτε ένα e αριθμός που είναι σχετικά πρώτοι με m

117
00:05:22,000 --> 00:05:25,000
και μικρότερο από πι.

118
00:05:25,000 --> 00:05:28,000
Δύο αριθμοί είναι σχετικά prime ή coprime

119
00:05:28,000 --> 00:05:33,000
αν ο μόνος θετικός ακέραιος που διαιρεί τους δύο ομοιόμορφα είναι 1.

120
00:05:33,000 --> 00:05:37,000
Με άλλα λόγια, ο μέγιστος κοινός διαιρέτης των e και πι

121
00:05:37,000 --> 00:05:39,000
πρέπει να είναι 1.

122
00:05:39,000 --> 00:05:44,000
Στην πράξη, είναι σύνηθες για το ηλεκτρονικό να είναι ο πρώτος αριθμός 65537

123
00:05:44,000 --> 00:05:48,000
εφ 'όσον ο αριθμός αυτός δεν τυχαίνει να είναι ένας παράγοντας του m.

124
00:05:48,000 --> 00:05:53,000
Για τα κλειδιά μας, θα πάρει e = 5

125
00:05:53,000 --> 00:05:57,000
από τις 5 είναι σχετικά prime σε 924.

126
00:05:57,000 --> 00:06:01,000
Τέλος, θα χρειαστείτε ένα περισσότερο τον αριθμό, ο οποίος θα καλέσει d.

127
00:06:01,000 --> 00:06:11,000
D πρέπει να είναι κάποια τιμή που ικανοποιεί την εξίσωση de = 1 (mod m).

128
00:06:11,000 --> 00:06:17,000
Αυτό σημαίνει m mod θα χρησιμοποιήσουμε κάτι που ονομάζεται αρθρωτή αριθμητική.

129
00:06:17,000 --> 00:06:21,000
Στην modular αριθμητική, όταν ένας αριθμός υψηλότερος από ό, τι παίρνει κάποιο άνω όριο

130
00:06:21,000 --> 00:06:24,000
θα γυρίσει πίσω γύρω στο 0.

131
00:06:24,000 --> 00:06:27,000
Ένα ρολόι, για παράδειγμα, χρησιμοποιεί modular αριθμητική.

132
00:06:27,000 --> 00:06:31,000
Ένα λεπτό μετά τη 1:59, για παράδειγμα, είναι 2:00,

133
00:06:31,000 --> 00:06:33,000
Δεν 1:60.

134
00:06:33,000 --> 00:06:36,000
Το λεπτό χέρι έχει τυλιγμένο γύρω στο 0

135
00:06:36,000 --> 00:06:39,000
φτάνοντας ένα άνω φράγμα του 60.

136
00:06:39,000 --> 00:06:46,000
Έτσι, μπορούμε να πούμε 60 είναι ισοδύναμο με 0 (mod 60)

137
00:06:46,000 --> 00:06:57,000
και 125 είναι ισοδύναμο με 65 είναι ισοδύναμη με 5 (mod 60).

138
00:06:57,000 --> 00:07:02,000
Δημόσιο κλειδί μας θα είναι το e ζευγάρι και n

139
00:07:02,000 --> 00:07:09,000
όπου στην περίπτωση αυτή το e είναι 5 και το η είναι 989.

140
00:07:09,000 --> 00:07:15,000
Ιδιωτικό κλειδί μας θα είναι το ζεύγος d και n,

141
00:07:15,000 --> 00:07:22,000
που στην περίπτωσή μας είναι 185 και 989.

142
00:07:22,000 --> 00:07:25,000
Παρατηρήστε ότι η αρχική μας πρώτων p και q δεν εμφανίζονται

143
00:07:25,000 --> 00:07:29,000
οπουδήποτε σε ιδιωτικά ή δημόσια κλειδιά μας.

144
00:07:29,000 --> 00:07:33,000
Τώρα που έχουμε ζεύγος κλειδιών μας, ας ρίξουμε μια ματιά στο πώς μπορούμε να κρυπτογραφήσει

145
00:07:33,000 --> 00:07:36,000
και να αποκρυπτογραφήσει ένα μήνυμα.

146
00:07:36,000 --> 00:07:38,000
Θέλω να στείλω ένα μήνυμα προς τον Rob,

147
00:07:38,000 --> 00:07:42,000
έτσι θα είναι το ένα να δημιουργήσει αυτό το ζεύγος κλειδιών.

148
00:07:42,000 --> 00:07:46,000
Τότε εγώ θα ρωτήσω τον Rob για το δημόσιο κλειδί του, την οποία θα χρησιμοποιήσετε

149
00:07:46,000 --> 00:07:48,000
να κρυπτογραφήσει ένα μήνυμα να στείλει σ 'αυτόν.

150
00:07:48,000 --> 00:07:53,000
Θυμηθείτε, είναι εντελώς εντάξει για τον Rob να μοιραστεί το δημόσιο κλειδί του μαζί μου.

151
00:07:53,000 --> 00:07:56,000
Αλλά δεν θα ήταν εντάξει για να μοιραστεί το ιδιωτικό κλειδί του.

152
00:07:56,000 --> 00:08:00,000
Δεν έχω καμία ιδέα για το τι ιδιωτικό κλειδί του είναι.

153
00:08:00,000 --> 00:08:03,000
Μπορούμε να σπάσει μήνυμα m μας επάνω σε πολλά κομμάτια

154
00:08:03,000 --> 00:08:07,000
όλα μικρότερα από n και κατόπιν κρυπτογράφηση καθεμία από αυτές κομμάτια.

155
00:08:07,000 --> 00:08:12,000
Θα κρυπτογραφήσει το CS50 κορδόνι, το οποίο μπορεί να σπάσει σε 4 κομμάτια,

156
00:08:12,000 --> 00:08:14,000
μία ανά γράμμα.

157
00:08:14,000 --> 00:08:17,000
Για να κρυπτογραφήσει το μήνυμά μου, εγώ θα πρέπει να το μετατρέψει σε

158
00:08:17,000 --> 00:08:20,000
κάποια αριθμητική εκπροσώπηση.

159
00:08:20,000 --> 00:08:25,000
Ας ενώσετε τις τιμές ASCII με τους χαρακτήρες στο μήνυμα μου.

160
00:08:25,000 --> 00:08:28,000
Για να κρυπτογραφήσετε ένα συγκεκριμένο μήνυμα m

161
00:08:28,000 --> 00:08:37,000
Θα πρέπει να υπολογίσουμε c = m από το e (mod n).

162
00:08:37,000 --> 00:08:40,000
Αλλά m πρέπει να είναι μικρότερο από το η,

163
00:08:40,000 --> 00:08:45,000
ή αλλιώς το πλήρες μήνυμα δεν μπορεί να εκφραστεί modulo n.

164
00:08:45,000 --> 00:08:49,000
Μπορούμε να σπάσει μ επάνω σε πολλά κομμάτια, όλα από τα οποία είναι μικρότερα από ό, τι η,

165
00:08:49,000 --> 00:08:52,000
κρυπτογράφηση και κάθε ένα από αυτά κομμάτια.

166
00:08:52,000 --> 00:09:03,000
Η κρυπτογράφηση καθένα από αυτά τα κομμάτια, παίρνουμε c1 = 67 στο 5 (mod 989)

167
00:09:03,000 --> 00:09:06,000
οποίες = 658.

168
00:09:06,000 --> 00:09:15,000
Για το δεύτερο κομμάτι μας έχουμε 83 έως το 5 (mod 989)

169
00:09:15,000 --> 00:09:18,000
οποίες = 15.

170
00:09:18,000 --> 00:09:26,000
Για τρίτη κομμάτι μας έχουμε 53 έως το 5 (mod 989)

171
00:09:26,000 --> 00:09:30,000
που = 799.

172
00:09:30,000 --> 00:09:39,000
Και, τέλος, για το τελευταίο κομμάτι μας έχουμε 48 έως την 5 (mod 989)

173
00:09:39,000 --> 00:09:43,000
οποία = 975.

174
00:09:43,000 --> 00:09:48,000
Τώρα μπορούμε να στείλουμε σε αυτές τις αξίες σε κρυπτογραφημένη Rob.

175
00:09:54,000 --> 00:09:58,000
Ορίστε, Rob.

176
00:09:58,000 --> 00:10:01,000
Αν το μήνυμά μας είναι κατά την πτήση, ας ρίξουμε μια άλλη ματιά

177
00:10:01,000 --> 00:10:07,000
στο πώς φτάσαμε ότι η τιμή για το d.

178
00:10:07,000 --> 00:10:17,000
Δ αριθμός μας χρειάζεται για να ικανοποιήσει 5d = 1 (mod 924).

179
00:10:17,000 --> 00:10:24,000
Αυτό καθιστά d η πολλαπλασιαστικό αντίστροφο της 5 modulo 924.

180
00:10:24,000 --> 00:10:28,000
Δεδομένου 2 ακέραιοι, α και β, ο διευρυμένος Ευκλείδειος αλγόριθμος

181
00:10:28,000 --> 00:10:33,000
μπορεί να χρησιμοποιηθεί για να βρείτε τον μέγιστο κοινό διαιρέτη των 2 αυτών ακέραιοι.

182
00:10:33,000 --> 00:10:37,000
Επίσης, θα μας δώσει άλλα 2 αριθμούς, x και y,

183
00:10:37,000 --> 00:10:47,000
που ικανοποιούν την εξίσωση ax + by = το μέγιστο κοινό διαιρέτη των a και b.

184
00:10:47,000 --> 00:10:49,000
Πώς αυτό να μας βοηθήσει;

185
00:10:49,000 --> 00:10:52,000
Λοιπόν, συνδέοντας e = 5 για ένα

186
00:10:52,000 --> 00:10:56,000
και m = 924 για β

187
00:10:56,000 --> 00:10:59,000
γνωρίζουμε ήδη ότι οι αριθμοί αυτοί είναι coprime.

188
00:10:59,000 --> 00:11:03,000
Μέγιστο κοινό διαιρέτη τους είναι 1.

189
00:11:03,000 --> 00:11:09,000
Αυτό μας δίνει 5x + 924y = 1

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

191
00:11:17,000 --> 00:11:22,000
Αλλά αν θέλουμε μόνο νοιάζονται για τα πάντα modulo 924

192
00:11:22,000 --> 00:11:25,000
τότε μπορούμε να ρίξει το - 924y.

193
00:11:25,000 --> 00:11:27,000
Σκεφτείτε πίσω στο ρολόι.

194
00:11:27,000 --> 00:11:31,000
Αν ο λεπτοδείκτης είναι στις 1 και στη συνέχεια να περάσει ακριβώς 10 ώρες,

195
00:11:31,000 --> 00:11:35,000
γνωρίζουμε το λεπτοδείκτη θα εξακολουθεί να είναι στο 1.

196
00:11:35,000 --> 00:11:39,000
Εδώ θα ξεκινήσει στις 1 και στη συνέχεια τυλίξτε γύρω ακριβώς y φορές,

197
00:11:39,000 --> 00:11:41,000
έτσι θα εξακολουθεί να είναι στο 1.

198
00:11:41,000 --> 00:11:49,000
Έχουμε 5x = 1 (mod 924).

199
00:11:49,000 --> 00:11:55,000
Και εδώ το x είναι το ίδιο με το δ ψάχναμε για πριν,

200
00:11:55,000 --> 00:11:58,000
έτσι αν χρησιμοποιήσουμε τον διευρυμένο Ευκλείδειο αλγόριθμο

201
00:11:58,000 --> 00:12:04,000
για να πάρει αυτό το x αριθμό, αυτός είναι ο αριθμός θα πρέπει να χρησιμοποιήσουμε ως d μας.

202
00:12:04,000 --> 00:12:07,000
Τώρα, ας τρέξει τον διευρυμένο Ευκλείδειο αλγόριθμο για ένα = 5

203
00:12:07,000 --> 00:12:11,000
και b = 924.

204
00:12:11,000 --> 00:12:14,000
Θα χρησιμοποιήσουμε μια μέθοδο που ονομάζεται η μέθοδος πίνακα.

205
00:12:14,000 --> 00:12:21,000
Τραπέζι μας θα έχουν 4 στήλες, x, y, d, και k.

206
00:12:21,000 --> 00:12:23,000
Τραπέζι μας ξεκινά με 2 σειρές.

207
00:12:23,000 --> 00:12:28,000
Στην πρώτη σειρά έχουμε 1, 0, τότε η αξία μας α, η οποία είναι 5,

208
00:12:28,000 --> 00:12:37,000
και δεύτερη σειρά μας είναι 0, 1, και η αξία μας για το β, η οποία είναι 924.

209
00:12:37,000 --> 00:12:40,000
Η αξία της τέταρτης στήλης, k, θα είναι το αποτέλεσμα

210
00:12:40,000 --> 00:12:45,000
χωρίζοντας την τιμή του d στη γραμμή πάνω από αυτό με την τιμή του d

211
00:12:45,000 --> 00:12:49,000
στην ίδια γραμμή.

212
00:12:49,000 --> 00:12:56,000
Έχουμε 5 διαιρείται με 924 είναι 0 με κάποια υπόλοιπο.

213
00:12:56,000 --> 00:12:59,000
Αυτό σημαίνει ότι έχουμε k = 0.

214
00:12:59,000 --> 00:13:05,000
Τώρα η αξία κάθε άλλο κύτταρο θα είναι η αξία των κυττάρων 2 σειρές παραπάνω

215
00:13:05,000 --> 00:13:09,000
μείον την αξία της γραμμής πάνω από το k φορές.

216
00:13:09,000 --> 00:13:11,000
Ας ξεκινήσουμε με το δ στην 3η σειρά.

217
00:13:11,000 --> 00:13:19,000
Έχουμε 5-924 * 0 = 5.

218
00:13:19,000 --> 00:13:25,000
Στη συνέχεια έχουμε 0 - 1 * 0 η οποία είναι 0

219
00:13:25,000 --> 00:13:30,000
και 1 - 0 * 0 το οποίο είναι 1.

220
00:13:30,000 --> 00:13:33,000
Δεν είναι και τόσο άσχημα, οπότε ας περάσουμε στην επόμενη σειρά.

221
00:13:33,000 --> 00:13:36,000
Πρώτα χρειαζόμαστε αξία μας κ.

222
00:13:36,000 --> 00:13:43,000
924 διαιρείται με 5 = 184 με κάποιο υπόλοιπο,

223
00:13:43,000 --> 00:13:46,000
έτσι αξία μας για το k είναι 184.

224
00:13:46,000 --> 00:13:54,000
Τώρα, 924 - 5 * 184 = 4.

225
00:13:54,000 --> 00:14:05,000
1-0 * 184 είναι 1 και 0 - 1 * 184 είναι -184.

226
00:14:05,000 --> 00:14:07,000
Εντάξει, ας κάνουμε την επόμενη σειρά.

227
00:14:07,000 --> 00:14:10,000
Αξία μας κ θα είναι 1, επειδή

228
00:14:10,000 --> 00:14:15,000
5 διαιρούμενο με 4 = 1 με κάποιο υπόλοιπο.

229
00:14:15,000 --> 00:14:17,000
Ας συμπληρώστε τα άλλα στήλες.

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
Και 1 - 184 * 1 είναι 185.

233
00:14:33,000 --> 00:14:35,000
Ας δούμε ποιο είναι το επόμενο μας αξία του k θα είναι.

234
00:14:35,000 --> 00:14:40,000
Λοιπόν, φαίνεται σαν να έχετε 4 διαιρείται με 1, η οποία είναι 4.

235
00:14:40,000 --> 00:14:43,000
Σε αυτή την περίπτωση όπου είμαστε διαιρώντας με 1 τέτοια ώστε το k είναι ίσο προς

236
00:14:43,000 --> 00:14:50,000
η τιμή του d στην παραπάνω γραμμή σημαίνει ότι τελειώσαμε με τον αλγόριθμο μας.

237
00:14:50,000 --> 00:14:58,000
Μπορούμε να δούμε ότι εδώ έχουμε x = 185 και y = -1 στην τελευταία γραμμή.

238
00:14:58,000 --> 00:15:00,000
Ας επανέλθω στο αρχικό μας στόχο.

239
00:15:00,000 --> 00:15:04,000
Είπαμε ότι η τιμή του x ως αποτέλεσμα της λειτουργίας αυτόν τον αλγόριθμο

240
00:15:04,000 --> 00:15:08,000
θα είναι το πολλαπλασιαστικό αντίστροφο της (mod β).

241
00:15:08,000 --> 00:15:15,000
Αυτό σημαίνει ότι 185 είναι το πολλαπλασιαστικό αντίστροφο της 5 (mod 924)

242
00:15:15,000 --> 00:15:20,000
πράγμα που σημαίνει ότι έχουμε μια τιμή για το δ 185.

243
00:15:20,000 --> 00:15:23,000
Το γεγονός ότι το d = 1 στην τελευταία σειρά

244
00:15:23,000 --> 00:15:26,000
επαληθεύει ότι το e coprime σε m.

245
00:15:26,000 --> 00:15:30,000
Αν δεν ήταν 1 τότε θα πρέπει να επιλέξετε ένα νέο e.

246
00:15:30,000 --> 00:15:33,000
Ας δούμε τώρα αν ο Rob έχει λάβει το μήνυμά μου.

247
00:15:33,000 --> 00:15:35,000
Όταν κάποιος μου στείλει ένα κρυπτογραφημένο μήνυμα

248
00:15:35,000 --> 00:15:38,000
εφ 'όσον έχω παραμένει ιδιωτικό κλειδί μου ένα μυστικό

249
00:15:38,000 --> 00:15:41,000
Είμαι ο μόνος που μπορεί να αποκρυπτογραφήσει το μήνυμα.

250
00:15:41,000 --> 00:15:46,000
Για να αποκρυπτογραφήσετε ένα κομμάτι γ μπορώ να υπολογίσω το αρχικό μήνυμα

251
00:15:46,000 --> 00:15:53,000
είναι ίσο με το κομμάτι να δ ισχύς (mod n).

252
00:15:53,000 --> 00:15:57,000
Να θυμάστε ότι d και n είναι από το ιδιωτικό κλειδί μου.

253
00:15:57,000 --> 00:16:01,000
Για να πάρετε μια πλήρη μήνυμα από κομμάτια του θα αποκρυπτογραφήσει κάθε κομμάτι

254
00:16:01,000 --> 00:16:04,000
και τη συγκέντρωση των αποτελεσμάτων.

255
00:16:04,000 --> 00:16:08,000
Ακριβώς πόσο ασφαλές είναι RSA;

256
00:16:08,000 --> 00:16:10,000
Η αλήθεια είναι, δεν ξέρουμε.

257
00:16:10,000 --> 00:16:14,000
Ασφάλεια με βάση το πόσο καιρό θα έπαιρνε έναν εισβολέα να σπάσουμε ένα μήνυμα

258
00:16:14,000 --> 00:16:16,000
κρυπτογραφούνται με RSA.

259
00:16:16,000 --> 00:16:19,000
Θυμηθείτε ότι ένας εισβολέας έχει πρόσβαση στο δημόσιο κλειδί σας,

260
00:16:19,000 --> 00:16:21,000
το οποίο περιέχει τόσο το ηλεκτρονικό και n.

261
00:16:21,000 --> 00:16:26,000
Αν ο εισβολέας καταφέρει να συνυπολογίσει n σε 2 πρώτους αριθμούς του, p και q,

262
00:16:26,000 --> 00:16:30,000
τότε θα μπορούσε να υπολογίσει δ χρησιμοποιώντας το διευρυμένο Ευκλείδειο αλγόριθμο.

263
00:16:30,000 --> 00:16:35,000
Αυτό της δίνει το ιδιωτικό κλειδί, το οποίο μπορεί να χρησιμοποιηθεί για να αποκρυπτογραφήσει κάποιο μήνυμα.

264
00:16:35,000 --> 00:16:38,000
Αλλά πόσο γρήγορα μπορούμε να παράγοντα ακέραιοι;

265
00:16:38,000 --> 00:16:41,000
Και πάλι, δεν γνωρίζουμε.

266
00:16:41,000 --> 00:16:43,000
Κανείς δεν έχει βρει ένα γρήγορο τρόπο για να γίνει αυτό,

267
00:16:43,000 --> 00:16:46,000
πράγμα που σημαίνει ότι δίνεται αρκετά μεγάλο n

268
00:16:46,000 --> 00:16:49,000
θα χρειαζόταν έναν εισβολέα εξωπραγματικά μεγάλο

269
00:16:49,000 --> 00:16:51,000
να συνυπολογίσει τον αριθμό.

270
00:16:51,000 --> 00:16:54,000
Αν κάποιος αποκάλυψε ένα γρήγορο τρόπο από παραγοντοποίηση ακεραίων

271
00:16:54,000 --> 00:16:57,000
RSA θα σπάσει.

272
00:16:57,000 --> 00:17:01,000
Αλλά ακόμα και αν παραγοντοποίηση ακεραίου είναι εγγενώς αργή

273
00:17:01,000 --> 00:17:04,000
η RSA αλγόριθμος θα μπορούσε να έχει ακόμη κάποιο ελάττωμα σε αυτό

274
00:17:04,000 --> 00:17:07,000
που επιτρέπει την εύκολη αποκρυπτογράφηση των μηνυμάτων.

275
00:17:07,000 --> 00:17:10,000
Κανείς δεν έχει βρεθεί και αποκάλυψε ένα τέτοιο ελάττωμα ακόμα,

276
00:17:10,000 --> 00:17:12,000
αλλά αυτό δεν σημαίνει ότι δεν υπάρχει τέτοιο στοιχείο.

277
00:17:12,000 --> 00:17:17,000
Θεωρητικά, κάποιος θα μπορούσε να είναι εκεί έξω διαβάζει όλα τα δεδομένα κρυπτογραφούνται με RSA.

278
00:17:17,000 --> 00:17:19,000
Υπάρχει ένα άλλο κομμάτι του ζητήματος της ιδιωτικής ζωής.

279
00:17:19,000 --> 00:17:23,000
Αν ο Tommy κρυπτογραφεί κάποιο μήνυμα με το δημόσιο κλειδί μου

280
00:17:23,000 --> 00:17:26,000
και ένας εισβολέας κρυπτογραφεί το ίδιο μήνυμα με το δημόσιο κλειδί μου

281
00:17:26,000 --> 00:17:29,000
ο εισβολέας θα δείτε ότι τα 2 μηνύματα είναι πανομοιότυπα

282
00:17:29,000 --> 00:17:32,000
και επομένως να γνωρίζουν τι Tommy κρυπτογραφούνται.

283
00:17:32,000 --> 00:17:36,000
Για να αποφευχθεί αυτό, τα μηνύματα είναι συνήθως παραγεμισμένο με τυχαία bits

284
00:17:36,000 --> 00:17:39,000
πριν κρυπτογραφούνται, έτσι ώστε το ίδιο μήνυμα κρυπτογραφείται

285
00:17:39,000 --> 00:17:44,000
πολλές φορές θα έχει διαφορετική εμφάνιση όσο το παραγέμισμα στο μήνυμα είναι διαφορετική.

286
00:17:44,000 --> 00:17:47,000
Αλλά να θυμάστε πως πρέπει να χωριστεί σε κομμάτια μηνύματα

287
00:17:47,000 --> 00:17:50,000
έτσι ώστε κάθε κομμάτι είναι μικρότερο από n;

288
00:17:50,000 --> 00:17:52,000
Padding τα κομμάτια που σημαίνει ότι μπορεί να έχουμε για να χωρίσει τα πράγματα

289
00:17:52,000 --> 00:17:57,000
σε ακόμη περισσότερα κομμάτια αφού το παραγεμισμένο κομμάτι πρέπει να είναι μικρότερη από n.

290
00:17:57,000 --> 00:18:01,000
Κρυπτογράφησης και αποκρυπτογράφησης είναι σχετικά ακριβά με την RSA,

291
00:18:01,000 --> 00:18:05,000
και έτσι να χρειάζεται να σπάσει ένα μήνυμα σε πολλά κομμάτια μπορεί να είναι πολύ δαπανηρή.

292
00:18:05,000 --> 00:18:09,000
Εάν ένας μεγάλος όγκος των δεδομένων θα πρέπει να είναι κρυπτογραφημένη και αποκρυπτογραφούνται

293
00:18:09,000 --> 00:18:12,000
μπορούμε να συνδυάσουμε τα πλεονεκτήματα των αλγορίθμων συμμετρικού κλειδιού

294
00:18:12,000 --> 00:18:16,000
με εκείνες της RSA για να πάρει τόσο την ασφάλεια και την αποτελεσματικότητα.

295
00:18:16,000 --> 00:18:18,000
Αν και δεν θα μπω σε αυτό εδώ,

296
00:18:18,000 --> 00:18:23,000
AES είναι ένα συμμετρικό κλειδί αλγόριθμο, όπως το Vigenere και τους αλγόριθμους κρυπτογράφησης του Καίσαρα

297
00:18:23,000 --> 00:18:25,000
αλλά πολύ πιο δύσκολο να σπάσει.

298
00:18:25,000 --> 00:18:30,000
Φυσικά, δεν μπορούμε να χρησιμοποιήσουμε AES χωρίς τη θέσπιση ενός κοινού μυστικού κλειδιού

299
00:18:30,000 --> 00:18:34,000
μεταξύ των 2 συστημάτων, και είδαμε το πρόβλημα με αυτό πριν.

300
00:18:34,000 --> 00:18:40,000
Αλλά τώρα μπορούμε να χρησιμοποιήσουμε για τη δημιουργία RSA το κοινό μυστικό κλειδί μεταξύ των 2 συστημάτων.

301
00:18:40,000 --> 00:18:43,000
Θα καλέσετε τον υπολογιστή την αποστολή των δεδομένων από τον αποστολέα

302
00:18:43,000 --> 00:18:46,000
και ο υπολογιστής που λαμβάνει τα δεδομένα του δέκτη.

303
00:18:46,000 --> 00:18:49,000
Ο δέκτης έχει ένα ζεύγος κλειδιών RSA και στέλνει

304
00:18:49,000 --> 00:18:51,000
το δημόσιο κλειδί του αποστολέα.

305
00:18:51,000 --> 00:18:54,000
Ο αποστολέας δημιουργεί ένα κλειδί AES,

306
00:18:54,000 --> 00:18:57,000
κρυπτογραφεί με RSA δημόσιο κλειδί του παραλήπτη,

307
00:18:57,000 --> 00:19:00,000
και στέλνει το κλειδί AES στο δέκτη.

308
00:19:00,000 --> 00:19:04,000
Ο δέκτης αποκρυπτογραφεί το μήνυμα με το ιδιωτικό κλειδί RSA του.

309
00:19:04,000 --> 00:19:09,000
Τόσο ο αποστολέας όσο και ο παραλήπτης έχουν τώρα ένα κοινό κλειδί AES μεταξύ τους.

310
00:19:09,000 --> 00:19:14,000
AES, η οποία είναι πολύ πιο γρήγορα σε κρυπτογράφησης και αποκρυπτογράφησης του RSA,

311
00:19:14,000 --> 00:19:18,000
μπορούν πλέον να χρησιμοποιηθούν για την κρυπτογράφηση των μεγάλων όγκων δεδομένων και να τα στείλει στο δέκτη,

312
00:19:18,000 --> 00:19:21,000
ο οποίος μπορεί να αποκρυπτογραφήσει χρησιμοποιώντας το ίδιο κλειδί.

313
00:19:21,000 --> 00:19:26,000
AES, η οποία είναι πολύ πιο γρήγορα σε κρυπτογράφησης και αποκρυπτογράφησης του RSA,

314
00:19:26,000 --> 00:19:30,000
μπορούν πλέον να χρησιμοποιηθούν για την κρυπτογράφηση των μεγάλων όγκων δεδομένων και να τα στείλει στο δέκτη,

315
00:19:30,000 --> 00:19:32,000
ο οποίος μπορεί να αποκρυπτογραφήσει χρησιμοποιώντας το ίδιο κλειδί.

316
00:19:32,000 --> 00:19:36,000
Χρειαζόμασταν απλά RSA για να μεταφέρετε το κοινόχρηστο κλειδί.

317
00:19:36,000 --> 00:19:40,000
Εμείς δεν χρειάζεται πλέον να χρησιμοποιούν RSA καθόλου.

318
00:19:40,000 --> 00:19:46,000
Φαίνεται σαν να έχω ένα μήνυμα.

319
00:19:46,000 --> 00:19:49,000
Δεν έχει σημασία αν κάποιος διαβάσει τι είναι στο αεροπλάνο χαρτί πριν το αλιεύονται

320
00:19:49,000 --> 00:19:55,000
επειδή είμαι ο μόνος με το ιδιωτικό κλειδί.

321
00:19:55,000 --> 00:19:57,000
Ας αποκρυπτογράφηση κάθε ένα από τα κομμάτια στο μήνυμα.

322
00:19:57,000 --> 00:20:07,000
Το πρώτο κομμάτι, 658, θα αυξηθεί στο δ δύναμη, η οποία είναι 185,

323
00:20:07,000 --> 00:20:18,000
mod n, η οποία είναι 989, είναι ίση με 67,

324
00:20:18,000 --> 00:20:24,000
το οποίο είναι το γράμμα C σε ASCII.

325
00:20:24,000 --> 00:20:31,000
Τώρα, πάνω στο δεύτερο κομμάτι.

326
00:20:31,000 --> 00:20:35,000
Το δεύτερο κομμάτι έχει αξία 15,

327
00:20:35,000 --> 00:20:41,000
η οποία θα αυξήσει την δύναμη 185ος,

328
00:20:41,000 --> 00:20:51,000
mod 989, και αυτό είναι ίσο με 83

329
00:20:51,000 --> 00:20:57,000
το οποίο είναι το γράμμα S σε ASCII.

330
00:20:57,000 --> 00:21:06,000
Τώρα για το τρίτο κομμάτι, το οποίο έχει αξία 799, θα αυξηθεί σε 185,

331
00:21:06,000 --> 00:21:17,000
mod 989, και αυτό είναι ίσο με 53,

332
00:21:17,000 --> 00:21:24,000
η οποία είναι η τιμή του χαρακτήρα 5 σε ASCII.

333
00:21:24,000 --> 00:21:30,000
Τώρα για το τελευταίο κομμάτι, το οποίο έχει αξία 975,

334
00:21:30,000 --> 00:21:41,000
θα αυξηθεί σε 185, mod 989,

335
00:21:41,000 --> 00:21:51,000
και αυτό είναι ίσο με 48, η οποία είναι η τιμή της 0 χαρακτήρα σε ASCII.

336
00:21:51,000 --> 00:21:57,000
Το όνομά μου είναι Rob Bowden, και αυτό είναι CS50.

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

338
00:22:06,000 --> 00:22:08,000
RSA καθόλου.

339
00:22:08,000 --> 00:22:14,000
RSA καθόλου. [Γέλια]

340
00:22:14,000 --> 00:22:17,000
Σε όλα.