[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. Peress li l-ċavetta privata għandhom jinżammu sigriet u biss iċ-ċavetta privata jistgħu jintużaw biex decrypt messaġġi, jekk 2-utenti jridu jibagħtu messaġġi encrypted ma 'RSA quddiem u lura kemm utenti jeħtieġ li jkollhom stess pubblika u privata tagħhom par ċwievet. Messaġġi mill-utent 1 sa utent 2 biss juża par ċwievet 2 utent, u l-messaġġi minn utent 2 sa utent 1 biss juża par ċwievet 1 utent. 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 ċavetta algoriżmika simetriċi. Kif tagħmel 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 konna 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 'ħaddieħor irridu mingħajr ma tikkomprometti s-sigurtà ta 'messaġġ encrypted. Messaġġi encrypted bl-użu ta 'ċavetta pubblika tista' biss tiġ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. Peress li l-ċavetta privata għandu jinżamm sigriet 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.