[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Harvard University]
[To je CS50.] [CS50.TV]
Poďme sa pozrieť na RSA, široko používaný algoritmus pre šifrovanie dát.
Šifrovacie algoritmy ako Caesar a Vigenère kódy nie sú príliš bezpečné.
S Caesara, útočník potrebuje len vyskúšať 25 rôznych kľúčov
dostať správu na obyčajný text.
Kým Vigenère kód je bezpečnejšie ako Caesara
vzhľadom k väčšej hľadanie priestor pre kľúče, raz útočník
vie, dĺžku kľúča v Vigenère kód,
, Ktoré môžu byť stanovená prostredníctvom analýzy vzoriek v šifrovaných textu,
Vigenère kód nie je to, že oveľa bezpečnejšie ako Caesara.
RSA, na druhej strane, nie je náchylné k útokom, ako je tento.
Caesar kód a Vigenère kód používať rovnaký kľúč
ako šifrovať a dešifrovať správy.
Táto vlastnosť robí Tieto šifry symetrické kľúčových algoritmov.
Základným problémom symetrická kľúčové algoritmy
je to, že oni sa spoliehajú na jednej strane a šifrovanie a odoslanie správy
a jeden prijímajúci a dešifrovanie správy
sa už dohodli vopred na kľúč budú obaja používať.
Ale máme trochu problém pri spustení tu.
Ako 2 počítače, ktoré chcú komunikovať vytvoriť tajný kľúč medzi nimi?
Ak kľúč musí byť tajná, potom potrebujeme spôsob, ako šifrovať a dešifrovať kľúč.
Ak všetko, čo máme, je symetrický kľúč kryptografia
potom sme práve prišli späť do rovnakého problému.
RSA, na druhej strane, používa dvojica kľúčov,
jeden pre šifrovanie a iný pre dešifrovanie.
Jedným z nich je tzv verejný kľúč, a druhý je súkromný kľúč.
Verejný kľúč slúži na šifrovanie správ.
Ako asi tušíte podľa názvu, môžeme podeliť o naše verejný kľúč s
niekto chceme, bez toho, aby bola ohrozená bezpečnosť šifrované správe.
Správy šifrovaná pomocou verejného kľúča
dá dešifrovať iba so zodpovedajúcim privátnym kľúčom.
Aj keď môžete zdieľať váš verejný kľúč, mali by ste mať svoj súkromný kľúč v tajnosti.
a to iba súkromný kľúč môže byť použitý na dešifrovanie správ
ak 2 užívatelia chcú poslať správy šifrované pomocou RSA
tam a späť obaja užívatelia musia mať svoju vlastnú verejné a súkromné ​​kľúče.
Správy od užívateľa 1 až 2 užívateľovi
používať iba užívateľské 2 kľúčovú pár, a správy od užívateľa 2 k užívateľovi 1
používať iba Užívateľ 1 je dvojica kľúčov.
Skutočnosť, že sú 2 samostatné kľúče na šifrovanie a dešifrovanie správ
robí RSA asymetrický kľúčový algoritmus.
Nepotrebujeme na zašifrovanie verejný kľúč, aby sa odoslať ju do iného počítača
, Pretože kľúč je verejný rovnako.
To znamená, že RSA nemá rovnaký spúšťací problém
ako symetrická kľúčové algoritmy.
Takže keď chcem odoslať správu pomocou RSA šifrovanie
Robymu, budem musieť najprv Rob verejný kľúč.
Ak chcete generovať dvojicu kľúčov, Rob musí vybrať 2 veľké prvočísla.
Tieto čísla budú použité v oboch verejných a súkromných kľúčov,
ale verejný kľúč bude používať iba produkt týchto 2 čísel,
nie samotná čísla.
Potom, čo som šifrovaná správu pomocou Rob verejný kľúč
Môžem poslať správu Rob.
U počítača, factoring čísla je ťažký problém.
Verejný kľúč, pamätajte, používal produkt 2 prvočísel.
Tento výrobok musí mať iba 2 faktory,
ktoré sa dejú, že sú čísla, ktoré tvorí súkromný kľúč.
Aby bolo možné dešifrovať správy, bude RSA použite tento súkromný kľúč
alebo čísla násobí spoločne v procese vytvárania verejného kľúča.
Vzhľadom k tomu, že je výpočtovo ťažké faktora sa počet
používa vo verejnej kľúča do 2 čísla používaných v súkromnom kľúči
je to ťažké pre útočníkovi zistiť súkromného kľúča
že bude nutné dešifrovať správy.
Teraz poďme do niektorých nižších úrovní detailov RSA.
Pozrime sa najprv, ako môžeme vytvoriť dvojicu kľúčov.
Po prvé, budeme potrebovať 2 prvočísla.
Zavoláme tieto 2 čísla p a q.
Pri výbere p a q, v praxi by sme pseudorandomly vytvárať
veľké množstvo a potom použiť test na určenie, či
tieto čísla sú pravdepodobne pripraviť.
Môžeme si ponechať generovanie náhodných čísel znovu a znovu
až budeme mať 2 prvočísla, ktoré môžeme použiť.
Tu poďme vybrať p = 23 a q = 43.
Pamätajte si, že v praxi by p a q byť oveľa väčšie čísla.
Pokiaľ je nám známe, že čím väčšie čísla, tým ťažšie je
bezva zašifrovanú správu.
Ale je to aj drahšie pre šifrovanie a dešifrovanie správ.
Dnes sa často odporúča, aby p a q sú aspoň 1024 bitov,
ktorá stavia na každé číslo na viac ako 300 desatinných miest.
Ale budeme vyberať tieto malé čísla pre tento príklad.
Teraz budeme násobiť p a q spoločne získať tretie číslo,
ktoré budeme nazývať n
V našom prípade, n = 23 * 43, ktorý = 989.
Sme N = 989.
Ďalšie budeme násobiť p - 1 s q - 1
získať štvrté číslo, ktoré budeme nazývať m
V našom prípade, m = 22 * ​​42, ktorý = 924.
Máme m = 924.
Teraz budeme potrebovať číslo e, ktorá je nesúdeliteľné m
a menej ako m.
Dve čísla sú nesúdeliteľné, alebo coprime
ak len pozitívne celé číslo, ktoré delí obe rovnomerne je 1.
Inými slovami, najväčší spoločný deliteľ E a M
musí byť 1.
V praxi, to je spoločné pre e byť prvočíslo 65537
tak dlho, ako je toto číslo sa nestane byť faktor m.
Pre našich kľúče, budeme vyberať e = 5
od 5 je nesúdeliteľné 924.
Nakoniec, budeme potrebovať jeden väčší počet, ktorý budeme nazývať d
D musí byť nejaká hodnota, ktorá spĺňa rovnicu de = 1 (mod m).
To m mod znamená budeme používať niečo, čo nazýva modulárny aritmetika.
V modulárnej aritmetike, raz číslo dostane vyšší ako niektoré hornú hranicu
to sa zalomia späť k 0.
Hodiny, napríklad, používa modulárny aritmetiku.
Minútu po 01:59, napríklad, je 2:00,
nie 1:60.
Minútová ručička sa omotal okolo 0
po dosiahnutí hornej hranice 60.
Takže môžeme povedať, 60 je ekvivalentná 0 (mod 60)
a 125 je ekvivalent k 65 je ekvivalentná 5 (mod 60).
Naše verejné kľúč bude dvojica e a n
kde v tomto prípade je e 5 a n je 989.
Naše vlastné kľúč bude dvojica d a n,
ktorá je v našom prípade 185 a 989.
Všimnite si, že náš pôvodný prvočísla p a q sa nezobrazí
kdekoľvek v našich súkromných alebo verejných kľúčov.
Teraz, keď máme pár kľúčov, poďme sa pozrieť na to, ako môžeme zašifrovať
a dešifrovať správy.
Chcem poslať správu Rob,
tak on bude tým, kto k vygenerovanie tejto dvojice kľúčov.
Spýtam sa Rob jeho verejného kľúča, ktorý budem používať
na zašifrovanie správy poslať k nemu.
Pamätajte si, že je to úplne v poriadku Rob zdieľať jeho verejný kľúč so mnou.
Ale to by nebolo v poriadku zdieľať svoj súkromný kľúč.
Nemám potuchy, čo jeho súkromný kľúč je.
Môžeme porušiť správu m do niekoľkých kúsky
všetky menšie ako n a potom zašifrovať každý z týchto blokov.
Ak budeme zašifrovať reťazec CS50, ktoré môžeme rozdeliť do 4 kusy,
jeden na písmeno.
Za účelom šifrovanie môj vzkaz, budem musieť previesť do
nejaký druh numerickej reprezentácie.
Poďme zreťaziť hodnoty ASCII s postavami v mojej správe.
Aby bolo možné šifrovanie danú správu m
Budem sa musieť počítať c = m na e (mod n).
Ale m musí byť menšie ako n,
inak celá správa nemôže byť vyjadrená modulo n
Môžeme rozdeliť m až do niekoľkých blokov, z ktorých všetky sú menšie ako n,
a šifrovať každý z týchto blokov.
Šifrovanie každý z týchto blokov, dostaneme c1 = 67 k 5 (mod 989)
ktoré = 658.
Pre nášho druhého bloku máme 83 na 5 (mod 989)
ktoré = 15.
Pre nášho tretieho bloku máme 53 na 5 (mod 989)
ktoré = 799.
A konečne, pre náš posledný kus máme 48 na 5 (mod 989)
ktorý = 975.
Teraz môžeme poslať cez tieto šifrované hodnoty Rob.
Tu to máš, Robe.
Kým naše posolstvo je v lete, poďme sa ešte raz pozrieť
na to, ako sme sa dostali, že hodnotu d
Naše číslo d potrebné na uspokojenie 5d = 1 (mod 924).
To je d multiplikatívnej inverzný 5 modulo 924.
Vzhľadom k tomu, 2 celé čísla a, b, rozšírená Euclidean algoritmus
môže byť použitý na nájdenie najväčšieho spoločného deliteľa týchto 2 čísel.
To bude tiež dať nám ďalšie 2 čísla, x a y,
ktoré spĺňajú rovnicu ax + by = najväčší spoločný deliteľ a a b
Ako to pomôže nám?
No, zasunutím e = 5 pre
a m = 924 pre b
už vieme, že tieto čísla sú coprime.
Ich najväčší spoločný deliteľ je 1.
To nám dáva 5x + 924y = 1
alebo 5x = 1 - 924y.
Ale ak nás však zaujíma iba o všetkom modulo 924
potom môžeme pretiahnuť - 924y.
Spomeňte si na hodiny.
Ak minútová ručička je na 1 a potom presne 10 hodín prejsť,
vieme, že minútová ručička bude stále na 1.
Tu začíname na 1 a potom zabaliť okolo presne y časy,
takže budeme stále v 1.
Máme 5x = 1 (mod 924).
A tu to x je rovnaký ako v d sme hľadali skôr,
takže ak budeme používať rozšírené Euclidean algoritmus
a získajte tento číslo x, že je to číslo by sme mali používať ako náš d.
Teraz poďme spustiť rozšírený Euclidean algoritmus pre = 5
a b = 924.
Použijeme metódu nazvanú tabuľka metóda.
Naša tabuľka bude mať 4 stĺpce, x, y, d, a k
Náš stôl začína s 2 riadky.
V prvom rade máme 1, 0, potom sa naša hodnota, ktorá je 5,
a naša druhá rada je 0, 1, a naša hodnota pre B, ktorý je 924.
Hodnota 4. stĺpca, k, bude výsledok
delenie hodnotu d na riadku nad ním s hodnotou d
na rovnakom riadku.
Máme 5 deleno 924 je 0 s nejakým zvyškom.
To znamená, že máme k = 0.
Teraz sa hodnota každého iného bunky bude hodnota bunky 2 radoch nad ňou
mínus hodnota na riadku nad ním časy k.
Poďme začať s d v 3. rade.
Máme 5-924 * 0 = 5.
Potom máme 0-1 * 0, čo je 0
a 1 - 0 * 0, ktorá je 1.
Nie je to tak zlé, takže sa poďme presunúť na ďalší riadok.
Najprv musíme našu hodnotu k.
924 deleno 5 = 184 s nejakým zvyškom,
takže naša hodnota k je 184.
Teraz 924-5 * 184 = 4.
1-0 * 184 je 1 a 0 - 1 * 184 je -184.
Dobre, poďme urobiť ďalší riadok.
Naša hodnota k bude 1, pretože
5 deleno 4 = 1 s nejakým zvyškom.
Poďme vyplniť v ostatných stĺpcoch.
5-4 * 1 = 1.
0-1 * 1 = -1.
A 1 - 184 * 1 je 185.
Pozrime sa, čo naše ďalšie hodnota súčiniteľa bude.
No, vyzerá to, že máme 4 delené 1, čo je 4.
V tomto prípade, keď sme delením 1 tak, že k je rovná
hodnota d vo vyššie uvedenom riadku znamená, že skončíme s naším algoritmom.
Môžeme vidieť, že máme x = 185, y = -1 v poslednom riadku.
Poďme sa teraz vrátiť k nášmu pôvodnému cieľu.
Povedali sme, že hodnota x v dôsledku prevádzky tohto algoritmu
by multiplikatívnej inverzné k (mod b).
To znamená, že 185 je multiplikatívnej inverzný 5 (mod 924)
, Čo znamená, že sa majú hodnotu 185 pre d
Skutočnosť, že d = 1 v poslednom riadku
overí, že e bola coprime k m.
Ak by tomu tak nebolo 1, potom budeme musieť vybrať nového e
Teraz sa pozrieme, či Rob získal moju správu.
Keď mi niekto pošle šifrovanú správu
tak dlho, ako som držal som súkromný kľúč v tajnosti
Som jediný, kto môže dešifrovať správy.
Ak chcete dešifrovať kus c môžem vypočítať pôvodnú správu
je rovná bloku na d moci (mod n).
Pamätajte si, že d a n sú z môjho súkromného kľúča.
Ak chcete získať kompletnú správu z jeho kúsky sme dešifrovať každý blok
a zreťaziť výsledky.
Presne tak, ako bezpečný je RSA?
Pravdou je, že nevieme.
Bezpečnosť je založená na tom, ako dlho to bude trvať, aby útočník bezva správu
šifrovaný pomocou RSA.
Pamätajte si, že útočník má prístup k vášmu verejný kľúč,
ktorý obsahuje ako e a n
Ak útočník dokáže faktor N do svojich 2 pripraví, p a q,
potom by mohla vypočítať d pomocou rozšíreného Euclidean algoritmus.
To jej dáva súkromný kľúč, ktorý môže byť použitý na dešifrovanie žiadne správy.
Ale ako rýchlo môžeme vytknúť celé čísla?
Opäť, nevieme.
Nikto našiel rýchly spôsob, ako to urobiť,
To znamená, že vzhľadom na dostatočne veľká n
to by sa útočníkovi nereálne dlho
započítavať číslo.
Ak niekto odhalil rýchly spôsob factoringových celých čísel
RSA by byť rozbitý.
Ale aj keď faktorizace celého čísla je vo svojej podstate pomalé
RSA algoritmus mohol ešte mať nejakú vadu v tom
, Ktorá umožňuje ľahké dešifrovanie správ.
Nikto našiel a odhalil tak chybu ešte,
ale to neznamená že neexistuje.
Teoreticky by mohol niekto byť vonku čítanie všetkých dát zašifrované pomocou RSA.
Je tu ďalší kúsok o ochrane osobných vydanie.
Ak Tommy zašifruje nejakú správu pomocou verejného kľúča svoj
a útočník zašifruje rovnaký správu pomocou verejného kľúča svoj
útočník uvidí, že 2 správy sú totožné
a tak viem, čo Tommy šifrované.
Aby sa tomu zabránilo, sú správy zvyčajne čalúnené s náhodnými bity
pred zašifrovaný tak, že rovnaká správa zašifrované
viackrát bude vyzerať inak, ak polstrovanie na správy sa líšia.
Ale nezabudnite, ako máme rozdeliť správ na kúsky
tak, že každý blok je menšie ako n?
Čalúnenie na kusy znamená, že možno budeme musieť rozdeliť veci do
do ešte väčšie kúsky od polstrovaný bloku musí byť menší ako n.
Šifrovanie a dešifrovanie sú pomerne drahé s RSA,
a tak museli rozbiť správu do mnohých kúsky môže byť veľmi nákladné.
Ak veľký objem dát musí byť šifrované a dešifrované
môžeme spojiť výhody symetrická kľúčové algoritmy
s tými RSA dostať aj bezpečnosť a efektivitu.
Aj keď nepôjdeme do toho tu,
AES je symetrický algoritmus kľúča ako Vigenère a Caesar šifry
ale oveľa ťažšie prasknúť.
Samozrejme, nemôžeme použiť AES bez stanovenia zdieľaného tajného kľúča
medzi 2 systémy, a my sme videli problém s tým predtým.
Ale teraz môžeme použiť RSA založiť zdieľaného tajného kľúča medzi 2 systémy.
Zavoláme počítač odosielanie dát odosielateľa
a počítač prijímajúci údaje prijímača.
Prijímač má pár RSA kľúčov a odošle
verejný kľúč odosielateľa.
Odosielateľ generuje kľúč AES,
zašifruje s prijímačom RSA verejného kľúča,
a odošle kľúč AES k prijímaču.
Prijímač dešifruje správu s RSA privátnym kľúčom.
Odosielateľ aj príjemca majú teraz spoločný kľúča AES medzi nimi.
AES, čo je oveľa rýchlejší pri šifrovanie a dešifrovanie, ako RSA,
možno teraz použiť pre šifrovanie veľkých objemov dát a poslať ich do prijímača,
kto môže dešifrovať pomocou rovnakého kľúča.
AES, čo je oveľa rýchlejší pri šifrovanie a dešifrovanie, ako RSA,
možno teraz použiť pre šifrovanie veľkých objemov dát a poslať ich do prijímača,
kto môže dešifrovať pomocou rovnakého kľúča.
Sme len potrebovali RSA preniesť zdieľaný kľúč.
Už nepotrebujeme používať RSA vôbec.
Vyzerá to, že som dostal správu.
Nezáleží na tom, či niekto prečítať, čo je na papierové lietadlo predtým, než som ho chytil
pretože som jediný, kto má súkromný kľúč.
Poďme dešifrovať každý z blokov v správe.
Prvý blok, 658, sme zvýšiť na d sile, ktorá je 185,
mod n, ktoré je 989, je rovná 67,
ktorý je písmeno C v ASCII.
Teraz, na druhej bloku.
Druhý blok má hodnotu 15,
ktoré sme zvýšiť na 185. moci,
mod 989, a to sa rovná 83
ktorý je písmeno S v ASCII.
Teraz za tretie bloku, ktorý má hodnotu 799, zvýšime na 185,
mod 989, a to sa rovná 53,
čo je hodnota znaku 5 v ASCII.
Teraz pre posledný kus, ktorý má hodnotu 975,
chováme na 185, mod 989,
a to sa rovná 48, čo je hodnota znaku 0 v ASCII.
Moje meno je Rob Bowden, a to je CS50.
[CS50.TV]
RSA vôbec.
RSA vôbec. [Smiech]
Na všetkých.