TTKK / J.Koskinen / Tietoturvallisuuden perusteet, 2002

Kryptologiaa

Sisältö

[1] Symmetrisen salauksen idea;

[2] Kryptoanalyysi

[1] Yksisuuntainen tiivistys

[2] Yksisuuntainen funktio

[1] Lohkosalaus

[2] Lohkoalgoritmien moodit

Vuosalaus

[1] Julkisen avaimen algoritmit

[2] Allekirjoitus; Avaimen aitous

Kooste (kertaus tai esikatsaus)

(Symmetrinen) salakirjoitus Motivointia Tietotekniikka-alallakin voi epäilemättä pärjätä tietoturvallisesti ilman että tietää kryptologiasta muuta kuin sen olemassaolon. Tällä kurssilla tulee esille paljon muutakin, joskin silti melko minimaalisesti tekniikan yliopistotasoa ajatellen. Tämä sivu tarjoaa sille johdantoa joka hieman ylittää tuon olemassaolon tuntemisen. Sisältöä ja tavoitetta Tässä jaksossa on aluksi johdattelua salauksen ideaan, lähtien liikkeelle kerta-avainmenetelmästä. Sen jälkeen käsitellään hieman salauksen murtajan näkökulmaa. Tavoitekysymyksiä: Mihin perustuu kerta-avainkryptauksen turvallisuus ja mitä ongelmia järjestelmässä on? Mitä tarkoittaa salauksen murtaminen? Miksi se on vaikeaa? Millaiset lisätiedot voivat helpottaa sitä? Yhteyksiä Myös lohkosalausta koskevan jakson alussa on yleistä johdantoa salauksen ideaan.

(Symmetrinen) salakirjoitus

Lähettäjä ja vastaanottaja voidaan tulkita myös samaksi henkilöksi, joka vain tallettaa viestinsä eli jonkin tiedon myöhempää käyttöä varten niin että muut eivät saa siitä selvää. Henkilöiden tai heidän suoraan käyttämiensä koneiden sijasta osapuolet voivat olla vaikkapa tietoverkossa sijaitsevia reitittimiä.

Yleinen mekaanisiin lukkoihinkin pätevä periaate on, että algoritmia ei voi olettaa salaiseksi, ainoastaan avain on salainen. Koska avain on lukittaessa ja avattaessa sama, järjestelmää sanotaan symmetriseksi.

Esimerkki 1. Viesti eli selväteksti (tai ilmiteksti, 'plaintext') p = jono bittejä (keksitään luennolla), avain k = 0110101.... (kuulijoiden valitsema jatko), kryptoteksti c lasketaan biteittäin XOR-summana: c = p XOR k = .... . Operaatiota XOR (eli eXclusive OR, 'poissulkeva tai') merkitään yleensä rengastetulla plussalla, mutta kirjoitetaan tässä pelkkä +. Tällöin 0+0 = 1+1 = 0 ja 0+1 = 1+0 = 1. Soveltamalla tätä bittijonojen c, k ja p vastinbitteihin saadaan kryptotekstistä c helposti takaisin selväteksti p:

c+k = (p+k)+ k = p + (k + k) = p + 0-jono = p.

Esimerkki 2. Pitkää avainta on hankala käsitellä. Samaa lyhyttä avainta, esim. k₁ = 0110101 voisi tietysti toistaa, jolloin k olisi 0110101 0110101 0110101 0110101 ... . Jos viestin ajatellaan koostuvan samanmittaisista lohkoista p = p₁p₂p₃..., muodostuu kryptotekstistä c=c₁c₂c₃... sellainen, että c₁ XOR c₂ = p₁ XOR p₂ jne. Avaimen vaikutus eliminoituu siis täysin pareittain XOR-summatuista kryptolohkoista. Kryptoanalyytikolta ei kulu kauaakaan selvittää selvätekstiä p tilastollisilla analyyseilla, sillä varsinkin luonnollisen kielisissä viesteissä on runsaasti redundanssia - eli sitä samaa "ylimäärätietoa", jonka ansiosta luennoitsijan taululle kirjoittamasta tekstistä saa yleensä selvää, vaikka mistään yksittäin nähdystä kirjaimesta ei ehkä saisikaan, jos muut on pyyhitty pois sen ympäriltä.

Esimerkki 3. Jotain muuntelua voisi järjestää avaimelle k₁ = 0110101, jotta äskeiseltä ongelmalta vältyttäisiin. Muodostetaanpa "pseudoavain" k = k₁k₂k₃... seuraavasti: k_i+1 = luvun a * k_i seitsemän alinta bittiä, missä a on jokin k₁:stä riippuva luku, vaikkapa a = k₁. Saadaan k = 53, (2809 ==>) 121, (6413 ==>) 13, (699 ==>) 49, ... eli binäärijonona k = 0110101 1111001 0001101 0110001 ... . Seitsemän alimman bitin ottamisen voisi ilmaista hienommin jakojäännöksenä modulo 128 (=2⁷). Vastaava menettelyä käytetään näennäissatunnaislukujen muodostamisessa, joskaan jakajana ei silloin ole kakkosen potenssi. Modulaarinen aritmetiikka tavataan kurssin aikana vielä useaan kertaan.

Äskeinen avainta "venyttävä" salausperiaate on esimerkki vuokryptauksesta (stream cipher). Käytännössä venytysperiaatteen pitää olla mutkikkaampi (avainvuo, "key stream" vaikeammin arvattavissa) ja lähtökohtana olevan avaimen tietenkin paljon pitempi (esim 128 bittiä). Aiheeseen palataan toisaalla.

Symmetrinen salaus hyvällä algoritmilla antaa yksinkertaisella tavalla tehokkaan suojan sekä tiedon luottamuksellisuudelle että eheydelle. Paljon konstikkaampaa onkin sitten se, mitä pitää tehdä ennen kuin symmetristä salausta voidaan käyttää. On nimittäin sovittava yhteisestä avaimesta ja sitähän ei voida tehdä ainakaan symmetrisen salauksen avulla. (No, hyvä on, jos käytössä on entinen symmetrinen avain, niin mistä se sitten saatiin, tai sen edeltäjä jne ... ja jos tällaisessa tapauksessa jokin aiempi paljastuu niin, miten on turvallisuuden laita?). Yksi perusmenetelmä, jolla salausavaimesta voidaan sopia turvattoman kanavan ylitse, luonnostellaan toisaalla ja yksi käyttökohde tulee esille IPSec:n yhteydessä.

