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] [Harvard University]

3
00:00:04,000 --> 00:00:07,000
[Mae hyn yn CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:11,000
Gadewch i ni edrych ar RSA, algorithm a ddefnyddir yn eang ar gyfer amgryptio data.

5
00:00:11,000 --> 00:00:16,000
Nid yw algorithmau Encryption fel Cesar a seifferau Vigenère yn ddiogel iawn.

6
00:00:16,000 --> 00:00:20,000
Gyda'r cipher Cesar, ymosodwr ond angen i roi cynnig ar 25 allweddi gwahanol

7
00:00:20,000 --> 00:00:22,000
i gael testun y neges yn blaen.

8
00:00:22,000 --> 00:00:25,000
Er bod y cipher Vigenère yn fwy diogel na'r cipher Cesar

9
00:00:25,000 --> 00:00:28,000
oherwydd y gofod chwilio mwy ar gyfer allweddi, unwaith y bydd ymosodwr

10
00:00:28,000 --> 00:00:30,000
yn gwybod hyd y allweddol mewn cipher Vigenère,

11
00:00:30,000 --> 00:00:34,000
y gellir ei benderfynu drwy ddadansoddiad o batrymau yn y testun wedi'i amgryptio,

12
00:00:34,000 --> 00:00:38,000
nid yw'r cipher Vigenère yw bod llawer mwy diogel na'r cipher Cesar.

13
00:00:38,000 --> 00:00:42,000
RSA, ar y llaw arall, nid yw'n agored i ymosodiadau fel hyn.

14
00:00:42,000 --> 00:00:45,000
Mae'r cipher Cesar a Vigenère cipher yn defnyddio'r un allweddol

15
00:00:45,000 --> 00:00:47,000
i'r ddau amgryptio a dadgryptio neges.

16
00:00:47,000 --> 00:00:51,000
Mae'r eiddo yn gwneud hyn yn allweddol seifferau algorithmau cymesur.

17
00:00:51,000 --> 00:00:54,000
Mae problem sylfaenol gyda algorithmau allweddol cymesur

18
00:00:54,000 --> 00:00:57,000
yw eu bod yn dibynnu ar yr un amgryptio ac yn anfon y neges

19
00:00:57,000 --> 00:00:59,000
a'r un sy'n derbyn ac yn decrypting y neges

20
00:00:59,000 --> 00:01:03,000
i eisoes wedi cytuno ar ymlaen llaw ar yr allwedd bydd y ddau yn eu defnyddio.

21
00:01:03,000 --> 00:01:06,000
Ond mae gennym dipyn o broblem startup yma.

22
00:01:06,000 --> 00:01:10,000
Sut mae 2 gyfrifiadur sydd am gyfathrebu sefydlu allwedd gudd rhyngddynt?

23
00:01:10,000 --> 00:01:16,000
Os oes rhaid i'r allweddol yn gyfrinach, yna mae angen ffordd i amgryptio a dadgryptio yr allwedd.

24
00:01:16,000 --> 00:01:18,000
Os yw'r holl gennym yw cryptograffeg cymesur allweddol

25
00:01:18,000 --> 00:01:21,000
yna rydym wedi newydd ddod yn ôl at yr un broblem.

26
00:01:21,000 --> 00:01:25,000
RSA, ar y llaw arall, yn defnyddio pâr o allweddi,

27
00:01:25,000 --> 00:01:28,000
un ar gyfer amgryptio a'r llall ar gyfer dadgriptio.

28
00:01:28,000 --> 00:01:32,000
Enw un yw'r allwedd gyhoeddus, a'r llall yw'r allwedd breifat.

29
00:01:32,000 --> 00:01:34,000
Yr allwedd gyhoeddus yn cael ei ddefnyddio i amgryptio negeseuon.

30
00:01:34,000 --> 00:01:38,000
Fel y gallech ddyfalu gan ei enw, gallwn rannu ein cyhoeddus allweddol gyda

31
00:01:38,000 --> 00:01:43,000
unrhyw un yr ydym eisiau heb gyfaddawdu diogelwch neges wedi ei amgryptio.

32
00:01:43,000 --> 00:01:45,000
Negeseuon hamgryptio gan ddefnyddio allwedd gyhoeddus

33
00:01:45,000 --> 00:01:49,000
dim ond ei dadgriptio gyda'i allwedd breifat.

34
00:01:49,000 --> 00:01:53,000
Er y gallwch rannu eich allwedd gyhoeddus, dylech bob amser gadw eich cyfrinach preifat allweddol.

61
00:01:55,000 --> 00:01:58,000
a dim ond yr allwedd breifat yn cael ei ddefnyddio i negeseuon dadgryptio

62
00:01:58,000 --> 00:02:02,000
os 2 defnyddiwr yn dymuno anfon negeseuon amgryptio gyda RSA

63
00:02:02,000 --> 00:02:07,000
yn ôl ac ymlaen ddwy angen i ddefnyddwyr gael eu hunain cyhoeddus a phreifat pâr allweddol.

64
00:02:07,000 --> 00:02:10,000
Negeseuon gan ddefnyddiwr 1 i ddefnyddiwr 2

65
00:02:10,000 --> 00:02:15,000
ond yn defnyddio pâr 2 defnyddiwr allweddol, a negeseuon o ddefnyddiwr 2 i ddefnyddiwr 1

66
00:02:15,000 --> 00:02:17,000
ond yn defnyddio defnyddiwr 1 pâr allweddol.

67
00:02:17,000 --> 00:02:21,000
Mae'r ffaith fod 2 allweddi ar wahân i amgryptio a dadgryptio negeseuon

68
00:02:21,000 --> 00:02:24,000
gwneud RSA algorithm allweddol anghymesur.

69
00:02:24,000 --> 00:02:28,000
Nid oes angen i amgryptio allweddol cyhoeddus er mwyn ei anfon at gyfrifiadur arall

70
00:02:28,000 --> 00:02:31,000
gan fod yr allwedd yn gyhoeddus beth bynnag.

71
00:02:31,000 --> 00:02:33,000
Mae hyn yn golygu nad oes gan RSA y broblem startup un

72
00:02:33,000 --> 00:02:36,000
fel y algorithmau cymesur allweddol.

73
00:02:36,000 --> 00:02:39,000
Felly, os ydw i eisiau anfon neges gan ddefnyddio amgryptio RSA

74
00:02:39,000 --> 00:02:42,000
i Rob, 'n annhymerus' yn gyntaf bydd angen Rob allweddol gyhoeddus.

75
00:02:42,000 --> 00:02:47,000
I greu pâr o allweddi, Rob angen i ddewis 2 rif cysefin mawr.

76
00:02:47,000 --> 00:02:50,000
Bydd y rhifau hyn yn cael ei ddefnyddio yn y ddwy allweddi cyhoeddus a'r sector preifat,

77
00:02:50,000 --> 00:02:54,000
ond bydd yr allwedd gyhoeddus ond yn defnyddio'r cynnyrch o'r 2 rhifau,

78
00:02:54,000 --> 00:02:56,000
nid yw'r niferoedd eu hunain.

79
00:02:56,000 --> 00:02:59,000
Unwaith yr wyf wedi amgryptio y neges gan ddefnyddio Rob allweddol cyhoeddus

80
00:02:59,000 --> 00:03:01,000
Gallaf anfon y neges i Rob.

81
00:03:01,000 --> 00:03:05,000
Am cyfrifiadur, rhifau ffactorio yn broblem anodd.

82
00:03:05,000 --> 00:03:09,000
Yr allwedd gyhoeddus, cofiwch, a ddefnyddir y cynnyrch o 2 rhifau cysefin.

83
00:03:09,000 --> 00:03:12,000
Mae'n rhaid i'r cynnyrch yna dim ond 2 ffactor,

84
00:03:12,000 --> 00:03:16,000
sy'n digwydd i fod y rhif sy'n gwneud i fyny 'r allwedd breifat.

85
00:03:16,000 --> 00:03:20,000
Er mwyn dadgryptio y neges, bydd RSA defnyddio'r allwedd breifat

86
00:03:20,000 --> 00:03:25,000
neu y niferoedd lluosi â'i gilydd yn y broses o greu yr allwedd gyhoeddus.

87
00:03:25,000 --> 00:03:28,000
Oherwydd ei fod yn computationally anodd i ffactor y nifer

88
00:03:28,000 --> 00:03:32,000
a ddefnyddir mewn cywair cyhoeddus i 2 rhifau a ddefnyddir yn yr allwedd breifat

89
00:03:32,000 --> 00:03:36,000
mae'n anodd i ymosodwr at chyfrif i maes yr allwedd breifat

90
00:03:36,000 --> 00:03:39,000
a fydd yn angenrheidiol i dadgryptio y neges.

91
00:03:39,000 --> 00:03:43,000
Nawr gadewch i ni fynd i mewn i rai manylion lefel is o RSA.

92
00:03:43,000 --> 00:03:46,000
Gadewch i ni yn gyntaf weld sut y gallwn greu pâr o allweddi.

93
00:03:46,000 --> 00:03:49,000
Yn gyntaf, bydd angen 2 rhifau cysefin.

94
00:03:49,000 --> 00:03:52,000
Byddwn yn galw'r rhain yn 2 rif p a q.

95
00:03:52,000 --> 00:03:56,000
Er mwyn dewis p a q, yn ymarferol byddem yn pseudorandomly cynhyrchu

96
00:03:56,000 --> 00:03:59,000
niferoedd mawr ac yna defnyddio prawf ar gyfer penderfynu a ddylid

97
00:03:59,000 --> 00:04:02,000
niferoedd hynny yn ôl pob tebyg cysefin.

98
00:04:02,000 --> 00:04:05,000
Gallwn gadw cynhyrchu rhifau ar hap drosodd a throsodd

99
00:04:05,000 --> 00:04:08,000
hyd nes y byddwn yn cael 2 rhifau cysefin y gallwn eu defnyddio.

100
00:04:08,000 --> 00:04:15,000
Yma gadewch i ni ddewis p = 23 a q = 43.

101
00:04:15,000 --> 00:04:19,000
Cofiwch, yn ymarferol, dylai p a q yn niferoedd llawer mwy.

102
00:04:19,000 --> 00:04:22,000
Cyn belled ag y gwyddom, y mwyaf y nifer, yr anoddaf yw hi

103
00:04:22,000 --> 00:04:25,000
i fynd i'r afael neges wedi ei amgryptio.

104
00:04:25,000 --> 00:04:29,000
Ond mae hefyd yn fwy costus i negeseuon amgryptio a dadgryptio.

105
00:04:29,000 --> 00:04:33,000
Heddiw, mae'n argymhellir yn aml fod p a q yn o leiaf 1024 darnau,

106
00:04:33,000 --> 00:04:37,000
sy'n rhoi pob rhif ar dros 300 o digid degol.

107
00:04:37,000 --> 00:04:40,000
Ond byddwn yn dewis y niferoedd bach ar gyfer yr enghraifft hon.

108
00:04:40,000 --> 00:04:43,000
Nawr byddwn yn lluosi p a q at ei gilydd i gael nifer 3ydd,

109
00:04:43,000 --> 00:04:45,000
y byddwn yn galw n.

110
00:04:45,000 --> 00:04:55,000
Yn ein hachos ni, n = 23 * 43, sy'n = 989.

111
00:04:55,000 --> 00:04:58,000
Rydym wedi n = 989.

112
00:04:58,000 --> 00:05:02,000
Nesaf byddwn yn lluosi p - 1 gyda q - 1

113
00:05:02,000 --> 00:05:05,000
i gael rhif 4, y byddwn yn galw m.

114
00:05:05,000 --> 00:05:15,000
Yn ein hachos ni, m = 22 * ​​42, sy'n = 924.

115
00:05:15,000 --> 00:05:18,000
Rydym wedi m = 924.

116
00:05:18,000 --> 00:05:22,000
Nawr bydd angen inni gael e rhif sydd gymharol wych i m

117
00:05:22,000 --> 00:05:25,000
a llai na m.

118
00:05:25,000 --> 00:05:28,000
Mae dau niferoedd yn gymharol cysefin neu coprime

119
00:05:28,000 --> 00:05:33,000
os yw'r cyfanrif positif yn unig sy'n rhannu ddau ohonynt gyfartal yw 1.

120
00:05:33,000 --> 00:05:37,000
Mewn geiriau eraill, y rhannydd mwyaf cyffredin o e m a

121
00:05:37,000 --> 00:05:39,000
Mae'n rhaid i fod yn 1.

122
00:05:39,000 --> 00:05:44,000
Yn ymarferol, mae'n gyffredin i e i fod yn rhif cysefin 65,537

123
00:05:44,000 --> 00:05:48,000
cyn belled nad y nifer hwn yn digwydd i fod yn ffactor o m.

124
00:05:48,000 --> 00:05:53,000
Ar gyfer ein allweddi, byddwn yn dewis e = 5

125
00:05:53,000 --> 00:05:57,000
ers 5 yn gymharol wych i 924.

126
00:05:57,000 --> 00:06:01,000
Yn olaf, bydd angen un rhif fwy, y byddwn yn galw d.

127
00:06:01,000 --> 00:06:11,000
Rhaid i D fod rhywfaint o werth sy'n bodloni'r hafaliad de = 1 (mod m).

128
00:06:11,000 --> 00:06:17,000
Mae hyn yn m mod yn dynodi y byddwn yn defnyddio rhywbeth o'r enw rhifyddeg modiwlaidd.

129
00:06:17,000 --> 00:06:21,000
Yn rhifyddeg modiwlaidd, unwaith y mae nifer yn cael uwch na rhai rhwymo uchaf

130
00:06:21,000 --> 00:06:24,000
bydd yn lapio o gwmpas yn ôl i 0.

131
00:06:24,000 --> 00:06:27,000
Mae cloc, er enghraifft, yn defnyddio rhifyddeg modiwlaidd.

132
00:06:27,000 --> 00:06:31,000
Un munud ar ôl 01:59, er enghraifft, yn 2:00,

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

134
00:06:33,000 --> 00:06:36,000
Y llaw munud wedi lapio o amgylch i 0

135
00:06:36,000 --> 00:06:39,000
ar gyrraedd uchaf rhwymo o 60.

136
00:06:39,000 --> 00:06:46,000
Felly, gallwn ddweud 60 yn cyfateb i 0 (mod 60)

137
00:06:46,000 --> 00:06:57,000
a 125 yn cyfateb i 65 yn cyfateb i 5 (mod 60).

138
00:06:57,000 --> 00:07:02,000
Bydd ein cyhoeddus allweddol fydd y e pâr a n

139
00:07:02,000 --> 00:07:09,000
lle yn yr achos hwn yw e 5 a n yn 989.

140
00:07:09,000 --> 00:07:15,000
Bydd ein allwedd breifat fydd y pâr a d n,

141
00:07:15,000 --> 00:07:22,000
sydd, yn ein hachos 185 a 989.

142
00:07:22,000 --> 00:07:25,000
Hysbysiad nad yw ein gwreiddiol rhifau cysefin p a q yn ymddangos

143
00:07:25,000 --> 00:07:29,000
unrhyw le yn yr allweddi preifat neu gyhoeddus.

144
00:07:29,000 --> 00:07:33,000
Nawr ein bod wedi ein pâr o allweddi, gadewch i ni edrych ar sut y gallwn amgryptio

145
00:07:33,000 --> 00:07:36,000
a dadgryptio neges.

146
00:07:36,000 --> 00:07:38,000
Dw i eisiau anfon neges i Rob,

147
00:07:38,000 --> 00:07:42,000
felly bydd yn cael yr un i gynhyrchu y pâr allweddol.

148
00:07:42,000 --> 00:07:46,000
Yna, byddaf yn gofyn i Rob am ei cyhoeddus allweddol, a byddaf yn defnyddio

149
00:07:46,000 --> 00:07:48,000
i amgryptio neges i'w hanfon iddo.

150
00:07:48,000 --> 00:07:53,000
Cofiwch, mae'n hollol iawn i Rob i rannu ei cyhoeddus allweddol gyda mi.

151
00:07:53,000 --> 00:07:56,000
Ond ni fyddai'n iawn i rannu ei allwedd breifat.

152
00:07:56,000 --> 00:08:00,000
Nid oes gennyf unrhyw syniad beth yw ei allwedd breifat yn.

153
00:08:00,000 --> 00:08:03,000
Gallwn torri ein m neges i fyny yn ddarnau nifer o

154
00:08:03,000 --> 00:08:07,000
i gyd yn llai na n ac yna amgryptio pob un o'r darnau.

155
00:08:07,000 --> 00:08:12,000
Byddwn yn encrypt y, CS50 llinyn y gallwn dorri i fyny i mewn 4 ddarnau,

156
00:08:12,000 --> 00:08:14,000
un ar gyfer pob llythyren.

157
00:08:14,000 --> 00:08:17,000
Er mwyn amgryptio fy neges, bydd angen i mi droi i mewn i

158
00:08:17,000 --> 00:08:20,000
rhyw fath o gynrychiolaeth rhifol.

159
00:08:20,000 --> 00:08:25,000
Gadewch i concatenate y gwerthoedd ASCII gyda'r cymeriadau yn fy neges.

160
00:08:25,000 --> 00:08:28,000
Er mwyn amgryptio a m neges a roddir

161
00:08:28,000 --> 00:08:37,000
Bydd angen i mi gyfrifo c = m i'r e (mod n).

162
00:08:37,000 --> 00:08:40,000
Ond mae'n rhaid m fod yn llai na n,

163
00:08:40,000 --> 00:08:45,000
neu ni all y neges llawn yn cael ei fynegi modwlo n.

164
00:08:45,000 --> 00:08:49,000
Gallwn dorri m i fyny i ddarnau nifer, pob un ohonynt yn llai na n,

165
00:08:49,000 --> 00:08:52,000
ac amgryptio pob un o'r darnau.

166
00:08:52,000 --> 00:09:03,000
Amgryptio pob un o'r darnau, rydym yn cael c1 = 67 i 5 (mod 989)

167
00:09:03,000 --> 00:09:06,000
sy'n = 658.

168
00:09:06,000 --> 00:09:15,000
Ar gyfer ein darn 2 mae gennym 83 i 5 (mod 989)

169
00:09:15,000 --> 00:09:18,000
sy'n = 15.

170
00:09:18,000 --> 00:09:26,000
Ar gyfer ein darn drydedd wedi 53 i 5 (mod 989)

171
00:09:26,000 --> 00:09:30,000
sy'n = 799.

172
00:09:30,000 --> 00:09:39,000
Ac yn olaf, ar gyfer ein darn olaf sydd gennym 48 at y 5 (mod 989)

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

174
00:09:43,000 --> 00:09:48,000
Nawr gallwn anfon dros y gwerthoedd amgryptio i Rob.

175
00:09:54,000 --> 00:09:58,000
Dyma chi fynd, Rob.

176
00:09:58,000 --> 00:10:01,000
Er bod ein neges yn hedfan, gadewch i ni edrych eto

177
00:10:01,000 --> 00:10:07,000
ar sut yr ydym yn cael y gwerth am d.

178
00:10:07,000 --> 00:10:17,000
Angen nifer Ein d i fodloni 5d = 1 (mod 924).

179
00:10:17,000 --> 00:10:24,000
Mae hyn yn gwneud d gwrthdro multiplicative o 5 modwlo 924.

180
00:10:24,000 --> 00:10:28,000
Cael 2 cyfanrifau, a b a, algorithm Ewclidaidd estynedig

181
00:10:28,000 --> 00:10:33,000
gellir ei ddefnyddio i ddod o hyd i'r rhannydd cyffredin mwyaf y 2 gyfanrifau.

182
00:10:33,000 --> 00:10:37,000
Bydd hefyd yn rhoi 2 rifau eraill, x ac y,

183
00:10:37,000 --> 00:10:47,000
sy'n bodloni'r hafaliad ax + by = y rhannydd mwyaf cyffredin o b a.

184
00:10:47,000 --> 00:10:49,000
Sut mae hyn yn helpu ni?

185
00:10:49,000 --> 00:10:52,000
Wel, plygio i mewn e = 5 ar gyfer

186
00:10:52,000 --> 00:10:56,000
ac m = 924 ar gyfer b

187
00:10:56,000 --> 00:10:59,000
rydym eisoes yn gwybod bod y niferoedd yn coprime.

188
00:10:59,000 --> 00:11:03,000
Mae eu mwyaf rhannydd cyffredin yw 1.

189
00:11:03,000 --> 00:11:09,000
Mae hyn yn rhoi i ni 5x + 924y = 1

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

191
00:11:17,000 --> 00:11:22,000
Ond os mai dim ond gofalu am bopeth modwlo 924

192
00:11:22,000 --> 00:11:25,000
yna gallwn gollwng y - 924y.

193
00:11:25,000 --> 00:11:27,000
Meddyliwch yn ôl at y cloc.

194
00:11:27,000 --> 00:11:31,000
Os y llaw munud ar 1 ac yna yn union 10 awr pasio,

195
00:11:31,000 --> 00:11:35,000
rydym yn gwybod y bydd y llaw munud yn dal i fod ar y 1.

196
00:11:35,000 --> 00:11:39,000
Yma, rydym yn dechrau ar 1 ac yna lapio o amgylch amseroedd yn union y,

197
00:11:39,000 --> 00:11:41,000
felly byddwn yn dal i fod yn 1.

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

199
00:11:49,000 --> 00:11:55,000
A dyma y x yw yr un fath â'r d roeddem yn chwilio am o'r blaen,

200
00:11:55,000 --> 00:11:58,000
felly os byddwn yn defnyddio'r algorithm Ewclidaidd estynedig

201
00:11:58,000 --> 00:12:04,000
i gael y rhif x, dyna'r rhif y dylem ei ddefnyddio fel ein d.

202
00:12:04,000 --> 00:12:07,000
Nawr, gadewch i redeg yr algorithm Ewclidaidd estynedig am 5 =

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

204
00:12:11,000 --> 00:12:14,000
Byddwn yn defnyddio dull o'r enw y dull bwrdd.

205
00:12:14,000 --> 00:12:21,000
Bydd ein bwrdd yn cael 4 colofn, x, y, d, a k.

206
00:12:21,000 --> 00:12:23,000
Mae ein bwrdd yn dechrau i ffwrdd gyda 2 res.

207
00:12:23,000 --> 00:12:28,000
Yn y rhes gyntaf rydym wedi 1, 0, yna mae ein gwerth, sef 5,

208
00:12:28,000 --> 00:12:37,000
ac mae ein ail res yw 0, 1, ac mae ein gwerth am b, sef 924.

209
00:12:37,000 --> 00:12:40,000
Bydd gwerth y golofn 4ydd, k, fod yn ganlyniad

210
00:12:40,000 --> 00:12:45,000
o rannu gwerth d yn y rhes uwch ei ben gyda gwerth d

211
00:12:45,000 --> 00:12:49,000
ar yr un rhes.

212
00:12:49,000 --> 00:12:56,000
Mae gennym 5 wedi'i rannu â 924 yw 0 gyda rhai gweddill.

213
00:12:56,000 --> 00:12:59,000
Mae hynny'n golygu ein bod wedi k = 0.

214
00:12:59,000 --> 00:13:05,000
Yn awr, bydd y gwerth pob cell arall fydd gwerth y 2 cell rhesi uchod

215
00:13:05,000 --> 00:13:09,000
minws gwerth y rhes uwch ei gwaith k.

216
00:13:09,000 --> 00:13:11,000
Gadewch i ni ddechrau gyda d yn y rhes 3ydd.

217
00:13:11,000 --> 00:13:19,000
Mae gennym 5-924 * 0 = 5.

218
00:13:19,000 --> 00:13:25,000
Nesaf rydym 0 - 1 * 0 a yw 0

219
00:13:25,000 --> 00:13:30,000
a 1 - 0 * 0 sef 1.

220
00:13:30,000 --> 00:13:33,000
Ddim yn rhy ddrwg, felly gadewch i ni symud ymlaen i'r rhes nesaf.

221
00:13:33,000 --> 00:13:36,000
Yn gyntaf mae angen ein gwerth k.

222
00:13:36,000 --> 00:13:43,000
924 wedi'i rannu â 5 = 184 gyda rhai gweddill,

223
00:13:43,000 --> 00:13:46,000
felly mae ein gwerth am k yw 184.

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

225
00:13:54,000 --> 00:14:05,000
1-0 * 184 yw 1 a 0-1 * 184 yn -184.

226
00:14:05,000 --> 00:14:07,000
Mae pob hawl, gadewch i ni wneud y rhes nesaf.

227
00:14:07,000 --> 00:14:10,000
Bydd ein gwerth k fod yn 1 oherwydd

228
00:14:10,000 --> 00:14:15,000
5 wedi'i rannu â 4 = 1 gyda rhai gweddill.

229
00:14:15,000 --> 00:14:17,000
Gadewch i ni llenwch y colofnau eraill.

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
Ac 1-184 * 1 yn 185.

233
00:14:33,000 --> 00:14:35,000
Gadewch i ni weld beth fyddai ein gwerth nesaf k fod.

234
00:14:35,000 --> 00:14:40,000
Wel, mae'n edrych fel mae gennym 4 wedi'i rannu gan 1, sef 4.

235
00:14:40,000 --> 00:14:43,000
Yn yr achos hwn lle'r ydym yn rhannu erbyn 1 fel bod k yn hafal i

236
00:14:43,000 --> 00:14:50,000
gwerth d yn y rhes uchod yn golygu ein bod yn ei wneud gyda ein algorithm.

237
00:14:50,000 --> 00:14:58,000
Gallwn weld yma fod gennym x = 185 ac y = -1 yn y rhes olaf.

238
00:14:58,000 --> 00:15:00,000
Gadewch i ni yn awr yn dod yn ôl at ein nod gwreiddiol.

239
00:15:00,000 --> 00:15:04,000
Rydym yn dweud bod y gwerth o x o ganlyniad i gynnal y algorithm

240
00:15:04,000 --> 00:15:08,000
fyddai wrthdro multiplicative o (mod b).

241
00:15:08,000 --> 00:15:15,000
Mae hynny'n golygu bod 185 yn wrthdro multiplicative o 5 (mod 924)

242
00:15:15,000 --> 00:15:20,000
sy'n golygu bod gennym werth o 185 i d.

243
00:15:20,000 --> 00:15:23,000
Mae'r ffaith bod d = 1 yn y rhes olaf

244
00:15:23,000 --> 00:15:26,000
cadarnhau bod e yn coprime i m.

245
00:15:26,000 --> 00:15:30,000
Os nad oedd 1, yna byddai'n rhaid i ni ddewis e newydd.

246
00:15:30,000 --> 00:15:33,000
Nawr gadewch i ni weld os Rob wedi derbyn fy neges.

247
00:15:33,000 --> 00:15:35,000
Pan fydd rhywun yn anfon neges i mi ei amgryptio

248
00:15:35,000 --> 00:15:38,000
cyn belled gan fy mod i wedi cadw fy allwedd breifat yn gyfrinach

249
00:15:38,000 --> 00:15:41,000
Fi yw'r unig un sy'n gallu dadgryptio y neges.

250
00:15:41,000 --> 00:15:46,000
I dadgryptio a c dalp gallaf gyfrifo y neges wreiddiol

251
00:15:46,000 --> 00:15:53,000
yn hafal i'r darn i d pŵer (mod n).

252
00:15:53,000 --> 00:15:57,000
Cofiwch fod d a n yn dod o fy allwedd breifat.

253
00:15:57,000 --> 00:16:01,000
I gael neges llawn o'i darnau rydym yn dadgryptio bob darn

254
00:16:01,000 --> 00:16:04,000
ac yn concatenate y canlyniadau.

255
00:16:04,000 --> 00:16:08,000
Yn union pa mor ddiogel yw RSA?

256
00:16:08,000 --> 00:16:10,000
Y gwir yw, nid ydym yn gwybod.

257
00:16:10,000 --> 00:16:14,000
Diogelwch yn seiliedig ar ba mor hir y byddai'n ei gymryd i ymosodwr i dorri neges

258
00:16:14,000 --> 00:16:16,000
amgryptio gyda RSA.

259
00:16:16,000 --> 00:16:19,000
Cofiwch fod ymosodwr yn cael mynediad at eich allwedd gyhoeddus,

260
00:16:19,000 --> 00:16:21,000
Ynddo, mae e a n.

261
00:16:21,000 --> 00:16:26,000
Os yw'r ymosodwr yn llwyddo i ffactor n yn ei 2 rhifau cysefin, p a q,

262
00:16:26,000 --> 00:16:30,000
yna gallai hi gyfrifo d ddefnyddio'r algorithm Ewclidaidd estynedig.

263
00:16:30,000 --> 00:16:35,000
Mae hyn yn rhoi iddi allwedd breifat, y gellir ei ddefnyddio i dadgryptio unrhyw neges.

264
00:16:35,000 --> 00:16:38,000
Ond pa mor gyflym rydym yn ffactor cyfanrifau?

265
00:16:38,000 --> 00:16:41,000
Unwaith eto, nid ydym yn gwybod.

266
00:16:41,000 --> 00:16:43,000
Does neb wedi dod o hyd i ffordd gyflym o wneud hynny,

267
00:16:43,000 --> 00:16:46,000
sy'n golygu y rhoddir digon mawr n

268
00:16:46,000 --> 00:16:49,000
byddai'n cymryd ymosodwr afrealistig o hir

269
00:16:49,000 --> 00:16:51,000
i ffactor y rhif.

270
00:16:51,000 --> 00:16:54,000
Os bydd rhywun yn dangos ffordd gyflym o gyfanrifau ffactoreiddio

271
00:16:54,000 --> 00:16:57,000
Byddai RSA yn cael ei dorri.

272
00:16:57,000 --> 00:17:01,000
Ond hyd yn oed os cyfanrif factorization yn ei hanfod yn araf

273
00:17:01,000 --> 00:17:04,000
gallai'r algorithm RSA yn dal i gael rhywfaint o nam yn ei

274
00:17:04,000 --> 00:17:07,000
sy'n caniatáu ar gyfer Gwall Rheolwr hawdd o negeseuon.

275
00:17:07,000 --> 00:17:10,000
Does neb wedi dod o hyd ac yn datgelu o'r fath yn wendid eto,

276
00:17:10,000 --> 00:17:12,000
ond nid yw hynny'n golygu nad oes un yn bodoli.

277
00:17:12,000 --> 00:17:17,000
Yn ddamcaniaethol, gallai rhywun fod allan yno yn darllen yr holl ddata amgryptio gyda RSA.

278
00:17:17,000 --> 00:17:19,000
Mae un arall dipyn o fater preifatrwydd.

279
00:17:19,000 --> 00:17:23,000
Os Tommy encrypts rhywfaint o neges gan ddefnyddio fy cyhoeddus allweddol

280
00:17:23,000 --> 00:17:26,000
ac ymosodwr encrypts yr un neges gan ddefnyddio fy cyhoeddus allweddol

281
00:17:26,000 --> 00:17:29,000
Bydd yr ymosodwr yn gweld bod y 2 negeseuon yn union yr un fath

282
00:17:29,000 --> 00:17:32,000
ac felly yn gwybod beth Tommy amgryptio.

283
00:17:32,000 --> 00:17:36,000
Er mwyn atal hyn, negeseuon yn cael eu padio fel arfer gyda darnau ar hap

284
00:17:36,000 --> 00:17:39,000
cyn cael ei amgryptio fel bod yr un neges amgryptio

285
00:17:39,000 --> 00:17:44,000
Bydd sawl gwaith yn edrych yn wahanol cyhyd â bod y padin ar y neges yn wahanol.

286
00:17:44,000 --> 00:17:47,000
Ond cofiwch sut y mae'n rhaid i ni rannu negeseuon i mewn i ddarnau

287
00:17:47,000 --> 00:17:50,000
fel bod pob darn yn llai na n?

288
00:17:50,000 --> 00:17:52,000
Phadin y darnau yn golygu y gallai fod yn rhaid i rannu pethau i fyny

289
00:17:52,000 --> 00:17:57,000
yn ddarnau hyd yn oed mwy gan fod yn rhaid i'r darn padded yn llai nag n.

290
00:17:57,000 --> 00:18:01,000
Encryption a dadgriptio yn gymharol ddrud gyda RSA,

291
00:18:01,000 --> 00:18:05,000
ac felly gall fod angen i dorri i fyny neges yn ddarnau lawer o fod yn gostus iawn.

292
00:18:05,000 --> 00:18:09,000
Os bydd swm mawr o ddata mae angen ei amgryptio a dadgryptio

293
00:18:09,000 --> 00:18:12,000
gallwn gyfuno manteision o algorithmau allweddol cymesur

294
00:18:12,000 --> 00:18:16,000
â rhai RSA i gael y ddau diogelwch ac effeithlonrwydd.

295
00:18:16,000 --> 00:18:18,000
Er na fyddwn yn mynd i mewn yma,

296
00:18:18,000 --> 00:18:23,000
AES yn algorithm allweddol cymesur fel y Vigenère a seifferau Caesar

297
00:18:23,000 --> 00:18:25,000
ond yn llawer anoddach i agenna.

298
00:18:25,000 --> 00:18:30,000
Wrth gwrs, ni allwn ddefnyddio AES heb sefydlu allwedd gudd

299
00:18:30,000 --> 00:18:34,000
rhwng y 2 system, ac rydym yn gweld y broblem gyda hynny o'r blaen.

300
00:18:34,000 --> 00:18:40,000
Ond nawr gallwn ddefnyddio'r RSA i sefydlu'r allwedd gudd rhwng y 2 system.

301
00:18:40,000 --> 00:18:43,000
Byddwn yn galw y cyfrifiadur yn anfon y data yr anfonwr

302
00:18:43,000 --> 00:18:46,000
ac mae'r cyfrifiadur yn derbyn y data y derbynnydd.

303
00:18:46,000 --> 00:18:49,000
Mae'r derbynnydd yn cael pâr allweddol RSA ac yn anfon

304
00:18:49,000 --> 00:18:51,000
yr allwedd gyhoeddus at yr anfonwr.

305
00:18:51,000 --> 00:18:54,000
Mae'r anfonwr yn cynhyrchu allweddol AES,

306
00:18:54,000 --> 00:18:57,000
amgryptio gyda allweddol y derbynnydd cyhoeddus RSA,

307
00:18:57,000 --> 00:19:00,000
ac yn anfon allweddol AES i'r derbynnydd.

308
00:19:00,000 --> 00:19:04,000
Mae'r derbynnydd decrypts y neges gyda'i allweddol RSA breifat.

309
00:19:04,000 --> 00:19:09,000
Mae'r anfonwr a'r derbynnydd bellach allweddol AES rhannu rhyngddynt.

310
00:19:09,000 --> 00:19:14,000
AES, sydd yn llawer cyflymach yn amgryptio a dadgriptio na RSA,

311
00:19:14,000 --> 00:19:18,000
yn awr yn gallu cael ei ddefnyddio i amgryptio y symiau mawr o ddata ac yn eu hanfon at y derbynnydd,

312
00:19:18,000 --> 00:19:21,000
sy'n gallu dadgryptio ddefnyddio'r allwedd un.

313
00:19:21,000 --> 00:19:26,000
AES, sydd yn llawer cyflymach yn amgryptio a dadgriptio na RSA,

314
00:19:26,000 --> 00:19:30,000
yn awr yn gallu cael ei ddefnyddio i amgryptio y symiau mawr o ddata ac yn eu hanfon at y derbynnydd,

315
00:19:30,000 --> 00:19:32,000
sy'n gallu dadgryptio ddefnyddio'r allwedd un.

316
00:19:32,000 --> 00:19:36,000
Rydym yn unig sydd ei angen RSA i drosglwyddo'r allweddol a rennir.

317
00:19:36,000 --> 00:19:40,000
Rydym nid oes angen i ddefnyddio RSA o gwbl.

318
00:19:40,000 --> 00:19:46,000
Mae'n edrych fel gen i neges.

319
00:19:46,000 --> 00:19:49,000
Nid oes ots os unrhyw un wedi darllen beth sydd ar yr awyren papur cyn i mi ei ddal

320
00:19:49,000 --> 00:19:55,000
oherwydd fi yw'r unig un gyda'r allwedd breifat.

321
00:19:55,000 --> 00:19:57,000
Gadewch i ni dadgryptio pob un o'r darnau yn y neges.

322
00:19:57,000 --> 00:20:07,000
Y darn cyntaf, 658, rydym yn codi i rym d, sef 185,

323
00:20:07,000 --> 00:20:18,000
mod n, sef 989, yn hafal i 67,

324
00:20:18,000 --> 00:20:24,000
sef y llythyren C yn ASCII.

325
00:20:24,000 --> 00:20:31,000
Yn awr, ar y darn ail.

326
00:20:31,000 --> 00:20:35,000
Mae'r darn gan ail werth 15,

327
00:20:35,000 --> 00:20:41,000
yr ydym yn codi i 185 y pŵer,

328
00:20:41,000 --> 00:20:51,000
mod 989, ac mae hyn yn hafal i 83

329
00:20:51,000 --> 00:20:57,000
sef y S llythyr yn ASCII.

330
00:20:57,000 --> 00:21:06,000
Nawr am y darn trydydd sydd â gwerth 799, rydym yn codi i 185,

331
00:21:06,000 --> 00:21:17,000
mod 989, ac mae hyn yn hafal i 53,

332
00:21:17,000 --> 00:21:24,000
sef y gwerth y cymeriad 5 yn ASCII.

333
00:21:24,000 --> 00:21:30,000
Nawr am y darn olaf, sydd â gwerth 975,

334
00:21:30,000 --> 00:21:41,000
rydym yn codi i 185, mod 989,

335
00:21:41,000 --> 00:21:51,000
ac mae hyn yn hafal i 48, sef gwerth y 0 cymeriad yn ASCII.

336
00:21:51,000 --> 00:21:57,000
Fy enw i yw Rob Bowden, ac mae hyn yn CS50.

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

338
00:22:06,000 --> 00:22:08,000
RSA o gwbl.

339
00:22:08,000 --> 00:22:14,000
RSA o gwbl. [Chwerthin]

340
00:22:14,000 --> 00:22:17,000
O gwbl.