[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. Koska yksityinen avain on pidettävä salassa ja vain yksityisen avaimen voidaan purkaa viestejä, jos 2 käyttäjät haluavat lähettää viestejä salataan RSA edestakaisin molemmat 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älle 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 kuin symmetrisen avaimen algoritmia. 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 kenenkään kanssa 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. Koska yksityinen avain on pidettävä salassa 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.