[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Harvard Universiteit]
[Hierdie is CS50.] [CS50.TV]
Kom ons neem 'n blik op die RSA, 'n wyd gebruik word algoritme vir die versleutelen van data.
Enkripsie-algoritmes soos Caesar en Vigenère getalle is nie baie veilig is.
Met die keiser cipher, 'n aanvaller moet slegs 25 verskillende sleutels om te probeer
die boodskap se gewone teks te kry.
Terwyl die Vigenère cipher is meer veilig as die keiser cipher
as gevolg van die groter search ruimte vir sleutels, een keer 'n aanvaller
ken die lengte van die sleutel in 'n Vigenère cipher,
wat bepaal kan word deur middel van 'n analise van patrone in die geïnkripteer teks,
die Vigenère cipher is nie veel meer veilig as die keiser cipher.
RSA, aan die ander kant, is nie kwesbaar vir aanvalle soos hierdie.
Die keiser cipher en Vigenère cipher gebruik dieselfde sleutel
aan beide enkripteer en dekripteer 'n boodskap.
Hierdie eienskap maak die getalle simmetriese sleutel algoritmes.
'N fundamentele probleem met simmetriese sleutel algoritmes
is dat hulle staatmaak op die een versleuteling en die stuur van die boodskap
en die een wat die boodskap ontvang en decrypten
reeds ooreengekom vooraf op die sleutel sal hulle albei gebruik.
Maar ons het 'n bietjie van 'n opstart probleem hier.
Hoe vestig 2 rekenaars wat wil om te kommunikeer nie 'n geheime sleutel tussen hulle?
As die sleutel geheim moet wees, dan moet ons 'n manier om te enkripteer en dekripteer die sleutel.
As alles wat ons het is 'n simmetriese sleutel kriptografie
dan het ons kom nou net terug na dieselfde probleem.
RSA, aan die ander kant, maak gebruik van 'n paar van die sleutels,
een vir enkripsie en 'n ander vir dekripsie.
Een daarvan is die openbare sleutel genoem, en die ander is die private sleutel.
Die publieke sleutel word gebruik om boodskappe te enkripteer.
As jy dalk raai deur sy naam, kan ons ons publieke sleutel deel met
iemand wat ons wil sonder om die sekuriteit van 'n geïnkripteer boodskap.
Boodskappe geïnkripteer met behulp van 'n publieke sleutel
kan slegs Ontcijferde met sy ooreenstemmende private sleutel.
Terwyl jy kan deel jou publieke sleutel, moet jy altyd jou private sleutel geheim hou.
en slegs die private sleutel kan gebruik word om te decrypt boodskappe
as 2 gebruikers wil boodskappe stuur geïnkripteer met RSA
heen en weer beide gebruikers nodig het om hul eie openbare en private sleutel paar te hê.
Boodskappe van gebruiker 1 na gebruiker 2
gebruik slegs gebruiker 2 se sleutel paar, en boodskappe van gebruiker 2 na gebruiker 1
gebruik slegs gebruiker 1 se sleutel paar.
Die feit dat daar is 2 aparte sleutels te enkripteer en decrypt boodskappe
maak RSA 'n asimmetriese sleutel algoritme.
Ons hoef nie die publieke sleutel enkripteer ten einde dit te stuur na 'n ander rekenaar
aangesien die sleutel is om die openbare elk geval.
Dit beteken dat die RSA nie dieselfde opstart probleem
as die simmetriese sleutel algoritmes.
So as ek wil 'n boodskap te stuur met RSA-enkripsie
te beroof, sal ek eers Rob se publieke sleutel.
'N paar sleutels te genereer, Rob 2 groot priemgetalle te kies.
Hierdie getalle sal gebruik word in beide die openbare en private sleutels,
maar die publieke sleutel sal slegs gebruik die produk van dié 2 getalle,
nie die getalle self.
Sodra ek die boodskap het geïnkripteer met behulp van Rob se publieke sleutel
Ek kan stuur die boodskap aan Rob.
Vir 'n rekenaar, factoring nommers is 'n harde probleem.
Die publieke sleutel, onthou, gebruik die produk van 2 priemgetalle.
Hierdie produk moet dan net 2 faktore,
wat gebeur met die getalle wat die private sleutel.
Ten einde die boodskap dekripteer, sal die RSA gebruik om hierdie private sleutel
of die getalle met mekaar vermenigvuldig word in die proses van die skep van die publieke sleutel.
Want dit is computationeel moeilik om die nommer aan 'n faktorontleding
wat gebruik word in 'n publieke sleutel in die 2 getalle wat gebruik word in die private sleutel
dit is moeilik vir 'n aanvaller die private sleutel om uit te vind
wat nodig sal wees om die boodskap te dekripteer.
Nou, laat ons gaan in 'n laer vlak besonderhede van die RSA.
Laat ons eers sien hoe ons kan 'n paar sleutels te genereer.
Eerstens, moet ons 2 priemgetalle.
Ons noem hierdie 2 getalle p en q.
Ten einde op te tel P en Q, in die praktyk sou ons pseudorandomly genereer
groot getalle en gebruik dan 'n toets om te bepaal of
die getalle is waarskynlik prima.
Ons kan aanhou om ewekansige getalle te genereer oor en oor weer
totdat ons het 2 primes wat ons kan gebruik.
Hier laat haal p = 23 en q = 43.
Onthou, in die praktyk, behoort p en q veel groter getalle.
Sover ons weet, hoe groter die nommers, hoe moeiliker is dit
'n geïnkripteer boodskap te kraak.
Maar dit is ook duurder om te Encrypt en decrypt boodskappe.
Vandag is dit dikwels aanbeveel dat P en Q is ten minste 1024 stukkies,
wat sit elke getal op meer as 300 desimale syfers.
Maar ons sal hierdie klein getalle kies vir hierdie voorbeeld.
Nou sal ons vermenigvuldig p en q saam 'n 3de nommer te kry,
wat ons sal noem.
In ons geval, n = 23 * 43, wat = 989.
Ons het N = 989.
Volgende sal ons vermenigvuldig p - 1 met q - 1
'n 4de nommer, wat ons noem m te verkry.
In ons geval, m = 22 * ​​42, wat = 924.
Ons het m = 924.
Nou sal ons moet 'n aantal e wat relatief priem is m
en minder as m.
Twee getalle relatief priem is of coprime
as die enigste positiewe heelgetal wat gesplitste hulle albei eweredig is 1.
Met ander woorde, die grootste gemene deler van e en m
moet wees 1.
In die praktyk, is dit algemeen vir e die priemgetal 65.537
so lank as wat hierdie getal nie gebeur met 'n faktor van m.
Vir ons sleutels, sal ons kies e = 5
sedert 5 is relatief priem tot 924.
Ten slotte, moet ons nog een nommer, wat ons noem d.
D moet 'n waarde wat die vergelyking bevredig de = 1 (mod m).
Hierdie mod m gee te kenne dat ons sal iets genoem modulêre rekenkunde gebruik.
In modulêre rekenkunde, kry een keer 'n aantal hoër as sommige bogrens
sal dit om terug te draai na 0.
'N klok, byvoorbeeld, modulêre rekenkunde gebruik.
Een minuut na 01:59, byvoorbeeld, is 02:00,
nie 1:60.
Die minuut hand toegedraai rondom 0
op die bereiking van 'n bogrens van 60.
Dus, kan ons sê 60 is gelyk aan 0 (mod 60)
en 125 is gelykstaande aan 65 is gelykstaande aan 5 (mod 60).
Ons publieke sleutel sal die paar e en n
waar in hierdie geval e is 5 en n 989.
Ons private sleutel sal wees om die paar D en N,
wat in ons geval is 185 en 989.
Let daarop dat ons oorspronklike primes p en q nie vertoon
oral in ons privaat-of openbare sleutels.
Nou dat ons ons paar sleutels, Kom ons neem 'n blik op hoe ons kan enkripteer
en decrypt 'n boodskap.
Ek wil 'n boodskap te stuur na Rob,
sodat hy sal die een hierdie sleutel paar te genereer.
Dan sal ek vra Rob vir sy publieke sleutel, wat ek sal gebruik
'n boodskap te stuur aan hom te enkripteer.
Onthou, dit is heeltemal goed vir Rob sy publieke sleutel met my te deel.
Maar dit sou nie oukei wees sy private sleutel te deel.
Ek het nie 'n idee wat sy private sleutel is.
Ons kan ons boodskap m breek in verskeie stukke
alle kleiner is as n en dan enkripteer elkeen van daardie stukke.
Ons sal enkripteer die string CS50, wat ons kan breek in 4 stukke,
een per brief.
In om my boodskap te enkripteer, sal ek nodig het om dit te omskep in '
'n soort van numeriese verteenwoordiging.
Kom ons koppel die ASCII-waardes met die karakters in my boodskap.
Ten einde 'n bepaalde boodskap m te enkripteer
Ek sal c = m na die e (mod n) te bereken.
Maar m moet kleiner wees as n,
of anders sal die volle boodskap kan nie uitgedruk word modulo n.
Ons kan breek m in verskeie stukke, wat almal kleiner is as n,
en elkeen van daardie stukke enkripteer.
Enkripteer van elk van hierdie stukke, kry ons c1 = 67 aan die 5 (mod 989)
wat = 658.
Vir ons tweede stuk het ons 83 tot die 5 (mod 989)
wat = 15.
Vir ons derde stuk het ons 53 tot die 5 (mod 989)
wat = 799.
En ten slotte, vir ons laaste stuk het ons 48 tot die 5 (mod 989)
wat = 975.
Nou het ons kan stuur oor hierdie geïnkripteer waardes na Rob.
Hier gaan jy, Rob.
Terwyl ons boodskap in vlug is, laat ons kyk weer na
hoe ons het dat waarde vir d.
Ons nommer d nodig 5d = 1 (mod 924) te voldoen.
Dit maak d die multiplikatiewe inverse van 5 modulo 924.
Gegewe 2 heelgetalle, a en b, die uitgebreide Euklidiese algoritme
kan gebruik word om die grootste gemene deler van hierdie 2 heelgetalle te vind.
Dit sal ook ons ​​2 ander getalle, x en y,
wat voldoen aan die vergelyking ax + by = die grootste gemene deler van a en b.
Hoe dit ons help?
Wel, steek in e = 5 vir 'n
en m = 924 vir b
ons reeds weet dat hierdie getalle coprime is.
Hul grootste gemene deler is 1.
Dit gee ons 5x + 924y = 1
of 5x = 1 - 924y.
Maar as ons net sorg oor alles modulo 924
dan kan ons drop die 924y.
Dink terug aan die klok.
As die minuut hand is op 1 en dan presies 10 uur slaag,
ons weet die minuut hand nog sal wees op die 1.
Hier het ons begin op 1 en dan draai om presies y tye,
so ons sal nog steeds by 1.
Ons het 'n 5x = 1 (mod 924).
En hier x is dieselfde as die d wat ons is op soek na voor,
so as ons die uitgebreide Euklidiese algoritme
hierdie getal x te kry, dit is die getal wat ons moet gebruik as ons d.
Laat ons nou loop die uitgebreide Euklidiese algoritme vir 'n = 5
en b = 924.
Ons sal gebruik maak van 'n metode om die tabel-metode genoem.
Ons tafel 4 kolomme, x, y, d, en k sal hê.
Ons tafel begin af met 2 rye.
Ons het in die eerste ry 1, 0, dan is ons waarde van a, wat 5,
en ons tweede ry is 0, 1 en ons waarde vir b, wat is 924.
Die waarde van die 4de kolom, k, sal die gevolg wees
die verdeling van die waarde van d in die ry bo dit met die waarde van d
op dieselfde ry.
Ons het 5 gedeel deur 924 0 met 'n paar res.
Dit beteken dat ons k = 0.
Nou is die waarde van elke ander sel sal die waarde van die sel 2 rye bokant dit wees
minus die waarde van die ry bokant dit keer k.
Kom ons begin met d in die 3de ry.
Ons het 5-924 * 0 = 5.
Volgende het ons 0 - 1 * 0 wat 0
en 1 - 0 * 0 wat 1.
Nie te sleg nie, so laat ons beweeg op na die volgende ry.
Eerstens moet ons ons waarde van k.
924 gedeel deur 5 = 184 met 'n paar res,
sodat ons waarde vir k is 184.
Nou 924 - 5 * 184 = 4.
1 - 0 * 184 is 1 en 0 - 1 * 184 is -184.
Alle reg, laat ons doen die volgende ry.
Ons waarde van k sal 1 omdat
5 4 = 1 gedeel deur met 'n paar res.
Kom ons vul in die ander kolomme.
5 - 4 * 1 = 1.
0 - 1 * 1 = -1.
En 1 184 * 1 185.
Kom ons kyk wat ons volgende waarde van k sou wees.
Wel, dit lyk asof ons 4 gedeel deur 1, wat is 4.
So dat k in hierdie geval waar ons deel deur 1 is gelyk aan
die waarde van d in die bogenoemde ry beteken dat ons klaar is met ons algoritme.
Ons kan hier sien dat ons x = 185 en y = -1 in die laaste ry.
Kom ons kom nou terug na ons oorspronklike doel.
Ons het gesê dat die waarde van x as 'n gevolg van die uitvoer van hierdie algoritme
die multiplikatiewe inverse van 'n (mod b).
Dit beteken dat 185 is die multiplikatiewe inverse van 5 (mod 924)
wat beteken dat ons 'n waarde van 185 vir d.
Die feit dat d = 1 in die laaste ry
verifieer dat die e is coprime na m.
As dit nie was 1 dan sou ons 'n nuwe e te kies.
Nou laat ons kyk of Rob my boodskap ontvang het.
Wanneer iemand stuur vir my 'n geënkripteerde boodskap
so lank as wat ek my private sleutel bewaar 'n geheim
Ek is die enigste een wat kan dekripteer die boodskap.
Te dekripteer 'n stuk c Ek kan die oorspronklike boodskap bereken
is gelyk aan die stuk d krag (mod n).
Onthou dat D en N is van my private sleutel.
'N volledige boodskap te kry van sy stukke wat ons dekripteer elke stuk
en koppel die resultate.
Presies hoe veilig is die RSA?
Die waarheid is, weet ons nie.
Security is gebaseer op hoe lank dit sou 'n aanvaller 'n boodskap neem om te kraak
geïnkripteer met RSA.
Onthou dat 'n aanvaller het toegang tot jou publieke sleutel,
waarin beide e en n.
Indien die aanvaller bestuur n faktor in sy 2 primes, P en Q,
dan het sy d kon bereken deur gebruik te maak van die uitgebreide Euklidiese algoritme.
Dit gee haar die private sleutel wat kan dekripteer wat gebruik word om enige boodskap.
Maar hoe vinnig kan ons heelgetalle faktor?
Weereens, weet ons nie.
Niemand het 'n vinnige manier om dit te doen,
wat beteken dat, gegee wat groot genoeg is n
dit sou 'n aanvaller onrealisties lank neem
die nommer aan 'n faktorontleding.
As iemand 'n vinnige manier van factoring heelgetalle geopenbaar
RSA sal gebreek word nie.
Maar selfs as integer faktorisering is inherent stadig
die RSA-algoritme kan nog 'n fout in die
wat voorsiening maak vir maklike dekripsie van die boodskappe.
Niemand is gevind en openbaar so 'n fout nie,
maar dit beteken nie dat 'n mens nie bestaan ​​nie.
In teorie, kan iemand uit die lees van alle data geïnkripteer met RSA.
Daar is nog 'n bietjie van 'n privaatheid probleem.
As Tommy codeert 'n boodskap met my publieke sleutel
en 'n aanvaller versleutelt die dieselfde boodskap met my publieke sleutel
die aanvaller sal sien dat die 2 boodskappe is identies
en dus weet wat Tommy geïnkripteer.
Ten einde dit te voorkom, is tipies boodskappe bepolsterd met random stukkies
voordat dit geïnkripteer sodat dieselfde boodskap geïnkripteer
verskeie kere so lank sal anders lyk as die padding op die boodskap is anders.
Maar onthou hoe ons boodskappe in stukke te verdeel
sodat elke stuk kleiner is as n?
Padding die stukke beteken dat ons kan hê om dinge te verdeel
in selfs meer stukke sedert die opgestopte stuk moet wees kleiner as n.
Enkripsie en dekripsie is relatief duur met RSA,
en so hoef te breek 'n boodskap in baie stukke kan baie duur wees.
As 'n groot volume van data moet word geïnkripteer en Ontcijferde
ons kan kombineer die voordele van die simmetriese sleutel algoritmes
met dié van die RSA beide veiligheid en doeltreffendheid te kry.
Alhoewel ons sal hier nie inkom nie,
AES is 'n simmetriese sleutel algoritme soos die Vigenère en Caesar getalle
maar baie moeiliker om te kraak.
Van die kursus, kan ons nie gebruik AES sonder die stigting van 'n gedeelde geheime sleutel
tussen die 2 stelsels, en ons het die probleem met dit voor.
Maar nou is ons RSA die gedeelde geheime sleutel tussen die 2 stelsels kan gebruik om vas te stel.
Ons sal noem die rekenaar stuur van die data die sender
en die rekenaar die data ontvang die ontvanger.
Die ontvanger het 'n RSA sleutel paar en stuur
die publieke sleutel na die sender.
Die sender genereer 'n AES-sleutel,
versleutelt dit met die ontvanger se RSA publieke sleutel,
en stuur die AES sleutel tot die ontvanger.
Die ontvanger dekripteer die boodskap met die RSA private sleutel.
Beide die sender en die ontvanger het nou 'n gedeelde AES sleutel tussen hulle.
AES, wat is baie vinniger op enkripsie en dekripsie as RSA,
kan nou gebruik word om die groot volumes van data te enkripteer en stuur dit aan die ontvanger,
wat kan dekripteer deur gebruik te maak van die dieselfde sleutel.
AES, wat is baie vinniger op enkripsie en dekripsie as RSA,
kan nou gebruik word om die groot volumes van data te enkripteer en stuur dit aan die ontvanger,
wat kan dekripteer deur gebruik te maak van die dieselfde sleutel.
Ons het net nodig om die RSA die gedeelde sleutel te dra.
Ons hoef nie meer RSA te gebruik.
Dit lyk soos ek het 'n boodskap.
Dit maak nie saak as iemand lees wat op die papier vliegtuig is voordat ek dit gevang
want ek is die enigste een met die private sleutel.
Kom ons decrypt elk van die stukke in die boodskap.
Die eerste stuk, 658, samel ons die d krag, wat 185,
modulo n, wat 989, is gelyk aan 67,
wat is die letter C in ASCII.
Nou, op die tweede stuk.
Die tweede stuk waarde 15,
wat ons maak aan die 185 mag,
mod 989, en dit is gelyk aan 83
wat is die letter S in ASCII.
Nou vir die derde stuk, wat 'n waarde 799, ons verhoog tot 185,
mod 989, en dit is gelyk aan 53,
wat is die waarde van die karakter 5 in ASCII.
Nou vir die laaste stuk, wat 'n waarde 975,
ons verhoog tot 185, mod 989,
en dit is gelyk aan 48, wat is die waarde van die karakter 0 in ASCII.
My naam is Rob Bowden, en dit is CS50.
[CS50.TV]
RSA at all.
RSA at all. [Lag]
At all.