[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.
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.