[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Inivèsite Harvard]
[Sa a se CS50.] [CS50.TV]
Se pou nou pran yon gade nan RSA, yon algorithm lajman itilize pou chifreman done.
Algoritm chifreman tankou Seza tande kòz ak Vigenère Algorithms yo pa twò an sekirite.
Avèk Seza tande kòz kalkile a, yon atakè sèlman bezwen eseye 25 kle diferan
jwenn plenn tèks mesaj la.
Pandan ke kalkile nan Vigenère se plis sekirite pase Seza tande kòz kalkile nan
paske nan espas ki la rechèch pi gwo pou kle, yon fwa yon atakè
konnen longè nan kle a nan yon kalkile Vigenère,
ki ka detèmine atravè yon analiz de pwensip ki nan tèks la chiffres,
kalkile nan Vigenère se pa sa ki pi plis an sekirite pase Seza tande kòz kalkile a.
RSA, sou la lòt bò, se pa vilnerab a atak tankou sa a.
Kalkile nan Seza tande kòz ak Vigenère kalkile itilize kle a menm
a tou de ankripte ak dekriptaj yon mesaj.
Pwopriyete sa a fè sa yo algoritm kle Algorithms simetrik.
Yon pwoblèm fondamantal ak algoritm simetrik kle
se yo ke yo konte sou yon sèl nan chifreman ak voye mesaj la
ak yon sèl la ap resevwa ak dechifre mesaj la
te deja te dakò inicio sou kle a yo pral tou de itilize.
Men, nou gen yon ti jan nan yon pwoblèm demaraj isit la.
Kijan 2 òdinatè yo ki vle kominike etabli yon kle sekrè ant yo?
Si kle a dwe sekrè a, Lè sa a, nou bezwen yon fason yo ankripte ak dekriptaj kle a.
Si tout sa nou genyen se pou chifreman simetrik kle
Lè sa a, nou te jis tounen vin jwenn menm pwoblèm nan.
RSA, sou lòt men an, sèvi ak yon pè kle,
yonn pou chifreman e yon lòt pou dekripte.
Youn nan yo rele kle piblik la, ak lòt la se kle a prive.
Se kle a piblik itilize yo ankripte mesaj.
Kòm ou ta ka devine pa non li yo, nou kapab pataje kle piblik nou yo avèk
nenpòt moun nou vle san yo pa konpwomèt sekirite a nan yon mesaj chiffres.
Messages chiffres lè l sèvi avèk yon kle piblik
kapab fèt sèlman dechifre ak kle korespondan li yo prive.
Pandan ke ou ka pataje kle piblik ou, ou ta dwe toujou kenbe prive ou kle sekrè.
epi li ka sèlman kle nan prive ap itilize yo dekriptaj mesaj
si 2 itilizatè vle voye mesaj chiffres ak RSA
retounen ak lide tou de itilizatè bezwen gen pwòp yo pè piblik ak prive kle.
Mesaj soti nan itilizatè 1 a itilizatè 2
sèlman itilize kle pè 2 itilizatè a, ak mesaj soti nan itilizatè 2 a itilizatè 1
sèlman itilize kle pè 1 user a.
Reyalite a ke gen 2 kle apa ankripte ak dekriptaj mesaj
fè RSA yon asimetri algorithm kle.
Nou pa bezwen ankripte kle piblik la yo nan lòd yo voye li nan yon lòt òdinatè
depi kle a se piblik de tout fason.
Sa vle di ke RSA pa gen menm pwoblèm nan demaraj
kòm algoritm yo simetrik kle.
Se konsa, si mwen vle voye yon mesaj lè l sèvi avèk RSA chifreman
Rob, mwen pral premye bezwen piblik kle Rob a.
Jenere yon pè kle, Rob bezwen chwazi 2 gwo nonb premie.
Nimewo sa yo pral itilize nan tou de kle yo piblik ak prive,
men kle piblik la pral sèlman itilize pwodwi a nan 2 nimewo sa yo,
pa chif yo tèt yo.
Yon fwa mwen te chiffres mesaj la lè l sèvi avèk kle piblik Rob a
Mwen ka voye voye mesaj la nan Rob.
Pou yon òdinatè, nimewo faktorizasyon se yon pwoblèm difisil.
Kle a piblik, sonje, yo itilize pwodwi a nan 2 nonb premie.
Sa a pwodui dwe fèt Lè sa a, gen sèlman 2 faktè,
ki rive yo nimewo yo ki fè moute kle a prive.
Yo nan lòd yo mesaj la dekriptaj, RSA ap itilize sa kle prive
oswa nimewo yo miltipliye ansanm nan pwosesis pou kreye kle a piblik la.
Paske li nan kalkil difisil yo faktè nimewo a
itilize nan yon kle piblik nan 2 chif yo itilize nan kle a prive
li difisil pou yon atakè figi l kle a prive
ki pral nesesè yo dekriptaj mesaj la.
Koulye a, kite a ale nan kèk detay pi ba nivo nan RSA.
Se pou nou premye wè kijan nou ka jenere yon pè kle.
Premyèman, nou pral bezwen 2 nonb premie.
Nou pral rele nimewo sa yo 2 P ak Q.
Yo nan lòd yo chwazi P ak Q, nan pratik nou ta pseudorandomly jenere
nimewo gwo ak Lè sa a, sèvi ak yon tès pou detèmine si wi ou non
moun ki nimewo yo se pwobableman premye.
Nou kapab kenbe génération nimewo o aza sou yo ak sou ankò
jiskaske nou gen 2 primes ke nou ka itilize.
Isit la kite a chwazi p = 23 epi q = 43.
Sonje byen, nan pratik, P ak Q yo ta dwe anpil pi gwo nonb.
Osi lwen ke nou konnen, pi gwo a nimewo yo, pi rèd nan li se
krak yon mesaj chiffres.
Men, li la tou plis chè ankripte ak dekriptaj mesaj.
Jodi a li nan souvan rekòmande pou P ak Q gen omwen 1024 Bits,
ki mete chak nimewo nan plis pase 300 chif desimal.
Men, nou pral chwazi nimewo sa yo ti pou egzanp sa a.
Koulye a, nou pral anpil anpil pitit P ak Q ansanm yo ka resevwa yon nimewo 3rd,
ki nou ap rele n.
Nan ka nou an, n = 23 * 43, ki = 989.
Nou te n = 989.
Next nou pral anpil anpil pitit p - 1 ak q - 1
jwenn yon nimewo 4yèm, ki nou ap rele m.
Nan ka nou an, m = 22 * ​​42, ki = 924.
Nou gen m = 924.
Koulye a, nou pral bezwen yon nimewo e ke se relativman pwemye m
ak mwens pase m.
De nonb yo relativman pwemye oswa coprime
si nonm antye a sèlman pozitif ki divize yo tou de respire se 1.
Nan lòt mo, pi gran divizè a komen nan e ak m
dwe 1.
An pratik, li a ki komen pou e yo dwe nimewo a pwemye 65537
osi lontan ke nimewo sa a pa rive yo dwe yon faktè de m.
Pou kle nou yo, nou pral chwazi e = 5
depi 5 se relativman pwemye 924.
Finalman, nou pral bezwen yon sèl plis nimewo, ki nou ap rele d.
D dwe gen kèk valè ki satisfè ekwasyon an de = 1 (Mod m).
Sa a m Mod vle nou pral sèvi ak yon bagay yo rele modilè aritmetik.
Nan aritmetik modilè, yon fwa yon nimewo vin pi wo pase kèk mare anwo
li pral vlope tounen otou a 0.
Yon revèy, pou egzanp, itilize aritmetik modilè.
Yon minit apre 1:59, pou egzanp, se 2:00,
pa 1:60.
Te men nan minit mare nan ren a 0
lè l genyen yon anwo mare l 'nan 60.
Se konsa, nou ka di 60 se ekivalan 0 (Mod 60)
ak 125 ki ekivalan a 65 ki ekivalan a 5 (Mod 60).
Kle piblik nou yo ap e la pè ak n
kote nan ka sa a e se 5 epi n se 989.
Kle prive nou yo ap d la pè ak n,
ki nan ka nou an, se 185 ak 989.
Remake orijinal nou primes P ak Q pa parèt
nenpòt kote nan kle prive oswa piblik nou yo.
Kounye a ke nou gen pè nou an kle, kite a pran yon gade nan ki jan nou ka ankripte
ak dekriptaj yon mesaj.
Mwen vle voye yon mesaj bay Rob,
pou l 'ka fè yon sèl la yo kreye sa a pè kle.
Lè sa a, mwen pral mande Rob pou kle piblik li a, ki m ap sèvi ak
ankripte yon mesaj pou voye bay l 'yo.
Sonje byen, li la totalman oke pou Rob yo pataje kle piblik li avè m '.
Men, li pa ta dwe oke yo pataje kle prive l 'yo.
Mwen pa gen okenn lide ki sa kle prive li ye.
Nou ka kraze m mesaj nou an moute nan sègman plizyè
tout pi piti pase n ak Lè sa a, ankripte chak nan sa yo fragman.
Nou pral ankripte CS50 nan fisèl, ki nou ka kraze moute nan 4 sègman,
youn pou chak lèt.
Yo nan lòd yo ankripte mesaj mwen, mwen pral bezwen konvèti li an
kèk kalite reprezantasyon nimerik.
Se pou nou anchene valè yo ASCII ak karaktè yo ki nan mesaj mwen an.
Yo nan lòd yo ankripte yon m mesaj bay
Mwen pral bezwen kalkile c = m e an (n Mod).
Men, m dwe pi piti pase n,
oswa lòt moun mesaj la plen pa kapab eksprime modulo n.
Nou ka kraze m moute nan sègman plizyè, nan tout ki se pi piti pase n,
ak ankripte chak nan sa yo fragman.
Chifreman chak nan sa yo fragman, nou jwenn c1 = 67 a 5 an (Mod 989)
ki = 658 yo.
Pou moso dezyèm nou an, nou gen 83 a 5 an (Mod 989)
ki = 15.
Pou moso twazyèm nou an, nou gen 53 a 5 an (Mod 989)
ki = 799.
Epi finalman, pou moso dènye nou an, nou gen 48 a 5 an (Mod 989)
ki = 975.
Koulye a, nou ka voye voye sou valè sa yo chiffres Rob.
La a ou ale, Rob.
Pandan ke mesaj nou an se nan vòl, kite a pran yon lòt gade
nan ki jan nou te resevwa ki valè pou d.
D nimewo nou an bezwen satisfè 5D = 1 (Mod 924).
Sa fè d Envès miltiplikatif nan 5 modulo 924.
Bay 2 nonm antye yo, A ak B yo, pwolonje algorithm nan eklidyen
yo ka itilize yo jwenn pi gran divizè a komen nan 2 sa yo nonm antye relatif.
Li pral tou ba nou 2 nimewo lòt, x ak y,
ki satisfè rach la ekwasyon + By = pi gran divizè a komen nan yon b ak.
Kijan sa a ede nou?
Oke, rakorde nan e = 5 pou yon
ak m = 924 pou b
nou deja konnen ke nimewo sa yo se coprime.
Pi gran yo divizè komen se 1.
Sa ban-nou 5x + 924y = 1
oswa 5x = 1 - 924y.
Men, si nou sèlman pran swen sou tout bagay modulo 924
Lè sa a, nou ka lage - 924y la.
Panse tounen nan revèy la.
Si se men nan minit se sou 1 ak Lè sa a, egzakteman 10 èdtan pase,
nou konnen men an minit ap toujou gen sou 1 an.
Isit la nou kòmanse nan 1 ak Lè sa a, vlope toutotou fwa egzakteman y,
se konsa nou pral toujou gen 1.
Nou gen 5x = 1 (Mod 924).
Ak isit la sa a x se menm bagay la kòm d nan nou te kap chèche anvan,
Se konsa, si nou itilize pwolonje algorithm nan eklidyen
jwenn sa a x nimewo, sa se nimewo a nou ta dwe itilize kòm d nou an.
Koulye a, kite a kouri pwolonje algorithm nan eklidyen pou yon 5 =
epi b = 924.
Nou pral sèvi ak yon metòd ki rele metòd la tab.
Tab nou yo ap gen 4 kolòn, x, y, d, ak k.
Tab nou an kòmanse koupe ak 2 ranje.
Nan premye ranje a nou gen 1, 0, donk valè nou an yon, ki se 5,
ak ranje dezyèm nou an se 0, 1, ak valè nou yo pou b, ki se 924.
Valè a nan kolòn nan 4yèm, k, yo pral rezilta nan
nan divize valè a nan d nan ranje ki anwo a li ak valè a nan d
sou ranje a menm.
Nou gen 5 divize pa 924 se 0 ak kèk rès.
Sa vle di nou gen k = 0.
Koulye a, valè a nan chak selil lòt yo pral valè a nan 2 ranje yo selil pi wo pase l
mwens valè a nan ranje a pi wo pase l fwa k.
Kite la kòmanse avèk d nan ranje a 3yèm.
Nou gen 5 - 924 * 0 = 5.
Next nou gen 0 - 1 * 0 ki se 0
ak 1 - 0 * 0 ki se 1.
Pa twò move, kidonk kite yo deplase sou ranje a kap vini an.
Premye nou bezwen valè nou an k.
924 divize pa 5 184 = ak kèk rès,
se konsa valè nou an pou k se 184.
Koulye a, 924 - 5 * 184 = 4.
1 - 0 * 184 se 1 ak 0 - 1 * 184 se -184.
Tout dwa, kite a fè ranje a kap vini an.
Valè nou yo ki genyen k ap 1 paske
5 divize pa 4 1 = ak kèk rès.
Se pou nou ranpli nan kolòn yo ak lòt.
5 - 4 * 1 = 1.
0 - 1 * 1 = -1.
Ak 1 - 184 * 1 se 185.
Ann wè sa ki valè pwochen nou yo nan k ta dwe.
Oke, li sanble nou gen 4 divize pa 1, ki se 4.
Nan ka sa a kote n ap divize pa 1 sa yo ki k se egal a
valè a nan d nan ranje ki anwo a vle di ke nou ap fè ak algorithm nou an.
Nou ka wè isit la ke nou gen x = 185 epi y = -1 nan ranje ki sot pase yo.
Se pou nou kounye a tounen vin jwenn objektif orijinal nou an.
Nou te di ke valè x kòm yon konsekans kouri sa a algorithm
ta dwe envès la miltiplikatif yon (Mod b).
Sa vle di ke 185 se Envès miltiplikatif nan 5 (Mod 924)
ki vle di ke nou gen yon valè de 185 pou d.
Lefèt ke d = 1 nan ranje nan dènye
verifye te ke e coprime m.
Si se pa t '1 Lè sa a, nou ta gen yo chwazi yon e nouvo.
Koulye a, kite a wè si Rob te resevwa mesaj mwen an.
Lè yon moun ap voye m 'yon mesaj chiffres
osi lontan ke mwen te kenbe kle prive mwen yon sekrè
Mwen yon sèl la sèlman ki moun ki ka dekriptaj mesaj la.
Dekriptaj yon moso c mwen ka kalkile mesaj orijinal la
ki egal a moso nan d pouvwa (Mod n).
Sonje ke d ak n yo soti nan kle prive mwen an.
Pou jwenn yon mesaj plen soti nan sègman li nou dekriptaj chak moso
ak anchene rezilta yo.
Egzakteman kouman sekirite sa, se RSA?
Verite a se, nou pa konnen.
Sekirite a baze sou konbyen tan li ta pran yon atakè krak yon mesaj
chiffres ak RSA.
Sonje ke yon atakè gen aksè a kle piblik ou a,
ki gen tou de e ak n.
Si atakè a jere faktè n nan 2 primes li yo, P ak Q,
Lè sa a, li te kapab kalkile d lè l sèvi avèk pwolonje algorithm nan eklidyen.
Sa a ba l 'kle nan prive, ki ka itilize yo dekriptaj nenpòt mesaj.
Men, ki jan nou ka byen vit faktè nonb antye relatif?
Yon fwa ankò, nou pa konnen.
Okenn moun pa te jwenn yon fason vit nan fè li,
ki vle di ke yo bay gwo ase n
li ta pran yon atakè irealist long
faktè nimewo a.
Si yon moun devwale yon fason vit nan nonm antye relatif faktorizasyon
RSA ta gen pou kase.
Men, menm si nonb antye relatif faktorizasyon se natirèlman ralanti
algorithm nan RSA te ka toujou gen kèk defo nan li
ki pèmèt pou dekripte fasil nan mesaj.
Okenn moun pa te jwenn ak devwale tankou yon defo ankò,
men sa pa vle di yon sèl pa egziste.
Nan teyori, yon moun ta ka soti la lekti tout done chiffres ak RSA.
Genyen yon lòt ti jan nan yon pwoblèm konfidansyalite.
Si Tommy chifre kèk mesaj lè l sèvi avèk kle piblik m '
ak yon atakè chifre menm mesaj la lè l sèvi avèk kle piblik m '
atakè a pral wè ke mesaj yo 2 se idantik
e konsa konnen ki sa Tommy chiffres.
Yo nan lòd yo anpeche sa a, mesaj yo, se tipikman Matlasye ak Bits o aza
avan ke yo te chiffres pou ke menm mesaj la chiffres
plizyè fwa pral gade diferan osi lontan ke kouvèti a sou mesaj la se diferan.
Men, sonje ki jan nou dwe divize mesaj nan sègman
pou ke chak moso se ki pi piti pase n?
Kouvèti sègman yo vle di ke nou ka gen yo fann bagay yo
nan menm plis sègman depi moso nan Matlasye dwe pi piti pase n.
Chifreman ak dekripte yo relativman chè ak RSA,
ak sa ki bezwen kraze moute yon mesaj nan sègman anpil ka trè koute chè.
Si yon volim gwo done bezwen yo dwe chiffres ak dechifre
nou ka konbine benefis ki genyen nan algoritm simetrik kle
ak sa yo ki nan RSA jwenn tou de sekirite ak efikasite.
Malgre ke nou pa pral antre li isit la,
AES se yon algorithm simetrik kle tankou Vigenère la ak Seza tande kòz algorithms
men pi difisil krak.
Natirèlman, nou pa ka sèvi ak AES san etabli yon pataje kle sekrè
ant 2 sistèm yo, epi nou te wè pwoblèm nan ak ke anvan.
Men koulye a, nou kapab itilize RSA etabli pataje kle a sekrè ant 2 sistèm yo.
Nou pral rele òdinatè a voye done yo moun k la
ak òdinatè a ap resevwa done yo reseptè la.
Reseptè a gen yon pè RSA kle epi voye
kle a piblik la moun k la.
Moun k nan jenere yon kle AES,
chifre li ak RSA kle reseptè a nan piblik la,
epi voye kle a AES reseptè la.
Reseptè a dechifr mesaj la ak kle RSA li yo prive.
Tou de moun k la ak reseptè a koulye a gen yon pataje AES kle ant yo.
AES, ki se anpil pi vit nan chifreman ak dekripte pase RSA,
kapab kounye a ka itilize ankripte komèsan ki gwo done epi voye yo bay reseptè a,
ki moun ki ka dekriptaj lè l sèvi avèk kle a menm.
AES, ki se anpil pi vit nan chifreman ak dekripte pase RSA,
kapab kounye a ka itilize ankripte komèsan ki gwo done epi voye yo bay reseptè a,
ki moun ki ka dekriptaj lè l sèvi avèk kle a menm.
Nou jis bezwen RSA transfere kle a pataje.
Nou pa bezwen sèvi ak RSA nan tout.
Li sanble ke mwen te gen yon mesaj.
Li pa enpòtan si nenpòt moun ki li sa ki la sou avyon an papye anvan m 'kenbe li
paske mwen yon sèl la sèlman ki gen kle a prive.
Se pou nou dekriptaj chak nan sègman yo ki nan mesaj la.
Moso a an premye, 658, nou leve sou pouvwa a d, ki se 185,
Mod n, ki se 989, ki egal a 67,
ki se C a lèt nan ASCII.
Koulye a, sou moso, dezyèm lan.
Moso nan dezyèm gen valè 15,
ki nou leve sou pouvwa a 185th,
989 Mod, e sa se egal a 83
ki se S nan lèt nan ASCII.
Koulye a, pou moso nan twazyèm, ki te gen valè 799, nou leve a 185,
989 Mod, e sa se egal a 53,
ki se valè a an karaktè a 5 nan ASCII.
Koulye a, pou moso nan dènye, ki te gen valè 975,
nou leve a 185, Mod 989,
ak sa a se egal a 48, ki se valè de 0 a karaktè nan ASCII.
Non mwen se Rob Bowden, ak sa a se CS50.
[CS50.TV]
RSA nan tout.
RSA nan tout. [Ri]
Nan tout.