Symmetrinen ja asymmetrinen salaus

Johdanto

Tämän kirjoituksen tarkoituksena on tuottaa kattava ja ymmärrettävä tietopaketti symmetrisen ja asymmetrisen salauksen periaatteista, eroista, eduista ja haitoista. Erilaisia salausmenetelmiä tarvitaan kaikkialla, missä halutaan lähettää luottamuksellista tietoa tai saada varmistettua tietyn käyttäjän identiteetti. Verkkopankit, tiedon salaajat ja muut tarvitsevat erilaisia tapoja tiedon salaamiseen. Esseessä käsitellään tekniikkaa hyvin pintapuolisesti ja pitäydytään periaatteiden selventämisessä. Teksti on tarkoitettu maallikon ymmärrettäväksi, ei tekniseksi raportiksi. Jonkinlainen peruskäsitys matematiikasta ja algoritmien toiminnasta kuitenkin vaaditaan tekstin ymmärtämiseksi. 

Kirjoitus on alunperin laadittu keväällä 2020 osana lohkoketjukurssia. Minua pyydettiin antamaan lausunto pitkän matematiikan uudesta kirjasta kurssille 11, algoritmit ja lukuteoria. Kirjassa käsiteltiin RSA-salaus, mutta ilman mitään sen kummempaa kontekstia tai taustoitusta. Mielestäni on tärkeää ymmärtää symmetrisen salauksen idea ja heikkoudet ennenkuin lähdetään miettimään vaikeampia asioita. Tarjosin tätä esseetä osaksi materiaalia. Olisihan se sääli jättää se pöytälaatikkoon, kun olen nähnyt vaivaa sen kirjoittamiseksi.


Symmetrinen salaus

Symmetrinen salaus ovat periaatteeltaan helpoimpia salausalgoritmeja. Viesti salataan salausavaimella ja puretaan myös samaa avainta käyttäen. Tällöin sekä lähettäjän, että vastaanottajan täytyy tietää salainen avain. 

Caesarin menetelmä

Yksi vanhimmista menetelmistä on Caesarin menetelmäksi ristitty salaus, jossa kaksi aakkostoa asetettiin vierekkäin ja siirrettiin toista ennalta sovittu merkkimäärä eteenpäin. Nimeni ”Mikko” voitaisiin salata Caesar 3 -salauksella siten, että jokainen merkki kirjoitettaisiinkin kolme merkkiä myöhemmin aakkostossa esiintyvällä merkillä. Tällöin salattu nimeni olisi ”Plnnr”. Jos salauksen idean tietää, ei vaadi kovinkaan suuria kykyjä selvittää mitä salatussa tekstissä sanotaan.(1) Kuvassa 1 selitetään salauksen idea. (2)

Kuva 1. Caesar-salauksen periaate

Periaatteessa samanlainen olisi myös matemaattisempi salaus. Minun nimeni ”Mikko” on ASCII-koodina 77 105 107 107 111, jota voisi tässä tapauksessa käsitellä yhtenä suurena lukuna. Jos salausavaimeni olisi esimerkiksi 31, voisin kertoa tuon luvun kyseisellä salausavaimella. Tuloksena olisi luku 2 390 258 320 320 441, joka tekstiksi muokattuna ei tuota mitään järkevää. Voin kuitenkin lähettää luvun vastaanottajalle, joka tietää salausavaimeni. Hänen on helppo jakaa luku ja saada taas selkeästi luettava teksti. 

Vigenère-menetelmä

Caesar-salaus on helppo murtaa, jos kokeilee kaikki mahdollisuudet läpi. Suomessa kirjaimia on vain 28, joten vaihtoehtoja ei ole kovin paljon. Hivenen monimutkaisempi salaus olisi jokaisen kirjaimen vaihtaminen toiseksi ennalta sovitun logiikan mukaisesti. Tällainen on esimerkiksi Vigenère-salaus. Siinä ensimmäinen merkki on sama kuin alkuperäisessäkin, mutta jokainen merkki vierittää salausmerkistöä Caesar-salauksen mukaisesti yhdellä eteenpäin. Tällä tavoin salausavain muuttuu hieman jokaista merkkiä kohti. (Kuva 2)(3)  Tämä ei ole kovin paljoa Caesar-salausta monimutkaisempi tai työläämpi murtaa, jos tietää salauksen perusidean. 

