[Powered by Google Translate] [RSA] [Rob Bowden] [Tommy MacWilliam] [Chuo Kikuu cha Harvard] [Hii ni CS50.] [CS50.TV] Hebu tuangalie RSA, algorithm sana kutumika kwa ajili ya encrypting data. Algorithms encryption kama Kaisari na ciphers Vigenère ni si salama sana. Kwa cipher Kaisari, mshambulizi tu mahitaji ya kujaribu 25 funguo mbalimbali kupata ujumbe wa wazi asilia. Wakati cipher Vigenère ni salama zaidi kuliko cipher Kaisari sababu ya kubwa tafuta nafasi kwa funguo, mara moja mshambulizi anajua urefu wa muhimu katika cipher Vigenère, ambayo inaweza kuamua kupitia uchambuzi wa ruwaza katika maandishi encrypted, Cipher Vigenère si kwamba salama zaidi kuliko cipher Kaisari. RSA, kwa upande mwingine, si katika mazingira magumu na mashambulizi kama hii. Cipher Kaisari na Vigenère cipher kutumia ufunguo huo kwa wote Simba na decrypt ujumbe. Hii inafanya mali hizo ciphers algorithms muhimu symmetriska. Tatizo la msingi na muhimu algorithms symmetriska ni kwamba wao wanategemea moja encrypting na kutuma ujumbe na moja ya kupokea na decrypting ujumbe kuwa tayari walikubaliana upfront juu ya ufunguo wao wote kutumia. Lakini tuna tatizo kidogo ya startup hapa. Jinsi gani 2 kompyuta kwamba unataka kuwasiliana kuanzisha muhimu siri kati yao? Kama muhimu lazima siri, basi tunahitaji njia encrypt na decrypt muhimu. Kama wote tuna ni symmetriska key cryptography kisha tumekuwa tu kurudi tatizo moja. RSA, kwa upande mwingine, anatumia jozi ya funguo, moja kwa encryption na mwingine kwa ajili ya decryption. Moja inaitwa muhimu ya umma, na nyingine ni ufunguo binafsi. muhimu ya umma hutumiwa encrypt ujumbe. Kama unaweza nadhani kwa jina lake, tunaweza kushiriki ufunguo yetu ya umma na mtu yeyote tunataka bila kuacha usalama wa ujumbe ambao umefungiwa. Ujumbe encrypted kutumia ufunguo wa umma inaweza tu decrypted na ufunguo wake sambamba binafsi. Wakati unaweza kushiriki muhimu yako ya umma, unapaswa daima kuweka ufunguo wako binafsi siri. Tangu ufunguo binafsi kuhifadhiwa siri na ufunguo binafsi tu inaweza kutumika kwa ujumbe decrypt, ikiwa 2 watumiaji unataka kutuma ujumbe umesimbwa kwa RSA na kurudi wote watumiaji haja ya kuwa na umma na binafsi zao wenyewe jozi ufunguo. Ujumbe kutoka kwa mtumiaji 1 kwa mtumiaji 2 tu kutumia mtumiaji 2 muhimu ya jozi, na ujumbe kutoka kwa mtumiaji 2 kwa mtumiaji 1 tu kutumia mtumiaji 1 muhimu ya jozi. ukweli kwamba kuna 2 tofauti funguo encrypt na ujumbe decrypt hufanya RSA Differentierade muhimu algorithm. Hatuna haja ya kutia fumbo muhimu ya umma ili kutuma kwa kompyuta nyingine tangu muhimu ni umma anyway. Hii ina maana kwamba RSA hana huo startup tatizo kama algorithm symmetriska muhimu. Jinsi ya kufanya kompyuta 2 kwamba unataka kuwasiliana kuanzisha muhimu siri kati yao? Kama muhimu lazima siri, basi tunahitaji njia encrypt na decrypt muhimu. Kama wote tuna ni symmetriska key cryptography basi tumekuwa tu kurudi tatizo moja. RSA, kwa upande mwingine, anatumia jozi ya funguo, moja kwa encryption na mwingine kwa ajili ya decryption. Moja inaitwa muhimu ya umma, na nyingine ni ufunguo binafsi. muhimu ya umma hutumiwa encrypt ujumbe. Kama unaweza nadhani kwa jina lake, tunaweza kushiriki ufunguo yetu ya umma na mtu yeyote tunataka bila kuacha usalama wa ujumbe ambao umefungiwa. Ujumbe encrypted kutumia ufunguo umma zinaweza tu decrypted na muhimu yake sambamba binafsi. Wakati unaweza kushiriki muhimu yako ya umma, unapaswa daima kuweka ufunguo wako binafsi siri. Tangu ufunguo binafsi kuhifadhiwa siri na tu ufunguo binafsi inaweza kutumika kwa ujumbe decrypt ikiwa 2 watumiaji unataka kutuma ujumbe fiche pamoja na RSA na kurudi wote watumiaji haja ya kuwa na umma na binafsi zao wenyewe jozi ufunguo. Ujumbe kutoka kwa mtumiaji 1 kwa mtumiaji 2 tu kutumia mtumiaji 2 muhimu ya jozi, na ujumbe kutoka kwa mtumiaji 2 kwa mtumiaji 1 tu kutumia mtumiaji 1 muhimu ya jozi. ukweli kwamba kuna 2 tofauti funguo encrypt na ujumbe decrypt hufanya RSA Differentierade muhimu algorithm. Hatuna haja ya kutia fumbo muhimu ya umma ili kutuma kwa kompyuta nyingine tangu muhimu ni umma anyway. Hii ina maana kwamba RSA hana huo startup tatizo kama symmetriska algorithms muhimu. Hivyo kama mimi unataka kutuma ujumbe kwa kutumia encryption RSA Rob, mimi kwanza utahitaji Rob wa umma muhimu. Kuzalisha jozi ya funguo, Rob inahitaji kuchukua 2 idadi kubwa ya waziri mkuu. Namba hizi zitatumika katika wawili funguo za umma na binafsi, lakini muhimu ya umma tu kutumia bidhaa za namba hizi 2, si idadi wenyewe. Mara nimekuwa encrypted ujumbe kwa kutumia Rob wa umma ufunguo Siwezi kutuma ujumbe kwa Rob. Kwa ajili ya kompyuta, factoring idadi ni tatizo ngumu. muhimu ya umma, kumbuka, kutumika bidhaa za namba 2 ya waziri mkuu. Bidhaa hii lazima basi kuwa sababu tu 2, ambayo kutokea kwa kuwa idadi kwamba kufanya juu ya ufunguo binafsi. Ili decrypt ujumbe, RSA kutumia ufunguo binafsi au namba tele pamoja katika mchakato wa kuunda muhimu ya umma. Sababu ni vigumu computationally sababu idadi kutumika katika muhimu ya umma ndani ya namba 2 kutumika katika ufunguo binafsi ni vigumu kwa mshambulizi kufikiri ufunguo binafsi kwamba itakuwa muhimu decrypt ujumbe. Sasa hebu kwenda katika maelezo ya chini baadhi ngazi ya RSA. Hebu kwanza tuone jinsi gani tunaweza kuzalisha jozi ya funguo. Kwanza, sisi itabidi 2 idadi ya waziri mkuu. Tutamwita nambari hizi 2 p na q. Ili kubaini p na q, katika mazoezi tunataka pseudorandomly kuzalisha idadi kubwa na kisha kutumia mtihani kwa ajili ya kuamua iwapo au wale idadi ni pengine waziri mkuu. Tunaweza kuendelea kuzalisha idadi random tena na tena mpaka tuna primes 2 kwamba tunaweza kutumia. Hapa hebu pick p = 23 na q = 43. Kumbuka, katika mazoezi, p na q wanapaswa kuwa kubwa idadi. Mbali kama sisi kujua, idadi kubwa, ngumu ni ufa ujumbe ambao umefungiwa. Lakini pia ni ghali zaidi ujumbe Simba na decrypt. Leo ni mara nyingi ilipendekeza kwamba p na q ni angalau 1024 bits, ambao unaweka idadi ya kila saa digits zaidi ya 300 decimal. Lakini tutaweza kuchukua namba hizi ndogo kwa ajili ya mfano huu. Sasa tutaweza kuzidisha p na q pamoja na kupata idadi 3, ambayo Tutamwita n. Katika kesi yetu, n = 23 * 43, ambayo = 989. Tuna n = 989. Next tutaweza kuzidisha p - 1 na q - 1 kupata idadi 4, ambayo Tutamwita m. Katika kesi yetu, m = 22 * ​​42, ambayo = 924. Tuna m = 924. Sasa tutaweza haja e idadi ambayo ni kiasi mkuu m na chini ya m. Namba mbili ni kiasi mkuu au coprime ikiwa tu integer chanya kwamba mgawanyiko wote wawili ni sawasawa 1. Kwa maneno mengine, kubwa kawaida kigawanyo ya e na m lazima 1. Katika mazoezi, ni kawaida kwa e kuwa idadi mkuu 65,537 muda mrefu kama idadi hii haina kutokea kwa kuwa sababu ya m. Kwa funguo wetu, tutaweza kuchukua e = 5 tangu 5 ni kiasi mkuu 924. Hatimaye, tutaweza haja moja zaidi ya namba, ambayo Tutamwita d. D lazima baadhi thamani utakaokubalika equation de = 1 (Mod m). Hii m Mod kunaashiria tutaweza kutumia kitu kinachoitwa byggelement hesabu. Katika hesabu za msimu, mara moja idadi anapata juu kuliko amefungwa baadhi ya juu ni litamalizika nyuma karibu na 0. saa, kwa mfano, hutumia hesabu byggelement. Dakika moja baada ya 1:59, kwa mfano, ni 2:00, si 1:60. mkono dakika ina kung'ata kwa 0 baada ya kufikia juu amefungwa ya 60. Hivyo, tunaweza kusema 60 ni sawa na 0 (Mod 60) na 125 ni sawa na 65 ni sawa na 5 (Mod 60). Ufunguo yetu ya umma itakuwa e jozi na n ambapo katika kesi hii e ni 5 na n ni 989. Ufunguo yetu binafsi itakuwa d jozi na n, ambayo katika kesi zetu ni 185 na 989. Ona kwamba primes yetu ya awali na p q wala kuonekana mahali popote katika funguo yetu binafsi au ya umma. Sasa kwa kuwa tuna jozi yetu ya funguo, hebu tuangalie ni jinsi gani tunaweza encrypt na decrypt ujumbe. Nataka kupeleka ujumbe kwa Rob, hivyo yeye atakuwa mmoja wa kuzalisha hii jozi ufunguo. Basi mimi itabidi kuuliza Rob kwa ufunguo wake wa umma, ambayo mimi itabidi kutumia encrypt ujumbe kutuma kwake. Kumbuka, ni kabisa sawa kwa Rob kushiriki ufunguo wake wa umma na mimi. Lakini itakuwa ni sawa na kushiriki ufunguo wake binafsi. Mimi si kuwa na wazo lolote nini ufunguo wake binafsi ni. Tunaweza kuvunja ujumbe wetu m juu katika chunks kadhaa ndogo kuliko zote n na kisha encrypt kila chunks hizo. Tutaweza encrypt CS50 kamba, ambayo tunaweza kuvunja katika chunks 4, moja kwa kila barua. Ili kuficha ujumbe wangu, mimi itabidi kubadili kwenye baadhi ya aina ya uwakilishi numeric. Hebu concatenate maadili ASCII na wahusika katika ujumbe wangu. Ili kuficha kupewa ujumbe m Mimi itabidi compute c = m e (Mod n). Lakini m lazima kuwa ndogo kuliko n, au mwingine ujumbe kamili hawezi kuwa walionyesha modulo n. Tunaweza kuvunja m juu katika chunks kadhaa, ambayo yote ni ndogo kuliko n, na simba kila chunks hizo. Encrypting kila chunks hizi, sisi kupata C1 = 67-5 (Mod 989) ambayo = 658. Kwa chunk pili yetu tuna 83-5 (Mod 989) ambayo = 15. Kwa chunk yetu ya tatu tuna 53-5 (Mod 989) ambayo = 799. Na hatimaye, kwa chunk yetu ya mwisho tuna 48-5 (Mod 989) ambayo = 975. Sasa tunaweza kutuma juu ya maadili haya fiche Rob. Hapa kwenda, Rob. Wakati ujumbe wetu ni katika ndege, hebu kuchukua kuangalia mwingine katika jinsi sisi got kwamba thamani kwa d. Idadi yetu d zinahitajika kukidhi 5d = 1 (Mod 924). Hii inafanya d inverse multiplicative ya 5 modulo 924. Kutokana 2 integers, b, na kupanuliwa Euclidean algorithm inaweza kutumika kwa kupata kubwa ya kawaida integers kigawanyo ya hizi 2. Itakuwa pia kutupa 2 idadi nyingine, x na y, kwamba kukidhi shoka equation + na = kigawanyo kubwa ya kawaida ya b na. Jinsi gani hii kutusaidia? Naam, kuziba katika e = 5 kwa na m = 924 kwa b sisi tayari kujua kuwa hizi namba ni coprime. Kawaida wao mkuu kigawanyo ni 1. Hii inatupa 5x + 924y = 1 au 5x = 1 - 924y. Lakini kama sisi tu huduma ya juu kila kitu modulo 924 basi tunaweza kuacha - 924y. Fikiria nyuma ya saa. Kama mkono dakika ni juu ya 1 na kisha hasa masaa 10 kupita, tunajua mkono dakika bado kuwa juu ya 1. Hapa sisi kuanza saa 1 na kisha wrap kuzunguka mara hasa y, hivyo tutaweza bado kuwa katika 1. Tuna 5x = 1 (Mod 924). Na hapa x hii ni sawa kama sisi d walikuwa wanatafuta kabla, hivyo kama sisi kutumia kupanuliwa Euclidean algorithm kupata hii x idadi, hiyo ni idadi tunapaswa kutumia kama d wetu. Sasa hebu kukimbia kupanuliwa Euclidean algorithm kwa 5 = na b = 924. Tutaweza kutumia njia inayoitwa njia meza. Meza yetu itakuwa na nguzo 4, x, y, d, na k. Meza yetu kuanza mbali na safu 2. Katika safu ya kwanza tuna 1, 0, basi thamani yetu ya, ambayo ni 5, na safu ya pili yetu ni 0, 1, na thamani yetu kwa b, ambayo ni 924. thamani ya safu ya 4, k, itakuwa matokeo ya kugawa thamani ya d katika mstari hapo juu kwa thamani ya d juu ya mstari huo. Tuna 5 kugawanywa na 924 ni 0 kwa salio baadhi. Hiyo ina maana tuna k = 0. Sasa thamani ya kila kiini nyingine itakuwa thamani ya safu kiini 2 hapo juu bala thamani ya mstari hapo juu ni mara k. Hebu kuanza na d katika mstari 3. Tuna 5-924 * 0 = 5. Next tuna 0-1 * 0 ambayo ni 0 na 1-0 * 0 ambayo ni 1. Si mbaya sana, hivyo basi hoja juu ya mstari unaofuata. Kwanza tunahitaji thamani yetu ya k. 924 kugawanywa na 5 = 184 na salio baadhi, hivyo thamani yetu kwa k ni 184. Sasa 924-5 * 184 = 4. 1-0 * 184 ni 1 na 0-1 * 184 ni -184. Haki zote, hebu kufanya mstari unaofuata. Thamani yetu ya k itakuwa 1 kwa sababu 5 kugawanywa na 4 = 1 na salio baadhi. Hebu kujaza katika nguzo nyingine. 5-4 * 1 = 1. 0-1 * 1 = -1. Na 1-184 * 1 ni 185. Hebu kuona nini thamani yetu ya pili ya k itakuwa. Naam, inaonekana kama tuna 4 kugawanywa na 1, ambayo ni 4. Katika kesi hii ambapo sisi ni kugawa na 1 vile k kwamba ni sawa na thamani ya d katika mstari hapo juu ina maana kwamba sisi ni kosa na kompyuta yetu. Tunaweza kuona hapa kwamba tuna x = 185 na y = -1 katika mstari wa mwisho. Hebu sasa kurudi lengo yetu ya awali. Sisi alisema kuwa thamani ya x kama matokeo ya kuendesha algorithm itakuwa inverse multiplicative ya (Mod b). Hiyo ina maana kwamba ni 185 inverse multiplicative ya 5 (Mod 924) ambayo ina maana kwamba tuna thamani ya 185 kwa ajili ya d. ukweli kwamba d = 1 katika mstari wa mwisho inathibitisha e kwamba alikuwa coprime kwa m. Kama si 1 kisha sisi ingekuwa kuchukua e mpya. Sasa hebu angalia kama Rob imepokea ujumbe wangu. Wakati mtu anatuma ujumbe ambao umefungiwa yangu muda mrefu kama mimi ve naendelea ufunguo wangu binafsi siri Mimi ni mmoja tu ambao wanaweza decrypt ujumbe. Ili decrypt c chunk naweza mahesabu ya ujumbe halisi ni sawa na chunk d nguvu (Mod n). Kumbuka kwamba d na n ni kutoka ufunguo wangu binafsi. Ili kupata ujumbe kamili kutoka chunks yake sisi decrypt kila chunk na concatenate matokeo. Hasa jinsi salama ni RSA? Ukweli ni kwamba, sisi hatujui. Usalama ni msingi kwa muda gani itachukua mshambulizi kwa ufa ujumbe umesimbwa kwa RSA. Kumbuka kwamba mshambulizi ina kupata ufunguo yako ya umma, ambayo ina wote e na n. Kama mshambulizi itaweza Factor n ndani yake primes 2, uk na q, kisha aliweza kukokotoa d kutumia kupanuliwa Euclidean algorithm. Hii inatoa yake muhimu binafsi, ambayo inaweza kutumika decrypt ujumbe wowote. Lakini jinsi ya haraka tunaweza Factor integers? Tena, hatujui. Hakuna ina kupatikana kwa njia ya haraka ya kufanya hivyo, ambayo ina maana kwamba aliyopewa kubwa ya kutosha n itachukua muda mrefu mshambulizi unrealistically kwa sababu idadi. Kama mtu umebaini njia ya haraka ya integers factoring RSA itakuwa kuvunjwa. Lakini hata kama integer factorization ni inneboende polepole Algorithm RSA bado anaweza kuwa na baadhi ya flaw katika hilo ambayo inaruhusu kwa decryption rahisi ya ujumbe. Hakuna mtu ambaye kupatikana na umebaini flaw vile bado, lakini hiyo haina maana moja haipo. Katika nadharia, mtu angeweza kuwa nje kuna kusoma data zote umesimbwa kwa RSA. Kuna mwingine kidogo ya suala faragha. Kama Tommy encrypts baadhi ujumbe kwa kutumia ufunguo wangu umma na mshambulizi encrypts ujumbe huo kutumia ufunguo wangu umma mshambulizi utaona kwamba ujumbe 2 ni sawa na hivyo kujua nini Tommy msimbo. Ili kuzuia hili, ujumbe ni kawaida padded na bits random kabla ya kuwa encrypted ili kwamba ujumbe huo encrypted mara nyingi utaangalia tofauti kwa muda mrefu kama padding juu ya ujumbe ni tofauti. Lakini kumbuka jinsi tuna pasua ujumbe katika chunks ili kila chunk ni ndogo kuliko n? Padding chunks ina maana kwamba sisi tupate kuwa na mgawanyiko mambo up katika chunks hata zaidi tangu chunk padded lazima kuwa ndogo kuliko n. Encryption na decryption ni kiasi ghali na RSA, na hivyo wanaohitaji kuvunja ujumbe katika chunks wengi wanaweza kuwa gharama kubwa sana. Kama kiasi kikubwa cha data mahitaji ya kuwa na encrypted decrypted tunaweza kuchanganya faida ya algorithms symmetriska ufunguo na wale wa RSA kupata wawili wa usalama na ufanisi. Ingawa sisi si kwenda ndani yake hapa, AES ni muhimu symmetriska algorithm kama Vigenère na Kaisari ciphers lakini vigumu sana ufa. Bila shaka, hatuwezi kutumia AES bila kuanzisha pamoja ufunguo wa siri kati ya mifumo ya 2, na tuliona tatizo na kwamba kabla. Lakini sasa tunaweza kutumia RSA kuanzisha pamoja ufunguo wa siri kati ya mifumo ya 2. Tutamwita kompyuta kutuma data mtumaji na kompyuta kupokea data receiver. receiver ina RSA jozi ufunguo na zituma muhimu ya umma kwa mtumaji. Sender inazalisha muhimu AES, encrypts kwa ufunguo receiver ya RSA umma, na zituma muhimu AES kwa mpokeaji. receiver decrypts ujumbe na ufunguo wake RSA binafsi. Wote mtumaji na mpokeaji sasa kuwa pamoja AES muhimu kati yao. AES, ambayo ni kwa kasi zaidi katika encryption na decryption kuliko RSA, sasa inaweza kutumika encrypt kiasi kikubwa cha data na kuwatuma receiver, ambao wanaweza decrypt kutumia ufunguo huo. AES, ambayo ni kwa kasi zaidi katika encryption na decryption kuliko RSA, sasa inaweza kutumika encrypt kiasi kikubwa cha data na kuwatuma receiver, ambao wanaweza decrypt kutumia ufunguo huo. Sisi tu inahitajika RSA kuhamisha muhimu pamoja. Sisi hakuna tena haja ya kutumia RSA wakati wote. Inaonekana kama mimi nimepata ujumbe. Haijalishi kama mtu yeyote kusoma nini juu ya ndege karatasi kabla mimi hawakupata hiyo kwa sababu mimi nina moja tu na ufunguo binafsi. Hebu decrypt kila chunks katika ujumbe. chunk kwanza, 658, sisi kuongeza nguvu d, ambayo ni 185, Mod n, ambayo ni 989, ni sawa na 67, ambayo ni C barua katika ASCII. Sasa, kwenye chunk pili. chunk pili ana thamani 15, ambayo sisi kuongeza kwa nguvu 185, Mod 989, na hii ni sawa na 83 ambayo ni S barua katika ASCII. Sasa kwa ajili ya chunk ya tatu, ambayo ina thamani 799, sisi kuongeza kwa 185, Mod 989, na hii ni sawa na 53, ambayo ni thamani ya tabia 5 katika ASCII. Sasa kwa ajili ya chunk ya mwisho, ambayo ina thamani 975, sisi kuongeza kwa 185, 989 Mod, na hii ni sawa na 48, ambayo ni thamani ya 0 tabia katika ASCII. Jina langu ni Rob Bowden, na hii ni CS50. [CS50.TV] RSA wakati wote. RSA wakati wote. [Kicheko] Wakati wote.