Murtaminen ja algoritmien turvallisuus

Esimerkiksi DES-algoritmia voidaan jo pitää heikkona, koska sen avain on vain 56-bittinen, ja kaikki vaihtoehdot läpikäyvä ns. raa'an voiman hyökkäys (brute force attack) on nykymahdollisuuksien rajoissa. Algoritmia sinänsä voi pitää onnistuneena, koska sitä on tutkittu "menestyksettä" erittäin laajasti alusta, eli 70-luvun puolivälistä asti.

Edellä sanotusta huolimatta ja toisaalta juuri sen vuoksi kryptoalgoritmin käyttäjän on syytä tuntea hyvin käsitteistö sekä algoritmien ja hyökkäysten perusluonne, jotta hän voi suhteuttaa käytäntöön algoritmien turvallisuutta koskevat tutkimustulokset - samoinkuin markkinahenkilöiden vakuuttelut tarjolla olevien menetelmien koetellusta turvallisuudesta.

Joka tapauksessa käytännön algoritmeissa, kerta-avaimen käyttöä lukuunottamatta, turvaudutaan laskennalliseen turvallisuuteen, mikä tarkoittaa sitä, että järjestelmän murtaminen tehdään hyvin työlääksi, mutta ei kuitenkaan mahdottomaksi.

Yksi tärkeä luokitus on sen mukaan, millaisin oletuksin algoritmit tarjoavat laskennallista turvallisuutta, eli kuinka voimakkaan vastustajan ne kestävät. Lähtökohtana on, että vastustaja tuntee algoritmin ja hänellä on salatekstiä, jonka hän haluaisi purkaa. Vastustajan voimakkuutta kuvaa se, mitä muuta hän tietää:

1. vain salateksti
2. tunnettu selväteksi: edellisen lisäksi vastustajalla on selväteksti-salateksti pareja (samalla avaimella salattuja kuin purettavakin teksti).
3. valittu selväteksti: vastustaja saa haltuunsa em. pareja joissa hän on voinut valita selvätekstin: hän on siis jotenkin pystynyt syöttämään salausalgoritmin läpi haluamiaan selvätekstejä vaikka ei tunnekaan avainta. Voimakkaammassa (ns. adaptiivisessa) versiossa hän pystyy aiempien tulosten perusteella valitsemaan uusia selvätekstejä.
4. valittu salateksti: kuten kohdassa 2, mutta vastustaja voikin valita salatekstin. Tehtäväksi tyypillisesti muodostuukin avaimen ratkaiseminen. Tilanne liittyy lähinnä julkisen avaimen systeemeihin.
5. valittu teksti: edelliset kohdat yhdessä.

Yksisuuntaista kryptografiaa Motivointia Jos ajatellaan salakirjoitusta, tuntuu välttämättömältä että tehdyn operaation pystyy purkamaan eli laskemaan käänteisfunktion. Yksisuuntainen tiivistäminen sotii tätä ajatusta vastaan ja on kuitenkin keskeinen apuväline kryptografiassa. Tavoitteiltaan helpommin ymmärrettävissä, mutta matemaattisesti haastavaa on sitten sellainen yksisuuntaisuus, joka joissain tapauksissa voidaan varustaa käänteistoimituksella. Tässä vaiheessa vain mainitaan näitä jälkimmäisen kaltaisia funktioita. Sisältöä ja tavoitetta Pääpaino on yksisuuntaisen tiivistämisen periaatteiden esitelyssä. Toisena asiana otetaan esille sellaiset yksisuuntaiset funktiot, joita voidaan julkisen avaimen kryptosysteemeissä salaluukun kautta kääntää. Tavoitekysymys on vain ensimmäisestä aihepiiristä: Miksei tarkistussumman laskeminen riitä kryptografisen tiivistämisen tarpeisiin? Mitä hash-funktioissa tehdään asian "korjaamiseksi"? Havainnollistusta Erillisellä sivulla voit laskea syöttämäsi tekstin MD5-tiivisteen. Kokeile, miten paljon tuo 32 heksadesimaalinumerona annettava tiiviste muuttuu kun muutat ascii-tekstissä yhden bitin jossain kohdassa. Yhden bitin ero on esim. kirjainpareilla B-C, D-E, ..., X-Y (ja samoin pienillä), joista ensimmäisen koodi on parillinen ja seuraavan pariton eli koodissa muuttuu viimeinen bitti.

Tarkistussumma ja yksisuuntainen tiivistefunktio

Tutuin esimerkki tarkistussummasta on henkilötunnuksen viimeinen merkki, joka on laskettu muista merkeistä. Vastaava merkitys on pankkisiirron viitenumeron viimeisellä numeromerkillä. Tällaisten tarkistussummien tarkoituksena on näppäily- ym. virheiden havaitseminen (vrt. myös eheys tietokannoissa)

Yksinumeroinen tarkistussumma voitaisiin periaatteessa laskea vaikkapa summaamalla kaikki numeromerkit ja ottamalla tulokseksi summan viimeinen numero. Näin lasketaan esim. pariteettibitti. Yleensä tarkistussumman algoritmi on monimutkaisempi, eikä kyse enää ole pelkästä summaamisesta. Esimerkiksi CRC:n (eli Cyclic Redundancy Check-menetelmän) ideana on lisätä bittilohkon perään tietty määrä (16 tai 32) bittejä siten, että tulos on jaollinen annetulla kiinteällä luvulla. Jos vastaanottaja ei saa jakoa tasan, lohkossa tai tarkistussummassa (eli FCS:ssä, Frame Check -Sekvenssissä) on tapahtunut muutos. Tätä menetelmää ei mutta lukuisia muita löytyy T. Vuoren laatimasta dokumentista Tarkistusmerkkien laskentamekanismeja, josta ilmenee myös miten moninaisissa yhteyksissä tarkistuksia käytetään.

