Julkisen avaimen salausjärjestelmä

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ä .

Ajatus julkisen avaimen salausjärjestelmästä

Yleiset periaatteet

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.

Toteutus yksisuuntaisen toiminnon kautta

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 .

Esimerkkejä

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.

Julkisen avaimen salausjärjestelmä

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.

  1. Bob valitsee parin ja lähettää salausavaimen (julkinen avain) Alicelle julkisen kanavan kautta, ja salauksenpurkuavain (yksityinen avain) on suojattu ja salainen (se ei saa lähettää julkisen kanavan kautta).
  2. Viestin lähettämiseen Bobille Alice käyttää julkisen avaimen : määrittämää salaustoimintoa ,  joka on vastaanotettu salateksti.
  3. Bob purkaa salatekstin käänteisellä muunnolla , jonka arvo yksilöi .

Tieteellinen perusta

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 .

Perusperiaatteet julkisen avaimen salausjärjestelmien rakentamiseen

  1. Aloitetaan vaikeasta tehtävästä . Sen pitäisi olla vaikea ratkaista teoriassa: ei pitäisi olla algoritmia, jolla voitaisiin lajitella kaikki ongelman ratkaisuvaihtoehdot polynomiajassa suhteessa tehtävän kokoon. On oikeampaa sanoa: ei pitäisi olla tunnettua polynomialgoritmia, joka ratkaisee tämän ongelman - koska ei ole vielä todistettu mihinkään ongelmaan, että sille ei periaatteessa ole sopivaa algoritmia.
  2. Voit valita kevyen alitehtävän . Se on ratkaistava polynomiajassa ja parempi jos lineaarisessa ajassa.
  3. "Sekoita ja ravista" saadaksesi tehtävän , joka on täysin erilainen kuin alkuperäinen. Ongelman pitäisi ainakin näyttää alkuperäiseltä ratkaisemattomalta ongelmalta .
  4. avautuu kuvauksella, kuinka sitä voidaan käyttää salausavaimena. Kuinka saada se pidetään salassa kuin salainen porsaanreikä.
  5. Salausjärjestelmä on järjestetty siten, että laillisen käyttäjän ja kryptoanalyytikon salauksenpurkualgoritmit eroavat merkittävästi toisistaan. Kun toinen ratkaisee -ongelman, ensimmäinen käyttää salaista porsaanreikää ja ratkaisee -ongelman.

Salaus useilla julkisilla avaimilla

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] .

Julkisen avaimen algoritmien krypta-analyysi

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] .

Järjestelmän ominaisuudet

Sovellus

Julkisen avaimen salausjärjestelmäalgoritmeja voidaan käyttää [7] :

Edut

Epäsymmetristen salausten edut symmetrisiin verrattuna :

Haitat

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

Epäsymmetristen salausten tyypit

Katso myös

Muistiinpanot

  1. Bruce Schneier. Sovellettu kryptografia. 2. painos Protokollat, algoritmit ja lähdetekstit C-kielellä. Luku 2.7 Digitaaliset allekirjoitukset ja salaus.
  2. Salomaa A. Julkisen avaimen salaus. Kanssa. 74-75
  3. Handbook of Applied Cryptography, Menezes AJ, Oorschot PC, Vanstone SA s. 25-26
  4. Bruce Schneier. Sovellettu kryptografia. 2. painos Protokollat, algoritmit ja lähdetekstit C-kielellä. Luku 3.5
  5. PGP. Avainten jakelu. . Arkistoitu alkuperäisestä 26. heinäkuuta 2013.
  6. Riittävän suojan periaate (pääsemätön linkki) . Haettu 4. joulukuuta 2008. Arkistoitu alkuperäisestä 24. toukokuuta 2010. 
  7. Barichev S. Kryptografia ilman salaisuuksia. Kanssa. kaksikymmentä

Kirjallisuus

Linkit