[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Harvardin yliopisto]
[Tämä on CS50.] [CS50.TV]
Katsotaanpa katsomaan RSA, laajalti käytetty algoritmi salaamalla tietoja.
Salausalgoritmeja kuten Caesar ja Vigenère ciphers eivät ole kovin turvallinen.
Kanssa Caesar cipher, hyökkääjä tarvitsee vain kokeilla 25 eri avaimet
saada viestin pelkkänä tekstinä.
Vaikka Vigenère cipher on turvallisempi kuin Caesar cipher
koska suurempi hakualue avaimia, kun hyökkääjä
tuntee avaimen pituus on Vigenère salakirjoituksen,
mikä voidaan määrittää kautta analyysi kuvioita salattu teksti,
Vigenère cipher ei ole niin paljon turvallisempi kuin Caesar cipher.
RSA, toisaalta, ei ole alttiina hyökkäyksille kuin tämä.
Caesar cipher ja Vigenère salaus käyttävät samaa avainta
sekä salata ja purkaa viestin.
Tämä ominaisuus tekee näistä ciphers symmetrisen avaimen algoritmit.
Perustavanlaatuinen ongelma symmetrisen avaimen algoritmit
on, että ne nojaavat yhden salauksen ja lähettää viestin
ja yksi vastaanottava ja purkaa viestin
pitänyt jo sopineet etukäteen keskeisistä ne molemmat käyttävät.
Mutta meillä on hieman käynnistyksen ongelma.
Miten 2 tietokonetta, jotka haluavat kommunikoida perustaa salainen avain niiden välillä?
Jos avain on salainen, niin meidän tapa salata ja purkaa avain.
Jos kaikki meillä on symmetrinen avaimen salausta
Sitten olemme vain palata samaan ongelmaan.
RSA, toisaalta, käyttää kahta avainta,
yksi salaus ja toinen salauksen.
Yksi on nimeltään julkisen avaimen, ja toinen on yksityinen avain.
Julkista avainta käytetään viestien salaamiseen.
Kuten ehkä arvata sen nimen, voimme jakaa julkisen avaimen
kukaan haluamme vaarantamatta turvallisuutta salatun viestin.
Viestit salataan julkisen avaimen
salaus voidaan purkaa vain sen vastaavan yksityisen avaimen.
Vaikka voit jakaa julkisen avaimen, sinun tulisi aina pitää yksityisen avaimen salainen.
ja ainoastaan ​​yksityinen avain voidaan purkaa viestejä
jos 2 käyttäjät haluavat lähettää viestejä salattu RSA
edestakaisin molempien käyttäjät tarvitsevat oman julkisen ja yksityisen avaimen parin.
Viestejä käyttäjältä 1 käyttäjälle 2
käyttää ainoastaan ​​käyttäjän 2: n avainpari, ja viestejä käyttäjältä 2 käyttäjä 1
käyttää vain käyttäjän 1: n avainpari.
Se seikka, että on olemassa 2 erillisiä näppäimiä salata ja purkaa viestien
tekee RSA epäsymmetrisen avaimen algoritmilla.
Meidän ei tarvitse salata julkisen avaimen, jotta voit lähettää sen toiseen tietokoneeseen
koska avain on julkinen muutenkin.
Tämä tarkoittaa, että RSA ei ole sama käynnistys ongelma
kuten symmetrisen avaimen algoritmit.
Joten jos haluan lähettää viestin RSA salausta
ryöstää, minä ensin Rob julkisen avaimen.
Voit luoda avainpari, Rob tarvitsee valita 2 isoa alkulukuja.
Nämä numerot käyttää sekä julkisia ja yksityisiä avaimia,
mutta julkisen avaimen käyttää vain tuotteen näiden 2 numerot,
ei numerot itse.
Kun olen salataan viestin Rob julkisen avaimen
Voin lähettää viestin Rob.
Saat tietokoneen, factoring numeroita on vaikea ongelma.
Julkinen avain, muista, käytetty tuote 2 alkuluvut.
Tämä tuote on sitten vain 2 tekijöitä,
jotka sattuvat olemaan numeroita, jotka muodostavat yksityisen avaimen.
Jotta viestin salausta, RSA käyttää tätä yksityistä avainta
tai numerot kerrotaan yhdessä luomassa julkisen avaimen.
Koska se on laskennallisesti vaikeaa tekijä numero
käytetään julkisen avaimen 2 numeroita käytetään yksityisen avaimen
se on vaikeaa hyökkääjä selvittää yksityisen avaimen
että on tarpeen purkaa viestin.
Mennäänpä johonkin alhaisempi yksityiskohtia RSA.
Katsotaanpa ensin katsoa, ​​miten voimme luoda avainpari.
Ensinnäkin, me tarvitsemme 2 alkulukuja.
Me kutsumme näitä 2 numeroiden p ja q.
Jotta voit noutaa p ja q, käytännössä olisimme näennäissatunnaisesti tuottaa
suuria määriä ja käyttää sitten testi sille, onko vai ei
nämä luvut ovat todennäköisesti prime.
Voimme pitää tuottaa satunnaisia ​​numeroita uudestaan ​​ja uudestaan
kunnes meillä on 2 alkulukuja, että voimme käyttää.
Täällä mennään valita p = 23 ja q = 43.
Muista, käytännössä, p ja q pitäisi olla paljon suurempia määriä.
Sikäli kuin tiedämme, suuremmat numerot, sitä vaikeampaa on
murtaa salatun viestin.
Mutta se on myös kalliimpaa salata ja purkaa viestejä.
Nykyään se on usein suositeltavaa, että p ja q ovat vähintään 1024 bittiä,
mikä asettaa kunkin numeron yli 300 desimaalia.
Mutta me valita näiden pienien tässä esimerkissä.
Nyt me kerrotaan p ja q yhdessä saada kolmas numero,
jonka me kutsumme n.
Meidän tapauksessamme, n = 23 * 43, joka = 989.
Olemme N = 989.
Seuraavaksi me kerrotaan p - 1, q - 1
saada neljäs numero, joka soitamme m..
Meidän tapauksessamme, m = 22 * ​​42, joka = 924.
Meillä on m = 924.
Nyt me tarvitsemme useita e, joka on suhteellisen prime M
ja vähemmän kuin m.
Kaksi numeroa ovat suhteellisen prime tai keskenään jaottomia
jos ainoa positiivinen kokonaisluku, joka jakaa molemmat tasaisesti on 1.
Toisin sanoen suurin yhteinen tekijä e: n ja m:
on oltava 1.
Käytännössä on yleistä, että e on alkuluku 65537
niin kauan kuin tämä määrä ei tapahdu olla tekijä, m.
Meidän avaimet, me valita e = 5
koska 5 on suhteellisen prime on 924.
Lopuksi, me tarvitsemme yhden numero, jonka me kutsumme d.
D on oltava jokin arvo, joka täyttää yhtälön de = 1 (mod m).
Tämä mod m merkitsee käytämme jotain kutsutaan modulaarinen aritmeettinen.
Vuonna modulaarinen aritmeettinen, kun joukko saa ylittää joidenkin yläraja
se kääri takaisin noin 0.
Kello, esimerkiksi käyttää modulaarinen aritmetiikka.
Yksi minuutti sen jälkeen 1:59, esimerkiksi, on 02:00,
ei 1:60.
Minuuttiosoitin on kiedottu 0
päästyään yläraja 60.
Niin, voimme sanoa, 60 vastaa 0 (mod 60)
ja 125 vastaa 65 vastaa 5 (mod 60).
Meidän julkinen avain tulee olemaan pari e ja n
jossa tässä tapauksessa e on 5 ja n on 989.
Meidän yksityinen avain on pari d ja n,
joka tässä tapauksessa on 185 ja 989.
Huomaa, että alkuperäinen alkulukuja p ja q eivät näy
missä meidän yksityisten tai julkisten avaimia.
Nyt meillä on avainpari, katsotaanpa katsomaan miten voimme salata
ja purkaa viestin.
Haluan lähettää viestin Rob,
joten hän tulee olemaan yksi tuottaa tämän avainparin.
Sitten kysyn Rob hänen julkisen avaimen, jonka minä käytän
salata viestin lähettää hänelle.
Muista, se on täysin kunnossa Rob jakaa hänen julkisen avaimen minulle.
Mutta se ei olisi kunnossa jakaa hänen yksityinen avain.
Minulla ei ole mitään käsitystä siitä, mitä hänen yksityinen avain on.
Voimme rikkoa meidän viestimme m useiksi paloiksi
kaikki pienempi kuin n, ja sitten salata kunkin paloina.
Me salaa merkkijono CS50, jonka voimme hajota 4 paloina,
yksi per kirjain.
Jotta salata minun viestini, minun täytyy muuntaa se
jonkinlainen numeerinen edustus.
Katsotaanpa liität ASCII arvot merkkiä viestini.
Jotta salata tietty viesti m
Minun täytyy laskea c = m e (mod n).
Mutta m on oltava pienempi kuin n,
tai sitten koko viesti ei voida ilmaista modulo n.
Voimme murtaa m useiksi paloina, jotka kaikki ovat pienempiä kuin n,
ja salata kunkin paloina.
Salaaminen jokainen paloina, saamme c1 = 67 5 (mod 989)
mikä = 658.
Meidän toinen murikka meillä 83 5 (mod 989)
jossa = 15.
Sillä meidän kolmas murikka meillä 53 5 (mod 989)
mikä = 799.
Ja lopuksi, meidän viimeinen murikka meillä 48 5 (mod 989)
mikä = 975.
Nyt voimme lähettää näinä salatun arvot Rob.
Tässä, Rob.
Vaikka meidän viestimme on lento, mennään katsomaan uudelleen
miten saimme tämän arvon d.
Meidän numero d täyttämiseksi tarvittavat 5D = 1 (mod 924).
Tämä tekee d kerrottava käänteisluku 5 modulo 924.
Annettu 2 kokonaislukuja, a ja b, laajennetun euklidisen algoritmin
voidaan käyttää löytämään suurin yhteinen tekijä näiden 2 kokonaislukuja.
Se myös antaa meille 2 muut numerot, x ja y,
, jotka täyttävät yhtälön ax + by = suurin yhteinen tekijä a ja b.
Miten tämä auttaa meitä?
No, kytkemällä e = 5
ja m = 924 b:
me jo tiedämme, että nämä luvut ovat keskenään jaottomia.
Heidän suurin yhteinen tekijä on 1.
Tämä antaa meille 5x + 924y = 1
tai 5x = 1 - 924y.
Mutta jos me vain välitä kaikesta modulo 924
voimme pudota - 924y.
Muistele kelloa.
Jos minuutti käsi on 1 ja sitten tasan 10 tunnin kuluessa,
tiedämme minuutti käsi yhä olla 1.
Täällä alkaa klo 1 ja sitten kietoa tarkalleen y kertaa,
niin me vielä olla 1.
Meillä on 5x = 1 (mod 924).
Ja tässä tämä x on sama kuin d odotimme ennen,
joten jos käytämme laajennetun Eukleideen algoritmi
saat tämän määrän x, joka on määrä meidän pitäisi käyttää meidän d.
Nyt ajaa laajennettu Eukleideen algoritmi = 5
ja b = 924.
Käytämme menetelmää, jota kutsutaan taulukossa menetelmällä.
Meidän pöytä on 4 sarakkeet, x, y, d, ja k.
Meidän pöytä alkaa 2 krs.
Ensimmäisen rivin meillä on 1, 0, silloin arvo, joka on 5,
ja meidän toinen rivi on 0, 1, ja meidän arvo b, joka on 924.
Arvo neljäs sarake, k, on seurausta
jakamalla arvo d rivin yläpuolella sen arvo d
samalla rivillä.
Meillä on 5 jaettuna 924 on 0 joidenkin loput.
Tämä tarkoittaa, että meillä on k = 0.
Nyt arvo joka toinen solu tulee olemaan arvo solun 2 riviä sen yläpuolella
miinus arvo rivin yläpuolella kertaa k.
Aloitetaan d 3. krs.
Meillä on 5-924 * 0 = 5.
Seuraavaksi meillä on 0-1 * 0 on 0
ja 1-0 * 0, joka on 1.
Ei liian paha, joten katsotaanpa siirtyä seuraavalle riville.
Ensin meidän arvomme k.
924 jaettuna 5 = 184 joidenkin loput
joten meidän arvo k 184.
Nyt 924-5 * 184 = 4.
1-0 * 184 on 1 ja 0-1 * 184 on -184.
Selvä, tehdään seuraavan rivin.
Meidän k: n arvo on 1, koska
5 jaettuna 4 = 1 joitakin jäljellä.
Katsotaanpa täyttää muihin sarakkeisiin.
5-4 * 1 = 1.
0-1 * 1 = -1.
Ja 1-184 * 1 185.
Katsotaan mitä seuraavaksi k arvo olisi.
No, näyttää siltä, ​​meillä on 4 jaettuna 1, joka on 4.
Tässä tapauksessa olemme jakamalla 1 siten, että k on yhtä kuin
d: n arvo edellä rivin tarkoittaa sitä, että olemme tehneet kanssa algoritmi.
Voimme nähdä, tässä, että meillä on x = 185 ja y = -1 viimeisellä rivillä.
Katsotaanpa nyt palata meidän alkuperäinen tavoite.
Sanoimme, että arvo x seurauksena käynnissä tämän algoritmin
olisi kerrottava käänteisluku (mod b).
Tämä tarkoittaa, että 185 on kerrottava käänteisluku 5 (mod 924)
mikä tarkoittaa, että meillä on arvo 185 d.
Siitä, että d = 1 viimeisellä rivillä
varmistaa, että e on keskenään jaottomia m: ään.
Jos se ei ole 1, niin meillä olisi valita uuden sähköpostiviestin.
Nyt katsotaanpas jos Rob on saanut viestin.
Kun joku lähettää minulle salattu viesti
niin kauan kuin olen pidin yksityisen avaimen salaisuus
Olen ainoa, joka voi purkaa viestin.
Purkaa murikka c voin laskea alkuperäisen viestin
on yhtä suuri kuin palan ja d teho (mod n).
Muista, että d ja n ovat minun yksityinen avain.
Saadaksesi täyden viestin sen paloina me purkaa kunkin murikka
ja liität tuloksia.
Kuinka turvallinen on RSA?
Totuus on, emme tiedä.
Turvallisuus perustuu siihen, kuinka kauan kestäisi hyökkääjä murtaa viestiin
salataan RSA.
Muista, että hyökkääjä pääsee käsiksi julkisen avaimen,
joka sisältää sekä E ja N.
Jos hyökkääjä onnistuu tekijä n osaksi 2 alkulukuja, p ja q,
Sitten hän voisi laskea d käyttäen laajennettua Eukleideen algoritmi.
Tämä antaa hänelle yksityisen avaimen, jota voidaan käyttää purkaa viestin.
Mutta kuinka nopeasti voimme tekijä kokonaislukuja?
Jälleen, emme tiedä.
Kukaan ei ole löytänyt nopea tapa tehdä se,
mikä tarkoittaa, että annetaan riittävän suuri n
kestäisi hyökkääjä epärealistisen pitkä
tekijään numero.
Jos joku paljasti nopea tapa factoring kokonaislukujen
RSA olisi rikki.
Mutta vaikka kokonaisluku tekijöihinjakoalgoritmi on luonnostaan ​​hidasta
RSA algoritmi voi silti olla joitakin virhe siinä
, joka mahdollistaa helpon salauksen purkaminen viestejä.
Kukaan ei ole löytänyt, ja havaittiin niin vika vielä,
mutta se ei tarkoita sellaista ei ole.
Teoriassa joku voisi olla siellä lukee kaikki tiedot salataan RSA.
On toinenkin vähän yksityisyyttä kysymys.
Jos Tommy salaa joitakin viestin minun julkisen avaimen
ja hyökkääjä salaa saman viestin minun julkisen avaimen
hyökkääjä näkee että 2 viestit ovat identtiset
ja siten tietämään, mitä Tommy salataan.
Estämiseksi tämän viestit ovat tyypillisesti pehmustettu satunnaisia ​​bittejä
ennen salataan niin, että sama viesti salataan
useita kertoja näyttää erilaiselta niin kauan kuin pehmusteet sanoma on erilainen.
Mutta muista, miten meidän on jakaa viestejä järkäle
siten, että kukin pala on pienempi kuin n?
Pehmusteet paloina tarkoittaa, että meillä olisi jakaa asioita
vielä enemmän paloina koska pehmustettu murikka on oltava pienempi kuin n.
Salaus ja salauksen purku ovat suhteellisen kalliita RSA,
ja niin tarvitsee rikkoa jopa viestin useisiin palasiin voi olla hyvin kallista.
Jos suuri määrä tietoja on oltava salataan ja salaus puretaan
voimme yhdistää edut symmetrisen avaimen algoritmit
kanssa RSA saada sekä turvallisuutta ja tehokkuutta.
Vaikka emme aio mennä sitä täällä,
AES on symmetrinen avain algoritmi Vigenère ja Caesar ciphers
mutta paljon vaikeampi murtaa.
Tietenkään emme voi käyttää AES perustamatta jaetun salaisen avaimen
välillä 2 järjestelmiä, ja näimme ongelma, että ennen.
Mutta nyt voimme käyttää RSA luoda jaetun salaisen avaimen välillä 2 järjestelmiä.
Soitamme tietokone lähettää tiedot lähettäjän
ja tietokone vastaanottaa dataa vastaanottimen.
Vastaanottimessa on RSA-avainparin ja lähettää
julkisen avaimen lähettäjälle.
Lähettäjän muodostaa AES-avaimella,
salaa sen vastaanottajan RSA julkisen avaimen,
ja lähettää AES-avaimella vastaanottimeen.
Vastaanotin purkaa viestin salauksen ja sen RSA: n salaisen avaimen.
Sekä lähettäjän että vastaanottajan on nyt jaettu AES-avaimella niiden välillä.
AES, joka on paljon nopeampi salaus ja salauksen kuin RSA,
voidaan nyt käyttää salaamiseen suuria tietomääriä ja lähettää ne vastaanotin,
kuka voi purkaa käyttämällä samaa avainta.
AES, joka on paljon nopeampi salaus ja salauksen kuin RSA,
voidaan nyt käyttää salaamiseen suuria tietomääriä ja lähettää ne vastaanotin,
kuka voi purkaa käyttämällä samaa avainta.
Me vain tarvitaan RSA siirtää jaetun avaimen.
Meidän ei enää tarvitse käyttää RSA lainkaan.
Se näyttää minulla viestin.
Sillä ei ole väliä, jos joku lukea mitä on paperilennokki ennen sain sen
koska olen ainoa yksityisen avaimen.
Katsotaanpa purkaa jokaisen paloina viestin.
Ensimmäinen kimpale, 658, me korottaa d voima, joka on 185,
mod n, joka on 989, on yhtä suuri kuin 67,
joka on kirjain C ASCII.
Nyt päälle toinen murikka.
Toinen pala on arvo 15,
jonka me nostamme sen 185th valtaa,
mod 989, ja tämä on yhtä suuri kuin 83
joka on kirjain S ASCII.
Nyt kolmannen palan, jonka arvo on 799, me korottaa 185,
mod 989, ja tämä on yhtä suuri kuin 53,
joka on arvo merkin 5 ASCII-muodossa.
Nyt viimeisen palan, jonka arvo on 975,
keräämme 185, mod 989,
ja tämä on yhtä suuri kuin 48, joka on arvo merkki 0 ASCII-muodossa.
Nimeni on Rob Bowden, ja tämä on CS50.
[CS50.TV]
RSA lainkaan.
RSA lainkaan. [Naurua]
Ollenkaan.