[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Harvard University]
[Mae hyn yn CS50.] [CS50.TV]
Gadewch i ni edrych ar RSA, algorithm a ddefnyddir yn eang ar gyfer amgryptio data.
Nid yw algorithmau Encryption fel Cesar a seifferau Vigenère yn ddiogel iawn.
Gyda'r cipher Cesar, ymosodwr ond angen i roi cynnig ar 25 allweddi gwahanol
i gael testun y neges yn blaen.
Er bod y cipher Vigenère yn fwy diogel na'r cipher Cesar
oherwydd y gofod chwilio mwy ar gyfer allweddi, unwaith y bydd ymosodwr
yn gwybod hyd y allweddol mewn cipher Vigenère,
y gellir ei benderfynu drwy ddadansoddiad o batrymau yn y testun wedi'i amgryptio,
nid yw'r cipher Vigenère yw bod llawer mwy diogel na'r cipher Cesar.
RSA, ar y llaw arall, nid yw'n agored i ymosodiadau fel hyn.
Mae'r cipher Cesar a Vigenère cipher yn defnyddio'r un allweddol
i'r ddau amgryptio a dadgryptio neges.
Mae'r eiddo yn gwneud hyn yn allweddol seifferau algorithmau cymesur.
Mae problem sylfaenol gyda algorithmau allweddol cymesur
yw eu bod yn dibynnu ar yr un amgryptio ac yn anfon y neges
a'r un sy'n derbyn ac yn decrypting y neges
i eisoes wedi cytuno ar ymlaen llaw ar yr allwedd bydd y ddau yn eu defnyddio.
Ond mae gennym dipyn o broblem startup yma.
Sut mae 2 gyfrifiadur sydd am gyfathrebu sefydlu allwedd gudd rhyngddynt?
Os oes rhaid i'r allweddol yn gyfrinach, yna mae angen ffordd i amgryptio a dadgryptio yr allwedd.
Os yw'r holl gennym yw cryptograffeg cymesur allweddol
yna rydym wedi newydd ddod yn ôl at yr un broblem.
RSA, ar y llaw arall, yn defnyddio pâr o allweddi,
un ar gyfer amgryptio a'r llall ar gyfer dadgriptio.
Enw un yw'r allwedd gyhoeddus, a'r llall yw'r allwedd breifat.
Yr allwedd gyhoeddus yn cael ei ddefnyddio i amgryptio negeseuon.
Fel y gallech ddyfalu gan ei enw, gallwn rannu ein cyhoeddus allweddol gyda
unrhyw un yr ydym eisiau heb gyfaddawdu diogelwch neges wedi ei amgryptio.
Negeseuon hamgryptio gan ddefnyddio allwedd gyhoeddus
dim ond ei dadgriptio gyda'i allwedd breifat.
Er y gallwch rannu eich allwedd gyhoeddus, dylech bob amser gadw eich cyfrinach preifat allweddol.
a dim ond yr allwedd breifat yn cael ei ddefnyddio i negeseuon dadgryptio
os 2 defnyddiwr yn dymuno anfon negeseuon amgryptio gyda RSA
yn ôl ac ymlaen ddwy angen i ddefnyddwyr gael eu hunain cyhoeddus a phreifat pâr allweddol.
Negeseuon gan ddefnyddiwr 1 i ddefnyddiwr 2
ond yn defnyddio pâr 2 defnyddiwr allweddol, a negeseuon o ddefnyddiwr 2 i ddefnyddiwr 1
ond yn defnyddio defnyddiwr 1 pâr allweddol.
Mae'r ffaith fod 2 allweddi ar wahân i amgryptio a dadgryptio negeseuon
gwneud RSA algorithm allweddol anghymesur.
Nid oes angen i amgryptio allweddol cyhoeddus er mwyn ei anfon at gyfrifiadur arall
gan fod yr allwedd yn gyhoeddus beth bynnag.
Mae hyn yn golygu nad oes gan RSA y broblem startup un
fel y algorithmau cymesur allweddol.
Felly, os ydw i eisiau anfon neges gan ddefnyddio amgryptio RSA
i Rob, 'n annhymerus' yn gyntaf bydd angen Rob allweddol gyhoeddus.
I greu pâr o allweddi, Rob angen i ddewis 2 rif cysefin mawr.
Bydd y rhifau hyn yn cael ei ddefnyddio yn y ddwy allweddi cyhoeddus a'r sector preifat,
ond bydd yr allwedd gyhoeddus ond yn defnyddio'r cynnyrch o'r 2 rhifau,
nid yw'r niferoedd eu hunain.
Unwaith yr wyf wedi amgryptio y neges gan ddefnyddio Rob allweddol cyhoeddus
Gallaf anfon y neges i Rob.
Am cyfrifiadur, rhifau ffactorio yn broblem anodd.
Yr allwedd gyhoeddus, cofiwch, a ddefnyddir y cynnyrch o 2 rhifau cysefin.
Mae'n rhaid i'r cynnyrch yna dim ond 2 ffactor,
sy'n digwydd i fod y rhif sy'n gwneud i fyny 'r allwedd breifat.
Er mwyn dadgryptio y neges, bydd RSA defnyddio'r allwedd breifat
neu y niferoedd lluosi â'i gilydd yn y broses o greu yr allwedd gyhoeddus.
Oherwydd ei fod yn computationally anodd i ffactor y nifer
a ddefnyddir mewn cywair cyhoeddus i 2 rhifau a ddefnyddir yn yr allwedd breifat
mae'n anodd i ymosodwr at chyfrif i maes yr allwedd breifat
a fydd yn angenrheidiol i dadgryptio y neges.
Nawr gadewch i ni fynd i mewn i rai manylion lefel is o RSA.
Gadewch i ni yn gyntaf weld sut y gallwn greu pâr o allweddi.
Yn gyntaf, bydd angen 2 rhifau cysefin.
Byddwn yn galw'r rhain yn 2 rif p a q.
Er mwyn dewis p a q, yn ymarferol byddem yn pseudorandomly cynhyrchu
niferoedd mawr ac yna defnyddio prawf ar gyfer penderfynu a ddylid
niferoedd hynny yn ôl pob tebyg cysefin.
Gallwn gadw cynhyrchu rhifau ar hap drosodd a throsodd
hyd nes y byddwn yn cael 2 rhifau cysefin y gallwn eu defnyddio.
Yma gadewch i ni ddewis p = 23 a q = 43.
Cofiwch, yn ymarferol, dylai p a q yn niferoedd llawer mwy.
Cyn belled ag y gwyddom, y mwyaf y nifer, yr anoddaf yw hi
i fynd i'r afael neges wedi ei amgryptio.
Ond mae hefyd yn fwy costus i negeseuon amgryptio a dadgryptio.
Heddiw, mae'n argymhellir yn aml fod p a q yn o leiaf 1024 darnau,
sy'n rhoi pob rhif ar dros 300 o digid degol.
Ond byddwn yn dewis y niferoedd bach ar gyfer yr enghraifft hon.
Nawr byddwn yn lluosi p a q at ei gilydd i gael nifer 3ydd,
y byddwn yn galw n.
Yn ein hachos ni, n = 23 * 43, sy'n = 989.
Rydym wedi n = 989.
Nesaf byddwn yn lluosi p - 1 gyda q - 1
i gael rhif 4, y byddwn yn galw m.
Yn ein hachos ni, m = 22 * ​​42, sy'n = 924.
Rydym wedi m = 924.
Nawr bydd angen inni gael e rhif sydd gymharol wych i m
a llai na m.
Mae dau niferoedd yn gymharol cysefin neu coprime
os yw'r cyfanrif positif yn unig sy'n rhannu ddau ohonynt gyfartal yw 1.
Mewn geiriau eraill, y rhannydd mwyaf cyffredin o e m a
Mae'n rhaid i fod yn 1.
Yn ymarferol, mae'n gyffredin i e i fod yn rhif cysefin 65,537
cyn belled nad y nifer hwn yn digwydd i fod yn ffactor o m.
Ar gyfer ein allweddi, byddwn yn dewis e = 5
ers 5 yn gymharol wych i 924.
Yn olaf, bydd angen un rhif fwy, y byddwn yn galw d.
Rhaid i D fod rhywfaint o werth sy'n bodloni'r hafaliad de = 1 (mod m).
Mae hyn yn m mod yn dynodi y byddwn yn defnyddio rhywbeth o'r enw rhifyddeg modiwlaidd.
Yn rhifyddeg modiwlaidd, unwaith y mae nifer yn cael uwch na rhai rhwymo uchaf
bydd yn lapio o gwmpas yn ôl i 0.
Mae cloc, er enghraifft, yn defnyddio rhifyddeg modiwlaidd.
Un munud ar ôl 01:59, er enghraifft, yn 2:00,
Nid yw 1:60.
Y llaw munud wedi lapio o amgylch i 0
ar gyrraedd uchaf rhwymo o 60.
Felly, gallwn ddweud 60 yn cyfateb i 0 (mod 60)
a 125 yn cyfateb i 65 yn cyfateb i 5 (mod 60).
Bydd ein cyhoeddus allweddol fydd y e pâr a n
lle yn yr achos hwn yw e 5 a n yn 989.
Bydd ein allwedd breifat fydd y pâr a d n,
sydd, yn ein hachos 185 a 989.
Hysbysiad nad yw ein gwreiddiol rhifau cysefin p a q yn ymddangos
unrhyw le yn yr allweddi preifat neu gyhoeddus.
Nawr ein bod wedi ein pâr o allweddi, gadewch i ni edrych ar sut y gallwn amgryptio
a dadgryptio neges.
Dw i eisiau anfon neges i Rob,
felly bydd yn cael yr un i gynhyrchu y pâr allweddol.
Yna, byddaf yn gofyn i Rob am ei cyhoeddus allweddol, a byddaf yn defnyddio
i amgryptio neges i'w hanfon iddo.
Cofiwch, mae'n hollol iawn i Rob i rannu ei cyhoeddus allweddol gyda mi.
Ond ni fyddai'n iawn i rannu ei allwedd breifat.
Nid oes gennyf unrhyw syniad beth yw ei allwedd breifat yn.
Gallwn torri ein m neges i fyny yn ddarnau nifer o
i gyd yn llai na n ac yna amgryptio pob un o'r darnau.
Byddwn yn encrypt y, CS50 llinyn y gallwn dorri i fyny i mewn 4 ddarnau,
un ar gyfer pob llythyren.
Er mwyn amgryptio fy neges, bydd angen i mi droi i mewn i
rhyw fath o gynrychiolaeth rhifol.
Gadewch i concatenate y gwerthoedd ASCII gyda'r cymeriadau yn fy neges.
Er mwyn amgryptio a m neges a roddir
Bydd angen i mi gyfrifo c = m i'r e (mod n).
Ond mae'n rhaid m fod yn llai na n,
neu ni all y neges llawn yn cael ei fynegi modwlo n.
Gallwn dorri m i fyny i ddarnau nifer, pob un ohonynt yn llai na n,
ac amgryptio pob un o'r darnau.
Amgryptio pob un o'r darnau, rydym yn cael c1 = 67 i 5 (mod 989)
sy'n = 658.
Ar gyfer ein darn 2 mae gennym 83 i 5 (mod 989)
sy'n = 15.
Ar gyfer ein darn drydedd wedi 53 i 5 (mod 989)
sy'n = 799.
Ac yn olaf, ar gyfer ein darn olaf sydd gennym 48 at y 5 (mod 989)
a = 975.
Nawr gallwn anfon dros y gwerthoedd amgryptio i Rob.
Dyma chi fynd, Rob.
Er bod ein neges yn hedfan, gadewch i ni edrych eto
ar sut yr ydym yn cael y gwerth am d.
Angen nifer Ein d i fodloni 5d = 1 (mod 924).
Mae hyn yn gwneud d gwrthdro multiplicative o 5 modwlo 924.
Cael 2 cyfanrifau, a b a, algorithm Ewclidaidd estynedig
gellir ei ddefnyddio i ddod o hyd i'r rhannydd cyffredin mwyaf y 2 gyfanrifau.
Bydd hefyd yn rhoi 2 rifau eraill, x ac y,
sy'n bodloni'r hafaliad ax + by = y rhannydd mwyaf cyffredin o b a.
Sut mae hyn yn helpu ni?
Wel, plygio i mewn e = 5 ar gyfer
ac m = 924 ar gyfer b
rydym eisoes yn gwybod bod y niferoedd yn coprime.
Mae eu mwyaf rhannydd cyffredin yw 1.
Mae hyn yn rhoi i ni 5x + 924y = 1
neu 5x = 1 - 924y.
Ond os mai dim ond gofalu am bopeth modwlo 924
yna gallwn gollwng y - 924y.
Meddyliwch yn ôl at y cloc.
Os y llaw munud ar 1 ac yna yn union 10 awr pasio,
rydym yn gwybod y bydd y llaw munud yn dal i fod ar y 1.
Yma, rydym yn dechrau ar 1 ac yna lapio o amgylch amseroedd yn union y,
felly byddwn yn dal i fod yn 1.
Rydym wedi 5x = 1 (mod 924).
A dyma y x yw yr un fath â'r d roeddem yn chwilio am o'r blaen,
felly os byddwn yn defnyddio'r algorithm Ewclidaidd estynedig
i gael y rhif x, dyna'r rhif y dylem ei ddefnyddio fel ein d.
Nawr, gadewch i redeg yr algorithm Ewclidaidd estynedig am 5 =
a b = 924.
Byddwn yn defnyddio dull o'r enw y dull bwrdd.
Bydd ein bwrdd yn cael 4 colofn, x, y, d, a k.
Mae ein bwrdd yn dechrau i ffwrdd gyda 2 res.
Yn y rhes gyntaf rydym wedi 1, 0, yna mae ein gwerth, sef 5,
ac mae ein ail res yw 0, 1, ac mae ein gwerth am b, sef 924.
Bydd gwerth y golofn 4ydd, k, fod yn ganlyniad
o rannu gwerth d yn y rhes uwch ei ben gyda gwerth d
ar yr un rhes.
Mae gennym 5 wedi'i rannu â 924 yw 0 gyda rhai gweddill.
Mae hynny'n golygu ein bod wedi k = 0.
Yn awr, bydd y gwerth pob cell arall fydd gwerth y 2 cell rhesi uchod
minws gwerth y rhes uwch ei gwaith k.
Gadewch i ni ddechrau gyda d yn y rhes 3ydd.
Mae gennym 5-924 * 0 = 5.
Nesaf rydym 0 - 1 * 0 a yw 0
a 1 - 0 * 0 sef 1.
Ddim yn rhy ddrwg, felly gadewch i ni symud ymlaen i'r rhes nesaf.
Yn gyntaf mae angen ein gwerth k.
924 wedi'i rannu â 5 = 184 gyda rhai gweddill,
felly mae ein gwerth am k yw 184.
Nawr 924-5 * 184 = 4.
1-0 * 184 yw 1 a 0-1 * 184 yn -184.
Mae pob hawl, gadewch i ni wneud y rhes nesaf.
Bydd ein gwerth k fod yn 1 oherwydd
5 wedi'i rannu â 4 = 1 gyda rhai gweddill.
Gadewch i ni llenwch y colofnau eraill.
5-4 * 1 = 1.
0-1 * 1 = -1.
Ac 1-184 * 1 yn 185.
Gadewch i ni weld beth fyddai ein gwerth nesaf k fod.
Wel, mae'n edrych fel mae gennym 4 wedi'i rannu gan 1, sef 4.
Yn yr achos hwn lle'r ydym yn rhannu erbyn 1 fel bod k yn hafal i
gwerth d yn y rhes uchod yn golygu ein bod yn ei wneud gyda ein algorithm.
Gallwn weld yma fod gennym x = 185 ac y = -1 yn y rhes olaf.
Gadewch i ni yn awr yn dod yn ôl at ein nod gwreiddiol.
Rydym yn dweud bod y gwerth o x o ganlyniad i gynnal y algorithm
fyddai wrthdro multiplicative o (mod b).
Mae hynny'n golygu bod 185 yn wrthdro multiplicative o 5 (mod 924)
sy'n golygu bod gennym werth o 185 i d.
Mae'r ffaith bod d = 1 yn y rhes olaf
cadarnhau bod e yn coprime i m.
Os nad oedd 1, yna byddai'n rhaid i ni ddewis e newydd.
Nawr gadewch i ni weld os Rob wedi derbyn fy neges.
Pan fydd rhywun yn anfon neges i mi ei amgryptio
cyn belled gan fy mod i wedi cadw fy allwedd breifat yn gyfrinach
Fi yw'r unig un sy'n gallu dadgryptio y neges.
I dadgryptio a c dalp gallaf gyfrifo y neges wreiddiol
yn hafal i'r darn i d pŵer (mod n).
Cofiwch fod d a n yn dod o fy allwedd breifat.
I gael neges llawn o'i darnau rydym yn dadgryptio bob darn
ac yn concatenate y canlyniadau.
Yn union pa mor ddiogel yw RSA?
Y gwir yw, nid ydym yn gwybod.
Diogelwch yn seiliedig ar ba mor hir y byddai'n ei gymryd i ymosodwr i dorri neges
amgryptio gyda RSA.
Cofiwch fod ymosodwr yn cael mynediad at eich allwedd gyhoeddus,
Ynddo, mae e a n.
Os yw'r ymosodwr yn llwyddo i ffactor n yn ei 2 rhifau cysefin, p a q,
yna gallai hi gyfrifo d ddefnyddio'r algorithm Ewclidaidd estynedig.
Mae hyn yn rhoi iddi allwedd breifat, y gellir ei ddefnyddio i dadgryptio unrhyw neges.
Ond pa mor gyflym rydym yn ffactor cyfanrifau?
Unwaith eto, nid ydym yn gwybod.
Does neb wedi dod o hyd i ffordd gyflym o wneud hynny,
sy'n golygu y rhoddir digon mawr n
byddai'n cymryd ymosodwr afrealistig o hir
i ffactor y rhif.
Os bydd rhywun yn dangos ffordd gyflym o gyfanrifau ffactoreiddio
Byddai RSA yn cael ei dorri.
Ond hyd yn oed os cyfanrif factorization yn ei hanfod yn araf
gallai'r algorithm RSA yn dal i gael rhywfaint o nam yn ei
sy'n caniatáu ar gyfer Gwall Rheolwr hawdd o negeseuon.
Does neb wedi dod o hyd ac yn datgelu o'r fath yn wendid eto,
ond nid yw hynny'n golygu nad oes un yn bodoli.
Yn ddamcaniaethol, gallai rhywun fod allan yno yn darllen yr holl ddata amgryptio gyda RSA.
Mae un arall dipyn o fater preifatrwydd.
Os Tommy encrypts rhywfaint o neges gan ddefnyddio fy cyhoeddus allweddol
ac ymosodwr encrypts yr un neges gan ddefnyddio fy cyhoeddus allweddol
Bydd yr ymosodwr yn gweld bod y 2 negeseuon yn union yr un fath
ac felly yn gwybod beth Tommy amgryptio.
Er mwyn atal hyn, negeseuon yn cael eu padio fel arfer gyda darnau ar hap
cyn cael ei amgryptio fel bod yr un neges amgryptio
Bydd sawl gwaith yn edrych yn wahanol cyhyd â bod y padin ar y neges yn wahanol.
Ond cofiwch sut y mae'n rhaid i ni rannu negeseuon i mewn i ddarnau
fel bod pob darn yn llai na n?
Phadin y darnau yn golygu y gallai fod yn rhaid i rannu pethau i fyny
yn ddarnau hyd yn oed mwy gan fod yn rhaid i'r darn padded yn llai nag n.
Encryption a dadgriptio yn gymharol ddrud gyda RSA,
ac felly gall fod angen i dorri i fyny neges yn ddarnau lawer o fod yn gostus iawn.
Os bydd swm mawr o ddata mae angen ei amgryptio a dadgryptio
gallwn gyfuno manteision o algorithmau allweddol cymesur
â rhai RSA i gael y ddau diogelwch ac effeithlonrwydd.
Er na fyddwn yn mynd i mewn yma,
AES yn algorithm allweddol cymesur fel y Vigenère a seifferau Caesar
ond yn llawer anoddach i agenna.
Wrth gwrs, ni allwn ddefnyddio AES heb sefydlu allwedd gudd
rhwng y 2 system, ac rydym yn gweld y broblem gyda hynny o'r blaen.
Ond nawr gallwn ddefnyddio'r RSA i sefydlu'r allwedd gudd rhwng y 2 system.
Byddwn yn galw y cyfrifiadur yn anfon y data yr anfonwr
ac mae'r cyfrifiadur yn derbyn y data y derbynnydd.
Mae'r derbynnydd yn cael pâr allweddol RSA ac yn anfon
yr allwedd gyhoeddus at yr anfonwr.
Mae'r anfonwr yn cynhyrchu allweddol AES,
amgryptio gyda allweddol y derbynnydd cyhoeddus RSA,
ac yn anfon allweddol AES i'r derbynnydd.
Mae'r derbynnydd decrypts y neges gyda'i allweddol RSA breifat.
Mae'r anfonwr a'r derbynnydd bellach allweddol AES rhannu rhyngddynt.
AES, sydd yn llawer cyflymach yn amgryptio a dadgriptio na RSA,
yn awr yn gallu cael ei ddefnyddio i amgryptio y symiau mawr o ddata ac yn eu hanfon at y derbynnydd,
sy'n gallu dadgryptio ddefnyddio'r allwedd un.
AES, sydd yn llawer cyflymach yn amgryptio a dadgriptio na RSA,
yn awr yn gallu cael ei ddefnyddio i amgryptio y symiau mawr o ddata ac yn eu hanfon at y derbynnydd,
sy'n gallu dadgryptio ddefnyddio'r allwedd un.
Rydym yn unig sydd ei angen RSA i drosglwyddo'r allweddol a rennir.
Rydym nid oes angen i ddefnyddio RSA o gwbl.
Mae'n edrych fel gen i neges.
Nid oes ots os unrhyw un wedi darllen beth sydd ar yr awyren papur cyn i mi ei ddal
oherwydd fi yw'r unig un gyda'r allwedd breifat.
Gadewch i ni dadgryptio pob un o'r darnau yn y neges.
Y darn cyntaf, 658, rydym yn codi i rym d, sef 185,
mod n, sef 989, yn hafal i 67,
sef y llythyren C yn ASCII.
Yn awr, ar y darn ail.
Mae'r darn gan ail werth 15,
yr ydym yn codi i 185 y pŵer,
mod 989, ac mae hyn yn hafal i 83
sef y S llythyr yn ASCII.
Nawr am y darn trydydd sydd â gwerth 799, rydym yn codi i 185,
mod 989, ac mae hyn yn hafal i 53,
sef y gwerth y cymeriad 5 yn ASCII.
Nawr am y darn olaf, sydd â gwerth 975,
rydym yn codi i 185, mod 989,
ac mae hyn yn hafal i 48, sef gwerth y 0 cymeriad yn ASCII.
Fy enw i yw Rob Bowden, ac mae hyn yn CS50.
[CS50.TV]
RSA o gwbl.
RSA o gwbl. [Chwerthin]
O gwbl.