Kuva 2. Vigenère-salauksen purkutaulu



Aakkosten vaihto

Seuraava askel olisi vaihtaa kirjainten kooditusta ennalta sovitulla tavalla, mutta ilman mitään selkeää ja toistuvaa logiikkaa. Näissä murtamisen työmäärä on huomattavasti suurempi, sillä erilaisia logiikkavaihtoehtoja on suomalaisilla 28 kirjaimella 28! (3,05·1029). (4)  Tällainen salaus on kuitenkin suhteellisen nopea murtaa, jos tiedetään jokin viestissä oleva sana tai fraasi, tai jos tiedetään millä kielellä alkuperäinen salaamaton teksti on ollut. Jos tiedetään, että viesti alkaa aina sanoilla ”Morjens, mitä jätkä”, saadaan helposti tulkattua jo aloitussanoissa olleet 11 erilaista merkkiä. Tämän jälkeen viestistä saattaa löytyä useita sanoja, jotka voi arvata. 

Eri kielissä eri merkit toistuvat eri frekvensseillä. Esimerkiksi englannin kielessä yleisimmät kirjaimet ovat E, T, A, O ja I tässä järjestyksessä.(5)  Suomen kielessä yleisimmät olisivat taas A, I, T, N ja E.(6)  Jos viesti on riittävän pitkä ja tiedetään alkuperäisen viestin olleen englanniksi, voidaan laskea eri merkkien frekvenssit ja päätellä niistä selkokieliset merkit. 


One-time pad

Jos salaustapaa vaihdetaan sattumanvaraisesti ja ilman toistuvaa logiikkaa jokaisen kirjaimen kohdalla, saadaan erittäin turvallinen salausmenetelmä. Tällaisia salausjärjestelmiä ovat esimerkiksi ns. ”One-time pad” -salaukset, joita Yhdysvaltojen laivasto ja monet muut instanssit käyttävät edelleen. Kuvassa 3 on esimerkki one-time padista.(7)  Niissä tarvitaan ennalta jaettu salausavain, pad, tekstin salaamiseen ja purkamiseen. Yhtään riviä ei käytetä toistamiseen, jolloin tekstistä tulee mahdotonta purkaa. Tämän salauksen heikoin lenkki on salaus-avaimen turvallinen toimittaminen vastaanottajalle ja avaimen pitäminen salassa.(6) 


Kuva 3. Yhdysvaltain turvallisuuspalvelu NSA:n Diana-järjestelmän One-Time Pad

Symmetrinen salausavain voi tietenkin tietokoneiden aikakautena olla päätähuimaavan monimutkainen. Ongelmaksi muodostuukin se, miten yhteinen salausavain voidaan vaihtaa vastaanottajan ja lähettäjän välillä ja milloin sen tietää tulleen murretuksi. Jos Caesar lähettäisi salatuiksi tarkoitettuja viestejään kenraaleilleen, hän olisi suuremmassa vaarassa, kun ei osaisi epäillä vihollisen tietävän aikeistaan.  

ASYMMETRINEN SALAUS

Asymmetrisellä salauksella tarkoitetaan salausta, jossa vastaanottajalla ja lähettäjällä ei tarvitse olla tiedossaan samaa avainta. Asymmetrisessä salauksessa lähettäjällä ja vastaanottajalla on kummallakin yhteinen julkinen avain ja henkilökohtainen avain. Julkisen avaimen voi painaa vaikka käyntikorttiinsa, kun taas henkilökohtainen avain tulee pitää visusti omana tietona. 

Asymmetrinen algoritmi koostuu yleensä kolmesta algoritmista, tässä G, E ja D. (8)

  • G on nondeterministinen algoritmi, joka palauttaa avainparin (j, s)
  • E(j, m) on algoritmi, jolle annetaan parametreinä selkokielinen teksti m ja julkinen avain ja se palauttaa salatun tekstin c.
  • D(s, c) on purkualgoritmi, jolle annetaan algoritmina salattu teksti c ja salainen avain s. Algoritmi palauttaa selkokielisen tekstin.