Seuraavaksi esiteltävä yksisuuntainen tiivistäminen lisää tarkistusominaisuuteen kryptografista kätkemistä, joka on tarpeen, jottei esim. virus voisi viilata saastuttamaansa tiedostoa sellaiseksi, että se tuottaisi saman tarkistussumman kuin alkuperäinenkin.

Yksisuuntaisen tiivistefunktion eli hash-funktion (oikeastaan one-way hash function) tarkoitus on tuottaa viestistä (yleisemmin bittijonosta) kiinteän mittainen, lyhyt "tiivistelmä", joka edustaa koko viestiä sikäli, että on vaikea löytää mitään muuta viestiä, jolla olisi samanlainen tiiviste. Koska tiivisteen pituus on tyypillisesti 128 tai 160 bittiä ja viesti voi olla miten pitkä hyvänsä, on tietenkin olemassa runsaasti viestejä, joista tulee sama tiiviste, mutta oleellista on, ettei yhtään niistä pysty löytämään. Tiivisteestä (hash) käytetään myös nimityksiä 'digital fingerprint' tai 'message digest' (MD).

Tiivistefunktiolta H edellytetty yksisuuntaisuus merkitsee siis sitä, että kun on annettu h, ei voida millään kohtuullisella vaivalla löytää x:ää, jolle olisi H(x)=h. Usein vaaditaan enemmän: ei saisi löytyä yhtään paria viestejä jotka "törmäävät" eli tiivistyvät samaksi h:ksi - joko niin, että vaatimus koskee mitä tahansa h:ta tai niin, että mitään annettua x:ää kohti ei saa löytyä (eri) y:tä, joka toteuttaisi ehdon H(x)=H(y).

Yleinen yksisuuntaisen tiivistämisen periaate: käytetään "kutistusfunktiota" (compression function (!)), jolle syötetään iteratiivisesti aiempi kutistustulos ja seuraava viestilohko (kumpikin esim. 128 bittiä). Alussa tarvitaan alustusvektori (siis "nollas" kutistustulos) ja viestin täydennys lohkon monikerran mittaiseksi (täydennystä voidaan tehdä myös lohkokohtaisesti). Useimmiten viestin loppuun liitetään sen pituus. Kutistusvaiheen jälkeen voidaan tehdä vielä jokin toisenlainen muunnos.

Tunnetuimmat (yksisuuntaiset) tiivistealgoritmit kuuluvat MD4-perheeseen, jonka kehitystä (joka tapahtui 1990-luvun alkupuoliskolla) kuvaa seuraava kaavio:

MD4 --> MD5 ----->  SHA --> SHA-1
 | \___________
 |             \
ext-MD4 ---->  RIPEMD   ------->    RIPEMD-160

Yksisuuntaisella funktiolla tarkoitetaan yleensä sellaista injektiivistä funktiota f, jolle arvon x laskeminen arvosta f(x) on käytännössä mahdotonta. Arvon f(x) laskeminen x:stä sen sijaan ei saa olla vaikeaa. Seuraavassa on esimerkkejä yksisuuntaisista funktioista. Kaikille niistä on ominaista, että parametreina olevat luvut ovat suuria, useamman sadan desimaalinumeron pituisia.

• Diskreetti eksponenttifunktio: f(x) = g^x mod p, missä p on alkuluku ja g on primitiivinen eli sellainen että g^x käy läpi kaikki luvut 1,...,p-1, kun x käy 0,...,p-2.
• Neliö: f(x) = x² mod p*q   (oletus: luvut p ja q salaisia ja p,q=3 mod 4)
• RSA-funktio f(x) = x^e mod p*q   (oletus: luvut p ja q salaisia ja lukujen e ja (p-1)(q-1) suurin yhteinen tekijä on 1)
• Osajoukkosumma (sub-set sum): n:n mittainen bittivektori x kuvataan skalaarituloksi x.A, missä vektorin A n alkiota ovat likimain tasan jakautuneet välille 1,..., 2ⁿ (x:n selvittäminen osajoukkosummasta x.A on ns. selkäreppuprobleema, knapsack problem)

Lohkosalaus eli blokkikryptaus moodeineen Motivointia Symmetriset salausalgoritmit ovat käytännössä välttämättömiä, jos tietoa halutaan välittää luottamuksellisesti. Muina keinoina voisi tietysti ajatella steganografiaa, julkisen avaimen kryptosysteemejä tai kuriireja, mutta ne eivät riitä nykyajan tietoliikenteen vaatimuksiin. Salauksen käyttäjän ei ole välttämätöntä tietää, miten algoritmi tarkkaan ottaen toimii, mutta jonkinlainen käsitys pitää olla perusteeksi algoritmeja kohtaan tunnetulle luottamukselle, ja myös sen vuoksi että pystyy ymmärtämään niiden turvallisuudesta raportoivia tutkimustuloksia. Sisältöä ja tavoitetta Esitellään lohkosalauksen yleistä ideaa, Feistel-periaatetta, mainitaan DES- ja AES-algoritmit. Lisäksi esitellään lohkosalauksen käytön moodit ECB, CBC, CFB ja OFB. Mitä samanlaista ja mitä eroa on (symmetrisessä) lohkosalauksessa ja yksisuuntaisessa tiivistämisessä (eli kryptografisessa hash-funktiossa)? Miksi lohkosalausalgoritmeja ei välttämättä kannata käyttää elektronisen koodisanakirjan tavoin (eli ECB-moodissa)? Millä tavoin turvallisuutta voidaan parantaa?

Lohkosalaus eli blokkikryptaus

Edellä mainitut kaksi periaatetta tulevat selvimmin esille lohkosalauksessa, jossa algoritmia sovelletaan yhteen viestilohkoon eli kiinteään määrään viestibittejä kerrallaan. Kyseessä on siis funktio, jolla on parametrina avain ja joka muuntaa jokaisen n-bittisen vektorin joksikin toiseksi samanmittaiseksi. Pidentäminen olisi tilan haaskausta ja lyhentävää funktiota taas ei voisi kääntää. Kompressio ennen kryptausta on sitten eri juttu (ja varsin suositeltava, koska se vähentää selvätekstin redundanssia). Tyypillinen n eli lohkon koko on 64 tai 128.

