[Powered by Google Translate] [RSA]
[Robs Bowden] [Tomijs MacWilliam] [Hārvarda]
[Tas ir CS50.] [CS50.TV]
Pieņemsim to apskatīt RSA, plaši izmanto algoritmu datu šifrēšanai.
Šifrēšanas algoritmi, piemēram, Cēzara un Vigenère cipariem nav ļoti droša.
Ar Cēzara šifra, uzbrucējs tikai vajag izmēģināt 25 dažādas atslēgas
lai saņemtu ziņu s teksta.
Kamēr Vigenère šifra ir drošāka nekā Cēzara šifra
jo lielāku meklēšanas telpu atslēgām, kad uzbrucējs
zina atslēgas garums ir Vigenère izrēķināt,
ko var noteikt, izmantojot analīzi modeļus šifrētā tekstā,
the Vigenère šifra nav tik daudz drošāka nekā Cēzara šifra.
RSA, no otras puses, nav neaizsargāti pret uzbrukumiem kā šis.
Caesar šifra un Vigenère šifra izmantot to pašu atslēgu
gan šifrēt un atšifrēt ziņojumu.
Šī īpašība padara šos šifriem simetriskas galvenās algoritmus.
Pamatproblēma ar simetrisko galvenajiem algoritmiem
ir tas, ka viņi paļaujas uz vienu šifrējot un nosūtot īsziņu
un viens saņemšanu un atšifrēšanas ziņu
līdz jau ir vienojušās sākumā uz taustiņa viņi abi izmanto.
Bet mums ir mazliet starta problēmu šeit.
Kā 2 datori, kas vēlas sazināties izveidot slepenu atslēgu starp viņiem?
Ja atslēga ir slepena, tad mums ir nepieciešams veids, lai šifrētu un atšifrētu taustiņu.
Ja viss, kas mums ir simetriska atslēgas kriptogrāfijas
tad mēs esam tikai nāk atpakaļ uz to pašu problēmu.
RSA, no otras puses, izmanto atslēgu pāri,
viens šifrēšanai un citu par atšifrēšanu.
Viena sauc publisko atslēgu, un otrs ir privātā atslēga.
Publiskā atslēga tiek izmantota, lai šifrētu ziņojumus.
Kā jūs varētu uzminēt tās nosaukums, mēs varam dalīties mūsu publisko atslēgu ar
kāds mēs vēlamies neapdraudot drošību šifrētu ziņu.
Ziņas šifrēta, izmantojot publisko atslēgu
var atšifrēt tikai ar atbilstošo privāto atslēgu.
Kamēr jūs varat dalīties ar jūsu publisko atslēgu, jums vajadzētu vienmēr saglabāt savu privāto atslēgu noslēpumu.
un tikai privātā atslēga var izmantot, lai atšifrēt ziņojumus
ja 2 lietotāji vēlas, lai nosūtītu ziņojumus šifrēti ar RSA
un atpakaļ abi lietotāji ir vajadzīga sava valsts un privāto atslēgu pāri.
Ziņojumi no 1 lietotājs uz 2 lietotājam
izmantot tikai User 2 atslēgu pāri, un ziņas no 2 lietotājs līdz 1 lietotājam
izmantot tikai User 1 atslēgu pāri.
Fakts, ka tur ir 2 atsevišķas atslēgas šifrēt un atšifrēt ziņojumus
padara RSA asimetrisko atslēgu algoritms.
Mums nav nepieciešams, lai šifrētu publisko atslēgu, lai to nosūtītu uz citu datoru
jo galvenais ir publiski vienalga.
Tas nozīmē, ka DĀR nav tāda pati starta problēma
kā simetriskās galvenajiem algoritmiem.
Tātad, ja es gribu, lai nosūtītu īsziņu, izmantojot RSA šifrēšanu
aplaupīt, es vispirms aplaupīt publisko atslēgu.
Lai radītu atslēgu pāri, Robs nepieciešams uzņemt 2 lielas prime skaitu.
Šie numuri tiks izmantoti gan valsts un privātās atslēgas,
bet publiskā atslēga būs tikai izmantot produktu no šiem 2 numuriem,
nav skaitļi paši.
Kad esmu šifrēts ziņojumu, izmantojot aplaupīt publisko atslēgu
Es varu nosūtīt ziņu uz Rob.
Par datoru, faktorings skaitļi ir grūti problēma.
Publiskā atslēga, atcerieties, ko izmanto produktu par 2 galvenajiem numuriem.
Šis produkts ir, tad ir tikai 2 faktori,
kas gadās būt skaitļi, kas veido privāto atslēgu.
Lai atšifrēt ziņu, RSA izmantos šo privāto atslēgu
vai skaitļus reizina kopā veidojot publisko atslēgu.
Jo tas ir skaitļošanas grūti faktors numuru
izmanto publisko atslēgu no 2 numuriem, kas izmantoti privāto atslēgu
tas ir grūti uzbrucējs izrēķināt privāto atslēgu
kas būs nepieciešami, lai atšifrētu ziņojumu.
Tagad pieņemsim iedziļināties dažos zemāka līmeņa detaļas RSA.
Pieņemsim vispirms redzēt, kā mēs varam radīt atslēgu pāri.
Pirmkārt, mēs nepieciešams 2 prime skaitu.
Mēs saucam šie 2 skaitļi p un q.
Lai izvēlētos p un q, praksē mēs pseudorandomly radīt
liels skaits un tad izmanto kritēriju, lai noteiktu, vai nav
šie skaitļi, iespējams, ir galvenais.
Mēs varam saglabāt radītu nejaušības numurus atkal un atkal
līdz mums ir 2 PRIMES ka mēs varam izmantot.
Lūk pieņemsim uzņemt p = 23 un q = 43.
Atceros, praksē, p un q būtu daudz lielāki skaitļi.
Ciktāl mēs zinām, jo ​​lielāki skaitļiem, jo ​​grūtāk ir
kreka šifrētu ziņojumu.
Bet tas ir arī dārgāka, lai šifrētu un atšifrētu ziņojumus.
Šodien tā ir bieži ieteicams p un q ir vismaz 1024 biti,
kas liek katru numuru pie vairāk nekā 300 Decimālciparus.
Bet mēs pick šos mazos numurus šim piemēram.
Tagad mēs reizināt p un q kopā, lai iegūtu 3rd numuru,
ko mēs saucam n.
Mūsu gadījumā, n = 23 * 43, kas = 989.
Mums ir n = 989.
Nākamais mēs reizināt P - 1 ar Q - 1
lai iegūtu 4. numuru, ko mēs saucam m.
Mūsu gadījumā, m = 22 * ​​42, kas = 924.
Mums ir m = 924.
Tagad mums būs nepieciešams cipara e, kas ir salīdzinoši prime līdz m
un mazāk nekā m.
Divi skaitļi ir salīdzinoši prime vai coprime
ja vienīgais pozitīvais skaitlis, kas dala tos gan vienmērīgi ir 1.
Citiem vārdiem sakot, lielāko kopējo dalītājs e un m
jābūt 1.
Praksē tas ir parasts e būt pirmskaitlis 65.537
kamēr šis numurs nav gadās būt faktors m.
Mūsu atslēgas, mēs pick e = 5
jo 5 ir salīdzinoši prime un 924.
Visbeidzot, mums būs nepieciešams vēl viens numurs, ko mēs saucam d.
A jābūt dažas vērtības, kas apmierina vienādojumu de = 1 (mod m).
Šī mod m nozīmē mēs izmantot kaut ko sauc moduļu aritmētika.
Moduļu aritmētisko, kad vairāki kļūst lielāks nekā daži augšējo robežu
tas wrap atpakaļ ap 0.
Pulksteni, piemēram, izmanto modulāro aritmētika.
Vienu minūti pēc 01:59, piemēram, ir 2:00,
ne 1:60.
Minūti rokas ir aptīt ar 0
sasniedzot augšējo robežu 60.
Tātad, mēs varam teikt, 60 ir līdzvērtīga 0 (mod 60)
un 125 ir līdzvērtīga 65 gadiem ir līdzvērtīgs 5 (mod 60).
Mūsu sabiedrība atslēga būs pāris e un n
kur šajā gadījumā e ir 5 un n ir 989.
Mūsu privātā atslēga būs pāris d un n,
kas mūsu gadījumā ir 185 un 989.
Ievērojiet, ka mūsu sākotnējais PRIMES p un q neparādās
jebkur mūsu privāto vai publisko atslēgu.
Tagad, kad mums ir mūsu atslēgu pāri, pieņemsim to apskatīt, kā mēs varam šifrēt
un atšifrēt ziņu.
Es gribu, lai nosūtītu ziņu uz Rob,
tāpēc viņš būs viens, lai radītu šo atslēgu pāri.
Tad es ņemšu uzdot Rob viņa publisko atslēgu, ko es ņemšu izmantot
lai šifrētu ziņu, lai nosūtītu viņam.
Atcerieties, tas ir pilnīgi labi, lai Robs dalīties savā publisko atslēgu ar mani.
Bet tas nebūtu labi, lai dalītos savu privāto atslēgu.
Man nav nekādu ideju, ko viņa privāto atslēgu.
Mēs varam salauzt mūsu ziņu m pa vairākiem gabalos
viss mazāks nekā n un tad šifrēt katru no šiem gabalos.
Mēs šifrētu virkni CS50, ko mēs varam izjaukt uz 4 gabalos,
vienu uz vēstuli.
Lai šifrētu savu vēstījumu, man būs nepieciešams, lai pārvērstu to par
sava veida ciparu pārstāvību.
Pieņemsim saķēdēt ASCII vērtības ar manā ziņojumā rakstzīmes.
Lai šifrētu doto ziņu m
Man būs nepieciešams, lai aprēķinātu c = m uz e (mod n).
Bet m ir mazāks nekā n,
vai arī pilnu ziņu nevar izteikti MODULO n.
Mēs varam lauzt m pa vairākiem gabalos, no kuriem visi ir mazāki nekā n,
un šifrēt katru no šiem gabalos.
Šifrējot katra no šīm gabalos, mēs C1 = 67-5 taustiņu (mod 989)
kas = 658.
Par mūsu otrā rieciens mums ir 83 līdz 5 (mod 989)
kas = 15.
Par mūsu trešajā rieciens mums ir 53 līdz 5 (mod 989)
kas = 799.
Un visbeidzot, mūsu pēdējo gabalu mums ir 48 līdz 5 (mod 989)
kas = 975.
Tagad mēs varam nosūtīt pa šīs šifrētu vērtības Rob.
Šeit jums iet, Rob.
Kamēr mūsu vēstījums ir lidojuma, pieņemsim citu izskatu
pie kā mēs saņēmām ka vērtību d.
Mūsu numurs d lai apmierinātu 5D = 1 (mod 924).
Tas padara d multiplikatīvo apgriezto gada 5 moduļa 924.
Ievadīts 2 veseli skaitļi, un b, pagarinātā Eiklida algoritms
var izmantot, lai atrastu vislielāko kopējo dalītājs šiem 2 integers.
Tas arī dos mums 2 citiem numuriem, X un Y
kas atbilst vienādojums ax + by = vislielāko kopējo dalītājs a un b.
Kā tas mums palīdzēt?
Nu, tapām e = 5
un m = 924 par b
Mēs jau zinām, ka šie skaitļi ir coprime.
Viņu lielākais kopīgais dalītājs ir 1.
Tas dod mums 5x + 924y = 1
or 5x = 1 - 924y.
Bet, ja mēs tikai rūpējamies par visu moduļa 924
tad mēs varam nomest - 924y.
Think atpakaļ uz pulksteni.
Ja minūti rokas ir par 1 gadu un tad tieši 10 stundas caurlaide,
mēs zinām minūšu rādītājs joprojām būs uz 1.
Šeit mēs sākam pēc 1 un tad wrap ap tieši y reizes,
tāpēc mēs joprojām būs 1.
Mums ir 5x = 1 (mod 924).
Un šeit tas x ir tāds pats kā D Mēs meklējām pirms,
tāpēc, ja mēs izmantot paplašināto Eiklida algoritms
lai iegūtu šo numurs X, tas ir skaitlis mums vajadzētu izmantot kā mūsu d.
Tagad palaist pagarināts Eiklida algoritms a = 5
un b = 924.
Mēs izmantot metodi sauc tabulu metode.
Mūsu galda būs 4 kolonnas, x, y, d un k.
Mūsu galda sākas ar 2 rindās.
Pirmajā rindā mums ir 1, 0, tad mūsu vērtība, kas ir par 5,
un mūsu otrais rindā ir 0, 1, un mūsu cenas B, kas ir 924.
Par gada 4 kolonnas, k, vērtība būs rezultāts
gada dalot D vērtību rindā virs tā ar vērtību D
vienā rindā.
Mums ir 5 dalīts ar 924 ir 0 ar dažiem atlikušo.
Tas nozīmē, ka mums ir k = 0.
Tagad par katru citu šūnu vērtība būs vērtība šūnu 2 rindās virs tā
atņem rindas virs tā reizes k.
Sāksim ar D gada 3 kārtas.
Mums ir 5-924 * 0 = 5.
Nākamais mums ir 0-1 * 0, kas ir 0
un 1 - 0 * 0, kas ir 1.
Ne pārāk slikti, tāpēc pieņemsim pāriet uz nākamo rindu.
Vispirms mums ir nepieciešams mūsu vērtību k.
924 dalīts ar 5 = 184 ar dažiem atlikušo,
tāpēc mūsu vērtība k ir 184.
Tagad 924-5 * 184 = 4.
1-0 * 184 ir 1 un 0 - 1 * 184 -184.
Labi, pieņemsim do nākamo rindu.
Mūsu k vērtība būs 1, jo
5 dalīts ar 4 = 1 ar dažiem atlikušo.
Pieņemsim aizpildīt citām kolonnām.
5-4 * 1 = 1.
0-1 * 1 = -1.
Un 1-184 * 1 ir 185.
Paskatīsimies, kāda ir mūsu nākamais k vērtība būtu.
Nu, izskatās, ka mums ir 4 dala secīgi ar 1, kas ir par 4.
Šajā gadījumā, ja mēs dalot ar 1, ka k ir vienāds ar
gada D lielums iepriekš rindā nozīmē, ka mēs esam darīts ar mūsu algoritmu.
Mēs varam redzēt šeit, ka mums ir x = 185 un y = -1 pēdējā rindā.
Pieņemsim tagad nāk atpakaļ uz mūsu sākotnējo mērķi.
Mēs teicām, ka vērtība x rezultātā darboties šo algoritmu
būtu multiplikatīvo inversiju (mod b).
Tas nozīmē, ka 185 ir multiplikatīvo apgriezto gada 5 (mod 924)
kas nozīmē, ka mums ir vērtība 185 d.
Fakts, ka d = 1 pēdējā rindā
pārliecinās, ka e tika coprime m.
Ja tas būtu nevis 1, tad mēs būtu izvēlēties jaunu e.
Tagad pieņemsim redzēt, ja Robs ir saņēmusi manu vēstījumu.
Kad kāds sūta man šifrētu ziņojumu
kamēr es esmu tur manu privāto atslēgu noslēpumu
Es esmu vienīgais, kas var atšifrēt ziņojumu.
Lai atšifrētu gabaliņa c es varētu aprēķināt sākotnējo ziņojumu
ir vienāds ar rieciens uz D jaudu (mod n).
Atcerieties, ka d un n ir no manas privātās atslēgas.
Lai iegūtu pilnu ziņu no tās gabalos mēs atšifrēt katru rieciens
un saķēdēt rezultātus.
Kā tieši drošs ir RSA?
Patiesība ir, mēs nezinām.
Drošība ir balstīta uz to, cik ilgi tas veic uzbrucējs kreka ziņu
šifrēti ar RSA.
Atcerieties, ka uzbrucējs var piekļūt jūsu publisko atslēgu,
kas satur gan E un N.
Ja uzbrucējs izdodas faktors n savos 2 PRIMES, P un Q,
tad viņa varēja aprēķināt D, izmantojot paplašināto Eiklida algoritms.
Tas dod viņai privāto atslēgu, ko var izmantot, lai atšifrētu jebkuru ziņu.
Bet cik ātri mēs varam faktors integers?
Atkal, mēs nezinām.
Neviens nav atrasts ātrs veids, kā darīt to,
kas nozīmē, ka, ņemot vērā pietiekami liels n
tas būtu nepieciešams uzbrucēju nereāli ilgi
faktors numuru.
Ja kāds atklāja ātru veidu faktoringa integers
RSA būtu sadalīti.
Bet, pat ja skaitlim factorization būtības ir lēns
RSA algoritms varētu vēl kādu plaisāt tajā
, kas ļauj viegli atšifrēšanu ziņojumus.
Neviens nav atrasts, un atklāja šādu plaisāt vēl,
bet tas nenozīmē, ka tāda nav.
Teorētiski, kāds varētu būt tur izlasot visu datu šifrēti ar RSA.
Ir vēl viens privātuma jautājumu mazliet.
Ja Tomijs šifrē kādu ziņu, izmantojot manu publisko atslēgu
un uzbrucējs šifrē to pašu ziņu, izmantojot manu publisko atslēgu
uzbrucējs redzēs, ka 2 ziņojumi ir identiski
un tādējādi zina, ko Tomijs šifrēts.
Lai to novērstu, ziņojumi parasti polsterētām ar izlases bitiem
pirms šifrēta, ka tas pats vēstījums šifrēts
vairākas reizes izskatīsies dažādas, kamēr uz ziņu polsterējums ir atšķirīgs.
Bet atceros, kā mums ir sadalīt ziņas gabalos
lai katrs gabals ir mazāks nekā n?
Polsterējums gabalus nozīmē, ka mēs varētu būt sadalīt lietas uz augšu
vērā pat vairāk gabalos kopš polsterētām rieciens jābūt mazākām nekā n.
Šifrēšanu un atšifrēšanu ir salīdzinoši dārgi ar RSA,
un tāpēc nepieciešams, lai izjauktu up ziņu daudzās gabalos, var būt ļoti dārgi.
Ja liela apjoma datu jābūt šifrēta un atšifrēt
mēs varam apvienot ieguvumus no simetriskas galveno algoritmu
ar tiem RSA saņemt gan drošību un efektivitāti.
Lai gan mēs ne iedziļināties to šeit,
AES ir simetriska atslēgas algoritms piemēram Vigenère un Cēzara šifrēšana
bet daudz grūtāk kreka.
Protams, mēs nevaram izmantot AES nenosakot vienotu slepeno atslēgu
starp 2 sistēmās, un mēs redzējām problēmu ar to pirms tam.
Bet tagad mēs varam izmantot DĀR, lai izveidotu kopīgu slepenu atslēgu starp 2 sistēmās.
Mēs saucam datoru datu nosūtīšanas sūtītājam
un dators, kas saņem datus uztvērēju.
Uztvērējs ir RSA atslēgu pāri un nosūta
publiskā atslēga sūtītājam.
Sūtītājs ģenerē AES atslēgu,
šifrē to ar saņēmēja RSA publisko atslēgu,
un nosūta AES atslēgu uz uztvērēju.
Uztvērējs atšifrē ziņojumu ar savu RSA privāto atslēgu.
Gan sūtītājs un saņēmējs tagad ir kopīga AES atslēgu starp tiem.
AES, kas ir daudz ātrāks par šifrēšanu un atšifrēšanu nekā RSA,
tagad var izmantot, lai šifrētu lielus datu apjomus un nosūtīt tos uz uztvērēju,
kurš var atšifrēt, izmantojot to pašu atslēgu.
AES, kas ir daudz ātrāks par šifrēšanu un atšifrēšanu nekā RSA,
tagad var izmantot, lai šifrētu lielus datu apjomus un nosūtīt tos uz uztvērēju,
kurš var atšifrēt, izmantojot to pašu atslēgu.
Mēs vienkārši nepieciešams RSA nodot koplietojamo taustiņu.
Mums vairs nav nepieciešams izmantot DĀR vispār.
Izskatās, man ziņu.
Tas nav svarīgi, ja kāds lasītu, kas ir uz papīra lidmašīnas pirms es nozvejotas to
jo es esmu tikai viens ar privāto atslēgu.
Pieņemsim atšifrēt katru no ziņojuma daļām.
Pirmais rieciens, 658, mēs paceļam uz D jaudu, kas ir 185,
MOD N, kas ir 989, ir vienāda ar 67,
kas ir vēstule C ASCII.
Tagad, uz otro gabalu.
Otrais gabals ir vērtība 15,
kas mēs paceļam uz 185. varas,
MOD 989, un tas ir vienāds ar 83
kas ir burts S ASCII.
Tagad jau trešo rieciens, kura vērtība 799, mēs paaugstināt līdz 185,
MOD 989, un tas ir vienāds ar 53,
kas ir rakstura 5 ASCII vērtību.
Tagad par pēdējo gabalu, kas ir vērtība 975,
Mēs paaugstināt līdz 185, mod 989,
un tas ir vienāds ar 48, kas ir vērtība rakstzīmju 0 ASCII.
Mans vārds ir Rob Bowden, un tas ir CS50.
[CS50.TV]
DĀR vispār.
DĀR vispār. [Smiekli]
Vispār.