Salauksen ideana on se, että salatun tekstin voi palauttaa vain salaisen avaimen tunteva henkilö. Vastaavasti salaisella avaimella salattu viesti voidaan avata vain julkisella avaimella.(7) Tämä monimutkaiselta kuulostava asia selitetään yksinkertaisesti kuvassa 4.(9) Asymmetrinen salaus on tuhansia kertoja hitaampaa kuin symmetrinen salaus, joten sillä ei kannata kovin monimutkaisia viestejä lähettää. Yleensä asymmetrisellä salauksella lähetetään vastaanottajalle symmetrinen avain, jonka jälkeen viestintä jatkuu symmetrisellä salauksella.
Kuva 4. Julkisen ja yksityisen avaimen käyttö tekstin salaamisessa ja salauksen purkamisessa.


Merklen arvoitukset (Merkle’s puzzles)

Salausmenetelmän kehitti Ralph Merkle 1978.(10) Salauksen ideana on se, että lähettäjä lähettää useita kryptattuja ”arvoituksia” vastaanottajalle. Vastaanottaja valitsee arvoituksista jonkin sattumanvaraisesti ja murtaa salauksen brute forcella, eli kokeilemalla kaikki vaihtoehdot läpi. Löydettyään ratkaisun vastaanottaja löytää selkokielisen tunnisteen ja sessioavaimen, joten vastaanottaja voi viestiä lähettäjälle löytäneensä tietyn avaimen. Jos joku haluaa murtaa viestinnän, tulee hänen murtaa jokainen lähettäjän lähettämistä arvoituksista ja kokeilla kaikkia vaihtoehtoja. Jos lähettäjä lähetti esimerkiksi miljoona arvoitusta ja vastaanottajalla kesti minuutti murtaa yksi valitsemansa arvoitus, salakuuntelijalla kestäisi pahimmassa tapauksessa miljoona minuuttia eli noin kaksi vuotta murtaa viestintä. Tämä tietenkin olettaen, että vastaanottajalla ja salakuuntelijalla on käytössään yhtä suuri laskentateho.(11)  

Diffie-Hellmanin menetelmä

Ensimmäinen julkisen avaimen menetelmä on Whitfield Diffien ja Martin Hellmanin 1976 julkaisema salausmenetelmä.(12)  Saman menetelmän oli keksinyt jo aiemmin Malcolm Williamson, mutta keksintö pidettiin sotasalaisuutena.(13)  Suurin osa asymmetrisestä salauksesta toimii edelleen Diffie-Hellmanin periaatteella. Se on jatkuvasti käytössä selaimissa, puhelimissa ja muissa sähköisissä kommunikointivälineissä. 

Diffie-Hellmanin toimintaperiaate on hyvin matemaattinen, mutta siitä löytyy myös yksinkertaistettuja analogioita. Periaatteessa lähettäjän ja vastaanottajan on sovittava yhdessä algoritmista G. Lähettäjä laittaa oman salaisen avaimensa algoritmiin ja lähettää tuloksen vastaanottajalle. Vastaanottaja taas laittaa oman salaisen avaimensa algoritmiin lähettäjän salaisen avaimen kanssa ja lopputuloksena kumpikin saa saman julkisen avaimen. Usein käytetty analogia on muodostettu väreillä. (Kuva 5) (14)

Kuva 5. Diffie-Hellman värianalogia


Matemaattisempi selitys avaintenvaihtoprotokollalle on hieman vaikeampiselkoinen. Menetelmä perustuu modulo-funktiolle, joka palauttaa jakojäännöksen ja se merkitään mod. Esimerkiksi 3/5 on yksi kokonainen ja jakojäännös on 2. Sama voitaisiin kirjoittaa modulon avulla 3 mod 5 = 2. Kumpikin viestijäosapuoli sopii pienestä g-alkuluvusta ja todella suuresta alkuluvusta n (g täytyy olla pienempi kuin n). Todella suuri tarkoittaa, että luvussa on yli 600 numeroa. Lähettäjä valitsee itselleen luvun a ja vastaanottaja valitsee itselleen luvun b. Lähettäjä muodostaa oman julkisen lukunsa A laskemalla 

ja vastaavasti vastaanottaja laskee itselleen julkisen luvun B



Koska julkinen luku on vain jakojäännös, joka on välillä 0 - (n-1), kukaan ei voi päätellä lähettäjän tai vastaanottajan omaa lukua. Koska g on julkinen, vastauksen voi periaatteessa laskea kokeilemalla kaikki vaihtoehdot. Luvut ovat kuitenkin niin massiivisen suuria, etteivät supertietokoneetkaan löydä niihin vastauksia järkevissä ajoissa. 