Oheisessa kuvassa sovelletaan yksinkertaista lohkoalgoritmia viiden tavun mittaiseen selkotekstiin. Avaimena tässä on (tai sellaiseksi voidaan tulkita) lukunelikko (25413, 1, 3, 2). Ensimmäinen ilmaisee permutaation (yhden 125 mahdollisesta), kaksi seuraavaa siirtojen pituudet ja neljäs kierrosten lukumäärän.

Lohkoalgoritmilla salattaessa ajetaan siis aina yksi tekstilohko kerrallaan koko algoritmin läpi. Algoritmin käyttötavasta (moodista) riippuen tekstinä voi tosin olla muutakin kuin pelkkää selvätekstiä tai ei lainkaan sitä ja kryptotekstiä voi kerralla muodostua vähemmän kuin lohkon verran (moodeista on kerrottu erikseen).

Useimmat algoritmit pohjautuvat Feistel-periaatteeseen: On jokin kiinteä funktio f, jota sovelletaan avaimeen (tai siitä laskettuun lukuun) ja viestin loppupuolikkaaseen. Tulos XOR-summataan viestin alkupuolikkaan kanssa. Seuraavaa kierrosta varten puolikkaat vaihdetaan, eli loppuun tulee äskeinen summa ja alkuun äskeinen loppupuolikas sellaisenaan. Kierroksia tehdään tietty määrä. Joka kierroksella käytetään avaimesta eri tavalla muodostettua osa-avainta. Salauksen purku ei edellytä funktion f kääntämistä vaan XOR-operaation ominaisuuden ansiosta riittää toistaa samat kierrokset, kunhan osa-avainten muodostama jono käydään lopusta alkuun.

Valitsemalla erilaisia funktioita f, ja erilaisia osa-avainjonoja (eli avainsekvenssejä), saadaan erilaisia algoritmeja. On myös useita läheisiä muunnoksia Feistel-periaatteesta.

DES on vuonna 1977 standardoitu algoritmi, joka muodostuu 16 Feistel-kierroksesta. Avain on 56-bittinen. Joka 8:nneksi lisätään pariteettibitti, joten avain näyttää 64-bittiseltä. Lohkon koko on 64. Yksi tapa parantaa DES:n turvallisuutta on käyttää sitä kolminkerroin kahdella avaimella k₁ ja k₂. Merkitään: E_i = kryptaus ja D_i = dekryptaus avaimella k_i. Viestin M triple-DES-kryptaus on E₁( D₂ ( E₁( M))). (Kolmeakin eri avainta voi tietysti käyttää, kuten PGP:ssä tehdäänkin, mutta em. tekniikka on standardoitu.)

DES oli alunperin IBM:n ehdotus standardiksi vuodelta 1974. DES:n seuraajaksi tarkoitetun AES:n (Advanced Encryption Standard) luominen alkoi vuoden 1997 alussa. Virallinen kutsu ehdotuksille oli syyskuussa 1997. Elokuussa 1998 ensimmäisen AES-konferenssin yhteydessä NIST (National Institute of Standards and Technology) julisti 15 virallista ehdokasta julkisesti tutkittaviksi. Toinen konferenssi pidettiin maaliskuussa 1999. Ensimmäisen kierroksen julkinen kommentointiaika päättyi huhtikuussa 1999. Elokuussa 1999 julkistettiin loppukilpailuun hyväksytyt algoritmit, jotka ovat nimeltään MARS, RC6, Rijndael, Serpent ja Twofish. Lokakuussa 2000 standardoitavaksi valittiin Rijndael ja joulukuussa 2001 standardi oli valmis. [NIST:n AES-sivusto]

Lohkoalgoritmien (käytön) moodit

Useimmiten on syytä käyttää jotain seuraavista ketjuttavista moodeista, joissa seuraavan lohkon kryptaus riippuu aiemmista. Kaikissa niistä tarvitaan yhden lohkon mittainen alustusvektori (IV) eli bittijono, joka toimii lohkoalgoritmin ensimmäisenä syötteenä. Sen ei tarvitse olla salainen, mutta sen on syytä olla joka kerta uusi - ainakin OFB-moodissa.

• CBC, Cipher Block Chaining: edellinen kryptotekstilohko XOR-lisätään seuraavaan selvätekstilohkoon ennen sen kryptaamista.

  Seuraavissa kahdessa moodissa kryptotekstiä tuotetaan r bittiä kerrallaan (esim r=8) ja ne muodostetaan XOR-summana r:stä seuraavasta selvätekstibitistä ja r:stä bitistä, jotka on katkaistu lohkoalgoritmin tuottamasta tuloksesta (vasemmalta). Moodit eroavat siinä, miten lohkoalgoritmia käytetään:

• CFB, Cipher Feedback Mode: lohkoalgoritmin syötteenä on aiempi syöte, josta on katkaistu vasemmalta r bittiä ja liitetty oikealle edelliset r kryptobittiä.
• OFB, Output Feedback Mode: lohkoalgoritmilla kryptataan alustusvektoria yhä uudestaan.

Eri moodeilla on paitsi erilaiset kryptologiset ominaisuudet myös erilainen kyky toipua kryptotekstiin siirron aikana tulleista virheistä.

Harjoitus: Päteekö kaikkiin em. moodeihin seuraava? Jos salausalgoritmia sovellettaessa käytetään joka kerta eri avainta (tai jopa eri algoritmia, jossa on kuitenkin sama lohkokoko), niin salauksen purku onnistuu entiseen malliin, kunhan eri avaimia (algoritmeja) käytetään samassa järjestyksessä.

