[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Harvard Egyetem]
[Ez a CS50.] [CS50.TV]
Vessünk egy pillantást RSA, a széles körben használt algoritmus az adatok titkosítására.
Titkosítási algoritmusok, mint Caesar és Vigenère titkosításokat nem túl biztonságos.
A Caesar titkosítás, a támadó csak szüksége, hogy megpróbálja 25 különböző kulcs
hogy az üzenet egyszerű szöveg.
Míg a Vigenère titkosító sokkal biztonságosabb, mint a Caesar titkosítás
mivel a nagyobb keresési teret a kulcsoknak, amint egy támadó
tudja, hogy a hossza a kulcsot Vigenère titkosítást,
amely megállapítható keresztül elemzése minták a titkosított szöveg,
A Vigenère titkosítás nem az, hogy sokkal biztonságosabb, mint a Caesar titkosítás.
RSA, a másik viszont nem támadás veszélyének vannak kitéve, mint ez.
A Caesar titkosító és Vigenère titkosítás használja ugyanazt a kulcsot
mind titkosítani és visszafejteni az üzenetet.
Ez a tulajdonság teszi ezeket a szimmetrikus kulcsú titkosítási algoritmusok.
Az alapvető probléma szimmetrikus kulcsú
az, hogy hivatkozhat az egyik titkosítása és az üzenetet küldő
és az egyik fogadó és dekódoláshoz az üzenetet
A már előre megállapodott a kulcsfontosságú mindketten használni.
De van egy kis indítási probléma itt.
Hogyan lehet 2 számítógép, hogy szeretne kommunikálni létre titkos kulcs között?
Ha a kulcs legyen titok, akkor szükségünk van egy módja annak, hogy titkosítani és visszafejteni a kulcsot.
Ha minden megvan szimmetrikus kulcsú
akkor már csak jön vissza ugyanarra a problémára.
RSA, másrészt, pedig két kulcs,
az egyik a titkosítás és egy másik a dekódolás.
Az egyik az úgynevezett a nyilvános kulcsot, és a másik pedig a privát kulcs.
A nyilvános kulccsal titkosítja az üzeneteket.
Mint azt sejteni lehet a neve, meg tudjuk osztani a nyilvános kulcsot
bárki szeretnénk biztonságának veszélyeztetése nélkül a titkosított üzenetet.
Az üzenetek titkosítása a nyilvános kulccsal
csak akkor lehet visszafejteni a hozzá tartozó privát kulcs.
Amíg lehet osztani a nyilvános kulcsot, akkor mindig a privát kulcs titkos.
és csak a privát kulcs visszafejtéséhez használt üzenetek
ha 2 felhasználó szeretné üzeneteket küldjön titkosított RSA
oda-vissza a két felhasználónak kell saját köz-és magán kulcspár.
Üzenetek Felhasználói 1 és 2 felhasználó
kizárólag a felhasználó 2-es kulcspár, üzenetek és user 2 felhasználó 1
kizárólag a felhasználó 1-es kulcspár.
Az a tény, hogy van 2 különálló kulcsok titkosítani és visszafejteni üzenetek
teszi RSA aszimmetrikus kulcsú algoritmus.
Nem kell, hogy titkosítja a nyilvános kulcs ahhoz, hogy küldje el egy másik számítógépre
mivel a kulcs nyilvános egyébként.
Ez azt jelenti, hogy az RSA nem az ugyanaz rendszerindítási probléma
mint a szimmetrikus kulcsú algoritmusok.
Tehát, ha azt akarom, hogy küldjön egy üzenetet RSA titkosítás
Rob, én először meg kell Rob nyilvános kulcsa.
Ahhoz, hogy létrehoz egy pár kulcs, Rob kell felvenni 2 nagy prímszám.
Ezeket a számokat fogják használni a köz-és a magán kulcs,
de a nyilvános kulcsot csak akkor használja a terméket e 2 szám,
Nem a számok önmagukban.
Egyszer már titkosított az üzenetet Rob nyilvános kulcsával
Tudom elküldeni az üzenetet Rob.
Egy számítógép, faktoring számok egy nehéz probléma.
A nyilvános kulcs, emlékszem, használt a termék a 2 prímszám.
Ezt a terméket, akkor csak 2 tényező,
amely történetesen a számok teszik ki a privát kulcs.
Annak érdekében, hogy dekódolni az üzenetet, RSA fogja használni ezt a privát kulcsát
vagy a számok szorzata együtt a létrehozásának folyamatában a nyilvános kulcs.
Mert számításigényes nehéz faktor a szám
használják a nyilvános kulcsot a 2 szám használt privát kulcs
nehéz egy támadó számára, hogy kitaláljuk, a titkos kulcs
hogy lesz szükség dekódolni az üzenetet.
Most menjünk a néhány alacsonyabb szintű részletek RSA.
Nézzük először, hogyan tudunk generálni egy pár kulcs.
Először is, szükségünk lesz 2 prímszám.
Hívjuk ezeket a 2 szám p és q.
Annak érdekében, hogy vegye p és q a gyakorlatban mi lenne pseudorandomly létre
nagy számok majd egy tesztet annak meghatározására e vagy sem
ezek a számok valószínűleg prím.
Meg tudja tartani a véletlen szám generálás, újra és újra
amíg van 2 prímszám, hogy tudjuk használni.
Itt hadd vegye p = 23 és q = 43.
Ne feledje, gyakorlatban, p és q kell sokkal nagyobb számú.
Amennyire tudjuk, minél nagyobb a szám, annál nehezebb
feltörni a titkosított üzenetet.
De ez is drágább titkosítani és visszafejteni üzeneteket.
Ma már gyakran ajánlott, hogy p és q értéke legalább 1024 bit,
amely helyére teszi az egyes számot, több mint 300 decimális számjegy.
De mi lesz felvenni ezeket a kis számokat ezt a példát.
Most majd megszorozzuk p és q együtt, hogy a 3. szám,
amely hívjuk n.
A mi esetünkben, n = 23 * 43, ami = 989.
Van n = 989.
Ezután fogjuk megszorozzuk p - 1 q - 1
így a 4. szám, ami hívjuk m.
A mi esetünkben, m = 22 * ​​42, ami = 924.
Van m = 924.
Most szükségünk lesz egy sor e, amely relatív prím m
és kevesebb, mint m.
Két szám relatív prím, vagy relatív prímek
ha csak pozitív egész szám, amely elválasztja mindkettőjüket egyformán 1 lehet.
Más szóval, a legnagyobb közös osztója e és m
kell lennie 1.
A gyakorlatban ez gyakori e, hogy a prímszám 65537
amennyiben ez a szám nem történik, hogy egy tényező m.
A mi kulcs, akkor vedd e = 5
mivel 5 relatív prím 924.
Végül, szükségünk lesz még egy szám, amely hívjuk d.
F-et meg valami érték, amely megfelel az egyenlet de = 1 (mod m).
Ez a mod m jelenti fogjuk használni egy úgynevezett moduláris aritmetika.
A moduláris aritmetika, ha egy szám lesz magasabb, mint néhány felső határ
majd tekerje vissza mintegy 0-ra.
Egy óra, például a használat moduláris aritmetika.
Egy perc után 1:59, például, 2:00,
nem 1:60.
Abban a pillanatban, kéz köré 0-ra
elérve felső határa 60.
Tehát, azt mondhatjuk, a 60 felel meg 0 (mod 60)
és 125 ekvivalens 65 egyenértékű az 5 (mod 60).
A mi nyilvános kulcs lesz a pár e és n
ahol ebben az esetben az e értéke 5 és n értéke 989.
A privát kulcs lesz a pár d és n,
ami esetünkben: 185 és 989.
Figyeljük meg, hogy az eredeti prímszám p és q nem jelennek meg
bárhol a magán-és nyilvános kulcsokat egyaránt.
Most, hogy megvan a két kulcs, vessünk egy pillantást, hogyan lehet titkosítani
és dekódolja az üzenetet.
Azt akarom, hogy küldjön egy üzenetet, hogy Rob,
így ő lesz az, aki ezt a generál kulcspárt.
Akkor megkérdezem Rob az ő nyilvános kulcs, amelyet fogom használni
titkosítani egy üzenetet küld neki.
Ne feledd, ez teljesen rendben van Rob, hogy ossza meg nyilvános kulcsot velem.
De nem lenne jó, hogy megossza személyes kulcsot.
Nekem nincs ötlete, mi a titkos kulcs.
Mi lehet törni az üzenetet m-ig szét darabokra
összes kisebb, mint n, majd titkosítja minden egyes ilyen darabokat.
Majd titkosítja a húr CS50, amit tudunk szakítani, 4 darabokat,
enként egy levelet.
Annak érdekében, hogy titkosítja az üzenetemet, én kell alakítani
valamilyen numerikus képviselet.
Nézzük összefűzi az ASCII értékek a karakterek üzenetem.
Annak érdekében, hogy egy adott üzenet titkosítása m
Majd ki kell számolnunk c = m a e (mod n).
De m kisebbnek kell lennie, mint n,
vagy pedig a teljes üzenetet nem lehet kifejezni modulo n.
Mi tönkreteheti m több különálló darabokat, amelyek mindegyike kisebb, mint n,
és titkosítani minden egyes ilyen darabokat.
Titkosítása minden ilyen darabokat, megkapjuk c1 = 67 az 5 (mod 989)
amely = 658.
Mert a második darabja már 83 az 5 (mod 989)
ami = 15.
Mert a harmadik darabja már 53 az 5 (mod 989)
ami = 799.
És végül, a mi utolsó darabja már 48 az 5 (mod 989)
ami = 975.
Most küldhetünk át ezeket a titkosított értékek Rob.
Tessék, Rob.
Míg az üzenet a repülés, vessünk egy pillantást
, hogyan van, hogy értéket d.
A szám d teljesítéséhez szükséges 5d = 1 (mod 924).
Ez teszi d a multiplikatív inverzét modulo 5 924.
Adott 2 egész szám, a és b, az euklideszi meghosszabbított algoritmus
lehet használni, hogy megtalálja a legnagyobb közös osztója e 2 egész számok.
Azt is ad nekünk 2 egyéb számok, x és y,
, amelyek megfelelnek a egyenlete ax + by = a legnagyobb közös osztója a és b.
Hogyan segít ez nekünk?
Nos, dugulás e = 5 egy
és m = 924 a b
már tudjuk, hogy ezek a számok relatív prímek.
A legnagyobb közös osztó 1 lehet.
Ez ad nekünk 5x + 924y = 1
vagy 5x = 1 - 924y.
De ha csak az érdekel mindent modulo 924
akkor mi is csepp a - 924y.
Gondolj vissza az órát.
Ha a percmutató van 1-jén, majd pontosan 10 órán át,
tudjuk, hogy a percmutató továbbra is 1-jén.
Itt kezdődik az 1, majd a köré pontosan y alkalommal,
úgyhogy még az 1.
Van 5x = 1 (mod 924).
És itt ez x megegyezik a d kerestünk előtt,
így ha használja a kiterjesztett euklideszi algoritmus
, hogy ezt a számot x, ez a szám is kell használni, mint a mi d.
Most fut a kiterjesztett euklideszi algoritmus a = 5
és b = 924.
Fogjuk használni a módszert nevezett táblázatos módszerrel.
Mi tábla lesz 4 oszlop, x, y, d, és k.
A táblázat indul 2 soros.
Az első sorban van 1, 0, akkor a értéke, ami 5,
és a második sor jelentése 0, 1, és a mi érték B, a 924.
Értékét a 4. oszlop, k, lesz az eredménye
felosztásának értéke d sorban felette az értéke d
ugyanabban a sorban.
Jelenleg 5 osztva 924 0, némi maradék.
Ez azt jelenti, hogy k = 0.
Az érték minden más sejt lesz az értéke a cella 2 sor fölötte
mínusz az értékét a sor felette Times K.
Kezdjük ad a 3. sorban.
Van 5-924 * 0 = 5.
Ezután már 0-1 * 0, amely 0
és 1 - 0 * 0, amely 1.
Nem is rossz, úgyhogy menjünk tovább a következő sorra.
Először is szükségünk van értéke a k.
924 osztva 5 = 184 némi maradék,
így a értéke k 184.
Most 924-5 * 184 = 4.
1-0 * 184 jelentése 1 és 0 - 1 * 184 -184.
Rendben, lássuk a következő sorban.
A k értéke 1 lesz, mert
5 osztva 4 = 1 némi maradék.
Nézzük, töltse ki a többi oszlop.
5-4 * 1 = 1.
0-1 * 1 = -1.
És 1-184 * 1 185.
Lássuk, mi a következő k értéke lenne.
Nos, úgy néz ki, van 4 osztva 1, amely 4.
Ebben az esetben, ha vagyunk elosztjuk 1 ilyen hogy k egyenlő
értéke ad a fenti sorban azt jelenti, hogy mi történik a mi algoritmus.
Láthatjuk, hogy itt van x = 185 és y = -1 az utolsó sorban.
Nézzük most jön vissza az eredeti cél.
Azt mondtuk, hogy a x értékét eredményeként futó ezen algoritmus
lenne a multiplikatív inverzét egy (mod b).
Ez azt jelenti, hogy 185 a multiplikatív inverze 5 (mod 924)
ami azt jelenti, hogy értéke 185 d.
Az a tény, hogy a d = 1-ben az utolsó sorban
ellenőrzi, hogy e volt, a relatív prímek m.
Ha ez nem 1, akkor mi lenne, hogy válasszon egy új e.
Most nézzük meg, ha Rob megkapta az üzenetem.
Ha valaki küld nekem egy titkosított üzenet
amíg én megtartottam az én privát kulcs egy titkos
Én vagyok az egyetlen, aki tudja dekódolni az üzenetet.
Visszafejteni egy darab c tudok számítani az eredeti üzenet
egyenlő a csonkot-D teljesítmény (mod n).
Ne feledje, hogy d és n értéke az én privát kulcs.
Ahhoz, hogy a teljes üzenetet saját darabokat is hírbe egyes chunk
és összefűzi az eredményeket.
Pontosan mennyire biztonságos az RSA?
Az igazság az, hogy nem tudom.
Biztonság alapja, hogy mennyi ideig fog tartani, hogy a támadó kiváló üzenet
titkosítja RSA.
Ne feledje, hogy a támadó hozzáférhet a nyilvános kulcs,
amely mind az E és n.
Ha a támadónak sikerül faktor n bele 2 prím, p és q,
akkor tudta kiszámítani d a kiterjesztett euklideszi algoritmus.
Ez ad neki a privát kulcs, amelyeket fel lehet használni, hogy dekódolni a üzenetet.
De milyen gyorsan tudunk vennünk egész?
Még egyszer, nem tudjuk.
Senki sem talált egy gyors módja, hogy,
ami azt jelenti, hogy meghatározott, nagy elég n-
lenne szükség a támadónak irreálisan hosszú
A faktor a számot.
Ha valaki mutatott gyors módja a faktoring egészek
RSA lenne törve.
De még ha egész faktorizációs eredendően lassú
Az RSA algoritmus még mindig van néhány hibája, hogy
, amely lehetővé teszi az egyszerű dekódolás az üzeneteket.
Senki sem talált, és kiderült, egy ilyen hiba még,
de ez nem jelenti azt, nem létezik.
Elméletileg, valaki lehet ott olvasni az összes adatot titkosítja RSA.
Van még egy kis adatvédelmi kérdés.
Ha Tommy titkosít néhány üzenetet a nyilvános kulcs
és a támadó titkosítja ugyanazt az üzenetet a saját nyilvános kulcsú
a támadó fogja látni, hogy a 2 üzenet azonosak
és így tudom, mi Tommy titkosítva.
Annak érdekében, hogy ezt, az üzenetek általában párnázott véletlenszerű bit
mielőtt kódolják, ezért az ugyanazt az üzenetet titkosított
többször fogja eltérő amíg a padding az üzenet más.
De ne felejtsd el, hogy hogyan kell megosztani üzeneteket darabokat
úgy, hogy minden egyes csonk kisebb, mint n?
Padding a darabokat azt jelenti, hogy lehet, hogy szét a dolgokat
a még darabokat, mert a párnázott csonk kisebbnek kell lennie, mint a n.
Titkosítás és visszafejtés viszonylag drága az RSA,
és így kelljen szakítani egy üzenet a sok darabokat is nagyon költséges.
Ha nagy mennyiségű adatot kell titkosítható és visszafejthető
tudjuk kombinálni előnyeit szimmetrikus kulcsú
azokkal RSA, hogy a biztonság és a hatékonyság.
Bár mi nem megyünk bele itt,
AES szimmetrikus kulcsú algoritmus, mint a Vigenère és Caesar titkosítást
de sokkal nehezebb feltörni.
Természetesen nem tudjuk használni AES megállapítása nélkül egy megosztott titkos kulcs
a 2 rendszer, és azt látta, hogy a probléma, hogy mielőtt.
De most már tudjuk használni RSA megállapítani a megosztott titkos kulcsot a 2 rendszer.
Hívjuk a számítógép az adatokat küldő a feladó
és a számítógép az adatokat fogadó a kagylót.
A vevő egy RSA kulcspár, és elküldi
a nyilvános kulcsot a feladónak.
A feladó generál egy AES kulcsot,
titkosítja azt a vevő RSA nyilvános kulcs,
és elküldi az AES kulcsot a vevő.
A vevő dekódolja az üzenetet a RSA privát kulcs.
Mind a küldő és a vevő most van egy közös AES kulcs között.
AES, ami sokkal gyorsabb, mint a titkosítás és a visszafejtés RSA,
most titkosításához használt nagy mennyiségű adat, és elküldi őket, hogy a vevő,
aki képes visszafejteni segítségével ugyanazt a kulcsot.
AES, ami sokkal gyorsabb, mint a titkosítás és a visszafejtés RSA,
most titkosításához használt nagy mennyiségű adat, és elküldi őket, hogy a vevő,
aki képes visszafejteni segítségével ugyanazt a kulcsot.
Csak szükség RSA át a megosztott kulcsot.
Már nem kell használni RSA egyáltalán.
Úgy néz ki, kaptam egy üzenetet.
Nem számít, ha valaki olvassa el, mi van a papíron repülőgépen, mielőtt elkapta
mert én vagyok az egyetlen, akinek a privát kulcs.
Nézzük dekódolja egyes darabokat az üzenetben.
Az első darab, 658, emeljük a d hatalom, amely 185,
mod n, ami 989, egyenlő 67,
amely a C betű ASCII.
Most rá a második darab.
A második darab van értéke 15,
amelyhez fel a 185. hatalom,
mod 989, és ez egyenlő 83
amely a levél S ASCII.
Most, a harmadik darabja, amelynek értéke 799, emeljük a 185,
mod 989, és ez egyenlő 53,
amelynek az értéke a karakter 5 ASCII.
Most az utolsó darabja, amelynek értéke 975,
emeljük a 185, mod 989,
és ez egyenlő 48, amely az értéke a karakter 0 ASCII.
A nevem Rob Bowden, és ez CS50.
[CS50.TV]
RSA egyáltalán.
RSA egyáltalán. [Nevetés]
Egyáltalán.