[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Harvard University]
[Þetta er CS50.] [CS50.TV]
Við skulum taka a líta á RSA, mikið notað reiknirit til að dulkóða gögn.
Dulkóðunaralgrímin eins keisarans og Vigenère dulmál eru ekki mjög örugg.
Með Caesar dulmál, árásarmaður þarf aðeins að prófa 25 mismunandi lykla
til að fá texta á skeytis.
Þótt Vigenère dulmál er öruggari en Caesar dulmál
vegna stærri leita pláss fyrir takka, þegar árásarmaður
veit lengd lykilsins í Vigenère dulmál,
sem hægt er að ákvarða með greiningu mynstur í brengla texta,
the Vigenère dulmál er ekki það mikið öruggari en Caesar dulmál.
RSA, á hinn bóginn, er ekki viðkvæm fyrir árásum eins og þetta.
The Caesar dulmál og Vigenère dulmál nota sama takka
bæði dulkóða og hallmæla skilaboð.
Þessi eign gerir þessi dulmál samhverf reiknirit inni.
A grundvallaratriði vandamál með samhverft lykill reiknirit
er sú að þeir treysta á einn dulkóða og senda skilaboð
og einn taka og decrypting skilaboð
hafa þegar samið upfront á takkanum þeir vilja bæði nota.
En við höfum hluti af gangsetning vandamál hér.
Hvernig koma 2 tölvur sem vilja miðla leyndarlykli milli þeirra?
Ef lykillinn verður að vera leyndarmál, þá þurfum við leið til að dulkóða og hallmæla lykilinn.
Ef allt sem við höfum er samhverft lykill dulmál
þá höfum við bara komið aftur í sama vanda.
RSA, hins vegar notar par af lyklum,
einn fyrir dulkóðun og annar fyrir decryption.
Einn er kallað opinber lykill, og hitt er persónulegur lykill.
Almenningur lykill er notaður til að dulkóða skilaboð.
Eins og þú might giska frá nafni þess, getum við deilt dreifilykil okkar með
einhver sem við viljum án þess að skerða öryggi brengla skilaboð.
Skilaboð dulkóðuð með opinber lykill
Aðeins er hægt að decrypted með samsvarandi persónulegur lykill þess.
Þó að þú getir deilt opinber lykill, þú ættir alltaf að halda sér inni leyndarmál þitt.
og aðeins persónulegur lykill er hægt að nota til að hallmæla skilaboð
ef 2 notendur vilja til að senda skilaboð dulkóðuð með RSA
fram og til baka bæði notendur þurfa að hafa eigin opinbera og einkaaðila þeirra lyklapar.
Skilaboð frá notanda 1 Til Notandi 2
aðeins nota lyklapar Notandi 2, og skilaboð frá notanda 2 til Notandi 1
aðeins nota lyklapar Notandi 1 er.
Sú staðreynd að það eru 2 aðskilin lykla til að dulkóða og hallmæla skilaboð
gerir RSA ósamhverfum lykill reiknirit.
Við þurfum ekki að dulkóða opinber lykill til þess að senda það til annar tölva
þar sem lykillinn er opinber samt.
Þetta þýðir að RSA er ekki sama gangsetning vandamál
sem samhverft lykill reiknirit.
Svo ef ég vil að senda skilaboð með RSA dulkóðun
að ræna, mun ég þarf dreifilykil Rob er.
Til að búa til par af lyklum, Rob þarf að velja 2 stórar prímtölur.
Þessar tölur verða notaðar bæði í einka-og lykla,
en opinber lykill mun aðeins nota vöruna af þessum 2 tölum,
ekki tölurnar sjálfir.
Þegar ég hef dulkóðuð skilaboð notar opinber lykill Rob er
Ég er að senda skilaboð til Rob.
Fyrir tölvu Factoring númer er erfitt vandamál.
Almenningur lykill, muna, notað vöruna á 2 frumtalna.
Þessi vara má þá hafa aðeins 2 þætti,
sem verður að vera tölurnar sem gera upp persónulegur lykill.
Til að afkóða skilaboðin, RSA mun nota þetta einkalykilinn
eða tölurnar margfaldast saman í því ferli að búa til opinber lykill.
Vegna þess að það er computationally erfitt að þáttur númer
notað í opinber lykill í 2 númer sem notuð eru í almennum lykill
það er erfitt fyrir árásarmaður að reikna út einkalykilinn
það mun vera nauðsynlegt til að hallmæla the skilaboð.
Nú skulum fara í sumum lægri upplýsingar um RSA.
Við skulum sjá fyrst hvernig við getum búið til a par af lyklum.
Fyrst þurfum við að fá 2 prímtölur.
Við munum hringja í þessar 2 tölur p og q.
Í því skyni að ná p og q, í raun að við myndum pseudorandomly búa
mikill fjöldi og þá nota próf til að ákvarða hvort
þær tölur eru sennilega helsta.
Við getum haldið búa handahófi númer aftur og aftur
þar sem við höfum 2 primes sem við getum notað.
Hér skulum velja P = 23 og q = 43.
Mundu, í reynd, p og q ætti að vera miklu stærri tölur.
Eins og langt eins og við vitum, því meiri tölur, því erfiðara er
að sprunga er dulkóðuð skilaboð.
En það er líka dýrara að dulkóða og hallmæla skilaboð.
Í dag það er oft mælt með því að p og q eru að minnsta kosti 1024 bitar,
sem setur hvert númer á yfir 300 aukastafir.
En við munum ná þessir litlu tölur fyrir þessu dæmi.
Nú munum við margfalda p og q saman til að fá 3 númer,
sem við munum kalla n.
Í okkar tilviki, n = 23 * 43, sem = 989.
Við höfum N = 989.
Næst munum við margfalda p - 1 með Q - 1
að fá 4 númer sem við munum kalla m.
Í okkar tilviki, m = 22 * ​​42, sem = 924.
Við höfum M = 924.
Nú við þurfum að tala e sem er ósamþátta m
og minna en m.
Tvær tölur eru ósamþátta eða coprime
Ef einungis jákvæð heiltala sem skiptir þau bæði jafnt er 1.
Með öðrum orðum, mest sameiginlegt deilitöluna e og m
skal vera 1.
Í raun er það algengt að e vera frumtala 65537
svo lengi sem þessi tala gerist ekki að vera þáttur í m.
Um takka okkar, munum við velja e = 5
síðan 5 er ósamþátta 924.
Loks þurfum við að fá eitt númer, sem við munum kalla d.
D verður að vera einhver verðmæti sem uppfyllir jöfnuna de = 1 (mod m).
Þetta mod m táknar að við munum nota eitthvað sem kallast mát tölur.
Í mát tölur, þegar tala fær hærri en sumir efri
það verður sett aftur í kring til 0.
A klukka, til dæmis notar mát tölur.
Eina mínútu eftir 1:59, til dæmis, er 2:00,
ekki 1:60.
The mínútu hönd hefur vafið um að 0
á að ná efri mörk 60 ára.
Svo getum við sagt 60 jafngildir 0 (mod 60)
og 125 jafngildir 65 jafngildir 5 (mod 60).
Opinber lykill okkar verður par E og N
hvar í þessu tilfelli e er 5 og n er 989.
Persónulegur lykill okkar verður par d og n,
sem í okkar tilviki er 185 og 989.
Takið eftir að upprunalega primes okkar p og q birtast ekki
hvar sem er í einka-eða opinbera lykla okkar.
Nú þegar við höfum par okkar lykla, við skulum taka a líta á hvernig við getum dulkóða
og hallmæla skilaboð.
Mig langar til að senda skilaboð til að ræna,
svo hann verður að vera sá að búa til þennan takka par.
Og ég ætla að biðja Rob um opinber lykill hans, sem ég ætla að nota
til að dulkóða skilaboð til að senda til hans.
Mundu að það er alveg í lagi fyrir Rob að deila opinber lykill hans með mér.
En það væri ekki allt í lagi að deila einkalykilinn hans.
Ég hef ekki nokkra hugmynd hvað persónulegur lykill hans er.
Við getum skemmt skilaboð M okkar upp í nokkra búta
öll minni en n og dulkóða hverjum þeim klumpur.
Við munum dulkóða streng CS50, sem við getum brjóta upp í 4 bita,
einn bókstaf.
Til að dulkóða skilaboð til þín, ég þarf að umbreyta það inn í
einhvers konar tölugildi framsetning.
Skulum concatenate ASCII gildi með stafina í skilaboðunum mínum.
Til að dulkóða skeyti m
Ég þarf að reikna c = m í e (mod n).
En m verður að vera minni en n,
eða annars allt bréfið er ekki gefið modulo n.
Við getum skemmt m upp í nokkra búta, sem allir eru minni en n,
og dulkóða hverjum þeim klumpur.
Dulkóðun öllum þessum bitum, fáum við c1 = 67 til 5 (mod 989)
sem = 658.
Fyrir seinni klumpur okkar sem við höfum 83 til 5 (mod 989)
sem = 15.
Fyrir þriðja klumpur okkar sem við höfum 53 til 5 (mod 989)
hver = 799.
Og að lokum, að síðustu klumpur okkar sem við höfum 48 til 5 (mod 989)
sem = 975.
Nú getum við sent á þessa dulkóðuð gildi að ræna.
Hér þú fara, Rob.
Þó skilaboðin okkar er á flugi, við skulum taka annað útlit
á hvernig við fengum þessi gildi fyrir d.
Númer D okkar þarf að fullnægja 5D = 1 (mod 924).
Þetta gerir d multiplicative andhverfa 5 modulo 924.
Gefið 2 heiltölur a og b, útbreiddur Evklíðs
má nota til að finna mesta sameiginlega divisor af þessum 2 heiltölur.
Það mun einnig gefa okkur 2 aðrar tölur, x og y,
sem uppfylla jöfnuna ax + af = mesta sameiginlega divisor af a og b.
Hvernig virkar þetta hjálpað okkur?
Jæja, tengja í e = 5 fyrir
og m = 924 fyrir b
við vitum nú þegar að þessar tölur eru coprime.
Mesta sameiginlegt deilitöluna þeirra er 1.
Þetta gefur okkur 5x + 924y = 1
eða 5x = 1 - 924y.
En ef við vænt aðeins um allt modulo 924
þá getum við sleppa - 924y.
Hugsaðu aftur á klukkuna.
Ef mínútu hönd er á 1 og þá nákvæmlega 10 klukkustundir líða,
við vitum að mínútu vegar mun enn vera á 1.
Hér erum við að byrja á 1 og síðan sett í kringum nákvæmlega Y sinnum,
þannig að við munum enn á 1.
Við höfum 5x = 1 (mod 924).
Og hér er þetta x eins og D við vorum að leita að áður,
þannig að ef við notum langan Evklíðs
að fá þessa tölu x, það er númer við ættum að nota sem d okkar.
Nú skulum hlaupa útbreiddur Evklíðs fyrir = 5
og b = 924.
Við munum nota aðferð sem kallast borðið aðferð.
Taflan okkar mun hafa 4 dálka, x, y, D, og ​​k.
Borð okkar byrjar með 2 línum.
Í fyrstu röðinni við höfum 1, 0, þá gildi okkar a, sem er 5,
og önnur röðin okkar er 0, 1, og gildi okkar fyrir B, sem er 924.
Verðmæti 4. dálki, k, verður niðurstaðan
að deila verðmæti d í röð yfir það með verðmæti d
á sömu röð.
Við höfum 5 deilt með 924 er 0 með einhverjum afganginn.
Það þýðir að við höfum k = 0.
Nú gildi öll önnur frumu verður verðmæti klefi 2 röðum fyrir ofan það
mínus verðmæti röð yfir það sinnum k.
Við skulum byrja með D í 3 röð.
Við höfum 5-924 * 0 = 5.
Næst höfum við 0 - 1 * 0 sem er 0
og 1 - 0 * 0, sem er 1.
Ekki svo slæmt, þannig að við skulum fara í næstu línu.
Fyrst þurfum við gildi okkar k.
924 deilt með 5 = 184 með einhverjum afganginn,
svo er gildi okkar til K 184.
Nú 924-5 * 184 = 4.
1 - 0 * 184 er 1 og 0 - 1 * 184 er -184.
Allt í lagi, við skulum gera næstu línu.
Gildi okkar á k verður 1 því
5 deilt með 4 = 1 með einhverjum afganginn.
Við skulum fylla í öðrum dálkum.
5 - 4 * 1 = 1.
0 - 1 * 1 = -1.
Og 1-184 * 1 er 185.
Við skulum sjá hvað næsta gildi okkar k væri.
Jæja, það lítur út eins og við höfum 4 deilt með 1, sem er 4.
Í þessu tilfelli þar sem við erum að deila um 1 þannig að k er jafnt
verðmæti d í ofangreindum röð þýðir að við erum búin með reiknirit okkar.
Við sjáum hér að við höfum x = 185 og y = -1 í síðustu röð.
Við skulum nú koma aftur í upprunalegt markmið okkar.
Við sögðum að verðmæti x vegna keyra þetta reiknirit
væri multiplicative andhverfa A (mod b).
Það þýðir að 185 er multiplicative andhverfa 5 (mod 924)
sem þýðir að við höfum verðmæti 185 til d.
Sú staðreynd að d = 1 í síðustu röðinni
staðfestir að E var coprime á m.
Ef það væri ekki 1 þá yrðum við að velja nýtt e.
Nú skulum sjá hvort Rob hefur fengið skilaboð minn.
Þegar einhver sendir mér dulkóðuð skilaboð
svo lengi sem ég hef kept persónulegur lykill leyndarmál
Ég er sú eina sem getur hallmæla the skilaboð.
Til hallmæla klumpur c Ég get reikna upprunalega skeytið
er jafn klumpur til d vald (mod n).
Mundu að d og n eru frá persónulegur lykill.
Til að fá fulla skilaboð frá klumpur sínum við hallmæla hver klumpur
og concatenate niðurstöður.
Einmitt hversu öruggt er RSA?
Sannleikurinn er, vitum við ekki.
Öryggi er byggt á hversu langan tíma það myndi taka að árásarmaður til sprunga skilaboð
dulkóðuð með RSA.
Mundu að árásarmaður hafi aðgang að opinber lykill,
sem inniheldur bæði e og n.
Ef árásarmaður tekst að þáttur n í 2 primes þess, p og q,
þá hún mætti ​​reikna d með langan Evklíðs.
Þetta gefur henni persónulegur lykill, sem hægt er að nota til að hallmæla einhver skilaboð.
En hversu fljótt er hægt að þáttur heiltölur?
Aftur, vitum við ekki.
Enginn hefur fundið fljótur leið til að gera það,
sem þýðir að miðað nógu stór N
það myndi taka að árásarmaður unrealistically lengi
að þáttur númer.
Ef einhver ljós fljótlega leið heiltölur þátta
RSA væri brotinn.
En jafnvel þótt heiltala þáttun er í eðli sínu hægur
RSA reiknirit gæti samt hafa sumir galli í það
sem gerir ráð fyrir þægilegur decryption skilaboð.
Enginn hefur fundið og ljós svo galli enn,
en það þýðir ekki að maður er ekki til.
Fræðilega séð, einhver gæti verið þarna úti að lesa öll gögn dulkóðuð með RSA.
There 'annar hluti af næði tölublað.
Ef Tommy brengla nokkur skilaboð með opinber lykill minn
og árásarmaður brengla sömu skilaboð með opinber lykill minn
árásarmaður vilja sjá að 2 skilaboð eru eins
og þannig veit hvað Tommy dulkóðuð.
Í því skyni að koma í veg fyrir þetta, eru skilaboð yfirleitt padded með handahófi bits
áður en dulkóðuð þannig að sömu skilaboð dulkóðuð
mörgum sinnum mun líta öðruvísi svo lengi sem padding á bréfinu er öðruvísi.
En muna hvernig við verðum að skipta skilaboð í bita
þannig að hver bútur er minni en n?
Padding á klumpur þýðir að við gætum þurft að skipta það upp
í enn meira klumpur Þar sem padded klumpur verður að vera minni en n.
Dulkóðun og decryption er tiltölulega dýr og RSA,
og svo að þurfa að brjóta upp skilaboð í mörgum klumpur getur verið mjög dýrt.
Ef stór magn af gögnum þarf að vera dulkóðuð og afkóðað
við getum sameinað kosti samhverft lykill reiknirit
með þá RSA að fá bæði öryggi og skilvirkni.
Þó við munum ekki fara inn í það hér,
AES er samhverft lykill reiknirit eins Vigenère og Caesar dulmál
en miklu erfiðara að sprunga.
Auðvitað getum við ekki notað AES án stofnunar sameiginlega leyndarlykli
milli 2 kerfi, og við sá vandræðum með það áður.
En nú getum við notað RSA til að koma á sameiginlega leyndarlykli milli 2 kerfi.
Við munum hringja í tölvuna að senda gögn sendanda
og tölvan fengu gögn móttökutæki.
The símtól hefur RSA lykill par og sendir
opinber lykill til sendanda.
Sendandinn býr til AES lykill,
brengla það með RSA móttakanda,
og sendir AES lykill til the símtól.
The símtól hallmæla skilaboð með RSA persónulegur lykill þess.
Bæði sendandi og móttökutæki hafa nú hluti AES lykill milli þeirra.
AES, sem er mun hraðar á dulkóðun og decryption en RSA,
Nú er hægt að nota til að dulkóða mikið magn af gögnum og senda til móttakanda,
sem getur hallmæla með sama takka.
AES, sem er mun hraðar á dulkóðun og decryption en RSA,
Nú er hægt að nota til að dulkóða mikið magn af gögnum og senda til móttakanda,
sem getur hallmæla með sama takka.
Við þurftum bara RSA til að flytja hluti inni.
Við þurfum ekki lengur að nota RSA yfirleitt.
Það lítur út eins og ég hef fengið skilaboð.
Það skiptir ekki máli hvort einhver lesið það sem er á pappír flugvél áður en ég tók hana
vegna þess að ég er sú eina með persónulegur lykill.
Skulum hallmæla hvert klumpur í skilaboðum.
Fyrsta klumpur, 658, hækka við að d vald, sem er 185,
unga fólkið n, sem er 989, er jöfn 67,
sem er stafurinn C í ASCII.
Nú á seinni klumpur.
Annað klumpur hefur gildi 15,
sem við hækka í 185 völd,
unga fólkið 989, og það er jafnt 83
sem er bókstafurinn S í ASCII.
Nú á þriðja klumpur, sem hefur gildi 799, hækka við að 185,
unga fólkið 989, og það er jafn í 53,
sem er gildi eðli 5 í ASCII.
Nú á síðasta klumpur, sem hefur gildið 975,
við vekja til 185, unga fólkið 989,
og þetta er jafn 48, sem er gildi eðli 0 ASCII.
Mitt nafn er Rob Bowden, og þetta er CS50.
[CS50.TV]
RSA yfirleitt.
RSA yfirleitt. [Hlátur]
Á öllum.