Vuokryptaus Motivointia Kryptologian yleisen motivaation lisäksi vuosalaukseen tutustumisen perusteena voi pitää sitä, että lähes jokainen käyttää sitä päivittäin GSM-puheluissaan. Sisältöä ja tavoitetta Esitellään vuosalauksen toteutusta lohkosalaajalla ja lineaarisella siirtorekisterillä. Tavoitekysymys: Jos käytössäsi on lohkosalausalgoritmi, jossa lohkokoko on 8 tavua, miten saat siitä vuosalausalgoritmin, jolla voit salata esim. 9 tavun mittaisen tekstin niin että tuloskin on vain 9 tavua? Vaikka käytössäsi olisi loistava lohkosalausalgoritmi, miksi saattaisit silti päätyä vuosalauksen käyttöön etkä rakentaisi sitäkään ko. lohkosalaajasta? Millaista tekniikkaa voisit käyttää? Yhteyksiä Vuokryptauksen perusideaan johdatellaan symmetrisen salauksen esittelyn yhteydessä. Tässä jaksossa on hyödyksi, jos on tutustunut lohkoalgoritmien käytön moodeihin.

Vuokryptaus

Selvätekstiin summattavaa bittijonoa sanotaan myös avainvirraksi tai -vuoksi (key stream) ja sen mukaisesti kryptausmenetelmää sanotaan vuosalaukseksi tai jonosalaukseksi (stream cipher). Hyvässä algoritmissa avainvirta muodostetaan kryptografisesti vahvalla satunnaislukugeneraattorilla, mikä tarkoittaa, että seuraavaa bittiä ei pysty ennustamaan, vaikka edelliset olisikin saanut selville. Tämähän ei päde tavallisissa satunnaislukugeneraattoreissa, vaikka ne olisivat tilastollisilta ominaisuuksiltaan kuinka hyviä.

Jos avainvirta on riippumaton selvätekstistä (kuten esim. lohkoalgoritmin OFB-moodissa), se voidaan vaikkapa laskea etukäteen, mutta vastaanottajan avainvirran täytyy olla samassa vaiheessa lähettäjän virran kanssa. Tällaista vuokryptausta sanotaan synkroniseksi. Voidaan myös muodostaa ns. itsesynkronoivia systeemejä, jotka toipuvat automaattisesti häiriöistä. Perusidea on se, että avainvirta riippuu vain avaimesta ja tietystä rajoitetusta määrästä aiempia kryptotekstibittejä (näin on vaikka selvätekstibiteistä kaikki aiemmat vaikuttavat kryptotekstiin). Tavallisin tällainen systeemi on lohkoalgoritmin CFB-moodi, jossa r=1 (eli kunkin lohkosalauksen tuloksesta käytetään vain yksi bitti).

Vaikka vuosalaus voidaan toteuttaa lohkoalgoritmin avulla, näin ei tehdä silloin kun tavoitellaan suurta salausnopeutta. Yleensä vuokryptaus toteutetaan lineearisilla takaisinkytketyillä siirtorekistereillä (linear feedback shift registers, LFSR). Kovototeutuksina näin päästään tyypillisesti suurempiin nopeuksiin kuin lohkoalgoritmeilla. Pienten puskureiden tai tiukkojen reaaliaikavaatimusten yhteydessä, esim. telekommunikaatiossa vuosalaus on usein välttämätöntä (vrt. kaapeli-TV:n tai puhelun "scrambler" tai GSM-puhelun kryptaus radiotiellä).

LFSR koostuu n:stä yhden bitin rekisteristä R₀, R₁, ..., R_n-1, joihin on aluksi syötetty jotkin alkuarvot (avaimen bitit kryptauskäytössä). Kellon antaessa sykäyksen bitit siirtyvät ("shift") yhtä pienempään rekisteriin siten, että R₀:sta muodostuu rekisterin ulostulo. Tämä bitti syötetään samalla toiseen päähän ("feedback") eli rekisteriin R_n-1, kuitenkin siten, että siihen on XOR-summattu ("linear") joidenkin muiden rekisterien sisältö.

Kun siirtorekisterillä on jokin alkutila, se tulostaa bittijonon, joka toteuttaa tietyn lineaarisen rekursioyhtälön ja on jaksollinen. Jakson pituus on korkeintaan 2ⁿ-1. Tämä maksimaalinen jakso saavutetaan (kaikilla ei-nollilla alkutiloilla), mikäli takaisinkytkettävät rekisterit valitaan jonkin n:ttä astetta olevan ns. primitiivisen polynomin kertoimien mukaisesti.

Esimerkiksi polynomi on 1+x+x⁴ on primitiivinen ja vastaava rekursioyhtälö on s_i = s_i-1 + s_i-4 modulo 2 (i >=4). Tässä s_i vastaa polynomin 1:ä, s_i-1 vastaa x:ää ja s_i-4 x⁴:ää. Modulo 2 -laskun, eli XOR:n, mukaanhan + on sama kuin - ja yhtälö on yhtäpitävästi 0 = s_i + s_i-1 + s_i-4 modulo 2.)

Alkuarvoina ovat s_i, i=0,1,2,3. Ne ovat myös R_i:den alkutilat ja neljä ensimmäistä ulostuloa. Viidennestä eli s₄:stä eteenpäin ulostulo saadaan yhtälön mukaisesti.

Harjoitus. Jos ulostulossa jossain vaiheessa esiintyy ....1110 (eli viimeisenä tuli 0), laske seuraavat kaksi bittiä. Ohje: Käytä yhtälöä tai: Piirrä 1,1,1 ja 0 vierekkäisiin ruutuihin, merkitse takaisinsyöttö vasemmalta oikealle ja kytke siihen 0:n kohdalta XOR ja ala siirrellä. Tulosta vasemmalta. Miksei tarvinnut tietää varsinaista alkutilaa?

LFSR:n lineaarisuutta häivytetään vuokryptausalgoritmeissa kytkemällä useita sellaisia erityisin tavoin toisiinsa. Esimerkiksi GSM:n A5-algoritmissa on kellon kontrolloimina kolme LFSR:ää, pituuksiltaan 19, 22 ja 23. (Lisää A5:stä toisaalla.)

