[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Universiteti i Harvardit]
[Kjo është CS50.] [CS50.TV]
Le të marrin një vështrim në RSA, një algorithm përdorur gjerësisht për encrypting të dhënave.
Algoritme encryption si Cezarit dhe shifra Vigenere nuk janë shumë të sigurta.
Me shifër Cezarit, një sulmues ka nevojë vetëm për të provoni 25 çelësat ndryshme
për të marrë plain text mesazhi-së.
Ndërsa shifër Vigenere është më e sigurtë sesa shifër Caesar
për shkak të hapësirës më të madhe e kërkimit për çelësa, pasi një sulmues
e di gjatësinë e kyç në një shifër Vigenere,
e cila mund të përcaktohet me anë të një analize të modeleve në tekst koduar,
shifër Vigenere nuk është se shumë më i sigurt se sa shifër Cezarit.
RSA, në anën tjetër, nuk është e ndjeshme ndaj sulmeve si kjo.
Shifër Cezari dhe Vigenere shifër të përdorni të njëjtin kyç
të dy encrypt dhe decrypt një mesazh.
Kjo pronë i bën këto algoritme simetrike kryesore shifra.
Një problem themelor me algoritme simetrike kryesore
është se ata mbështeten në një encrypting dhe dërgimin e mesazhit
dhe ai merr dhe decrypting mesazh
për të kanë rënë dakord tashmë upfront në tast që ata të dy do të përdorin.
Por ne kemi një pak e një problemi për fillimin këtu.
Si mund të 2 kompjuterëve që duan të komunikojnë të krijuar një çelës sekret midis tyre?
Nëse çelësi duhet të jetë i fshehtë, atëherë ne kemi nevojë për një mënyrë për të encrypt dhe decrypt kryesore.
Nëse të gjithë ne kemi është Kriptografia simetrike kyçe
atëherë ne kemi ardhur vetëm përsëri në të njëjtin problem.
RSA, në anën tjetër, përdor një palë çelësa,
një për encryption dhe një tjetër për decryption.
Njëri është quajtur çelësi publik, dhe të tjera është çelësi privat.
Çelësi publik është përdorur për të encrypt mesazhe.
Si ju mund të me mend me emrin e saj, ne mund të ndajnë çelësin tonë publik me
dikush ne duam, pa kompromentuar sigurinë e një mesazhi të koduar.
Mesazhet koduar duke përdorur një çelës publik
mund të decrypted me kyç përkatës saj private.
Ndërsa ju mund të ndajnë kyç tuaj publik, ju duhet të mbani gjithmonë privat sekret tuaj kryesor.
dhe vetëm çelësi privat mund të përdoret për të decrypt mesazhe
2 përdorues në qoftë se dëshironi të dërgoni mesazhe të koduara me RSA
mbrapa dhe me radhë të dy përdoruesit duhet të ketë palë e tyre publike dhe private kyç.
Mesazhe nga 1 përdorues në 2 përdorues
përdorin vetëm palë kyç 2 përdoruesit, dhe mesazhe nga 2 përdorues në 1 përdorues
përdorin vetëm palë kyç 1 përdorues s.
Fakti që nuk janë të ndara 2 çelësat për të encrypt dhe decrypt mesazhe
RSA bën një algoritmi asimetrike kyç.
Ne nuk kemi nevojë për të encrypt çelësin publik në mënyrë që të dërgoni atë në një kompjuter tjetër
që çelësi është publike anyway.
Kjo do të thotë se RSA nuk kanë të njëjtin problem për fillimin
si algoritme simetrike kryesore.
Pra, nëse unë dua të dërgoj një mesazh duke përdorur encryption RSA
të vjedh, unë do të duhet së pari çelësin publik Rob.
Për të gjeneruar një palë çelësa, Rob duhet të marr 2 numra të mëdha kryeministër.
Këta numra do të përdoren në të dy çelësat publik dhe privat,
por çelësi publik do të përdorin vetëm produkt i këtyre numrave 2,
jo numrat e vetë.
Sapo kam mbyllur mesazhin duke përdorur çelësin publik Rob
Unë mund të dërgoni mesazhin tek Rob.
Për një kompjuter, numra factoring është një problem i vështirë.
Çelësi publik, mbani mend, e përdorur produktin e 2 numrave të kryeministrit.
Ky produkt duhet të ketë vetëm 2 faktorë,
që të ndodhë të jenë numrat që përbëjnë çelësin privat.
Në mënyrë për të decrypt mesazhi, RSA do të përdorni këtë çelës privat
ose numrat e shumëzuar së bashku në procesin e krijimit çelësin publik.
Për shkak se ajo është e vështirë për të computationally faktor numrin
përdorur në një kyç publik në 2 numra të përdorura në kyç privat
kjo është e vështirë për një sulmues të gjej çelësin privat
që do të jetë e nevojshme për të decrypt mesazhi.
Tani le të shkojmë në disa detaje të nivelit të ulët të RSA.
Le të parë të shohim se si mund të gjenerojnë një palë çelësa.
Së pari, ne do të duhet 2 numrat e kryeministrit.
Ne do të quajmë këto 2 numra p dhe q.
Në mënyrë që të marr p dhe q, në praktikë do të gjenerojë pseudorandomly
një numër i madh dhe pastaj të përdorin një test për të përcaktuar nëse janë apo jo
ato numra janë ndoshta kryeministër.
Ne mund të vazhdojmë të gjeneruar numra të rastit pushim
deri sa ne kemi 2 primes që ne mund të përdorni.
Këtu le të marr p = q = 23 dhe 43.
Mos harroni, në praktikë, p dhe q duhet të jetë një numër shumë më të mëdha.
Aq sa dimë, të mëdha e numrave, aq më e vështirë është
për të goditur një mesazh të koduar.
Por ajo është gjithashtu më e shtrenjtë për të encrypt dhe decrypt mesazhe.
Sot ajo është rekomanduar shpesh se p dhe q janë të paktën 1024 bit,
e cila e vë çdo numër në mbi 300 shifra dhjetore.
Por ne do të marr këto numra të vogla për këtë shembull.
Tani ne do të shumohen p dhe q bashku për të marrë një numër 3,
të cilat ne do të thërrasë n.
Në rastin tonë, n = 23 * 43, e cila = 989.
Ne kemi n = 989.
Ardhshëm ne do të shumohen P - 1 me q - 1
për të marrë një numër 4, të cilat ne do të thërrasë m.
Në rastin tonë, m = 22 * ​​42, e cila = 924.
Ne kemi m = 924.
Tani ne do të duhet një e numër që është relativisht kryeministër të m
dhe më pak se m.
Dy numra janë relativisht kryeministër apo coprime
në qoftë se numër i plotë pozitiv i vetëm që ndan ata të dy në mënyrë të barabartë është 1.
Me fjalë të tjera, pjesëtues i përbashkët i madh e dhe m
duhet të jetë 1.
Në praktikë, kjo është e zakonshme për të jetë numër kryesor 65.537
për aq kohë sa ky numër nuk ndodh të jetë një faktor i m.
Për çelësat tona, ne do të vini e = 5
nga 5 është relativisht kryeministër të 924.
Së fundi, ne do të duhet një numër më shumë, të cilat ne do të thërrasë d.
D duhet të jetë një vlerë që kënaq ekuacionin de = 1 (mod m).
Kjo mod m tregon ne do të përdorim diçka që quhet aritmetikë modulare.
Në aritmetikë modulare, pasi një numër merr më shumë se disa afate sipërme
ajo do të përfundojë kthehet rreth për të 0.
Një orë, për shembull, përdor aritmetikë modulare.
Një minutë pas 01:59, për shembull, është 2:00,
jo 1:60.
Dora minuta ka përfunduar rreth për të 0
me arritjen e një sipërme të detyruar të 60.
Pra, ne mund të themi 60 është e barabartë me 0 (mod 60)
dhe 125 është e barabartë me 65 është e barabartë me 5 (mod 60).
Çelësi ynë publik do të jetë e palë dhe n
ku në këtë rast E është 5 dhe n është 989.
Çelësi ynë privat do të jetë palë d dhe n,
e cila në rastin tonë është 185 dhe 989.
Vini re se origjinale tonë primes p dhe q nuk duket
kudo në çelësat tona private ose publike.
Tani që ne kemi palë tonë të çelësat, le të marrin një sy se si ne mund të encrypt
dhe decrypt një mesazh.
Unë dua të dërgoj një mesazh tek Rob,
kështu që ai do të jetë ai për të gjeneruar këtë palë kryesore.
Atëherë unë do të kërkoj për Rob kyç tij publike, të cilën unë do të përdorin
për të encrypt një mesazh për të dërguar atij.
Mos harroni, kjo është krejtësisht në rregull për të ndarë Rob çelësin e tij publike me mua.
Por kjo nuk do të jetë në rregull për të ndarë çelësin e tij privat.
Unë nuk kam asnjë ide se çfarë kyç e tij private është.
Ne mund të thyejnë m tonë mesazhit deri në chunks disa
të gjitha të vogla se n encrypt dhe pastaj secili prej këtyre chunks.
Ne do të encrypt CS50 varg, të cilat ne mund thyer deri në 4 chunks,
një për letër.
Në mënyrë që të encrypt mesazhin tim, unë do të duhet për të kthyer atë në
një lloj i përfaqësimit numerik.
Le të lidh vlerat ASCII me karaktereve në mesazhin tim.
Në mënyrë që të encrypt një mesazh dhënë m
Unë do të duhet për të llogaritur K = M me E (mod n).
Por m duhet të jetë më e vogël se n,
ose tjetër mesazhi i plotë nuk mund të shprehet modulo n.
Ne mund të shpërthejë m deri në chunks të ndryshme, të cilat janë më të vogla se n,
encrypt dhe secili prej këtyre chunks.
Encrypting secilën prej këtyre chunks, ne kemi marrë c1 = 67 me 5 (mod 989)
që = 658.
Për copë tonë të dytë ne kemi 83 me 5 (mod 989)
që = 15.
Për copë tonë të tretë, ne kemi 53 me 5 (mod 989)
që = 799.
Dhe së fundi, për copë tonë të fundit ne kemi 48 me 5 (mod 989)
që = 975.
Tani ne mund të dërgojë mbi këto vlera të koduara Rob.
Këtu ju shkoni, Rob.
Ndërsa mesazhi ynë është në fluturim, le të marrin një sy
se si kemi marrë këtë vlerë për d.
D tonë numri i nevojshëm për të kënaqur 5D = 1 (mod 924).
Kjo e bën të d inversi multiplicative e 5 modulo 924.
Duke pasur parasysh 2 integers, a dhe b, algorithm Euklidiane zgjeruar
mund të përdoret për të gjetur pjesëtues të madh të përbashkët të këtyre 2 integers.
Ai gjithashtu do të na japin 2 numra të tjerë, x dhe y,
që të kënaqë sëpatë ekuacion + nga = pjesëtues më të madh të përbashkët të A dhe B.
Si funksionon kjo të na ndihmojë?
E pra, në mbylljen e = 5 për një
dhe m = 924 për b
ne tashmë e dimë se këto numra janë coprime.
Pjesëtues më e madhe e tyre e përbashkët është 1.
Kjo na jep 5x + 924y = 1
ose 5x = 1 - 924y.
Por nëse ne vetëm kujdeset për çdo gjë modulo 924
atëherë ne mund të bjerë - 924y.
Mendoni përsëri për orën.
Nëse dora minutë është më 1 dhe më pas pikërisht 10 orë kalojnë,
ne e dimë se dora minuta do të vazhdojë të jetë në 1.
Këtu ne të fillojë në 1 dhe pastaj të përfundojë rreth herë pikërisht y,
kështu që ne do të vazhdojë të jetë në 1.
Ne kemi 5x = 1 (mod 924).
Dhe këtu ky x është i njëjtë si d kemi qenë duke kërkuar për para,
kështu që nëse ne përdorim algoritmin zgjeruar Euklidiane
për të marrë këtë numër x, që është numri ne duhet të përdorin si d tonë.
Tani le të kandidojë algorithm Euklidiane zgjatur për një = 5
dhe b = 924.
Ne do të përdorim një metodë të quajtur metoda tryezë.
Tabela e jonë do të ketë 4 kolona, ​​x, y, d, dhe k.
Tabela tonë fillon me 2 rreshta.
Në radhë të parë ne kemi 1, 0, atëherë vlera jonë e një, e cila është 5,
dhe rresht ynë i dytë është 0, 1, dhe vlera jonë për B, e cila është 924.
Vlera e kolonës 4, k, do të jetë rezultat
të ndarë vlerën e D në rreshtin lart atë me vlerë të d
në të njëjtin rresht.
Ne kemi ndarë nga 5 924 është 0 me disa mbetur.
Kjo do të thotë ne kemi k = 0.
Tani vlera e çdo qelizë tjetër do të jetë vlera e 2 rreshtave celularë mësipërme të
minus vlerën e rresht më lart atë herë k.
Le të fillojmë me d në rreshtin e 3.
Ne kemi 5-924 * 0 = 5.
Tjetra ne kemi 0-1 * 0 e cila është 0
dhe 1 - 0 * 0 cila është 1.
Jo shumë e keqe, kështu që le të shkojë për në rresht tjetër.
Së pari ne kemi nevojë për vlerën tonë të k.
924 ndara me 5 = 184 me disa mbetur,
kështu vlera tonë për k është 184.
Tani 924-5 * 184 = 4.
1 - 0 * 184 është 1 dhe 0 - 1 * 184 është -184.
Të gjithë të drejtë, le të bëjë rresht tjetër.
Vlera jonë e k do të jetë 1 për shkak
5 ndarë nga 4 1 = me disa mbetur.
Le të plotësoni kolonat e tjera.
5 - 4 * 1 = 1.
0 - 1 * 1 = -1.
Dhe 1-184 * 1 është 185.
Le të shohim se çfarë vlera jonë e ardhshme të k do të jetë.
E pra, kjo duket si ne kemi 4 pjesëtohet me 1, e cila është 4.
Në këtë rast ne jemi duke pjesetuar me 1 tilla që k është e barabartë me
vlera e d në radhën e mësipërme do të thotë se ne jemi duke bërë me algorithm tonë.
Ne mund të shohim këtu se kemi x = 185 dhe y = -1 në rreshtin e fundit.
Le të kthehemi tani në qëllimin tonë origjinal.
Kemi thënë se vlera e x si pasojë e drejtimin e këtij algoritmi
do të jetë inversi multiplicative e një (b mod).
Kjo do të thotë se 185 është inversi multiplicative e 5 (mod 924)
që do të thotë se kemi një vlerë prej 185 për d.
Fakti që d = 1 në rreshtin e fundit
vërteton se e ka coprime të m.
Në qoftë se kjo nuk ishin 1 atëherë ne do të duhet të marr një e re.
Tani le të shohim nëse Rob ka marrë mesazhin tim.
Kur dikush dërgon mua një mesazh të koduar
sa kohë që unë kam kryesore e mia mbajtur një sekret privat
Unë jam i vetmi që mund të decrypt mesazhi.
Për të dekodojnë një c segmentin unë mund të llogarisin mesazhin origjinal
është e barabartë me copë tek D fuqisë (MOD n).
Mos harroni se d dhe n janë nga kyç time private.
Për të marrë një mesazh të plotë nga chunks e saj ne decrypt çdo copë
dhe lidh rezultatet.
Saktësisht se si të sigurt është RSA?
E vërteta është, ne nuk e dimë.
Sigurisë është i bazuar në sa kohë do të marrë një sulmues për të goditur një mesazh
koduar me RSA.
Mos harroni se një sulmues ka qasje në kyç tuaj publik,
i cili përmban edhe E dhe n.
Nëse sulmuesi arrin të faktor në primes n 2 e saj, p dhe q,
atëherë ajo mund të llogarisin d përdorur algorithm Euklidiane zgjeruar.
Kjo i jep asaj çelësin privat, i cili mund të përdoret për të decrypt ndonjë mesazh.
Por sa shpejt mund të kemi faktor integers?
Përsëri, ne nuk e dimë.
Askush nuk ka gjetur një mënyrë të shpejtë për të bërë atë,
që do të thotë se duke pasur parasysh mjaft e madhe n
ajo do të marrë një sulmues jorealiste të gjatë
faktor për numrin.
Nëse dikush zbuloi një mënyrë të shpejtë të integers factoring
RSA do të jetë i prishur.
Por edhe nëse factorization numër i plotë është në thelb i ngadalshëm
algorithm RSA ende mund të ketë disa krisje në atë
që lejon për decryption lehtë të mesazheve.
Askush nuk ka gjetur të tillë dhe zbuloi një krisje ende,
por kjo nuk do të thotë nuk ekziston.
Në teori, dikush mund të jetë atje lexuar të gjitha të dhënat e koduara me RSA.
Nuk është një tjetër pak e një çështje private.
Nëse Tommy kodon një mesazh duke përdorur çelësin publik time
dhe një sulmues kodon të njëjtin mesazh duke përdorur çelësin publik time
sulmuesi do të shihni se 2 mesazhe janë identike
dhe kështu e di se çfarë Tommy koduar.
Në mënyrë për të parandaluar këtë, mesazhet janë mbushur zakonisht me copa të rastit
para se të koduar në mënyrë që të njëjtin mesazh Encrypted
herë të shumta do të duken të ndryshme për aq kohë sa mbushje në mesazhin është e ndryshme.
Por mos harroni se ne kemi për të ndarë mesazhet në chunks
në mënyrë që çdo copë është më i vogël se n?
Zbutja e chunks të thotë që ne mund të kemi për të ndarë gjërat
në chunks aq më tepër që duhet të jetë mbushur copë e vogël se n.
Encryption decryption dhe janë relativisht të shtrenjta me RSA,
dhe kështu kanë nevojë për të thyer një mesazh në chunks shumë mund të jetë shumë i kushtueshëm.
Nëse një vëllim i madh i të dhënave duhet të jetë i mbyllur dhe decrypted
ne mund të kombinojnë përfitimet e algoritme simetrike kryesore
me ato të RSA për të marrë edhe sigurinë dhe efikasitetin.
Edhe pse ne nuk do të shkojë në atë këtu,
AES është një algoritmi simetrik kyç si Vigenere dhe Cezarit shifra
por shumë e vështirë për të goditur.
Sigurisht, ne nuk mund të përdorë AES pa krijimin e një çelës sekret të përbashkët
mes 2 sistemeve, dhe ne pa problem me këtë më parë.
Por tani ne mund të përdorim për të krijuar RSA kyç sekret të përbashkët në mes të 2 sistemeve.
Ne do të thërrasë në kompjuter dërguar dhënave të dërguesit
dhe marrjes së të dhënave kompjuterike marrës.
Marrësi ka një palë RSA kyç dhe dërgon
çelësi publik të dërguesit.
Dërguesi gjeneron një çelës AES,
kodon atë me çelës RSA publik të drejtorit,
dhe dërgon kyç AES të pranuesit.
Marrësi decrypts mesazh me çelës RSA saj private.
Si dërguesi dhe marrësi tani kanë një çelës të përbashkët AES mes tyre.
AES, e cila është shumë më e shpejtë në encryption dhe decryption se RSA,
tani mund të përdoret për të encrypt vëllime të mëdha të të dhënave dhe për të dërguar ato në marrës,
i cili mund të decrypt duke përdorur të njëjtin kyç.
AES, e cila është shumë më e shpejtë në encryption dhe decryption se RSA,
tani mund të përdoret për të encrypt vëllime të mëdha të të dhënave dhe për të dërguar ato në marrës,
i cili mund të decrypt duke përdorur të njëjtin kyç.
Ne vetëm e nevojshme për të transferuar RSA kyç përbashkët.
Ne nuk duhet të përdorni RSA në të gjitha.
Ajo duket si unë kam marrë një mesazh.
Kjo nuk ka rëndësi në qoftë se dikush të lexoni se çfarë është në aeroplan letër para se të kapur atë
sepse unë jam i vetmi me çelës privat.
Le të decrypt secilin nga segmentet në mesazh.
Copë e parë, 658, ne të rritur të energjisë d, i cili është 185,
MOD n, e cila është 989, është i barabartë me 67,
cila është C letër në ASCII.
Tani, mbi copë dytë.
Copë e dytë ka vlerë 15,
që ne të rritur në pushtet 185,
mod 989, dhe kjo është e barabartë me 83
cila është letër S në ASCII.
Tani për copë e tretë, i cili ka vlerën 799, ne të rritur deri në 185,
mod 989, dhe kjo është e barabartë me 53,
cila është vlera e karakter 5 në ASCII.
Tani për copë fundit, i cili ka vlerën 975,
ne të rritur deri në 185, 989, mod
dhe kjo është e barabartë me 48, e cila është vlera e karakterit 0 në ASCII.
Emri im është Rob Bowden, dhe kjo është CS50.
[CS50.TV]
RSA në të gjitha.
RSA në të gjitha. [Qeshura]
Në të gjitha.