Julkisen avaimen salausjärjestelmä (eräänlainen epäsymmetrinen salaus , epäsymmetrinen salaus ) - salaus- ja/tai sähköisen allekirjoituksen (ES) järjestelmä, jossa julkinen avain välitetään avoimen (eli suojaamattoman, havaittavissa olevan) kanavan kautta ja sitä käytetään varmistamaan ES:lle ja salausviesteille. ES:n luomiseen ja viestin salauksen purkamiseen käytetään yksityistä avainta [1] . Julkisen avaimen salausjärjestelmiä käytetään tällä hetkellä laajalti erilaisissa verkkoprotokollissa , erityisesti TLS-protokollassa ja sen edeltäjässä SSL :ssä (perustanaHTTPS ), SSH :ksi . Käytetään myös PGP :ssä , S/MIME :ssä .
Epäsymmetrinen julkisen avaimen salaus perustuu seuraaviin periaatteisiin:
Jos avainten omistajalle on lähetettävä salattu viesti, lähettäjän on saatava julkinen avain. Lähettäjä salaa viestinsä vastaanottajan julkisella avaimella ja välittää sen vastaanottajalle (avainten omistajalle) avoimia kanavia pitkin. Samanaikaisesti kukaan ei voi purkaa viestin salausta paitsi yksityisen avaimen omistaja.
Tämän seurauksena viestit voidaan salata turvallisesti samalla, kun salauksen purkuavain pidetään salassa kaikille - myös viestin lähettäjille.
Tämä periaate voidaan selittää paketin lähettämisen arkipäiväisellä analogialla "lukko - avain lukkoon". Osallistujalla A on henkilökohtainen lukko ja avain siihen. Jos osallistuja A haluaa vastaanottaa salaisen paketin osallistujalta B, hän antaa hänelle julkisesti linnansa. Osallistuja B lukitsee salaisen paketin lukon ja lähettää sen osallistujalle A. Saatuaan paketin osallistuja A avaa lukon avaimella ja vastaanottaa paketin.
Tietäminen lukon siirtämisestä ja paketin sieppaamisesta ei anna mahdolliselle hyökkääjälle mitään: vain osallistujalla A on lukon avain, joten pakettia ei voi avata.
Ajatus julkisen avaimen salakirjoituksesta liittyy hyvin läheisesti ajatukseen yksisuuntaisista funktioista , eli sellaisista funktioista , joista on melko helppo löytää arvo tunnetusta arvosta , kun taas sen määrittäminen on mahdotonta kohtuullinen aika.
Mutta yksisuuntainen toiminto itsessään on hyödytön sovelluksessa: se voi salata viestin, mutta se ei voi purkaa sen salausta. Siksi julkisen avaimen salaus käyttää yksisuuntaisia toimintoja porsaanreikään. Porsaanreikä on salaisuus, joka auttaa ymmärtämään. Eli on olemassa sellainen, että tietäen ja Voimme laskea . Jos esimerkiksi purat kellon useisiin osiin, on hyvin vaikeaa koota uudelleen toimivaa kelloa. Mutta jos on asennusohje (porsaanreikä), tämä ongelma voidaan ratkaista helposti.
Tiedon vastaanottaja luo julkisen avaimen ja "luukun" (toisin sanoen avaimen julkisen ja yksityisen osan), siirtää sitten julkisen avaimen lähettäjälle ja pitää "luukun" itselleen. Lähettäjä salaa tiedot julkisen avaimen perusteella: tällaisen salatun tiedon salaus on helppo purkaa, jos sinulla on sekä julkinen avain että "takaovi" samanaikaisesti. Toiminnon suhteen vastaanotin muodostaa takaoven ja välittää sitten tiedot toimintoparametreista lähettäjälle (vaikka vaikka toimintoparametrit tiedetään , "takaoven" havaitseminen on mahdotonta kohtuullisessa ajassa). Sen jälkeen lähettäjä muodostaa salatun viestin ja vastaanottaja poimii siitä tietäen .
Seuraava esimerkki auttaa ymmärtämään julkisen avaimen salauksen ideat ja menetelmät - salasanojen tallentaminen etätietokoneeseen, johon käyttäjien tulee muodostaa yhteys. Jokaisella verkon käyttäjällä on erilainen salasana. Sisäänkäynnillä hän ilmoittaa nimen ja syöttää salaisen salasanan. Mutta jos tallennat salasanan etätietokoneen levylle, joku voi lukea sen (tämän tietokoneen järjestelmänvalvojan on erityisen helppoa tehdä tämä) ja päästä käsiksi salaisiin tietoihin. Ongelman ratkaisemiseksi käytetään yksisuuntaista toimintoa. Kun luot salaisen salasanan, tietokone ei tallenna itse salasanaa, vaan tuloksen funktion laskemisesta tästä salasanasta ja käyttäjätunnuksesta. Esimerkiksi käyttäjä Alice keksi salasanan "Gladiolus". Tätä dataa tallennettaessa lasketaan funktion tulos ( ALICE_GLADIOLUS ), olkoon tuloksena merkkijono CAMOMILE , joka tallennetaan järjestelmään. Tämän seurauksena salasanatiedosto on seuraavanlainen:
Nimi | (Nimi: Salasana) |
---|---|
ALICE | KAMOMILLA |
PAPU | NARKISSUS |
Kirjautuminen näyttää nyt tältä:
Nimi: | ALICE |
---|---|
Salasana: | GLADIOLUS |
Kun Alice syöttää "salaisen" salasanan, tietokone tarkistaa, antaako ALICE_GLADIOLUKSelle käytetty toiminto oikean tuloksen CAMMILE , joka on tallennettu tietokoneen levylle. Nimessä tai salasanassa kannattaa vaihtaa ainakin yksi kirjain, ja toiminnon tulos on täysin erilainen. "Salaista" salasanaa ei tallenneta tietokoneelle missään muodossa. Muut käyttäjät voivat nyt tarkastella salasanatiedostoa yksityisyyttään menettämättä, koska toiminto on lähes peruuttamaton.
Edellisessä esimerkissä käytetään yksisuuntaista toimintoa ilman porsaanreikää, koska sen ei tarvitse saada alkuperäistä viestiä salatusta viestistä. Seuraavassa esimerkissä tarkastellaan mallia, jolla on kyky palauttaa alkuperäinen viesti käyttämällä "takaovea", eli tietoa, jota on vaikea löytää. Tekstin salaamiseksi voit ottaa suuren tilaajaluettelon, joka koostuu useista paksuista niteistä (setä käyttävien kaupungin asukkaiden numero on erittäin helppo löytää, mutta tilaajaa on lähes mahdotonta löytää tunnetulla numerolla) . Jokaiselle salatun viestin kirjaimelle valitaan samalla kirjaimella alkava nimi. Täten kirjain liitetään tilaajan puhelinnumeroon. Lähetettävä viesti, esimerkiksi " BOX ", salataan seuraavasti:
Viesti | Valittu nimi | Kryptoteksti |
---|---|---|
Vastaanottaja | Korolev | 5643452 |
O | Orekhov | 3572651 |
R | Ruzaeva | 4673956 |
O | Osipov | 3517289 |
B | Baturin | 7755628 |
Vastaanottaja | Kirsanova | 1235267 |
MUTTA | Arsenjev | 8492746 |
Salausteksti on numeroketju, joka on kirjoitettu heidän valitsemassaan järjestyksessä hakemistoon. Jotta tulkinta on vaikeaa, sinun tulee valita satunnaiset nimet, jotka alkavat halutulla kirjaimella. Alkuperäinen viesti voidaan siten salata useilla erilaisilla numerolistoilla (salausteksteillä).
Esimerkkejä tällaisista kryptoteksteistä:
Kryptoteksti 1 | Kryptoteksti 2 | Kryptoteksti 3 |
---|---|---|
1235267 | 5643452 | 1235267 |
3572651 | 3517289 | 3517289 |
4673956 | 4673956 | 4673956 |
3517289 | 3572651 | 3572651 |
7755628 | 7755628 | 7755628 |
5643452 | 1235267 | 5643452 |
8492746 | 8492746 | 8492746 |
Tekstin tulkitsemiseksi sinulla on oltava hakuteos, joka on koottu nousevien numeroiden mukaan. Tämä hakemisto on porsaanreikä (salaisuus, joka auttaa saamaan alkutekstin), jonka tietää vain vastaanottaja. Ilman molempien hakemistojen tietoja on yleensä mahdotonta tulkita tekstiä, mutta vain ensimmäinen hakemisto riittää salaukseen [2] . Tällöin vastaanottaja voi helposti muodostaa molemmat hakemistot etukäteen siirtämällä niistä vain ensimmäisen lähettäjälle salausta varten.
Olkoon avaintila ja ja ovat salaus- ja salauksenpurkuavaimet. on salaustoiminto mielivaltaiselle avaimelle siten, että . Tässä , missä on salatekstien tila, ja missä on viestien tila.
on salauksenpurkutoiminto, jota voidaan käyttää alkuperäisen viestin löytämiseen salatekstinä : , on salausjoukko ja sitä vastaava salauksenpurkujoukko. Jokaisella parilla on seuraava ominaisuus: tietäen , yhtälön ratkaiseminen on mahdotonta , eli annetulle mielivaltaiselle salatekstille on mahdotonta löytää viestiä . Tämä tarkoittaa, että annetusta avaimesta on mahdotonta määrittää vastaavaa salauksenpurkuavainta . on yksisuuntainen funktio, ja se on porsaanreikä [3] .
Alla on kaavio tietojen siirtämisestä henkilölle A henkilölle B. He voivat olla sekä yksilöitä että organisaatioita ja niin edelleen. Mutta ymmärtämisen helpottamiseksi on tapana tunnistaa ohjelman osallistujat ihmisten kanssa, joita kutsutaan useimmiten Aliceksi ja Bobiksi. Osallistujaa, joka yrittää siepata ja purkaa Alicen ja Bobin viestit, kutsutaan yleisimmin Eevaksi.
Epäsymmetriset salaukset alkoivat vuonna 1976 julkaistussa Whitfield Diffien ja Martin Hellmanin teoksessa New Directions in Modern Cryptography . Ralph Merklen julkisen avaimen jakelua koskevan työn vaikutuksesta he ehdottivat menetelmää yksityisten avainten hankkimiseksi julkista kanavaa käyttäen. Tämä eksponentiaalinen avaintenvaihtomenetelmä, joka tunnettiin nimellä Diffie-Hellman- avaintenvaihto , oli ensimmäinen julkaistu käytännön menetelmä salaisten avainten jakamiseen kanavan todennettujen käyttäjien välillä. Vuonna 2002 Hellman ehdotti algoritmin kutsumista "Diffie-Hellman-Merkleksi", tunnustaen Merklen panoksen julkisen avaimen salauksen keksimiseen. Saman järjestelmän kehitti Malcolm Williamson ( eng. Malcolm J. Williamson ) 1970-luvulla, mutta se pidettiin salassa vuoteen 1997 asti . Merklen julkisen avaimen jakelumenetelmä keksittiin vuonna 1974 ja julkaistiin vuonna 1978 , ja sitä kutsutaan myös Merklen arvoitukseksi.
Vuonna 1977 MIT :n tutkijat Ronald Rivest , Adi Shamir ja Leonard Adleman kehittivät faktorointiongelmaan perustuvan salausalgoritmin. Järjestelmä on nimetty heidän sukunimiensä ensimmäisten kirjainten mukaan ( RSA - Rivest, Shamir, Adleman). Saman järjestelmän keksi vuonna 1973 Government Communications Centerissä ( GCHQ ) työskennellyt Clifford Cocks , mutta tämä työ säilytettiin vain keskuksen sisäisissä asiakirjoissa, joten sen olemassaolo tiedettiin vasta vuonna 1977 . RSA oli ensimmäinen algoritmi, joka soveltui sekä salaukseen että digitaaliseen allekirjoitukseen.
Yleisesti tunnetut epäsymmetriset salausjärjestelmät perustuvat yhteen monimutkaisista matemaattisista ongelmista, mikä mahdollistaa yksisuuntaisten funktioiden ja takaoven funktioiden rakentamisen. Esimerkiksi Merkle-Hellman- ja Hoare-Rivest- salausjärjestelmät luottavat niin sanottuun reppuongelmaan .
Olkoon 3 avainta , , , jaettuna taulukon mukaisesti.
Kasvot | Avain |
---|---|
Alice | |
Papu | |
Carol | |
Dave | , |
Ellen | , |
Frangi | , |
Sitten Alice voi salata viestin avaimella ja Ellen voi purkaa salauksen avaimilla , Carol voi salata avaimella ja Dave voi purkaa salauksen avaimilla , . Jos Dave salaa viestin avaimella , Ellen voi lukea viestin, jos avaimella , niin Frank voi lukea sen, jos molemmilla avaimilla ja , niin Carol lukee viestin. Muut osallistujat toimivat samalla tavalla. Siten, jos yhtä avainten osajoukkoa käytetään salaukseen, joukon loput avaimet tarvitaan salauksen purkamiseen. Tällaista kaaviota voidaan käyttää n avaimelle.
Salattu avaimella | Purettu avaimella |
---|---|
ja | |
ja | |
ja | |
, | |
, | |
, |
Harkitse ensin sarjaa, joka koostuu kolmesta agentista: Alice, Bob ja Carol. Alice saa avaimet ja , Bob - ja , Carol - ja . Jos nyt lähetettävä viesti on salattu avaimella , vain Alice voi lukea sen käyttämällä peräkkäin avaimia ja . Jos haluat lähettää viestin Bobille, viesti salataan avaimella , Carol - avaimella . Jos haluat lähettää viestin sekä Alicelle että Carolille, avaimia ja käytetään salaukseen .
Tämän menetelmän etuna on, että sen toteuttamiseen tarvitaan vain yksi viesti ja n avainta (n agenttia sisältävässä mallissa). Jos lähetetään yksittäisiä viestejä, eli kullekin agentille (yhteensä n avainta) ja jokaiselle viestille käytetään erillisiä avaimia, niin avaimia tarvitaan viestien lähettämiseen kaikille eri osajoukkoille.
Tämän järjestelmän haittana on, että sinun on myös lähetettävä osajoukko agentteja (nimiluettelo voi olla pitkä), joille haluat lähettää viestin. Muuten jokaisen heistä on käytävä läpi kaikki näppäinyhdistelmät etsiessään sopivaa. Lisäksi agenttien on tallennettava huomattava määrä tietoa avaimista [4] .
Vaikuttaa siltä, että julkisen avaimen salausjärjestelmä on ihanteellinen järjestelmä, joka ei vaadi suojattua kanavaa salausavaimen lähettämiseen. Tämä merkitsisi sitä, että kaksi laillista käyttäjää voisivat kommunikoida avoimen kanavan kautta ilman, että heidän tarvitsee tavata avainten vaihtoa. Valitettavasti se ei ole. Kuva havainnollistaa kuinka Eve aktiivisena sieppaajana voi ottaa järjestelmän haltuunsa (purkaa Bobille tarkoitetun viestin salaus) rikkomatta salausjärjestelmää.
Tässä mallissa Eve sieppaa julkisen avaimen , jonka Bob on lähettänyt Alicelle. Sitten se luo avainparin ja "naamioituu" Bobiksi lähettämällä Alicelle julkisen avaimen , jonka Alice luulee olevan Bobin hänelle lähettämä julkinen avain. Eve sieppaa salatut viestit Alicelta Bobille, purkaa niiden salauksen salaisella avaimella , salaa ne uudelleen Bobin julkisella avaimella ja lähettää viestin Bobille. Näin ollen kukaan osallistujista ei ymmärrä, että on olemassa kolmas osapuoli, joka voi joko yksinkertaisesti siepata viestin tai korvata sen väärällä viestillä . Tämä korostaa julkisen avaimen todennuksen tarvetta. Tätä varten käytetään yleensä varmenteita . Hajautettu avaintenhallinta PGP :ssä ratkaisee ongelman takaajien avulla [5] .
Toinen hyökkäysmuoto on yksityisen avaimen laskeminen julkisesta avaimesta (kuva alla). Kryptusanalyytikko tuntee salausalgoritmin , analysoi sitä ja yrittää löytää . Tämä prosessi yksinkertaistuu, jos kryptoanalyytikko on siepannut useita kryptotekstejä c, jotka henkilö A on lähettänyt henkilölle B.
Useimmat julkisen avaimen salausjärjestelmät perustuvat suurten numeroiden tekijöihin perustuvaan ongelmaan. Esimerkiksi RSA käyttää kahden suuren luvun tuloa julkisena avaimena n. Tällaisen algoritmin murtamisen monimutkaisuus piilee luvun n:n faktoroinnin vaikeudessa. Mutta tämä ongelma voidaan ratkaista realistisesti. Ja joka vuosi hajoamisprosessi muuttuu nopeammaksi ja nopeammaksi. Alla on "Quadratic Sieve" -algoritmia käyttävät tekijätiedot.
vuosi | Desimaalien lukumäärä laajennetussa numerossa |
Kuinka monta kertaa vaikeampaa on kertoa 512-bittinen luku |
---|---|---|
1983 | 71 | > 20 miljoonaa |
1985 | 80 | > 2 miljoonaa |
1988 | 90 | 250 tuhatta |
1989 | 100 | 30 tuhatta |
1993 | 120 | 500 |
1994 | 129 | 100 |
Myös hajoamisongelma voidaan mahdollisesti ratkaista Shor-algoritmilla, kun käytetään riittävän tehokasta kvanttitietokonetta .
Monissa epäsymmetrisen salauksen menetelmissä kryptoanalyysin tuloksena saatu kryptografinen vahvuus eroaa merkittävästi algoritmien kehittäjien teoreettisiin arvioihin perustuvista arvoista. Siksi monissa maissa kysymys tietojen salausalgoritmien käytöstä kuuluu lainsäädännöllisen sääntelyn piiriin. Erityisesti Venäjällä vain sellaiset tietojen salausohjelmistotyökalut, jotka ovat läpäisseet valtion sertifioinnin hallintoelimissä, erityisesti FSB :ssä , FSTEC :ssä, ovat sallittuja valtion ja kaupallisten organisaatioiden käyttöön [6] .
Julkisen avaimen salausjärjestelmäalgoritmeja voidaan käyttää [7] :
Epäsymmetristen salausten edut symmetrisiin verrattuna :
Epäsymmetrisen salausalgoritmin haitat verrattuna symmetriseen salausalgoritmiin:
Symmetrinen avaimen pituus, bitti | RSA-avaimen pituus, bitti |
---|---|
56 | 384 |
64 | 512 |
80 | 768 |
112 | 1792 |
128 | 2304 |