Julkisen avaimen kryptosysteemit, RSA, allekirjoitus Motivointia Harva nykyaikainen turvaratkaisu tietoverkossa olisi olemassa ilman julkisen avaimen kryptologiaa. Se pohjautuu matematiikkaan, lähinnä lukuteoriaan, pitkälti toisin kuin symmetrinen, salaisen avaimen kryptologia. Yhtä lailla kuin on hyvä ymmärtää miten viimeksi mainitussa saadaan aikaan riittävästi diffuusiota ja konfuusiota bitteihin, on motivoitua tuntea julkisen avaimen menetelmien perusteita matematiikasta alkaen. Sisältöä ja tavoitetta Viimeiseen tavoitekysymykseen pystyy vastaamaan tämänkin sivun perusteella, mutta PKI:n tuntemisesta on varmasti apua. RSA-kryptosysteemissä on julkiset avaimet n (moduuli) ja e (salauseksponentti) sekä niitä vastaava yksityinen avain d (purkueksponentti). a) RSA:n turvallisuus perustuu siihen, että luvuista n ja e ei saa selville lukua d missään järkevässä ajassa. Pelkästään luvuista n ja d ei myöskään saisi selville lukua e. Miten avaimen laatija sitten on hoitanut asian? b) Lukua d voi käyttää myös allekirjoituseksponenttina, jolloin e on allekirjoituksen todennuseksponentti. Miksei samoja avaimia n, e ja d pitäisi kuitenkaan käyttää molempiin tarkoituksiin, eli salaukseen ja allekirjoitukseen? Rabinin kryptosysteemissä on julkinen avain n ja yksityiset avaimet p ja q. (p ja q ovat suuria alkulukuja, joiden jakojäännös modulo 4 on 3; n=pq.) a) Miten salataan viesti m, joka halutaan lähettää n:n omistajalle ja miten tämä saa sen auki? (Jälkimmäisessä ei vaadita tarkkoja kaavoja mutta sellainen tarkkuus kylläkin että syy redundanssin käyttötarpeelle selviää.). b) Jos avain n eli moduuli on 500-bittinen ja viesti m on 100-bittinen, mitä m:lle pitää tehdä ennen salauksen soveltamista? c) Jos viesti onkin sitten 100 000-bittinen, se pitäisi käsitellä 200 lohkona. Miksei näin kuitenkaan yleensä tehdä ja mikä on tavallisempi menettely (kuten RSA:ssakin)? Esittele kolme erilaista tapaa, joilla henkilö A voi vakuuttaa etäällä olevan henkilön B siitä, että K on A:n julkinen avain. Ainakin yhden tavan pitää toimia ilman kolmatta osapuolta ja ainakin yhdessä sellainen pitää olla. Yhteyksiä Tämän sivun asioita käytetään monessa yhteydessä. Erityinen liittymäkohta on kuitenkin PKI, joka jatkaa julkisen avaimen aitousongelman selvittelyä.

Julkisen avaimen kryptosysteemit, RSA, allekirjoitus

Harjoitus: modulaarista aritmetiikkaa

(2) Katsotaan, mitä tapahtuu, kun moduulina on 21 eli kahden alkuluvun tulo: Huomataan ensin, että 3:lla tai 7:llä jaolliset luvut ovat sikäli kehnoja, että ne "jakavat nollan" eli ne voivat olla toisena tekijänä kertolaskussa, jonka tulos on 0 eli jaollinen 21:llä. Tutkitaan siis vain lukuja, joissa ei ole tekijänä 3:a eikä 7:ä, eli sellaisia joiden syt 21:n kanssa on 1. Näitä osoittautuu olevan 12, joka on = (7-1)(3-1) eli Eulerin phi-funktio arvolla 21. (Kyseiset luvut muodostavat multiplikatiivisen ryhmän modulo 21. Edellä laskettiin sellaisessa modulo 7. Phi arvolla alkuluku p on p-1.)

