RSA-salausta (nimetty päässä alkukirjaimet kolmen keksijät) on algoritmi on epäsymmetrinen , on laajalti käytetty sähköistä kaupankäyntiä , ja yleisemmin vaihtaa luottamuksellisia tietoja Internetistä . Tämän algoritmin kuvailivat vuonna 1977 Ronald Rivest , Adi Shamir ja Leonard Adleman . RSA: n patentoi Massachusetts Institute of Technology (MIT) vuonna 1983 Yhdysvalloissa . Patentin voimassaolo päättyi 21. syyskuuta 2000.
Salaus RSA on epäsymmetrinen : se käyttää kahta avainta (kokonaislukuja), joka koostuu julkisen avaimen ja salata ja yksityisen avaimen varten salauksen luottamuksellisia tietoja. Molemmat avaimet on luonut henkilö, jonka usein nimeää sopimus Alice , joka haluaa luottamuksellisia tietoja. Alice tekee julkisen avaimen saataville. Tätä avainta käyttävät hänen kirjeenvaihtajansa ( Bob jne.) Salaamaan hänelle lähetetyt tiedot. Yksityinen avain on varattu Alicelle, ja sen avulla hän voi purkaa nämä tiedot. Alice voi käyttää yksityistä avainta myös allekirjoittamaan lähettämänsä tiedot, julkisen avaimen avulla kuka tahansa kirjeenvaihtajastaan voi tarkistaa allekirjoituksen.
Olennainen edellytys on, että salauksen salauksen purkaminen yksinomaan julkisella avaimella on "laskennallisesti mahdotonta", erityisesti yksityisen avaimen palauttaminen julkisesta avaimesta, toisin sanoen käytettävissä olevat laskentatavat ja tunnetut menetelmät vaihto (ja aika, jonka salaisuus on pidettävä) eivät salli tätä.
RSA-salausta käytetään usein symmetrisen salausavaimen kommunikointiin , mikä sallii vaihdon jatkamisen luottamuksellisesti: Bob lähettää Alicelle symmetrisen salausavaimen, jota Alice ja Bob voivat sitten käyttää tietojen vaihtamiseen.
Ronald Rivest, Adi Shamir ja Leonard Adleman julkaisivat salauksensa vuonna 1978 julkaisussa A Method for Digital Signatures and Public-Key Cryptosystems . He käyttävät kokonaislukujen ja Fermatin pienen lauseen yhtäläisyyksiä yksisuuntaisten toimintojen saamiseksi salaisella rikkomuksella (tai takaovella).
Kaikki laskelmat tehdään modulo kokonaisluku n, joka on kahden alkuluvun tulo . Fermat'n pieni lause on tärkeä rooli suunnittelussa salauksen.
Tyhjät ja salatut viestit ovat kokonaislukuja, jotka ovat pienempiä kuin kokonaisluku n . Salaus ja salauksen toiminnot koostuvat nostamaan viestin tiettyyn modulo n teho (tämä on modulaarinen potenssiin korotuksen toiminta ).
Pelkkä kuvaus matemaattisista periaatteista , joihin RSA-algoritmi perustuu, ei riitä. Sen käytännön toteutus vaatii muiden turvallisuuden kannalta välttämättömien asioiden huomioon ottamista. Esimerkiksi parin (yksityinen avain, julkinen avain) on luotava todella satunnaisella prosessilla, joka, vaikka se tiedetään, ei salli yksityisen avaimen uudelleen muodostamista. Salatun datan ei tulisi olla liian lyhyt, joten salauksen purku vaatii todella modulaarisen laskennan ja sitä on täydennettävä asianmukaisesti (esim. Optimaalinen epäsymmetrinen salauspehmuste ).
Avainten luomisen vaihe on Alicen vastuulla. Se ei puutu jokaiseen salaukseen, koska avaimet voidaan käyttää uudelleen. Ensimmäinen vaikeus, jota salaus ei ratkaise, on se, että Bob on varma siitä, että hänen hallussaan oleva julkinen avain on Alice. Avaimet uusitaan vain, jos yksityinen avain on vaarantunut, tai varotoimenpiteenä tietyn ajan kuluttua (joka voidaan laskea vuosina).
Koska e on alkuluku φ ( n ): llä, Bachet-Bézout-lauseen mukaan on olemassa kaksi kokonaislukua d ja k siten, että ed = 1 + k φ ( n ), toisin sanoen ed ≡ 1 (mod φ ( n ) ): e on todellakin käännettävä moduuli φ ( n ).
Koko edellisessä kappaleessa voimme käyttää Carmichaelin indikaattoria , joka jakaa φ ( n ) .
Pari ( n , e ) - tai ( e , n ) - on salauksen julkinen avain , kun taas sen yksityinen avain on numero d , tietäen, että salauksen purku edellyttää vain yksityistä avainta d ja kokonaislukua n , jonka tunnistaa julkinen avain (yksityinen avain määritellään joskus myös pariksi ( d , n ) tai tripletiksi ( p, q , d )).
Jos M on luonnollinen luku, joka on ehdottomasti pienempi kuin n, joka edustaa viestiä, salattua viestiä edustaa
jolloin luonnollinen luku C on ehdottomasti alle n .
Ja salakirjoituksen C , käytämme d , käänteinen e modulo ( p - 1) ( q - 1), ja löydämme tavallinen viesti M mukaan
Esimerkki pienistä alkuluvuista (käytännössä tarvitaan erittäin suuria alkulukuja):
Alicen julkinen avain on ( n , e ) = (33, 3) ja hänen yksityinen avain on ( n , d ) = (33, 7). Bob lähettää viestin Alicelle.
Mekanismi, jolla Alice allekirjoittaa yksityisen avaimensa avulla, on samanlainen vaihtamalla avaimet.
Todiste perustuu Fermatin pieneen lauseeseen , nimittäin siihen, että koska p ja q ovat kaksi alkulukua, meillä on ensimmäinen yhtälö, jos M ei ole p: n kerroin, ja toinen, jos se ei ole q : n monikerta :
Todellakin
Kulta
mikä tarkoittaa, että on olemassa kokonaisluku k sellainen, että
siksi, jos M ei ole p : n kerroin Fermatin pienen lauseen mukaan
ja vastaavasti, jos M ei ole q: n kerroin
Nämä kaksi yhtälöä saavutetaan itse asiassa mille tahansa kokonaisluvulle M , koska jos M on p: n kerroin , M ja kaikki sen nollasta poikkeavat tehot ovat yhtenevät 0 modulo p: n kanssa . Samoin q: lle .
Siksi kokonaisluku on p: n ja q: n , jotka ovat erilliset alkuluvut, kerrannaiset , siis niiden tulo pq = n (voimme nähdä sen seurauksena alkutekijöiksi hajoamisen ainutlaatuisuudesta tai suoremmin Gaussin lemmasta) , tietäen, että p ja q ovat ensisijaisia keskenään, ovat ensisijaisia ja erillisiä)
Näemme, että viestin salaus riittää tuntemaan e ja n . Toisaalta, purkamiseksi tarvitaan d ja n .
Laskea d käyttämällä e ja n , meidän on löydettävä modulaarinen käänteinen of e modulo ( p - 1) ( q - 1), jota emme voi tehdä tuntematta kokonaisluvut p ja q , eli hajoaminen n osaksi prime tekijät.
Salaus vaatii siis kykyä tarkistaa, että "erittäin suuret" luvut ovat alkulukuja, jotta voidaan löytää p ja q , mutta myös sitä, että näiden kahden erittäin suuren luvun tuloa ei ole käytännössä mahdollista jakaa tekijöihin. Tunnetut tehokkaat algoritmit, joiden avulla voidaan tarkistaa, että luku ei ole alkuluku, eivät tuota tekijöitä.
Arvo φ ( n ) on Eulerin indicatrix on n on ryhmän kertaluku on käännettävissä elementtien rengas ℤ / nℤ . Tämän ansiosta Eulerin lause ( Lagrangen lauseen seuraus ) voi nähdä heti, että jos M on alkuluku n: llä , on siten käännettävä (mikä pätee "useimpiin" luonnollisiin kokonaislukuihin M tarkasti alle n )
tai perustella RSA-salaus (sellaiselle M: lle ).
Osoittautuu, että kun n on erillisten alkioiden tulo, yhtälö pätee mihin tahansa M: ään (todiste on olennaisilta osiltaan yllä esitetty RSA: lle, erityistapauksessa, jossa n on kahden primaatin tulo).
Näppäinpari pyytää valitsemaan kaksi suurikokoista alkulukua, jotta niiden tuotteen laskeminen on laskennallisesti mahdotonta.
Suurikokoisen alkuluvun määrittämiseksi käytämme menetelmää, joka tarjoaa tarvittaessa satunnaisen parittoman kokonaisluvun, jonka koko on riittävä, primaattitestin avulla voidaan määrittää, onko se alkuluku vai ei, ja lopetamme heti, kun 'alkuluku saadaan. Alkulukulause varmistaa, että alkuluku löytyy jälkeen kohtuullisen yritysten lukumäärä.
Menetelmä vaatii kuitenkin erittäin nopean alkutestin. Käytännössä käytetään todennäköisyystestiä, Miller-Rabin-primaatiotestiä tai muunnosta. Tällainen testi ei takaa tarkalleen, että luku on ensisijainen, vaan vain (erittäin) suuren todennäköisyyden.
Vaaditut ominaisuudetEhkäistä tietoturvaloukkauksista, kaksi ensimmäistä numeroa ja päättäneet rakentaa avainpari on täytettävä seuraavat ominaisuudet:
Valitun eksponentin on todennettava seuraavat ominaisuudet:
Laskennassa ei ole mahdollista, että ensin lasketaan c d , sitten loput modulo n , koska se vaatisi käsittelyä kokonaislukuja, jotka ovat aivan liian suuri. Modulaarisen eksponention laskemiseksi on tehokkaita menetelmiä .
Voimme säilyttää eräänlaisen yksityisen avaimen, jotta salauksen purkaminen on nopeampaa käyttämällä Kiinan jäännöslausetta .
Meidän on erotettava toisistaan raakaa voimaa sisältävät hyökkäykset , jotka koostuvat p: n ja q : n löytämisestä vain n: n tietämyksen perusteella , ja hyökkäykset, jotka perustuvat tietoon n: stä, mutta myös tapaan, jolla p ja q muodostettiin, salauskäytöstä. käytetty ohjelmisto, yksi tai useampi mahdollisesti siepattu viesti jne.
RSA-algoritmin turvallisuus raa'an voiman hyökkäyksiä vastaan perustuu kahteen oletukseen:
On mahdollista, että toinen kahdesta oletuksesta on väärä tai molemmat. Toistaiseksi RSA on niin onnistunut, että tiedeyhteisön tiedossa ei ole algoritmia raa'an voimahyökkäyksen suorittamiseen tavanomaisilla tietokoneilla.
2. joulukuuta 2019, suurin tällä tavalla laskettu luku hajautettua laskentamenetelmää käyttäen oli 795 bittiä . RSA-avainten pituus on yleensä 1024 - 2048 bittiä. Jotkut asiantuntijat uskovat, on mahdollista, että 1024-bittisillä avaimilla murtuu lähitulevaisuudessa (vaikka tämä on kiistanalainen ), mutta harvat näkevät keino murtaa 4096-bittisillä avaimilla tällä tavalla lähitulevaisuudessa. . Voidaan kuitenkin olettaa, että RSA pysyy turvassa, jos avaimen koko on riittävän suuri. Alle 256 bitin kokoisen avaimen jakaminen osiin löytyy muutamassa minuutissa henkilökohtaiselta tietokoneelta vapaasti saatavilla olevia ohjelmistoja käyttäen. Jopa 512 bitin koolle ja vuodesta 1999 lähtien on jouduttu tekemään useita satoja tietokoneita toimimaan yhdessä. Turvallisuuden vuoksi on suositeltavaa, että RSA-avainten koko on vähintään 2048 bittiä.
Jos henkilöllä olisi "nopea" tapa laskea luku n , kaikki tähän periaatteeseen perustuvat salausalgoritmit kyseenalaistettaisiin, samoin kuin kaikki aikaisemmin näitä algoritmeja käyttäen salatut tiedot.
Vuonna 1994 kvanttitietokoneille kirjoitettiin algoritmi lukujen faktorointiin ei-eksponentiaalisessa ajassa . Tämä on Shor-algoritmi . Kvanttitietokoneiden sovellukset mahdollistavat teoreettisen RSA: n rikkomisen raakalla voimalla, mikä on aktivoinut aihetta koskevan tutkimuksen; mutta tällä hetkellä nämä tietokoneet tuottavat satunnaisia virheitä, jotka tekevät niistä tehottomia.
Muun tyyppiset hyökkäykset (katso alla olevat hyökkäykset ), jotka ovat paljon tehokkaampia, kohdistuvat tapaan, jolla alkuluvut p ja q on luotu, miten e on valittu, onko koodattuja viestejä saatavilla tai muuta muuta mahdollista tietoa käytetty. Osa tästä aiheesta julkaistusta tutkimuksesta on julkaistu, mutta viimeisimmät kryptoanalyysiyritysten ja tiedustelupalvelujen kuten NSA: n kehittämät tekniikat ovat edelleen huojussa.
Lopuksi on huomattava, että avaimen rikkominen jakamalla luku n ei vaadi odottamista, kun salattu viesti on käytettävissä. Tämä operaatio voidaan aloittaa vain julkisen avaimen tuntemuksen perusteella , johon pääsy on yleensä vapaata. Näissä olosuhteissa, jos n otetaan huomioon, yksityinen avain päätetään välittömästi. Tämän havainnon seurauksena on myös, että koodi voidaan rikkoa jo ennen sen käyttöä.
Kun kaksi ihmistä haluaa vaihtaa digitaalista tietoa luottamuksellisesti, esimerkiksi Internetissä sähköisen kaupankäynnin kanssa , heidän on käytettävä mekanismia näiden digitaalisten tietojen salaamiseen . Koska RSA on epäsymmetrinen salausalgoritmi , se perii näiden salausmekanismien laajuuden. Lainaamme:
Jälkimmäinen on itse asiassa integroitu RSA-mekanismiin. Symmetristen algoritmien ongelmana on, että sinun on oltava varma, että salausavain paljastetaan vain ihmisille, jotka haluavat jakaa salaisuuden. RSA sallii tämän symmetrisen avaimen välittämisen turvallisella tavalla. Tätä varten Alice valitsee ensin symmetrisen avaimen. Hän haluaa vaihtaa salaisuuden Bobin kanssa ja lähettää hänelle tämän symmetrisen avaimen RSA: n avulla. Tätä varten se salaa symmetrisen avaimen Bobin julkisella avaimella (RSA), joten on varma, että vain Bob voi purkaa tämän symmetrisen avaimen. Kun Bob on vastaanottanut viestin, hän purkaa sen salauksen ja voi sitten käyttää Alicen määrittelemää symmetristä avainta lähettämään hänelle salattuja viestejä, jotka vain hän ja Alice voivat purkaa.
RSA-salauksen rikkomiseksi on ehdotettu useita hyökkäyksiä.
Hyökkäys Wiener (1989) voidaan käyttää hyväksi, jos salainen eksponentti d on pienempi kuin . Tässä tapauksessa voimme löytää salaisen eksponentin käyttämällä jatkuvaa murto-osaa .
Håstadin hyökkäys , yksi ensimmäisistä löydetyistä (vuonna 1985), perustuu mahdollisuuteen, että julkinen eksponentti e on riittävän pieni. Sieppaamalla sama viesti, joka on lähetetty ainakin eri vastaanottajille, on mahdollista löytää alkuperäinen viesti käyttäen kiinalaisia loppulauseita .
Paul Kocher kuvasi vuonna 1995 uutta hyökkäystä RSA: ta vastaan: olettaen, että hyökkääjä Eve tiesi tarpeeksi Alicen asiakirjoista ja pystyi mittaamaan useiden salattujen asiakirjojen salauksen purkuajat, hän pystyi nopeasti johtamaan salauksen avaimen. Sama pätee allekirjoitukseen.
Vuonna 2003 Boneh ja Brumley esittivät käytännöllisemmän hyökkäyksen, joka mahdollisti löytää RSA-kertoimen verkkoyhteydestä ( SSL ) tukeutuen tietoihin, jotka jotkut Kiinan jäljellä olevaan lauseeseen sovelletut optimoinnit voivat suodattaa. Yksi tapa estää nämä hyökkäykset on varmistaa, että salauksen purku vie jatkuvasti aikaa. Tämä lähestymistapa voi kuitenkin vähentää suorituskykyä merkittävästi. Tämän vuoksi useimmat toteutukset (toteutettu) RSA käyttää toista tekniikkaa kutsutaan nimikkeellä "salauksen sokeuden" ( sokaistuminen ).
Pimennys hyödyntää RSA: n multiplikatiivisia ominaisuuksia lisäämällä laskentaan satunnaisen salaisen arvon, jonka vaikutus voidaan kumota. Koska arvo on erilainen kullekin salaukselle, salauksen purkuaika ei ole enää suoraan korreloitavissa salattavan datan kanssa, mikä voittaa ajoitushyökkäyksen: Alice valitsee laskemisen sijaan ensin salaisen satunnaisarvon r ja laskee . Tämän laskelman tulos on ja siksi r: n vaikutus voidaan kumota kertomalla sen käänteisarvolla.
Kuten tässä artikkelissa on kuvattu, RSA on deterministinen salaus, joten se ei voi olla semanttisesti turvallinen . Vastatoimenpide on todennäköisyyspehmustemallin käyttö siten, että mikään viestin arvo, kun se on salattu, ei anna epävarmaa tulosta, esimerkiksi jos C = M e ≤ N , yksinkertainen hyökkäys on laskenta suoraan e-juuresta C: tä, jota ei ole pienennetty modulo N.
Vuonna 1998 Daniel Bleichenbacher kuvaili ensimmäistä käytännöllistä "mukautettavan valitun salakirjoituksen" tyyppistä hyökkäystä RSA-viestejä vastaan. PKCS # 1 v1 -pehmustusjärjestelmän puutteiden vuoksi se pystyi palauttamaan SSL- istuntoavaimet . Tämän työn tuloksena kryptografit suosittelevat nyt muodollisesti turvallisten täyttömenetelmien käyttöä , kuten OAEP , ja RSA Laboratories ovat julkaisseet PKCS # 1: n uudet versiot, jotka kestävät näitä hyökkäyksiä.