[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Harvardeko Unibertsitateko]
[Hau da CS50.] [CS50.TV]
Dezagun RSA, datuak enkriptatzeko algoritmoa asko erabiltzen den begirada bat.
Encryption Caesar eta VigenĂ¨re zifraketen bezalako algoritmoak ez dira oso segurua.
Zesarrek zifratze, erasotzaile batek bakarrik, 25 gako ezberdin saiatu behar
mezua testu arruntera.
Zifraketa VigenĂ¨re da Zesarrek zifratze baino gehiago seguru bitartean
giltzak bilaketa espazio handiagoa delako, erasotzaile batek behin
gakoaren luzera ezagutzen VigenĂ¨re zifratze bat,
enkriptatutako testua ereduak azterketa bidez zehaztu daiteke,
Zifraketa VigenĂ¨re da gehiegi ez Zesarrek zifratze baino askoz ere seguruagoa da.
RSA, beste alde batetik, ez da hau atsegin erasoak zaurgarria.
Zesarren zifratua eta VigenĂ¨re Zifraketa erabili tekla berean
bai encrypt eta mezua desenkriptatu.
Jabetza Horrek horiek zifraketen simetrikoa gakoa algoritmoak.
Gako simetrikoa algoritmoak arazo nagusia A
mezua enkriptatzeko eta bidaltzeko konfiantza dutela
eta bat jasotzea eta mezua desenkriptatu
jadanik adostutako Upfront gakoa zein erabili egingo dute.
Baina arazoa startup apur bat behar dugu hemen.
Nola 2 komunikatu nahi duten ordenagailuak ezarri bien arteko gako sekretua?
Gako sekretua izango behar bada, eta gero enkriptatzeko eta desenkriptatzeko gakoa modu bat behar dugu.
Dugu simetrikoa gako kriptografia bada
ondoren besterik ez dugu arazo bera itzuli.
RSA, beste alde batetik, gako pare bat erabiltzen du,
enkriptatzea eta deszifratzeko beste bat.
One gako publikoa deitzen da, eta beste gako pribatua da.
Gako publikoa erabiltzen du mezuak enkriptatzeko.
Dezakezu bere izena asmatu, gure gako publikoa partekatu ahal izango dugu
Edozeinek enkriptatutako mezu baten segurtasuna arriskuan jarri gabe nahi dugu.
Mezuak gako publikoa erabiliz enkriptatuko
bakarrik ikus daiteke bere dagokion gako pribatua desenkriptatu.
Zure gako publikoa partekatu arren, beti gorde behar duzun zure gako pribatuaren sekretua.
soilik gako pribatua mezuak desenkriptatzeko erabili ahal izango dira
2 erabiltzaile mezuak RSA enkriptatuak bidali nahi izanez gero
atzera eta aurrera erabiltzaile bai erakunde publiko eta pribatu batzuk beren gako parea behar dute.
Erabiltzaile 1 erabiltzaile 2 Messages
bakarrik erabili user 2 gako-bikotea, eta mezuak user 2 erabiltzaile 1
bakarrik erabili user 1 gako parea.
Izan ere, ez dira 2 aparteko gakoak enkriptatzeko eta mezuak desenkriptatu
egiten RSA gako algoritmoa asimetrikoa.
Ez dugu behar gako publikoa enkriptatu behar beste ordenagailu batean bidaltzeko
gakoa da publiko geroztik, hala ere.
Horrek esan nahi du, RSA ez duten startup arazo bera
gako simetrikoa algoritmo gisa.
Beraz, bada RSA enkriptatzea erabiliz mezu bat bidali nahi dut
Rob, Rob gako publikoa behar dut.
Gako pare bat sortzeko, Rob 2 prime zenbakiak handiak jaso behar.
Zenbaki hauek bi gako publikoa eta pribatua erabiliko da,
baina gako publikoa bakarrik erabili 2 zenbaki horiek produktu,
zenbakiak beraiek ez.
Behin mezua Rob gako publikoa erabiliz enkriptatuko dut
Mezua bidali ahal izango dut Rob.
Ordenagailu baten, factoring zenbakiak arazo bat gogorra da.
Gako publikoa, gogoratu, 2 zenbaki lehenen produktua.
Produktu hau behar izan bakarrik 2 faktore
gertatuko den gako pribatua osatzen duten zenbakiak izan.
Mezua desenkriptatu ahal izateko, RSA gako pribatua erabiliko du
edo zenbakiak biderkatu eta gako publikoa sortzeko prozesuan.
Gogorra da computationally delako zenbaki faktore
gako publiko bat erabiltzen da gako pribatua erabiltzen 2 zenbakiak sartu
zaila da erasotzaile bat irudikatu nahi gako pribatua
beharrezkoa izango da mezua desenkriptatu.
Orain dezagun xehetasun batzuk RSA maila txikiagoa sartu.
Dezagun lehen ikus gako pare bat nola sortzen dezakegu.
Lehenik eta behin, prime zenbakiak 2 behar dugu.
Deitu horiek 2 zenbakiak p eta q dugu.
, P eta q, hautatzeko praktikan pseudorandomly sortzen ditugun
handi zenbakiak eta, ondoren, test bat erabili ala ez zehazteko
zenbaki horiek dira ziurrenik prime.
Ausazko zenbakiak sortzen dugu eta gehiagoko berriz
ahal izango dugu erabili 2 Lehenak arte.
Hemen dezagun hautatzeko p = 23 eta q = 43.
Gogoratu, praktikan, p eta q askoz handiagoa zenbakiak izan beharko luke.
Den neurrian ezagutzen dugun bezala, handiagoa zenbakiak, gogorragoa da
Enkriptatutako mezu bat crack.
Baina, era berean encrypt eta mezuak desenkriptatu garestia da.
Gaur egun askotan gomendatzen p eta q direla gutxienez 1024 bit,
300 baino gehiago digituak hamartar zenbaki bakoitza jartzen.
Baina zenbakiak txiki hauen adibide hau jaso dugu.
Orain, p eta q biderkatu dugu elkarrekin 3 zenbaki bat lortzeko,
horrek deitu n dugu.
Gure kasuan, n = 23 * 43, = 989.
Dugu = 989 n.
Hurrengoa p biderkatu dugu - 1 q - 1
4 zenbakia, deitu m dugu lortzeko.
Gure kasuan, m = 22 * ââ42 = 924.
M = 924 ditugu.
Orain zenbaki e nahiko prime behar dugu m
m baino txikiagoa.
Bi zenbakiak samarrak dira prime edo coprime
zenbaki oso positibo bakarra banatzen biak berdinarekin 1 bada.
Beste era batera esanda, e eta m zatitzaile komun handiena
1 izan behar da.
Praktikan, e ohikoa da zenbaki lehena 65537
luze bezala, zenbaki hau ez da gertatuko m faktore bat izan.
Gure teklak, hautatu dugu e = 5
5 baita nahiko 924 prime.
Azkenik, beste bat gehiago zenbakia, deitu d dugu behar dugu.
D batzuetan ekuazioa betetzen duen balioa izan behar du de = 1 (mod m).
Mod m honek ondorioztatzen du zerbait modular aritmetika izeneko erabiliko dugu.
Aritmetika modularra, behin zenbaki bat lortzen batzuk goiko doazen baino handiagoa
inguruan biltzea izango da 0.
Erloju bat, adibidez, aritmetika modularra erabiltzen du.
1:59 minutu bat izan ondoren, adibidez, 2:00
ez 1:60.
Minutuko eskua bilduta inguruan 0
60 aritzeko goiko iristean.
Beraz, esan 60 0 (60 mod) baliokidea
eta 125 65 baliokideak 5 (mod 60) baliokidea da.
Gure gako publikoa bikotea e eta n izango da
non kasu honetan e 5 da, eta n da 989.
Gure bikotea d eta n gako pribatua izango da,
gure kasuan, 185 eta 989.
Iragarki gure jatorrizko Lehenak p eta q ez dela agertzen
gure gakoak pribatu edo publiko edozein lekutan.
Orain gure gako pare bat dugula, dezagun enkripta dezakegu begirada bat
eta mezua desenkriptatu.
Rob mezu bat bidali nahi dut
beraz, gako parea sortzeko izan du.
Ondoren, Rob galdetu dut bere gako publikoa erabiltzen dut
zion bidali mezu bat enkriptatzeko.
Gogoan izan, erabat ados Rob bere gako publikoa partekatzeko nirekin.
Baina ez litzateke ados bere gako pribatua partekatzeko.
Ez daukat bere gako pribatua da, edozein ideia.
Gure mezua m apur daitezke zatiak hainbat
guztiak n baino txikiagoa, eta ondoren enkriptatzeko zatiak horietako bakoitzean.
Katea CS50, apurtzen hasi ahal izango dugu 4 zatitan banatuta dago enkriptatzeko dugu,
letra bakoitzeko bat.
Ordena nire mezua enkriptatzeko, bihurtzeko behar dut
ordezkaritza zenbakizko mota batzuk.
Dezagun kateatu nire mezua karaktereak ASCII balioak.
Emandako mezua m enkriptatu
C = m e (mod n) kalkulatzeko behar dut.
Baina m n baino txikiagoa izan behar da,
edo, bestela, mezu osoa ezin izango da adierazitako modulo n.
M apur daitezke zatiak hainbat, horiek guztiak dira n baino txikiagoa,
eta enkriptatzeko zatiak horietako bakoitzean.
Zatiak horietako bakoitzak enkriptatzea, iritsi C1 = 5 67 (mod 989)
= eta 658.
Gure bigarren zatia 83 dugu 5 (mod 989)
= 15.
Gure hirugarren zatia 5 (mod 989) 53 dugu
= 799.
Eta, azkenik, 5 (mod 989) 48 dugu gure azken zatia
zein = 975.
Orain baino gehiago bidali ahal izango dugu Rob enkriptatutako balio horiek.
Hemen, joan behar Rob.
Gure mezua hegaldia ari den bitartean, dezagun begirada beste
nola d balio hori lortu dugu.
Gure zenbaki d behar 5D = 1 (mod 924) asetzeko.
Hori dela eta, d 5 modulo 924 alderantzizkoa biderkatzaileak.
2 zenbaki osoen kontuan hartuta, eta b, algoritmo hedatua euklidestarra
2 Osoko zenbaki horien zatitzaile komun handiena aurkitzeko erabil daiteke.
Horrez gain, ematen diguten beste 2 zenbakiak, x eta y,
asetzeko ekuazioa ax + = eta b zatitzaile komun handiena.
Nola lagundu digu?
Beno, e = 5 plugging bat
eta m = 924 b
badakigu zenbakiak horiek coprime.
Bere zatitzaile komun handiena 1 da.
Honek ematen digu 5x + 924y = 1
edo 5x = 1 - 924y.
Baina bakarrik dugu guztia modulo 924 buruzko bada zaintzeko
924y orduan askatu ahal izango dugu.
Think itzuli erlojua.
Minutuko batetik, 1 bada, eta, ondoren, zehatz-mehatz 10 ordu igarotzen
minutuko alde batetik oraindik 1 badakigu.
Hona hemen hasteko 1 dugu, eta, ondoren, biltzeko inguruan zehazki y aldiz,
beraz, oraindik ere izango dugu 1.
5x = 1 (mod 924).
Eta hemen x d aurretik ziren bilatzen dugu berdina da,
hala badagokio hedatua euklidestarra algoritmoa erabili dugu
kopurua x hau lortzeko, zenbaki gisa erabili behar dugu gure d.
Orain dezagun exekutatu euklidestarra hedatua = 5 algoritmoa
eta b = 924.
Taula metodoa izeneko metodo bat erabiliko dugu.
Gure taula 4 zutabeak, x, y, d, eta k izango dute.
Gure taula 2 ilaratan hasten.
1, 0, gero, gure balio, hau da, 5 lehenengo errenkadan dugu,
eta gure bigarren ilaran 0, 1, eta gure b balioa, hau da, 924.
4 zutabean, k, balioa emaitza izango da
d balioa goiko errenkadan zatituz d balioa
berean errenkadan.
5 924 arabera banatzen da 0 gainerako batzuk ditugu.
Horrek esan nahi du = 0 k dugun.
Beste zelula guztien balio orain gainean zelula 2 errenkadak balioa izango da
ken aldiz k goiko errenkadan balioa.
Dezagun d hasteko 3. Errenkadan.
Ditugu 5 - 924 * 0 = 5.
Hurrengo dugu 0 - 1 0 0
eta 1 - 0 * 0 1.
Ez da oso txarra, beraz, hurrengo errenkadan mugitzeko.
Lehenik eta behin, gure k balio behar dugu.
924 5 = 184 arabera banatzen da gainerako batzuk
beraz, gure k balioa 184 da.
Orain 924 - 5 * 184 = 4.
1 - 0 * 184 1 eta 0 - 1 * 184 -184.
Guztiak eskubidea, egin dezagun hurrengo errenkadan.
Gure k balioa 1 delako izango da
5 4 = 1 arabera banatzen da gainerako batzuk.
Dezagun beste zutabe bete.
5 - 4 * 1 = 1.
0 - 1 * 1 = -1.
1 - 184 * 1 185 da.
Dezagun gure k hurrengo balioa litzateke ikus-en.
Beno, 4 1, hau da, 4 arabera banatzen da dirudienez.
1 zatituz ari gara, kasu honetan, hala nola, k dela berdina
goiko errenkadan d balioa esan nahi du ari gure algoritmoa egiten dugu.
Dugu hemen ikus ahal izango dugu x = 185 eta y = -1 azken errenkadan.
Dezagun gaur egun itzuli gure jatorrizko helburua.
X balioa emaitza gisa algoritmo hau exekutatzen ari esan genion
(mod b), biderkatzaileak alderantzizkoa izango litzateke.
Horrek esan nahi du 185 alderantzizkoa 5 biderkatzaileak (mod 924)
horrek esan nahi du 185 balioa d dugula.
Izan ere, d = 1 azken errenkadan
egiaztatzen e m coprime zela.
Ez balitz 1 ondoren, mezu berri bat jaso nahi dugu.
Ikus dezagun orain Rob jaso du nire mezua.
Norbaitek me Enkriptatutako mezu bat bidaltzen
Nik ez dut nire gako pribatua mantendu sekretu bat
Duen bakarra desenkriptatu ahal izateko mezua naiz.
Jatorrizko mezua desenkriptatu zatia c kalkulatu ahal izango dut
zatia d power (mod n) berdina da.
Gogoratu d eta g nire gako pribatuak dira.
Mezu osoa lortzeko bere zatiak dugun zatia bakoitzean desenkriptatu
eta kateatu emaitzak.
Zehazki nola RSA segurua da?
Egia da, ez dakigu.
Segurtasuna erasotzaile batek zenbat denbora hartu litzateke mezu bat crack oinarritutako
RSA zifratzen da.
Gogoratu erasotzaile batek zure gako publikoa sarbidea du,
e eta n dauka.
Erasotzaileak kudeatzen n faktorea, bere 2 Lehenak, p eta q sartu bada,
ondoren, d kalkula izan zuen hedatua euklidestarra algoritmoa erabiliz.
Honek bere gako pribatua desenkriptatzeko erabili ahal izango dira, edozein mezu.
Baina, nola azkar osoko zenbakien faktorea dugu?
Berriz ere, ez dakigu.
Inork ez du aurkitu modu azkar bat egiten,
Horrek esan nahi du, kontuan hartuta nahikoa n
erasotzaile batek hartuko luke unrealistically luzea
zenbaki faktore.
Norbait zituzten, factoring osoko zenbakien modu azkar bat bada
RSA hautsi egingo da.
Baina, nahiz eta guztia factorization da berez motela
RSA algoritmoa izan, oraindik akats batzuk
mezuak deszifratzeko erraza ahalbidetzen du.
Inork ez du aurkitu eta agerian flaw hala nola, oraindik,
baina horrek ez du esan nahi ez da existitzen.
Teorian, norbaitek izarrekin izan daiteke RSA bidez enkriptaturik dago datu guztiak irakurtzeko.
Pribatutasun-gai bat beste bit bat da.
Tommy mezu batzuk nire gako publikoa erabiliz enkriptatzen bada
eta erasotzaile batek mezu bera nire gako publikoa erabiliz enkriptatzen
Erasotzaileak 2 mezuak berdinak dira ikusiko
eta, beraz, badakite zer den Tommy enkriptatuko.
Hori gerta ez dadin, mezuak ausazko bit dira normalean hedatu
beraz, eta mezu bera enkriptatzen ari enkriptatzen aurretik
hainbat aldiz beste itxura bat da, betiere Mezu betegarria desberdina da.
Baina gogoratu mezuak nola banatu dugu zatitan banatuta dago
zatia beraz, bakoitzak n baino txikiagoa da?
Zatiak, tarte betegarri esan nahi du gauzak zatitzean sortu dugu agian
zatiak are gehiago geroztik sartu betea zatia n baino txikiagoa izan behar du.
Encryption eta deskodetzea nahiko garestiak RSA
eta, beraz, zatiak hainbat mezu bat hautsi beharrik oso garestia izan daiteke.
Enkriptatutako datuak bolumen handi bat behar du izan nahi baduzu eta desenkripta
algoritmoak gako simetrikoa onurak konbinatu ahal izango dugu
RSA duten bai segurtasuna eta eraginkortasuna lortzeko.
Ez dugun arren, sartu hemen,
AES VigenĂ¨re eta Caesar zifraketen bezalako algoritmoa gako simetrikoa
baina askoz zailagoa crack.
Jakina, ezin dugu erabili AES partekatutako gako sekretua ezarri gabe
2 sistemen artean, eta hori arazoa ikusi genuen aurretik.
Baina orain RSA dezakegu 2 sistemen arteko gako sekretua Elkarbanatutako ezartzeko.
Datuak bidaltzeko bidaltzailearen ordenagailuaren deitu dugu
eta ordenagailua datuak jasotzeko hargailua.
Hartzailea RSA gako-bikote bat du, eta bidaltzen
bidaltzaileari gako publikoa.
Igorleak AES-giltza bat sortzen du,
enkriptatzen hartzailea RSA gako publikoak
eta AES gakoa bidaltzen hargailua.
Hartzailea mezua desenkriptatu bere RSA gako pribatua.
Bi bidaltzailearen eta hartzailearen bien arteko AES Elkarbanatutako gakoa.
AES, enkriptatzea eta deskodetzea RSA baino askoz azkarrago,
daiteke, datu-bolumen handia enkriptatzeko erabiltzen eta hargailua bidaltzeko,
dezaketen pertsonak desenkriptatzeko gako bera erabiliz.
AES, enkriptatzea eta deskodetzea RSA baino askoz azkarrago,
daiteke, datu-bolumen handia enkriptatzeko erabiltzen eta hargailua bidaltzeko,
dezaketen pertsonak desenkriptatzeko gako bera erabiliz.
Besterik ez dugu behar RSA gako partekatua transferitzeko.
Behar ez dugu RSA guztiak erabiltzeko.
Nik got bezala mezu bat dirudi.
Ez du axola edonork irakurri zer paper hegazkin harrapatu nuen aurretik
gako pribatua bakarra naiz dudalako.
Dezagun deszifratu mezuaren zatiak bakoitzean.
Lehenengo zatia, 658, goratzeko d boterea, hau da, 185,
mod n, hau da, 989, 67 berdina da,
ASCII C gutun da.
Orain, bigarren zatiaren gainean.
Bigarren zatiaren 15. Balio du,
goratzeko 185th boterea,
mod 989, eta, hau da, 83 berdinak
hau da, gutun-S ASCII.
Orain hirugarren zatia, balioa 799, goratzeko, 185,
mod 989, eta 53 berdina da,
5 ASCII karaktere-balioa da.
Orain azken zatia, balioa 975,
goratzeko, 185, 989 mod
eta, hau da, 48, ASCII karaktere 0 balioa duen berdina.
Nire izena Rob Bowden da, eta hau da CS50.
[CS50.TV]
RSA at.
RSA at. [Barreak]
Guztiak.