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

2
00:00:02,000 --> 00:00:04,000
[רוב אודן] [טומי 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
אלגוריתמי הצפנה כמו צופן Vigenère קיסר ואינם בטוחים.

6
00:00:16,000 --> 00:00:20,000
עם קיסר הצופן, תוקף צריך רק לנסות 25 מפתחות שונים

7
00:00:20,000 --> 00:00:22,000
כדי לקבל טקסט הרגיל של ההודעה.

8
00:00:22,000 --> 00:00:25,000
בעוד צופן Vigenère בטוח יותר מאשר קיסר הצופן

9
00:00:25,000 --> 00:00:28,000
בגלל מרחב החיפוש הגדול יותר עבור מקשים, ברגע שתוקף

10
00:00:28,000 --> 00:00:30,000
יודע את אורכו של המפתח בצופן Vigenère,

11
00:00:30,000 --> 00:00:34,000
שניתן לקבוע באמצעות ניתוח הדפוסים בטקסט המוצפן,

12
00:00:34,000 --> 00:00:38,000
צופן Vigenère הוא לא הרבה יותר בטוח מאשר הקיסר הצופן.

13
00:00:38,000 --> 00:00:42,000
RSA, לעומת זאת, אינו פגיע להתקפות מסוג זה.

14
00:00:42,000 --> 00:00:45,000
קיסר הצופן וצופן Vigenère להשתמש באותו המפתח

15
00:00:45,000 --> 00:00:47,000
לשניהם הצפנה ופענוח הודעה.

16
00:00:47,000 --> 00:00:51,000
מאפיין זה הופך את אלגוריתמי מפתח סימטריים אלה צפנים.

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
לשדוד אותו, אני צריך את המפתח הציבורי של רוב ראשון.

75
00:02:42,000 --> 00:02:47,000
כדי ליצור זוג מפתחות, רוב צריך לקחת 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
ברגע שאני מוצפן הודעה באמצעות המפתח הציבורי של רוב

80
00:02:59,000 --> 00:03:01,000
אני יכול לשלוח את ההודעה לרוב.

81
00:03:01,000 --> 00:03:05,000
למחשב, מספרים הפקטורינג הוא בעיה קשה.

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, בפועל pseudorandomly יעוררו

96
00:03:56,000 --> 00:03:59,000
מספרים גדולים ולאחר מכן להשתמש במבחן לקביעה אם או לא

97
00:03:59,000 --> 00:04:02,000
המספרים האלה הם כנראה ממשלה.

98
00:04:02,000 --> 00:04:05,000
אנחנו יכולים להחזיק את יצירת מספרים אקראיים שוב ושוב

99
00:04:05,000 --> 00:04:08,000
עד שיש לנו 2 מספרים ראשוניים שאנחנו יכולים להשתמש בו.

100
00:04:08,000 --> 00:04:15,000
הנה בואו לקחת p = 23, q = 43.

101
00:04:15,000 --> 00:04:19,000
זכרו, בפועל, p ו 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 ביטים,

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
במקרה שלנו, n = 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 עם ש - 1

113
00:05:02,000 --> 00:05:05,000
כדי לקבל מספר 4, שאנחנו קוראים למ '.

114
00:05:05,000 --> 00:05:15,000
במקרה שלנו, מ '= 22 * ​​42, אשר = 924.

115
00:05:15,000 --> 00:05:18,000
יש לנו מ '= 924.

116
00:05:18,000 --> 00:05:22,000
עכשיו אנחנו נצטרך דואר מספר שיחסית לראש מ '

117
00:05:22,000 --> 00:05:25,000
ופחות מ מ '.

118
00:05:25,000 --> 00:05:28,000
שני מספרים הם יחסית ממשלה או coprime

119
00:05:28,000 --> 00:05:33,000
אם המספר החיובי היחיד שמחלק את שניהם באופן שווה הוא 1.

120
00:05:33,000 --> 00:05:37,000
במילים אחרות, מחלק המשותף הגדול ביותר של דואר ומטר

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
כל עוד מספר זה לא קורה להיות פקטור של מטר.

124
00:05:48,000 --> 00:05:53,000
למפתחות שלנו, אנחנו ניקח את הדואר = 5

125
00:05:53,000 --> 00:05:57,000
מאז 5 הוא יחסית ממשלת 924.

126
00:05:57,000 --> 00:06:01,000
לבסוף, אנחנו נצטרך יותר מספר אחד, שאנחנו קוראים ד.

127
00:06:01,000 --> 00:06:11,000
D חייב להיות איזה שהוא ערך שמספק את משוואת דה = 1 (mod מ ').

128
00:06:11,000 --> 00:06:17,000
מ mod זה מסמל אנו נשתמש משהו שנקרא חשבון מודולרי.

129
00:06:17,000 --> 00:06:21,000
באריתמטיקה מודולרית, פעם במספר גבוה יותר מאשר מקבל כמה גבול העליון

130
00:06:21,000 --> 00:06:24,000
זה יהיה לעטוף סביב חזרה ל 0.

131
00:06:24,000 --> 00:06:27,000
שעון, למשל, משתמש בחשבון מודולרי.

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
המפתח הציבורי שלנו יהיה דואר הזוג וn

139
00:07:02,000 --> 00:07:09,000
במקרה זה שבו דואר הוא 5 ו n הוא 989.

140
00:07:09,000 --> 00:07:15,000
המפתח הפרטי שלנו יהיה הזוג ד ו 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
אני רוצה לשלוח הודעה לרוב,

147
00:07:38,000 --> 00:07:42,000
אז הוא יהיה זה שכדי ליצור צמד מפתחות זה.

148
00:07:42,000 --> 00:07:46,000
ואז אני אשאל את רוב למפתח הציבורי שלו, שאני אשתמש

149
00:07:46,000 --> 00:07:48,000
כדי להצפין את הודעה לשלוח אליו.

150
00:07:48,000 --> 00:07:53,000
זכור, זה לגמרי בסדר לרוב לחלוק המפתח הציבורי שלו איתי.

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
אנחנו יכולים לשבור מ 'המסר שלנו לכמה חתיכות

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
כדי להצפין מ 'הודעת נתונה

161
00:08:28,000 --> 00:08:37,000
אני צריך לחשב ג = מ 'לדואר (mod n).

162
00:08:37,000 --> 00:08:40,000
אבל מ 'חייב להיות קטן מ n,

163
00:08:40,000 --> 00:08:45,000
או שהודעה המלאה לא יכולה לבוא לידי ביטוי מודולו n.

164
00:08:45,000 --> 00:08:49,000
אנחנו יכולים לשבור מ 'לכמה חתיכות, שכולם קטנים מ n,

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
עכשיו אנחנו יכולים לשלוח את הערכים המוצפנים האלה לרוב.

175
00:09:54,000 --> 00:09:58,000
הנה לך, רוב.

176
00:09:58,000 --> 00:10:01,000
בעוד המסר שלנו נמצא במצב טיסה, בואו ניקח מבט נוסף

177
00:10:01,000 --> 00:10:07,000
באיך הגיע לשווי שד.

178
00:10:07,000 --> 00:10:17,000
מספר ד צורך לספק 5d = 1 (mod 924).

179
00:10:17,000 --> 00:10:24,000
זה הופך ד ההופכים של 5 מודולו 924.

180
00:10:24,000 --> 00:10:28,000
בהינתן 2 מספרים שלמים, ו-B, האלגוריתם אוקלידית המורחב

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
שיספק את גרזן המשוואה + = ידי מחלק המשותף הגדול ביותר של ב.

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
ו= 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
אבל אם אכפת לנו רק על הכל מודולו 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 המספר הזה, זה המספר שאנחנו צריכים להשתמש כד.

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, ד, ו-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, והערך שלנו עבור b, שהוא 924.

209
00:12:37,000 --> 00:12:40,000
הערך של העמודה 4, k, יהיה התוצאה

210
00:12:40,000 --> 00:12:45,000
חלוקת הערך של ד בשורה מעליו עם הערך של ד

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
ראשית, עלינו הערך של k שלנו.

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
הערך של k יהיה 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
הערך של ד בשורה שמעל אומר שאנחנו עושים עם האלגוריתם שלנו.

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
העובדה שד = 1 בשורה האחרונה

244
00:15:23,000 --> 00:15:26,000
מוודא שהדואר היה coprime למ '.

245
00:15:26,000 --> 00:15:30,000
אם זה לא היה 1 ואז הייתי צריך לקחת את הדואר חדש.

246
00:15:30,000 --> 00:15:33,000
עכשיו בואו נראה אם ​​רוב קבל את ההודעה שלי.

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
זכור כי ד ו 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
אם טומי מצפין מסר כלשהו באמצעות המפתח הציבורי שלי

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
וכך יודע מה טומי מוצפן.

283
00:17:32,000 --> 00:17:36,000
כדי למנוע זאת, הודעות מרופדות בדרך כלל עם ביטים אקראיים

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
ריפוד גושי משמעות הוא שאולי יש לנו לפצל את הדברים

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 הוא אלגוריתם מפתח סימטרי כמו Vigenère וצפני קיסר

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, 989 mod,

335
00:21:41,000 --> 00:21:51,000
וזה שווה ל 48, שהוא הערך של 0 בתו ASCII.

336
00:21:51,000 --> 00:21:57,000
השם שלי הוא רוב אודן, וזה 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
בכלל.