Lasketaan toiset potenssit, toteamalla etukäteen että x:llä ja sen vastaluvulla eli (21-x):llä on sama neliö. Katsotaan, minkä verran luvuilla on neliöjuuria. Yritetään generointia potenssiin korottamalla. Osoittautuu että viimeistään 6. potenssi on aina 1 (ja usein jo 2. tai 3.; erityisesti generaattoria ei siis ole eli ryhmä ei ole syklinen. Silti aina myös Phi's eli 12. potenssi on 1.)

Julkisen avaimen idea, Rabinin systeemi

Mitäpä sitten, jos joku tunteekin p:n ja q:n? Tällöin hän voi laskea erikseen x:n neliöjuuret modulo p ja modulo q, sillä kun moduulina on alkuluku (joka on =3 mod 4), on olemassa tehokkaita algoritmeja neliöjuuren laskemiseen. Yhdistelemällä kaksi juurta modulo p ja kaksi juurta modulo q hän saa selville neljä ehdokasta x:ksi. Jos x:ään on koodattu jokin viesti, jossa on mukana hieman redundanssia (esim. luonnollista kieltä tai tarkistussumma), niin viesti erottuu ratkaisujen joukosta. Lievä epäinjektiivisyys ("4-to-1") ei siis haittaa.

Jos p ja q ovat riittävän suuria alkulukuja, niiden tuloa n on erittäin vaikea jakaa tekijöihin, joten valittuaan p:n ja q:n satunnaisesti, käyttäjä voi huoletta paljastaa n:n ja antaa toisten lähettää "neliö"viestejä hänelle. Kukaan muu ei niitä saa auki. Tämä on julkisen avaimen kryptografiaa ja luonnosteltu systeemi kantaa Rabinin nimeä (vuodelta 1979). Tämän systeemin murtaminen on yhtäpitävää luvun n tekijöihinjakamisen kanssa, seikka jota ei ole voitu todistaa seuraavaksi esiteltävästä RSA:sta.

Yleisesti salausavain (edellä "n") voi siis olla kaikkien saatavilla eli se on julkinen avain. Purkamiseen tarvitaan tietenkin jokin salausavaimesta riippuva tieto, ns. yksityinen, tai salainen, avain (tässä "p ja q"). Se, että nämä ovat erilaiset, antaa aiheen kutsua julkisen avaimen systeemejä myös epäsymmetrisiksi kryptosysteemeiksi. Joissain tapauksissa, kuten edellä, algoritmikin on hyvin erilainen eri suuntiin. Sitä, että julkisen avaimen laatija tietää, mitä sen takana on (tässä siis tekijöihinjako), sanotaan salaluukuksi (trapdoor). Kaikissa julkisen avaimen systeemeissä on jokin vastaava rakenne. Julkisella avaimella salatun viestin murtajalla on edessään jokin vaikealta näyttävä ongelma, joka ei ole lainkaan hankala, jos vain tuntee salaluukun.

RSA

Kannattaakin muodostaa ns. digitaalinen kirjekuori. Valitaan satunnainen symmetrisen salausalgoritmin avain k ja salataan viesti sen avulla. Salataan sitten k käyttäen vastaanottajan julkista RSA-avainta. Lähetetään nämä salatekstit vastaanottajalle yhdessä asianmukaisten otsikkotietojen kanssa, joilla tyypillisesti yksilöidään käytetyt algoritmit ja se mitä julkista avainta on käytetty. Näin vastaanottaja tietää, mitä viestin osille pitää tehdä. Tällaista menettelyä käytetään usein osana jotain laajempaa protokollaa, joista tällä kurssilla esiintyy PGP.

RSA:n kehittivät ja sittemmin patentoivat Rivest, Shamir ja Adleman. Alkuperäinen artikkeli vuodelta 1978 on "A method for obtaining digital signatures and public key cryptosystems".

Allekirjoitus

• sen pitää riippua allekirjoitettavasta dokumentista sekä jostain tiedosta, joka on ja jonka tiedetään olevan vain allekirjoittajan hallussa.
• sen tuottamisen, tallettamisen, tunnistamisen ja tarkastamisen (todentamisen) pitää olla suhteellisen helppoa.
• väärentämisen pitää olla laskennallisesti mahdotonta: ei annettuun allekirjoitukseen sopivaa uutta dokumenttia eikä annettuun dokumenttiin sopivaa allekirjoituksta.

Epäsymmetrisillä kryptosysteemeillä voidaan saada aikaan todellisia digitaalisia allekirjoituksia. Perusidea on, että allekirjoittaja A luo epäsymmetrisen avainparin (V,S) ja sitoo julkisesti avaimen julkisen osan V (=verifiointiavain) omaan identiteettiinsä ja käyttää salaista osaa S (=signeerausavain) dokumenttien allekirjoittamiseen. Kuka tahansa B voi vakuuttua allekirjoituksen aitoudesta, koska vain A on voinut laatia ne: vain A tuntee S:n ja vain S:llä allekirjoitetun dokumentin voi verifioida V:llä. Lisäksi A:n julkinen sitoutuminen V:hen saa aikaan sen, ettei hän voi kiistää S:llä allekirjoitettuja dokumentteja - paitsi yrittämällä väittää, että hänen avaimensa on paljastunut. Periaatteessahan mistä tahansa julkisesta avaimesta voi laskea vastaavan salaisen avaimen. Yksilöitä ja avaimia toisiinsa sitovien järjestelmien täytyy tämän vuoksi olla varuillaan, ettei kukaan yritä ottaa käyttöön helposti murrettavaa julkista avainta, jolloin myöhemmin esitettävälle murtumisväitteelle olisi ikäänkuin jälkikäteen löydettävissä selityskin.

RSA soveltuu epäsymmetrisistä systeemeistä sikäli luontevimmin allekirjoitukseen, että julkisen ja salaisen eksponentin roolit ovat matemaattisessa mielessä symmetriset (vrt. eo. laskelma, kyse on kommutatiivuudesta). Allekirjoitusta varten avaimia vain käytetään toisessa järjestyksesä kuin salauksessa. Dokumentin m allekirjoitus s muodostetaan salaisella eksponentilla d laskemalla s=m^d mod n. Kun m ja s lähetetään yhdessä, kuka tahansa, joka tuntee vastaavan julkisen avaimen e, voi verifioida eli todentaa, että m = s^e mod n.

Symmetrisellä algoritmilla salattavan viestin redundanssilla on merkitystä puretun viestin aitouden todentamiselle. Vastaava pätee epäsymmetristen systeemien allekirjoitukseen. Koska RSA:n tapauksessa pelkästä potenssista s=m^d mod n saa selville koko m:n, ei m:ää tarvitsisi välttämättä liittää mukaan, jos siinä on redundanssia. Toisaalta, kuten on jo todettu, RSA:n eksponenttilasku on hidas operaatio, minkä vuoksi yleensä vain viestin tiivistelmä allekirjoitetaan. Lähetys on siis:   m, (H(m))^d mod n,   missä H on hash-funktio.

Julkisen avaimen aitousongelma

• Avaimen julkaiseminen lähettämällä se viestin mukana (tai nykyisin:) www-sivulla tai uutisryhmässä jne.: ei mitään takeita aitoudesta, mutta jotain rinnakkaista kanavaa, esim. puhelinta voi kyllä käyttää varmistumiseen.
• Julkisesti nähtävillä oleva avainhakemisto: luotettu osapuoli (T) ylläpitää, hakemistoon rekisteröidytään autentikoidulla tavalla (esim. paikan päällä), avainta voi vaihtaa, tietokanta tai sen muutokset julkaistaan ajoittain, avaimen haku kannasta autentikoidaan, esim. seuraavasti:
  T:llä on oma julkinen avain, jonka jokainen asiakas tuntee luotettavasti. Asiakas A, joka aikoo kommunikoida B:n kanssa, pyytää B:n julkista avainta hakemistosta ja saa sen viestissä, jonka T on kryptannut yksityisellä avaimellaan (yleisemmin: allekirjoittanut). Sitten A lähettää viestin B:lle, joka pyytää A:n julkisen avaimen ja saa sen T:ltä vastaavasti kuin A. Tämän jälkeen molemmilla on toisen osapuolen aito julkinen avain ja ne voivat sopia esim. symmetrisestä avaimesta autentikoidusti.
• Avainten varmentaminen eli sertifiointi: Jokainen asiakas luo oman julkisen avaimensa ja hakee sille sertifikaatin varmenneviranomaiselta T (certificate authority). Kaikkien osapuolten on voitava luottaa T:hen, erityisesti siihen että T todentaa jokaisen asiakkaansa henkilöllisyyden. Varmenne koostuu asiakkaan nimestä ja julkisesta avaimesta, jotka T on allekirjoittanut.

Harjoitus: Miksi luotettu osapuoli on sitä luotettavampi mitä vähemmän se luottaa sinuun? Keksi esimerkkejä.

Harjoitus: Jos sinun pitää osoittaa henkilöllisyytesi, niin miksei se ei onnistu paperille kirjoittamasi allekirjoituksen avulla? Miten digitaalinen allekirjoitus muuttaa tilannetta?

Kryptologia, kooste/kertaus Motivointia Heti kun tietoa aletaan tallettaa ja siirtää digitaalisessa muodossa, tietoturvan toteutuksessa aletaan tarvita kryptologisia menetelmiä. Koska niitä on erilaisia eri tarkoituksiin, on syytä myös jäsentää hieman kokonaisuutta. Sisältöä ja tavoitetta Tämän sivun sisällön tiivistää ensimmäinen tavoitekysymys. Toinen kysymys on hieman soveltavampi. Kumpikin on ollut tentissä. Mitä erityyppisiä kryptografisia primitiivejä tietoturvan toteuttamiseen voidaan käyttää: Luettele erityyppiset menetelmät jaotellen sen mukaan, millaista avainta niissä käytetään. Kaikki kryptografia ei ole tiedon salaamista - eikä vesileimausta (josta oli samassa tentissä eri kysymys). Esittele kolme kryptografista algoritmi- tai protokollatyyppiä, joiden tavoite on jokin muu. Mainitse ainakin kahteen niistä jokin toteutus nimeltä, siis itse algoritmi tai protokolla eikä kokonaisuus, jonka osana se on. Yhteyksiä Tässä ei ole kerrattu kryptoprotokollien olemusta, vaikka ne ovatkin olennainen osa kryptologiaa. Niistä on melko tiivis yleisesitys toisaalla.

Kryptologia, kooste/kertaus

Suuri osa varsinkin perinteisestä tietoturvasta on silti toteutettavissa ilman salakirjoitusta, mutta mitä enemmän tieto on pelkästään digitaalisessa muodossa ja mitä enemmän sitä siirretään tietokoneiden välillä, sitä enemmän tarvitaan salausta ja muita kryptografisia toimintoja. Kaikissa niissä ei käytetä lainkaan avainta ja toisaalta on järjestelmiä, joissa yhteen suuntaan toimiva avain on hyödyllinen vasta julkaistuna ja vieläpä varmennettuna. Tällöinkin toiseen suuntaan toimivan avaimen on pysyttävä salassa.

Sopivilla ja riittävän turvallisilla kryptografisilla algoritmeilla ja niitä käyttäen rakennetuilla protokollilla voidaan luoda pohja useimpien tietoturvatavoitteiden toteuttamiselle, kunhan rakennetaan turvallinen implementaatio ja sille puolestaan turvallinen installaatio.

Kryptografisten primitiivien luokittelu

• Avaimettomat:
  • tiivistefunktiot (hash functions; MD2, MD4, MD5, SHA, RIPE-MD). Perusidea: jos vastaanottaja laskee viestistä tiivisteen ja saa saman kuin lähettäjä uskottavasti väittää, niin viestiä ei ole matkalla muutettu (ks. esimerkkejä ja nopeusvertailuja RIPE-MD:n sivulta).
  • Yksisuuntaiset funktiot, jotka voivat olla bijektioita, mutta joita ei pystytä kääntämään, eli ei ole salaluukkua. (Tällä kurssilla: eksponenttifunktio modulo alkuluku, eli yksisuuntainen permutaatio, joka on Diffie-Hellmanin protokollan perustana.)
  • satunnaisjonot, eli aidot satunnaisluvut, joita ei pysty ennustamaan edellisten perusteella (käytännössä taustalla oltava jokin fysikaalinen ilmiö).
• symmetrinen avain eli molempiin suuntiin sama :
  • symmetrisen avaimen salaus: lohkosalaus (block cipher, DES, IDEA, Skipjack, RC2, RC5, tuleva AES; sovelletaan erilaisissa moodeissa ECB, CBC, OFB, CFB) ja vuosalaus (stream cipher; A5, RC4, SEAL, unixin crypt), (ks. AES-painotteinen lohkoalgoritmikatsaus)
  • avaimelliset tiivistefunktiot (MAC:t eli message authentication codes): edellä hash-funktioiden kohdalla mainitun eheyden lisäksi tässä vakuututaan myös viestin lähteen autenttisuudesta.
  • allekirjoitus (joka ei tosin takaa kiistämättömyyttä),
  • näennäissatunnaisjonot (pseudorandom sequences). Avaimena on siemenluku, jota ei saa paljastaa, mutta sitä ei tarvitse myöskään tallettaa. Sen tärkein ominaisuus on mahdollisimman suuri entropia, eli se ettei sitä voi etukäteen ennustaa.
  • yksilöintiprimitiivit (salasanatyyppiset, myös kertasalasanat).
• epäsymmetrinen, julkinen avain (oikeastaan julkisen avaimen ja salaisen avaimen muodostama pari):
  • salaus julkisella avaimella (yksisuuntaisen funktion laskeminen), purkaminen 1-suuntaisen funktion salaluukkua käyttäen eli vastaavalla salaisella avaimella (vain RSA on kommutatiivinen, muita: Rabin, ElGamal, McEliece, elliptisten käyrien kryptosysteemit);
  • allekirjoitus salaisella avaimella (yleensä vain tiiviste), todentaminen julkisella (vastaavat kuin edellä, mutta vain RSA toimii sellaisenaan) ;
  • yksilöintiprimitiivit (haaste-vastetyyppiset, erityisesti nolla-tietotodistus).