Vaihtaminen perustuu kahteen matemaattiseen kaavaan. Oletetaan, että 



joten tietenkin myös 


Toinen tarvittava kaava on potenssin laskusäännön kaava.


Tästä seuraa, että lähettäjä voi lähettää oman modulonsa vastaanottajalle ja vastaanottaja voi lähettää oman modulonsa lähettäjälle. Tämän jälkeen kumpikin heistä korottaa vastaanotetun modulon oman salaisen numeronsa potenssiin. Lähettäjä laskee siis


ja vastaanottaja laskee 


jolloin kumpikin saa kummallekin uuden, mutta keskenään saman modulon. 

Menetelmän vahvuus on suuressa alkuluvussa n. Jos n on liian pieni, voi hyökkääjä kokeilla kaikki a:n ja b:n arvot läpi, kunnes tulee samoihin julkisen avaimen lopputuloksiin. 

RSA

RSA-salauksen kehittivät Rivest, Shamir ja Adleman 1976 ja he antoivat salaukselle nimen, joka koostui heidän sukunimiensä ensimmäisistä kirjaimista.(16)  Tekniikkaa on verrattu siihen, että esimerkiksi pankki lähettäisi avoimia lukollisia laatikoita asiakkailleen. Asiakkaat voisivat laittaa viestinsä laatikkoon ja sen jälkeen lukita laatikon. Asiakkaalla ei ole avainta, joten hän tai kukaan muukaan ei voi enää avata laatikkoa. Laatikko lähetetään pankkiin, jossa laatikko saadaan helposti auki avaimella. 


RSA:n mekanismi perustuu kahteen matemaattiseen tekijään. Ensimmäinen on Fermat’n pieni teoreema, jonka mukaan 

, jossa x on mikä tahansa luku, p on jokin alkuluku ja n on jokin kerroin. Toisin sanoen, np on aina jokin alkuluvun p moninkerta. 

Tämän lisäksi Rivest, Shamir ja Adleman huomasivat, että on melkein mahdotonta löytää kahden suuren alkuluvun tulon tekijöitä. Tarkistaminen on todella helppoa, sen kuin vain kertoo nuo kaksi lukua yhteen ja tarkistaa tuleeko vastauksesta sama. He julkaisivat Scientific American -lehden ”matemaattisia ongelmia” -palstalla tehtävän, jossa oli 129-numeroinen luku. He kertoivat, että luku on tuotettu kertomalla kaksi alkulukua yhteen ja arvioivat ratkaisun löytämiseen kuluvan 40 kvadriljoonaa vuotta.(17) Vastaus löytyi kuitenkin jo 90-luvulla.(18) 

Avaimen luominen

RSA-avain luodaan kertomalla kaksi erittäin suurta ja satunnaisesti valittua alkulukua yhteen. Tämä tulo on osa julkista avainta. Tulo voi olla julkinen, sillä tekijöitä on hankala löytää. Tämän lisäksi julkisessa avaimessa on mukana eksponentti e, joka voi olla suhteellisen pienikin, esimerkiksi 16-bittinen luku. Valitaan salaiseen avaimeen eksponentti d siten, että 


, jossa d on salainen eksponentti, e on julkinen eksponentti ja p ja q ovat suuren luvun tekemiseen käytetyt suuret alkuluvut.

Salaaminen

Lähettäjä ottaa vastaanottajan julkisen avaimen ja käyttää sitä salauksen tekemiseen. Viesti muutetaan numeromuotoon ja merkki merkiltä korotetaan julkisen avaimen eksponentin mukaiseen potenssiin. Jos luvusta tulee suurempi kuin n, otetaan luvusta jakojäännös.


, jossa c on salattu viesti, m on numeeriseen muotoon muutettu viesti, e on julkisen avaimen eksponentti ja n on julkisen avaimen suurien alkulukujen tulosta saatu luku.

Salauksen purkaminen

Kun vastaanottaja on saanut viestin, hän saa purettua sen korottamalla sen jokaisen merkin potenssiin salaisen avaimensa potenssiin d.

, jossa m on selkokielinen viesti, c salattu viesti ja d salaisen avaimen eksponentti. Purku toimii, sillä 


