[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Ollscoil Harvard]
[Tá sé seo CS50.] [CS50.TV]
A ligean ar ghlacadh le breathnú ar RSA, algartam a úsáidtear go forleathan le haghaidh sonraí encrypting.
Nach bhfuil halgartaim Criptiú cosúil le Caesar agus sifir Vigenère an-slán.
Leis an cipher Caesar, ní mór an ionsaitheoir amháin chun iarracht a dhéanamh 25 eochracha difriúla
a fháil ar an teachtaireacht ar gnáth-théacs.
Cé go bhfuil an cipher Vigenère níos sábháilte ná an cipher Caesar
mar gheall ar an spás cuardaigh níos mó le haghaidh eochracha, a luaithe a ionsaitheoir
fhios ag an fad an eochair i cipher Vigenère,
féidir a chinneadh trí anailís ar phatrúin sa téacs criptithe,
nach bhfuil an cipher Vigenère go bhfuil i bhfad níos sábháilte ná an shifir Caesar.
RSA, ar an láimh eile, nach bhfuil i mbaol ionsaithe mar seo.
Tá an cipher Caesar agus Vigenère cipher a bhaint as an eochair céanna a
iad araon, a criptigh agus dhíchriptiú teachtaireacht.
Déanann an mhaoin na halgartaim sifir eochair siméadracha.
Fadhb bhunúsach le halgartaim eochair siméadracha
is é sin siad ag brath ar an ceann gcriptiú agus a sheoladh an teachtaireacht
agus an ceann a fháil agus ndíchriptiú an teachtaireacht
chun an gcomhaontú cheana féin upfront ar an eochair beidh siad araon a úsáid.
Ach ní mór dúinn le beagán de fadhb tosaithe anseo.
Conas a 2 ríomhairí atá ag iarraidh a chur in iúl a bhunú eochair rúnda idir iad?
Más gá an eochair a bheith rúnda, ansin is gá dúinn ar bhealach a chriptiú agus a dhíchriptiú an eochair.
Má tá gach ní mór dúinn cripteagrafaíochta eochair siméadracha
ansin tá muid díreach tar éis teacht ar ais go dtí an fhadhb chéanna.
RSA, ar an láimh eile, úsáideann an péire eochracha,
ceann amháin le haghaidh chriptiú agus ceann eile do decryption.
Tá ceann amháin ar a dtugtar an eochair phoiblí, agus an ceann eile go bhfuil an eochair phríobháideach.
Is é an eochair phoiblí a úsáidtear chun teachtaireachtaí a chriptiú.
Mar a d'fhéadfadh buille faoi thuairim ag a ainm, is féidir linn a roinnt lenár eochair phoiblí le
duine ar bith ba mhaith linn gan cur isteach ar shlándáil teachtaireacht criptithe.
Teachtaireachtaí criptithe ag baint úsáide as eochair phoiblí
is féidir iad a decrypted ach amháin lena eochair phríobháideach a fhreagraíonn.
Cé gur féidir leat roinnt do eochair phoiblí, ba chóir duit a choinneáil i gcónaí do rún eochair phríobháideach.
agus ní féidir ach an eochair phríobháideach a úsáid chun teachtaireachtaí a dhíchriptiú
más mian 2 úsáideoir a sheoladh teachtaireachtaí criptithe le RSA
anonn 's anall is gá dá úsáideoirí a bhfuil a n-péire eochair féin poiblí agus príobháideacha.
Teachtaireachtaí ó úsáideoirí 1 go 2 úsáideoir
amháin 2 úsáideora péire eochair, agus teachtaireachtaí a úsáid ó úsáideoir seo 2 don úsáideoir 1
ach úsáid a bhaint as péire eochair úsáideora 1 ar.
Ós rud é go bhfuil 2 eochracha ar leith a chriptiú agus a dhíchriptiú teachtaireachtaí
Déanann RSA algartaim neamhshiméadracha eochair.
Ní gá dúinn a chriptiú an eochair phoiblí d'fhonn é a sheoladh chuig ríomhaire eile
ós rud é go bhfuil an eochair phoiblí ar aon nós.
Ciallaíonn sé seo nach bhfuil RSA bhfuil an fhadhb chéanna am tosaithe
mar na halgartaim siméadracha eochair.
Mar sin, más mian liom a sheoladh teachtaireacht ag baint úsáide as criptithe RSA
chun Rob, beidh mé gá an chéad eochair phoiblí Rob ar.
A ghiniúint le péire de eochracha, ní mór Rob a phiocadh 2 uimhreacha príomha mór.
Beidh na huimhreacha a úsáid sa dá eochair phoiblí agus phríobháideach,
ach beidh an eochair phoiblí a úsáid ach amháin an táirge na huimhreacha 2,
nach bhfuil an líon féin.
Chomh luath agus tá mé an teachtaireacht criptithe ag baint úsáide as eochair phoiblí Rob ar
Is féidir liom an teachtaireacht a sheoladh chuig Rob.
Le haghaidh ríomhaire, tá líon na fachtóireacht fadhb crua.
An eochair phoiblí, cuimhnigh, a úsáidtear an táirge de 2 uimhir phríomha.
Ní mór an táirge a bhfuil ansin ach 2 fachtóirí,
a tharlaíonn a bheith ar an líon a dhéanann suas an eochair phríobháideach.
D'fhonn a dhíchriptiú an teachtaireacht, beidh an RSA seo a úsáid eochair phríobháideach
nó iolrú ar an líon le chéile i an próiseas a chruthú ar an eochair phoiblí.
Toisc go bhfuil sé computationally deacair a fhachtóir an líon
a úsáidtear i eochair phoiblí i 2 uimhreacha arna úsáid i an eochair phríobháideach
tá sé deacair do ionsaitheoir a figiúr amach an eochair phríobháideach
a bheidh riachtanach chun a dhíchriptiú an teachtaireacht.
Anois, a ligean dul isteach i roinnt sonraí ar leibhéal níos ísle de RSA.
A ligean ar féach an chéad conas is féidir linn a ghiniúint le péire de eochracha.
Gcéad dul síos, beidh orainn gá 2 uimhreacha príomha.
Beidh muid glaoch ar na huimhreacha 2 p agus q.
D'fhonn a phiocadh p agus q, i gcleachtas ba mhaith linn a ghiniúint pseudorandomly
líon mór agus ansin a úsáid tástáil chun a chinneadh an bhfuil nó nach
Is iad na huimhreacha dócha príomha.
Is féidir linn a choinneáil ar ghiniúint uimhreacha randamacha arís agus arís eile
go dtí go mór dúinn 2 primes gur féidir linn a úsáid.
Seo a ligean ar phiocadh p = 23 agus q = 43.
Cuimhnigh, i gcleachtas, ba chóir go mbeadh p agus q líon i bhfad níos mó.
Chomh fada agus is eol dúinn, níos mó an líon, an níos deacra tá sé
a crack teachtaireacht criptithe.
Ach tá sé freisin níos costasaí chun teachtaireachtaí criptigh agus dhíchriptiú.
Sa lá atá inniu tá sé molta go minic go bhfuil p agus q ar a laghad 1,024 giotán,
a chuireann gach uimhir ag níos mó ná 300 dhigit de dheachúlacha.
Ach beidh muid ag roghnaigh na huimhreacha beaga i gcomhair sampla seo.
Anois, beidh muid ag méadú p agus q le chéile chun a fháil ar roinnt 3,
a beidh muid ag glaoch n.
In ár gcás, n = 23 * 43, a = 989.
Táimid tar éis a n = 989.
Next beidh muid ag méadú p - 1 le q - 1
a fháil ar roinnt 4, a beidh orainn glaoch m.
In ár gcás, m = 22 * ​​42, a = 924.
Tá m = 924.
Anois, beidh muid ag teastáil e uimhir atá réasúnta príomha le m
agus níos lú ná m.
Tá dhá líon réasúnta príomha nó coprime
má tá an slánuimhir ach dearfach go roinneann siad araon go cothrom 1.
I bhfocail eile, an divisor mó coitianta e agus m
caithfidh 1.
Go praiticiúil, tá sé coitianta do r a bheith ar an uimhir phríomha 65,537
chomh fada agus nach bhfuil an líon seo a tharlóidh a bheith ina fhachtóir de m.
Chun ár eochracha, beidh muid ag piocadh e = 5
ó 5 réasúnta príomha go 924.
Ar deireadh, beidh orainn gá uimhir amháin níos mó, a beidh orainn glaoch d.
Ní mór a bheith D roinnt luach a shásaíonn an chothromóid de = 1 (mod m).
Signifies seo m mod beidh muid ag úsáid a bhaint as rud ar a dtugtar uimhríochtúil modúlach.
I uimhríochtúil modúlach, faigheann uair amháin sa líon níos airde ná roinnt faoi cheangal uachtair
beidh sé wrap ar ais ar fud chun 0.
A clog, mar shampla, úsáideann uimhríocht modúlach.
Nóiméad amháin tar éis 01:59, mar shampla, 2:00,
Ní 1:60.
Tá an lámh nóiméad fillte timpeall 0
nuair a shroichtear an uachtair cheangal de 60.
Mar sin, is féidir linn a rá 60 Is ionann 0 (mod 60)
agus tá 125 comhionann le 65 Is ionann 5 (mod 60).
Beidh ár eochair phoiblí an e péire agus n
áit sa chás seo e 5 agus n Tá 989.
Beidh ár eochair phríobháideach an bheirt d agus n,
Is é atá in ár gcás 185 agus 989.
Fógra nach bhfuil ár n-bunaidh primes p agus q le feiceáil
áit ar bith in ár eochracha príobháideacha nó poiblí.
Anois go bhfuil muid ár péire eochracha, a ligean ar ghlacadh le breathnú ar conas is féidir linn a chriptiú
agus a dhíchriptiú teachtaireacht.
Ba mhaith liom teachtaireacht a chur chuig Rob,
mar sin beidh sé an ceann a ghiniúint an péire eochair.
Ansin, beidh mé ag iarraidh Rob as a chuid eochair phoiblí, rud a mbainfidh mé úsáid
a chriptiú teachtaireacht a sheoladh a thabhairt dó.
Cuimhnigh, tá sé go hiomlán ceart go leor le haghaidh Rob a roinnt ar a eochair phoiblí a dhéanamh liom.
Ach ní bheadh ​​sé ceart go leor a roinnt a eochair phríobháideach.
Ní féidir liom aon smaoineamh cad é a eochair phríobháideach.
Is féidir linn a bhriseadh ár m teachtaireacht suas i smután roinnt
go léir níos lú ná n agus ansin Criptigh gach ceann de na smután.
Beidh muid criptigh an CS50 teaghrán, ar féidir linn a bhriseadh suas i 4 smután,
amháin in aghaidh an litir.
D'fhonn a chriptiú mo theachtaireacht, beidh mé gá chun é a athrú
de shaghas éigin ionadaíochta uimhriúil.
A ligean ar iarcheangal na luachanna ASCII leis na carachtair i mo theachtaireacht.
D'fhonn a chriptiú a m teachtaireacht a thugtar
Feicfidh mé a c = m ríomh ar an e (mod n).
Ach ní mór m a bheith níos lú ná n,
eile nó nach féidir an teachtaireacht iomlán a chur in iúl modulo n.
Is féidir linn a bhriseadh m suas i smután agus arís eile, gach ceann acu níos lú ná n,
agus Criptigh gach ceann de na smután.
Encrypting gach ceann de na smután, a fháil againn c1 = 67 do na 5 (mod 989)
a = 658.
Chun ár smután dara ní mór dúinn 83 an 5 (mod 989)
a = 15.
Chun ár smután tríú ní mór dúinn 53 an 5 (mod 989)
a = 799.
Agus ar deireadh, le haghaidh ár smután deiridh atá againn 48 ar an 5 (mod 989)
a = 975.
Anois is féidir linn a sheoladh níos mó ná na luachanna criptithe a Rob.
Anseo a théann tú, Rob.
Cé go bhfuil ár teachtaireacht agus í ar eitilt, a ligean ar ghlacadh eile breathnú
ar conas a fuair muid go bhfuil luach ar d.
Ár n-uimhir d gá a shásamh 5d = 1 (mod 924).
Déanann sé seo d inbhéarta multiplicative de 5 modulo 924.
Mar gheall ar 2 slánuimhreacha, a b agus, an algartam leathnaithe Eoiclídeach
Is féidir é a úsáid chun teacht ar an divisor mó coiteann de na 2 slánuimhreacha.
Beidh sé a thabhairt dúinn freisin 2 uimhreacha eile, x agus y,
a shásóidh an ax + by chothromóid divisor = is mó coitianta b agus.
Conas a dhéanann an cuidiú linn?
Bhuel, plugging i r = 5 le haghaidh
agus m = 924 do b
Tá a fhios againn cheana féin go bhfuil na huimhreacha coprime.
Is é an divisor coitianta is mó 1.
Tugann sé seo dúinn 5x + 924y = 1
nó 5x = 1 - 924y.
Ach má táimid cúram ach thart ar gach rud modulo 924
ansin is féidir linn titim an - 924y.
Smaoinigh ar ais go dtí an clog.
Má tá an lámh nóiméad ar an 1 agus ansin pas a fháil go díreach 10 uair an chloig,
Tá a fhios againn go mbeidh an lámh nóiméad a bheith fós ar an 1.
Anseo táimid ag tosú ag 1 agus ansin wrap amanna go díreach y thart,
sin beidh orainn a bheith fós ag 1.
Tá 5x = 1 (mod 924).
Agus is é anseo an x ​​mar an gcéanna leis an d bhíomar ag lorg roimh,
mar sin má úsáidimid an algartam leathnaithe Eoiclídeach
seo a fháil x líon, go bhfuil an uimhir cheart dúinn a úsáid mar ár d.
Anois, a ligean ar siúl ar an algartam Eoiclídeach sínte ar feadh 5 =
agus b = 924.
Beidh muid úsáid a bhaint as modh ar a dtugtar an modh tábla.
Beidh ár tábla a bheith 4 colúin, x, y, d, agus k.
Tosaíonn Ár tábla amach le 2 sraitheanna.
Sa chéad sraith mór dúinn 1, 0, ansin is é ár luach, a bhfuil 5,
agus is é ár dara sraith 0, 1, agus ár luach b, a bhfuil 924.
Is é an luach an colún 4, k, an toradh
de tríd an luach d sa líne os a chionn le luach d
ar an ró céanna.
Tá 5 roinnte ar 924 Is é 0 le roinnt eile.
Ciallaíonn sin ní mór dúinn k = 0.
Anois, beidh an luach gach cille eile luach na 2 shraith cille os a chionn
lúide luach na ró os a chionn amanna k.
Let tús le d sa líne 3.
Tá 5-924 * 0 = 5.
Next ní mór dúinn 0-1 * 0 a bhfuil 0
agus 1-0 * 0 a bhfuil 1.
Ní ró-olc, mar sin a ligean ar bogadh ar aghaidh go dtí an ró eile.
An Chéad ní mór dúinn ár n-luach k.
924 roinnte ar a 5 = 184 le roinnt eile,
mar sin tá ár n-luach ar k 184.
Anois 924-5 * 184 = 4.
Is é 0 * 184 1 agus 0 - - 1 1 Is é * 184 -184.
Gach ceart, a ligean ar a dhéanamh ar an tsraith seo chugainn.
Beidh ár luach k 1 mar gheall ar
5 roinnte ar 4 = 1 le roinnt eile.
A ligean ar a líonadh isteach sna colúin eile.
5 - 4 * 1 = 1.
0-1 * 1 = -1.
Agus 1 - Is é 184 * 1 185.
A ligean ar a fheiceáil cad a bheadh ​​ár n-luach eile de k bheith.
Bhuel, tá sé cosúil ní mór dúinn 4 roinnte 1, a bhfuil 4.
Sa chás seo nuair a bhíonn muid ag roinnt ar 1 den sórt sin k cothrom le
ciallaíonn luach d an ró thuas go bhfuil muid ag déanamh leis an ár algartam.
Is féidir linn a fheiceáil anseo go bhfuil x = 185 agus y = -1 ar an tsraith seo caite.
A ligean ar teacht anois ar ais go dtí ár sprioc bunaidh.
Dúirt muid go bhfuil an luach ar x mar thoradh ar reáchtáil an algartam
a bheadh ​​an inbhéartach multiplicative a (mod b).
Ciallaíonn sé sin go bhfuil 185 inbhéarta multiplicative de 5 (mod 924)
rud a chiallaíonn go mór dúinn a luach 185 do d.
Ós rud é go d = 1 sa sraith deireanach sa
Fíoraíonn bhí coprime go e m.
Más rud é nach raibh sé 1 ansin ba mhaith linn a phiocadh e nua.
Anois, a ligean ar a fheiceáil má tá Rob a fuair mo theachtaireacht.
Nuair a chuireann duine éigin dom teachtaireacht criptithe
chomh fada agus tá mé choinnigh mo eochair phríobháideach rúnda a
Tá mé an ceann amháin ar féidir leo a dhíchriptiú an teachtaireacht.
Chun dhíchriptiú a c smután is féidir liom a ríomh ar an teachtaireacht bunaidh
is comhionann leis an smután a d cumhachta (mod n).
Cuimhnigh go bhfuil d agus n ó mo eochair phríobháideach.
Chun a fháil teachtaireacht iomlán a bhaint as a chuid smután mór dúinn dhíchriptiú gach smután
agus iarcheangal na torthaí.
Go cruinn conas slán RSA?
Is í an fhírinne, níl a fhios againn.
Slándáil bunaithe ar cé chomh fada is a thógfadh sé an ionsaitheoir a crack teachtaireacht
criptithe le RSA.
Cuimhnigh go bhfuil ionsaitheoir rochtain ar do eochair phoiblí,
ina bhfuil idir e agus n.
Má Bainistíonn an ionsaitheoir a n fhachtóir isteach ina 2 primes, p agus q,
ansin d'fhéadfadh sí a ríomh d baint úsáide as an algartam Eoiclídeach leathnaithe.
Tugann sé seo di an eochair phríobháideach, ar féidir a úsáid chun a dhíchriptiú aon teachtaireacht.
Ach conas is féidir go tapa linn slánuimhreacha fhachtóir?
Arís, níl a fhios againn.
Níl aon duine d'aimsigh ar bhealach tapa a dhéanamh air,
rud a chiallaíonn go thugtar mór go leor n
thógfadh sé an ionsaitheoir ró fhada
chun fhachtóir an uimhir.
Má léirigh duine éigin ar bhealach tapa na slánuimhreacha fachtóireacht
Bheadh ​​RSA a bhriseadh.
Ach fiú má slánuimhir factorization bunúsach mall
D'fhéadfadh an algartam RSA go bhfuil fós roinnt flaw i sé
a ligeann do decryption éasca teachtaireachtaí.
Níl aon duine d'aimsigh agus a nochtadh den sórt sin a locht go fóill,
ach ní chiallaíonn sin ní amháin ann.
Go teoiriciúil, d'fhéadfadh duine éigin a bheith ann amach ag léamh na sonraí go léir criptithe le RSA.
Níl eile beagán de cheist príobháideachta.
Má encrypts Tommy roinnt teachtaireacht baint úsáide as mo eochair phoiblí
agus encrypts an ionsaitheoir an teachtaireacht chéanna ag baint úsáide as mo eochair phoiblí
Beidh an ionsaitheoir a fheiceáil go bhfuil na teachtaireachtaí 2 comhionann
agus tá a fhios dá bhrí sin cad Tommy criptithe.
D'fhonn cosc ​​a chur ar seo, teachtaireachtaí stuáilte de ghnáth, le giotán randamach
sula criptithe ionas go mbeidh an teachtaireacht chéanna criptithe
Beidh amanna éagsúla cuma éagsúil chomh fada agus go bhfuil an stuáil ar an teachtaireacht éagsúla.
Ach cuimhnigh ar conas ní mór dúinn a teachtaireachtaí roinnt i smután
ionas go bhfuil gach smután níos lú ná n?
Stuáil na smután a chiallaíonn go fhéadfadh a bheith againn chun rudaí roinnte suas
i smután níos mó toisc go gcaithfidh an smután padded a bheith níos lú ná n.
Criptiú agus decryption atá sách daor le RSA,
agus mar sin is féidir gá a bhriseadh suas teachtaireacht i smután go leor a bheith an-daor.
Más gá le líon mór sonraí a bheith criptithe agus decrypted
is féidir linn a chur le chéile na buntáistí a bhaineann halgartaim eochair siméadracha
leo siúd de RSA a fháil slándáil agus éifeachtúlacht.
Cé nach mbeidh muid ag dul isteach ann anseo,
Is AES algartam siméadrach tábhachtacha cosúil leis an Vigenère agus sifir Caesar
ach tá i bhfad níos deacra a crack.
Ar ndóigh, ní féidir linn a úsáid AES gan a bhunú eochair roinnte rúnda
idir an 2 córais, agus chonaic muid an fadhb le sin roimhe seo.
Ach anois is féidir linn a úsáid RSA a bhunú ar an eochair roinnte rúnda idir an 2 córais.
Beidh muid glaoch ar an ríomhaire a sheoladh ar na sonraí an seoltóir
agus an ríomhaire a fháil ar na sonraí an ghlacadóra.
Tá an glacadóir le péire RSA eochair Seolann agus
an eochair phoiblí ar an seoltóir.
Gineann an seoltóir eochair AES,
encrypts sé leis an ghlacadóra eochair phoiblí RSA,
agus cuireann an eochair AES leis an ghlacadóra.
Decrypts an glacadóir an teachtaireacht lena eochair phríobháideach RSA.
Tá an seoltóir agus an ghlacadóra anois roinnte AES eochair eatarthu.
AES, a bhfuil i bhfad níos tapúla ag criptithe agus decryption ná RSA,
is féidir iad a úsáid anois a chriptiú an líon mór na sonraí agus iad a chur chuig an glacadóir,
ar féidir leo a dhíchriptiú ag baint úsáide as an eochair céanna.
AES, a bhfuil i bhfad níos tapúla ag criptithe agus decryption ná RSA,
is féidir iad a úsáid anois a chriptiú an líon mór na sonraí agus iad a chur chuig an glacadóir,
ar féidir leo a dhíchriptiú ag baint úsáide as an eochair céanna.
Is gá dúinn ach RSA a aistriú chuig an eochair roinnte.
Táimid a thuilleadh gá a úsáid RSA ar chor ar bith.
Breathnaíonn sé cosúil fuair mé teachtaireacht.
Ní chuireann sé ní más rud é duine ar bith a léamh cad atá ar an eitleán páipéar roimh ghabh mé é
mar go bhfuil mé an ceann amháin leis an eochair phríobháideach.
A ligean ar dhíchriptiú gach ceann de na smután chur sa teachtaireacht.
An smután chéad, 658, ardú muid go dtí an chumhacht d, a bhfuil 185,
mod n, a bhfuil 989, is ionann 67,
a bhfuil an litir C i ASCII.
Anois, ar an smután dara.
Tá an smután dara luach 15,
atá againn a ardú go dtí an chumhacht 185,
mod 989, agus tá sé seo cothrom le 83
a bhfuil an litir S i ASCII.
Anois le haghaidh an smután tríú, a bhfuil luach 799, ní mór dúinn a ardú go 185,
mod 989, agus tá sé seo cothrom le 53,
a bhfuil an luach an carachtar ASCII sa 5.
Anois le haghaidh an smután deiridh, a bhfuil luach 975,
ardú againn go 185, 989 mod,
agus tá sé seo cothrom le 48, a bhfuil luach an 0 carachtar ASCII sa.
Is é mo ainm Rob Bowden, agus tá sé seo CS50.
[CS50.TV]
RSA ar chor ar bith.
RSA ar chor ar bith. [Gáire]
Chor ar bith.