[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Università ta 'Harvard]
[Dan huwa CS50.] [CS50.TV]
Ejja tagħti ħarsa lejn RSA, algoriżmu użat ħafna għall encrypting data.
Algoritmi ta 'kriptar bħal Caesar u ciphers Vigenère mhumiex sikura ħafna.
Bl-cipher Caesar, attakkant teħtieġ biss li jippruvaw 25 ċwievet differenti
biex tikseb test sempliċi l-messaġġ tal-.
Filwaqt li l-cipher Vigenère hija aktar sikura minn l-cipher Caesar
minħabba l-ispazju tfittxija akbar għal ċwievet, ladarba l-attakkant
jaf it-tul taċ-ċavetta fil-cipher Vigenère,
li jista 'jiġi determinat permezz ta' analiżi ta 'xejriet fit-test encrypted,
l-cipher Vigenère mhuwiex li ħafna aktar sikuri minn l-cipher Caesar.
RSA, min-naħa l-oħra, mhuwiex vulnerabbli għal attakki bħal dan.
Il cipher Caesar u Vigenère cipher tuża l-istess ċavetta
kemm kriptaġġ u decrypt messaġġ.
Din il-proprjetà jagħmel dawn algoritmi ewlenin ciphers simetriċi.
A problema fundamentali ma 'algoritmi simmetriċi ewlenin
huwa li dawn jiddependu fuq il-wieħed encrypting u jibgħat il-messaġġ
u l-wieħed jirċievi u decrypting l-messaġġ
li diġà qablu bil-quddiem fuq l-muftieħ it-tnejn jużaw.
Imma aħna għandna daqsxejn ta 'problema istartjar hawn.
Kif 2 kompjuters li jridu jikkomunikaw jistabbilixxu sigrieti ewlenin bejniethom?
Jekk il-kjavi għandu jkun sigriet, allura għandna bżonn mod għall-kriptaġġ u decrypt-ċavetta.
Jekk kollha għandna huwa kriptografija ċavetta simetriċi
allura aħna stajt biss jerġgħu lura għall-istess problema.
RSA, min-naħa l-oħra, użi par ta 'ċwievet,
waħda għall encryption u ieħor għall deċifrar.
Wieħed huwa msejjaħ il-ċavetta pubblika, u l-oħra hija ċ-ċavetta privata.
Iċ-ċavetta pubblika tintuża għall-kriptaġġ messaġġi.
Kif inti tista raden mill-isem tagħha, nistgħu naqsmu ċavetta pubblika tagħna ma '
ħadd irridu mingħajr ma tikkomprometti s-sigurtà ta 'messaġġ encrypted.
Messaġġi encrypted bl-użu ta 'ċavetta pubblika
jista 'biss jiġi decrypted bl ċavetta privata tiegħu korrispondenti.
Filwaqt li inti tista 'taqsam ċavetta pubblika tiegħek, għandek dejjem iżżomm sigriet prinċipali tiegħek privat.
u biss iċ-ċavetta privata jistgħu jintużaw biex decrypt messaġġi
jekk 2 utenti jridu jibagħtu messaġġi encrypted bl RSA
quddiem u lura kemm għall-utenti jeħtieġ li jkollhom stess pubblika u privata tagħhom par ċwievet.
Messaġġi mill-utent 1 sa utent 2
jużaw biss par ċwievet 2-utent, u l-messaġġi minn utent 2 għal utenti 1
jużaw biss par ċwievet utent 1 ta.
Il-fatt li hemm 2 ċwievet separati li kriptaġġ u decrypt messaġġi
jagħmel RSA algoritmu ewlenin asimmetrika.
Aħna ma bżonn għall-kriptaġġ-ċavetta pubblika sabiex tibgħat lill-kompjuter ieħor
peress li l-ewlieni huwa pubbliku xorta waħda.
Dan ifisser li RSA ma jkollux il-problema istartjar istess
bħala l-algoritmi ewlenin simetriċi.
Mela jekk jien tixtieq li jibgħat messaġġ bl-użu ta 'encryption RSA
biex Rob, jien ser ewwel jeħtieġ ċavetta pubblika Rob s.
Biex jiġi ġġenerat par ta 'ċwievet, Rob jeħtieġ li pick 2 numri prime kbar.
Dawn in-numri se jintużaw fiż-żewġ ċwievet pubbliċi u privati,
iżda l-ċavetta pubblika għandha tuża biss il-prodott ta 'dawn in-numri 2,
mhux in-numri nfushom.
Ladarba Stajt encrypted l-messaġġ li jużaw ċavetta pubblika Rob s
I tista 'tibgħat il-messaġġ lill Rob.
Għal kompjuter, in-numri factoring hija problema iebsa.
Iċ-ċavetta pubblika, ftakar, użat il-prodott ta '2 numri prime.
Dan il-prodott għandu mbagħad ikollu biss 2-fatturi,
li jiġri li jkun in-numri li jiffurmaw il-ċavetta privata.
Sabiex decrypt-messaġġ, RSA ser tuża dan ċavetta privata
jew in-numri immultiplikat flimkien fil-proċess tal-ħolqien-ċavetta pubblika.
Għaliex dan huwa computationally diffiċli li fattur in-numru
użat fi ċavetta pubblika fil-numri 2 użati fil-ċavetta privata
huwa diffiċli għall-attakkant biex insemmu l-ċavetta privata
li se jkun meħtieġ li decrypt l-messaġġ.
Issa ejja jmorru fis xi dettalji livell aktar baxx ta 'RSA.
Ejja 1 naraw kif nistgħu jiġġeneraw par ta 'ċwievet.
L-ewwel, aħna ser bżonn 2 numri prime.
Aħna ser sejħa dawn in-numri 2 u q p.
Sabiex pick puq, fil-prattika aħna se pseudorandomly jiġġeneraw
numri kbar u mbagħad tuża test għad-determinazzjoni jekk
dawn in-numri huma probabbilment prime.
Nistgħu żżomm jiġġeneraw numri bl-addoċċ fuq u aktar mill-ġdid
sakemm għandna 2 PRIMES li nistgħu nużaw.
Hawn ejja pick p = 23 u q = 43.
Ftakar, fil-prattika, puq għandhom ikunu n-numri ferm akbar.
Safejn nafu, l-akbar in-numri, l-aktar diffiċli hija
biex jitwaqqaf messaġġ encrypted.
Imma hija wkoll aktar għaljin biex messaġġi kriptaġġ u decrypt.
Illum huwa spiss rakkomandat li puq huma mill-inqas 1024 bits,
li jpoġġi kull numru fuq minn 300 ċifri deċimali.
Iżda aħna ser pick dawn in-numri żgħar għall dan l-eżempju.
Issa aħna ser jimmultiplikaw puq flimkien biex jiksbu numru 3,
li aħna ser sejħa n.
Fil-każ tagħna, n = 23 * 43, li = 989.
Aħna n = 989.
Li jmiss aħna ser jimmultiplikaw p - 1 fejn q - 1
jikseb numru 4, li aħna ser sejħa m.
Fil-każ tagħna, m = 22 * ​​42, li = 924.
Għandna m = 924.
Issa aħna ser bżonn e numru li huwa relattivament prime li m
u inqas minn m.
Żewġ numri huma relattivament prime jew coprime
jekk l-eqreb numru sħiħ pożittiv unika li taqsam it-tnejn indaqs huwa 1.
Fi kliem ieħor, il-divisor komuni akbar ta 'e um
għandu jkun ta '1.
Fil-prattika, huwa komuni għall-e li jkun in-numru prime 65537
sakemm dan in-numru ma jiġri li jkun fattur ta 'm.
Għal ċwievet tagħna, aħna ser pick e = 5
mill-5 huwa relattivament prime għal 924.
Fl-aħħarnett, aħna ser bżonn numru wieħed aktar, li aħna ser sejħa d.
D għandu jkun hemm xi valur li jissodisfa l-ekwazzjoni de = 1 (mod m).
Dan m mod ifisser aħna ser tuża xi ħaġa imsejħa aritmetika modulari.
Fl-aritmetika modulari, ladarba numru gets ogħla minn uħud marbuta fuq
dan se jagħlaq lura madwar għal 0.
A arloġġ, per eżempju, l-użi aritmetika modulari.
Minuta wara 01:59, per eżempju, huwa 2:00,
mhux 1:60.
Il-idejn minuta kienet imgeżwer madwar għal 0
meta jilħaq rbit għoli ta '60.
Allura, nistgħu ngħidu 60 huwa ekwivalenti għal 0 (mod 60)
u 125 huwa ekwivalenti għal 65 huwa ekwivalenti għal 5 (mod 60).
Ċavetta pubblika tagħna se tkun l-e par un
fejn f'dan il-każ e huwa 5 u n huwa 989.
Ċavetta privata tagħna se tkun l-par du n,
li fil-każ tagħna huwa 185 u 989.
Avviż li oriġinal PRIMES tagħna puq ma jidhrux
kullimkien fid ċwievet privati ​​jew pubbliċi tagħna.
Issa li għandna par tagħna ta 'ċwievet, ejja tagħti ħarsa lejn kif nistgħu kriptaġġ
u decrypt messaġġ.
Irrid li jibgħat messaġġ lil Rob,
hekk hu se jkun il-wieħed li jiġġenera dan il-par ċavetta.
Imbagħad I ser jistaqsu Rob għal ċavetta pubblika tiegħu, li jiena ser tuża
biex jaqleb f'kowd messaġġ li jibgħat lilu.
Ftakar, huwa totalment okay biex Rob li jaqsmu ċavetta pubblika tiegħu miegħi.
Iżda ma jkunx okay li jaqsmu ċavetta privata tiegħu.
Jien m'għandi l-ebda idea dak ċavetta privata tiegħu huwa.
Aħna jista 'jaqta m messaġġ tagħna up fis biċċiet f'diversi
kollha iżgħar minn nu mbagħad kriptaġġ kull wieħed minn dawk biċċiet.
Aħna ser kriptaġġ-CS50 string, li nistgħu ikissru fis 4 biċċiet,
wieħed għal kull ittra.
Sabiex kriptaġġ messaġġ tiegħi, I bzonn li jissarfu fi
xi tip ta 'rappreżentazzjoni numerika.
Ejja concatenate-valuri ASCII mad-karattri fit-messaġġ tiegħi.
Sabiex biex jaqleb f'kowd messaġġ m partikolari
I bzonn biex tiġi kkalkulata c = m għall-e (mod n).
Imma m għandha tkun iżgħar minn n,
jew inkella l-messaġġ sħiħ ma tistax tiġi espressa modulo n.
Aħna jista 'jaqta m up fis biċċiet diversi, li kollha huma iżgħar minn n,
u kriptaġġ kull wieħed minn dawk biċċiet.
Encrypting kull wieħed minn dawn biċċiet, irridu jiksbu c1 = 67 tad-5 (mod 989)
li = 658.
Għat blokki 2 tagħna għandna 83 sa l-5 (mod 989)
li = 15.
Għat blokki 3 tagħna għandna 53 tad-5 (mod 989)
li = 799.
U fl-aħħarnett, għall-blokki aħħar tagħna għandna 48 għall-5 (mod 989)
li = 975.
Issa nistgħu jibgħat fuq dawn il-valuri kriptata biex Rob.
Hawnhekk inti tmur, Rob.
Filwaqt messaġġ tagħna huwa titjira, ejja jieħdu ieħor ħarsa
lejn kif sirna dak il-valur għall-d.
Numru d tagħna meħtieġa biex jissodisfaw 5d = 1 (mod 924).
Dan jagħmel d-invers multiplikattiv ta '5 modulo 924.
Minħabba 2 interi, a bu, l-algoritmu Euclidean estiż
jistgħu jintużaw biex isibu l-divisor komuni akbar ta 'dawn interi 2.
Huwa se jipprovdi wkoll tagħtina 2 numri oħra, xuy,
li jissodisfaw il-mannara ekwazzjoni + mill = il-divisor komuni akbar ta 'b u.
Kif jaħdem dan tgħinna?
Ukoll, fejn jitwaħħal fl-e = 5 għal
um = 924 għal b
aħna diġà jafu li dawn in-numri huma coprime.
Akbar divisor komuni tagħhom hija l-1.
Din tagħtina 5x + 924y = 1
jew 5x = 1 - 924y.
Imma jekk aħna biss jimpurtahom dwar dak kollu modulo 924
allura nistgħu qatra l - 924y.
Think lura għall-arloġġ.
Jekk l-idejn minuta hija l-1 u mbagħad eżattament 10 siegħa jgħaddu,
nafu l-idejn minuta xorta se tkun fuq il-1.
Hawnhekk aħna tibda fil-1 u mbagħad wrap madwar darbiet eżattament y,
hekk aħna ser xorta jkunu fl-1.
Għandna 5x = 1 (mod 924).
U hawn dan x hija l-istess bħall-d konna qed ifittxu qabel,
hekk jekk nużaw l-algoritmu Euclidean estiż
biex tinkiseb din x l-għadd, li n-numru għandna nużaw bħala d tagħna.
Issa ejja jimxu l-algoritmu Euclidean estiż għal 5 =
u b = 924.
Aħna ser jużaw metodu jissejjaħ il-metodu tal-mejda.
Tabella tagħna se jkollhom 4 kolonni, x, y, d, u k.
Tabella tagħna jibda off ma '2 ringieli.
Fl-ewwel ringiela għandna 1, 0, allura valur tagħna ta ', li huwa 5,
u ringiela tieni tagħna huwa 0, 1, u l-valur tagħna għall-b, li hija 924.
Il-valur tal-kolonna 4, k, se tkun ir-riżultat
tal diviż il-valur ta 'd fil-filliera hawn fuq mal-valur ta' d
fuq l-istess filliera.
Għandna 5 diviż bil 924 hija 0 b'xi bqija.
Dan ifisser li għandna k = 0.
Issa l-valur ta 'kull ċellula oħra se jkun il-valur ta' l-cell 2 fillieri ta 'hawn fuq
nieqes il-valur tal-filliera ta 'hawn fuq drabi k.
Nibdew bl d fil-filliera 3.
Għandna 5-924 * 0 = 5.
Li jmiss għandna 0-1 * 0, li hija 0
u 1 - 0 * 0, li hija l-1.
Mhux wisq ħażina, so ejja jimxu fuq il-filliera li jmiss.
L-ewwel għandna bżonn valur tagħna ta 'k.
924 diviż b'5 = 184 ma 'xi kumplament,
sabiex il-valur tagħna għall-k hija 184.
Issa 924-5 * 184 = 4.
1-0 * 184 huwa 1 u 0 - 1 * 184 hija -184.
Kull dritt, ejja jagħmlu l-ringiela li jmiss.
Valur tagħna ta 'k għandu jkun 1 minħabba
5 diviż bil 4 = 1 ma 'xi bqija.
Ejja imla l-kolonni l-oħra.
5-4 * 1 = 1.
0-1 * 1 = -1.
U 1-184 * 1 huwa 185.
Ejja naraw dak valur li jmiss tagħna ta 'k għandu jkun.
Ukoll, jidher qisu għandna 4 diviż bil 1, li hija 4.
F'dan il-każ fejn aħna qed jiġi diviż mill-1 b'tali mod li k huwa ugwali għal
il-valur ta 'd fil-filliera ta' hawn fuq ifisser li aħna qed isir mal algoritmu tagħna.
Nistgħu naraw hawnhekk li għandna x = 185 uy = -1 fl-aħħar ringiela.
Ejja issa wasal lura għall-għan oriġinali tagħna.
Aħna qal li l-valur ta 'x bħala riżultat ta' running dan algoritmu
ikun l-invers multiplikattiv ta '(b mod).
Dan ifisser li 185 huwa l-invers multiplikattiv ta 5 (mod 924)
li jfisser li għandna valur ta '185 għal d.
Il-fatt li d = 1 fl-aħħar ringiela
jivverifika li e kien coprime li m.
Li kieku ma kienx 1, imbagħad aħna jkollhom pick e ġdid.
Issa ejja ara jekk Rob tkun irċeviet il-messaġġ tiegħi.
Meta xi ħadd jibgħat me messaġġ encrypted
sakemm stajt tinżamm ċavetta privata tiegħi sigriet
Jien l-unika waħda li tista decrypt-messaġġ.
Biex decrypt a c blokki I jistgħu jikkalkolaw l-messaġġ oriġinali
huwa ugwali għall-blokki li d enerġija (mod n).
Ftakar li d un huma mill ċavetta privata tiegħi.
Biex tikseb messaġġ sħiħ mill-biċċiet tiegħu aħna decrypt kull blokki
u concatenate-riżultati.
Eżattament kif sikur huwa RSA?
Il-verità hija, ma nafux.
Sigurtà huwa bbażat fuq kemm żmien ikun jieħu attakkant biex jitwaqqaf messaġġ
encrypted ma 'RSA.
Ftakar li l-attakkant għandu aċċess għall-ċavetta pubblika tiegħek,
li fih kemm le un.
Jekk l-attakkant jirnexxilu fattur n fis-2 PRIMES tagħha, p uq,
allura hi tista 'tikkalkula d tuża l-algoritmu Euclidean estiż.
Dan jagħti tagħha l-muftieħ privat, li jistgħu jintużaw biex decrypt kull messaġġ.
Imma kif malajr nistgħu fattur interi?
Għal darb'oħra, ma nafux.
Ħadd ma sabet mod mgħaġġel ta 'kif isir dan,
li jfisser li jingħataw kbar biżżejjed n
hija kienet ser tieħu l-attakkant mhux realistiku twil
għall-fattur n-numru.
Jekk xi ħadd żvelat mod mgħaġġel ta 'numri interi factoring
RSA ser jinqasmu.
Iżda anke jekk factorization numru sħiħ hija intrinsikament bil-mod
l-algoritmu RSA tista 'xorta jkollha xi difett fiha
li tippermetti għall decryption ta 'messaġġi faċli.
Ħadd ma sabet u żvelat tali difett għadhom,
iżda dan ma jfissirx dan ma jeżistix.
Fit-teorija, xi ħadd jista 'jkun hemmhekk qari data kollha encrypted ma' RSA.
Hemm ieħor daqsxejn ta 'kwistjoni ta' privatezza.
Jekk Tommy encrypts xi messaġġ tuża ċavetta pubblika tiegħi
u attakkant encrypts l-istess messaġġ tuża ċavetta pubblika tiegħi
l-attakkant se tara li l-messaġġi 2 huma identiċi
u b'hekk ikunu jafu liema Tommy encrypted.
Sabiex jiġi evitat dan, il-messaġġi huma tipikament padded bits każwali
qabel ma encrypted sabiex l-istess messaġġ encrypted
darbiet multipli se tħares differenti sakemm il-ikkuttunar fuq il-messaġġ hija differenti.
Imma ftakar kif irridu maqsuma messaġġi fil-biċċiet
b'tali mod li kull blokki hija iżgħar minn n?
Ikkuttunar l-biċċiet ifisser li aħna jista 'jkollha li jaqsam affarijiet up
fis-biċċiet saħansitra aktar peress li l-blokki ikkuttunat għandha tkun iżgħar minn n.
Encryption u dekriptaġġ huma relattivament għaljin ma RSA,
u għalhekk jeħtieġu biex ikissru messaġġ fis-biċċiet ħafna jistgħu jiġu jiswew ħafna.
Jekk volum kbir ta 'dejta jeħtieġ li jkun encrypted u decrypted
nistgħu jgħaqqdu l-benefiċċji ta 'algoritmi simmetriċi ewlenin
ma 'dawk ta' RSA biex tikseb kemm is-sigurtà u l-effiċjenza.
Għalkemm aħna mhux se tidħol fis hawnhekk,
AES hija ċavetta algoriżmika simetriċi bħall-Vigenère u ciphers Caesar
iżda aktar diffiċli biex jitwaqqaf.
Naturalment, aħna ma tistax tuża AES mingħajr ma tistabbilixxi sigrieti ewlenin komuni
bejn is-sistemi 2, u rajna l-problema ma 'dan qabel.
Imma issa nistgħu nużaw RSA biex jistabbilixxu l-sigrieti ewlenin komuni bejn is-sistemi 2.
Aħna ser sejħa tal-kompjuter tintbagħat l-informazzjoni tal-mittent
u l-kompjuter tirċievi d-data tal-riċevitur.
Ir-riċevitur għandu par ta 'ċavetta ta' RSA u tibgħat
il-ċavetta pubblika lill-mittent.
Il-mittent jiġġenera ewlenin AES,
encrypts bl-riċevitur ċavetta pubblika RSA,
u jibgħat l-muftieħ AES lir-riċevitur.
Ir-riċevitur decrypts-messaġġ ma ċavetta privata tiegħu RSA.
Kemm il-mittent u r-riċevitur issa għandhom ċavetta AES maqsuma bejniethom.
AES, li hija ħafna aktar mgħaġġla mill-encryption u deċifrar minn RSA,
issa jistgħu jintużaw għall-kriptaġġ l-volumi kbar ta 'data u jibgħathom lill-riċevitur,
li jistgħu decrypt tuża l-istess ċavetta.
AES, li hija ħafna aktar mgħaġġla mill-encryption u deċifrar minn RSA,
issa jistgħu jintużaw għall-kriptaġġ l-volumi kbar ta 'data u jibgħathom lill-riċevitur,
li jistgħu decrypt tuża l-istess ċavetta.
Aħna biss meħtieġ RSA biex jittrasferixxu l-ċavetta kondiviża.
Aħna m'għadx bżonn jużaw RSA fil-livelli kollha.
Jidher qisu stajt ltqajna messaġġ.
Ma jimpurtax jekk xi ħadd jaqra x'hemm fuq l-ajruplan tal-karta qabel I maqbuda dan
għaliex jien l-unika waħda ma 'ċavetta privata.
Ejja decrypt kull wieħed mill-biċċiet fil-messaġġ.
Il-blokki 1, 658, aħna jgħollu l-qawwa d, li hija 185,
mod n, li hija 989, huwa ugwali għal 67,
li huwa l-ittra C fi ASCII.
Issa, fuq il-blokki 2.
Il-blokki 2 għandu valur 15,
li aħna jgħollu l-qawwa 185,
mod 989, u dan huwa daqs 83
li huwa l-S ittra ASCII.
Issa għall-blokki 3, li għandu valur 799, aħna jgħollu sa 185,
mod 989, u dan huwa ugwali għal 53,
li huwa l-valur tal-karattru 5 fl-ASCII.
Issa għall-blokki aħħar, li għandha valur 975,
aħna jgħollu sa 185, mod 989,
u dan huwa ugwali għal 48, li huwa l-valur tal-karattru ASCII 0.
Jisimni Rob Bowden, u dan huwa CS50.
[CS50.TV]
RSA fil-livelli kollha.
RSA fil-livelli kollha. [Daħk]
Fuq kollox.