, jossa c on salattu viesti, m on selkokielinen viesti, e on julkinen eksponentti, d on salaisen avaimen eksponentti ja n on suurten alkulukujen tulo.

Symmetrisen ja asymmetrisen salauksen vertailu

Asymmetristä ja symmetristä salausta voidaan tarkastella useista eri näkökulmista. Internetin aikana halutaan päivittäin ottaa salattuja yhteyksiä paikkoihin, joihin ei olla aiemmin otettu yhteyttä. Näihin tarpeisiin tarvitaan asymmetristä salausta, sillä mitään ennalta sovittua yhteistä salausta ei voida käyttää. Asymmetrinen salaus mahdollistaa turvallisten ja salaisten yhteyksien ottamisen. Asymmetrinen salaus on hitaampaa ja vaatii enemmän prosessoritehoa. Asymmetrisellä salauksella voidaan kuitenkin sopia yhdessä symmetrinen avain, jota käytetään kaikkeen muuhun tietoliikenteeseen. Tätä pyritään selittämään kuvassa 6. (19)

Kuva 6. Asymmetrisen ja symmetrisen salauksen hybridikäyttö



Kummallakin salauksella on vahvat puolensa, mutta internetin yhteydessä menetelmien hybridikäytöllä saadaan molempien parhaat puolet esiin. Asymmetrinen salaus tarjoaa salauksen ennalta tuntemattomien osapuolten kanssa. Symmetrinen tarjoaa vahvan salauksen suhteellisen vaivattomalla laskemisella. 


Lähteet

  1. CIA:n teksti yksinkertaisimmista salausmenetelmistä https://www.cia.gov/news-information/featured-story-archive/2007-featured-story-archive/cracking-the-code.html Luettu 23.03.2020
  2. Kuva Caesar Cipher https://en.wikipedia.org/wiki/Caesar_cipher Luettu 23.03.2020
  3. Vigenère-salaus https://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher Luettu 23.3.2020
  4. Homofoneettinen aakkosvaihto https://en.wikipedia.org/wiki/Substitution_cipher
  5. Eri kirjainten frekvenssit englannin kielessä http://pi.math.cornell.edu/~mec/2003-2004/cryptography/subs/frequencies.html 23.03.2020
  6. Suomen kielen kirjainten frekvenssit https://www.sttmedia.com/characterfrequency-finnish luettu 23.3.2020
  7. Kuva One Time Pad -salausavaimesta https://en.wikipedia.org/wiki/One-time_pad Luettu 23.3.2020
  8. Asymmetrisen salauksen algoritmien toimintaperiaate http://www.crypto-it.net/eng/asymmetric/index.html Luettu 23.3.2020
  9. Kuva julkisen ja yksityisen avaimen käytöstä https://en.wikipedia.org/wiki/Public-key_cryptography Luettu 23.3.2020
  10. Merkle, R. C. (1978). Secure communications over insecure channels. Communications of the ACM, 21(4), 294-299.
  11. Merklen arvoitukset https://en.wikipedia.org/wiki/Merkle%27s_Puzzles Luettu 23.3.2020
  12. Diffie, W., & Hellman, M. (1976). New directions in cryptography. IEEE transactions on Information Theory, 22(6), 644-654.
  13. Diffie-Hellmanin historiahttps://fi.wikipedia.org/wiki/Diffie%E2%80%93Hellman Luettu 23.3.2020
  14. Diffie-Hellman värianalogia https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange Luettu 23.3.2020
  15. Diffie-Hellmanin toiminta https://fi.wikipedia.org/wiki/Diffie%E2%80%93Hellman Luettu 23.3.2020
  16. Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital sig-natures and public-key cryptosystems. Communications of the ACM, 21(2), 120-126.
  17. Rivest, R. (1977). RSA-129-Challenge. Scientific American, August.
  18. Taubes, G. (1994). Small army of code-breakers conquers a 129-digit giant. Science, 264(5160), 776-778.
  19. Asymmetrisen ja symmetrisen salauksen vertailua. https://www.jscape.com/blog/bid/84422/Symmetric-vs-Asymmetric-Encryption Luettu 24.3.2020

Kommentit

Tämän blogin suosituimmat tekstit

Millaista on keskustella kreationistin kanssa?

Vastaus Vesa Kelan evoluutiokolumniin