Kryptografisen avaimen ominaisuudet

Aiemmin mainitsimme, että kryptografiassa usein oletamme että meillä on käytössämme aitoja satunnaislukuja. Olemme aiemmissa moduuleissa käyttäneet avaimia, selväkieltä ja salakieltä, jotka ovat koostuneet vain kirjaimista.

Tästä eteenpäin avain ei ole vain kirjain tai läjä kirjaimia, vaan bittikuvio. Varsin harvan tarvitsee elämänsä aikana nähdä bittejä, joten tämän osion esimerkkejä varten asioita on yksinkertaistettu jonkin verran.

Käytännössä avaimet esitetään usein mieluummin heksadesimaalilukuina kuin bittikuvioina. Heksadesimaaliluvut esiteltiin ensimäisessä moduulissa. Ne ovat bittikuvioiden toinen merkintätapa.

Oheisessa videossa käsitellään kahta vahvan avaimen tärkeintä ominaisuutta: ainutlaatuisuus ja pituus.

---

1. Avaimen oletetaan olevan ainutlaatuinen

Laadukas kryptografinen avain on luotu kryptografisesti vahvalla satunnaislukugeneraattorilla.

Haluamme poikkeuksetta, että kryptografinen avain on tuotettu joko CSPRNG:llä ja TRNG:llä.

---

2. Hyvä avain muodostuu riittävästä määrästä satunnaisia bittejä

Ainutlaatuisuuden lisäksi laadukas kryptografinen avain on riittävän pitkä. Tällöin raa’alla laskennalla ei ole mahdollista selvittää, mikä avain on oikea.

Tässä osiossa puhumme symmetrisistä menetelmistä, joissa samaa avainta käytetään enkoodauksessa ja dekoodauksessa.

Kerckhoffs-periaatteen mukaisesti salausalgoritmi, eli menetelmä, on yleisessä tiedossa ja ainoa salausjärjestelmän salaisuus on avain. Jos avaimen bittimäärä on liian pieni eli avain on liian lyhyt, avaimen arvaaminen, ja siten tiedon salauksen tai suojauksen murtaminen pelkästään avaimia kokeilemalla on mahdollista. Avainten systemaattista raa’alla laskennalla tapahtuvaa testaamista kutsutaan brute-force -hyökkäykseksi.

Kun arvioimme menetelmän tai avaimen turvallisuutta, esitetään turvallisuus niin sanottuna

\[(\textbf{t}, \boldsymbol\epsilon)\]

-turvallisuutena. Edellinen notaatio tarkoittaa sitä, että vaaditaan \(t\) hyökkäystä murtamaan avain tai menetelmä todennäköisyydellä \(\epsilon >0\).

---

Avaimen bittimäärä ja avainten lukumäärä

Avaimelta vaaditaan paitsi ainutlaatuisuutta, myös riittävää pituutta. Tarkastellaan, mitä tämä tarkoittaa.

Lähdetään liikkeelle lyhyestä avaimesta. Oletetaan, että salauksessa on käytetty 1-bittistä avainta:

• Mahdollisia avaimia on kaksi kappaletta.

• Tällöin avain voi siis saada bittiarvot 0 tai 1.

• Vastaava avaimen desimaaliarvo on joko nolla tai yksi.

• Avain voi olla Python-kielellä avain = 0b0 tai avain = 0b1.

• Oikea avain on mahdollista arvata 50% todennäköisyydellä: \(\frac{1}{2^1}\) eli \(\frac{1}{2}\).

• Voimme helposti kokeilla kumpaakin avainta ja murtaa salauksen.

Tehdään avaimesta hieman pidempi. Oletetaan, että salauksessa on käytetty 2-bittistä avainta:

• Mahdollisia avaimia on 4 kappaletta.

• Tällöin avain voi saada bittiarvot 00, 01, 10 tai 11.

• Vastaava avaimen desimaaliarvo on joko 0, 1, 2 tai 3.

• Avaimen bittiarvo voi Python-kielellä ilmaisten olla avain = 0b00, avain = 0b01, avain = 0b10 tai avain = 0b11.

• Oikea avain on mahdollista arvata 25% todennäköisyydellä: \(\frac{1}{2^2}\) eli \(\frac{1}{4}\).

• Voimme helposti kokeilla näitä neljää avainta ja murtaa salauksen.

Kasvatetaan avainta edelleen. Oletetaan, että salauksessa on käytetty 8-bittistä avainta:

• Mahdollisia avaimia on 256 kappaletta.

• Avain voi saada desimaaliarvoja 0:sta 255:een.

• Avaimen bittikuviot voivat siis olla Python-kielellä ilmaistuna mitä vain alkaen avain = b00000000 (desimaali 0), avain = 0b00000001 (desimaali 1) jne. ja jatkuen aina avain = 0b11111111:een (desimaali 255) asti.

• Oikea avain on mahdollista arvata 0.39% todennäköisyydellä: \(\frac{1}{2^8}\) eli \(\frac{1}{256}\).

• Näin pieni määrä avaimia on mahdollista käydä läpi vaikka käsin, eikä se siis ole tietokoneille mikään haaste.

Tästä näemme, miten avaimen bittimäärä ja avaimien lukumäärä ovat sidottuja toisiinsa. Avaimien lukumäärä tuplaantuu aina, kun avaimessa käytettyyn bittimäärän lisätään yksi bitti. Yhden bitin lisäyksellä kryptografisesta avaimesta tulee siis tuplasti vaikeampi arvata, ja sen murtaminen brute-force-menetelmällä vaatii kaksi kertaa enemmän laskentaa.

Mahdollisten avaimien määrä on siis aina \(2^{\text{avaimen_bittien_lkm}}\) ja todennäköisyys murtaa salaus kokeilemalla satunnaista avainta on \(\frac{1}{2^{\text{avaimen_bittien_lkm}}}\) .

Seuraavassa taulukossa kuvataan avaimen bittimäärän ja siitä seuraavan avainten määrän suhdetta:

---

Bittejä avaimessa	0	1	8	64	128	256	512	1024
Avaimia	0	2	256	1.8x10¹⁹	3.4x10³⁸	1.1x10⁷⁷	1.3x10¹⁵⁴	1.8x10³⁰⁸

---

Jos käyttämämme avain on 128-bittinen JA salain on erittäin hyvä, sanomme että ideaalisesti menetelmä on \((t, \frac{t}{2^{128}})\) -turvallinen.

Turvataso bitteinä EI OLE sama kuin käytetyn salaimen avaimen pituus!

Turvatason bitteinä määrittävät:

• avaimen pituus

• käytetyn menetelmän vahvuus

Jos salaimen matemaattiseen algoritmiin on olemassa hyökkäystapoja, joilla avain voidaan esimerkiksi siivilöidä (engl. sieve), täytyy salaimen heikkoutta kompensoida kasvattamalla avainten pituutta. Näin voidaan saavuttaa haluttu turvataso.

---

Muodostetaan 8-bittinen avain

Käytämme seuravassa kryptografisesti turvallista tapaa generoida avain. Python-ympäristössä tämä onnistuu esimerkiksi käyttämällä secrets-kirjastosta . Luodaan seuraavaksi oikea 8-bittinen avain. Tällainen avain on aivan lyhyt käytettäväksi tosielämässä, mutta oheinen koodi havainnollistaa yhden tavan generoida kryptografinen avain.

Inactive

Activate

# Otetaan käyttöön kirjastot
import secrets
from numpy import binary_repr

# Luodaan saatunnaislukugeneraattori
satunnaislukugeneraattori = secrets.SystemRandom()

# Luodaan 8-bittinen avain k, tämä luodaan joka kerta uudestaan
bittejä = 8
k = secrets.randbelow(2**bittejä)

print("Täysin satunnainen {}-bittinen avain!".format(bittejä))
print("Heksa-desimaalilukuna :{}".format(hex(k)))
print("Bitteinä              :b'{}".format(binary_repr(k,8)))

Näin tuotimme täysin satunnaisen avaimen. Jos ajat koodisolun uudestaan, tuotetaan aina uusi 8-bittinen avain. Koska avaimen bittimäärä on vähäinen, on epätodennäköistä että kukaan muu EI olisi generoinut samaa avainta.

---

Binäärisen avaimen käyttäminen - XOR

Salaimissa avainta käytetään bittitasolla. Funktio, jolla avainta käytetään, on binääri-operaatio ehdoton-tai (engl. exclusive OR). Tästä binäärioperaattorista käytetään lyhenteellä XOR ja sitä merkitään yleisesti symbolilla \(\oplus\).

Kerrataan nopeasti, miten XOR toimii.

• XOR ottaa sisäänsä kaksi bittiä tai bittijonoa. Esimerkiksi neljän bitin bittijonot 0b0110 ja b1100.

• XOR vertaa kahta bittiä tai bittijonossa samassa kohdassa olevia bittejä.

• Jos bittien arvo on sama, XOR palauttaa arvon 0. Jos bittien arvo on eri, XOR palauttaa arvon 1. Toisin sanoen \(1\oplus1=0\) ja \(0\oplus0 = 0\) ja \(1\oplus0 = 1\) ja \(0 \oplus1 = 1\).

• Neljän bitin jonojen tapauksessa tulos on \(0110\oplus1100 = 1010\)

---

Enkryptaus - symmetrinen avain

Enkryptaamme selvätekstin \(p\) avaimella \(k\) ja tuotamme salakirjoituksen \(c\). Matemaattisesti \(c=E(p,k)\) ja toisella tapaa merkittynä \(c=k\oplus p\).

Esimerkki: Käytämme aiemmin luomaamme satunnaista avainta \(k\) . Enkryptattava data (\(p\)) on esimerkissämme yksi ascii-merkki ”?”. Enkoodaus (\(E\)) tapahtuu XOR-operaatiolla (Pythonissa ^). Yksinkertainen esimerkkimme havainnollistaa, miten data, avain ja XOR-operaation bitit toimivat. Täsmälleen samalla tavalla avainta käytetään oikeissakin järjestelmissä. Silloin tosin avain on pidempi ja suojattava data monimutkaisempaa.

Inactive

Activate

from numpy import binary_repr

# Luodaan selvätekstiviesti p, joka saa arvon '?'
p_ascii = "?"

# Muunnetaan viesti tavuiksi, tavut otetaan käyttöön kokonaislukuna listasta, eli: p[0]
p = bytes(p_ascii, encoding="utf-8")

# Tulostetaan näkyviin viesti eri tavoilla.
print("Selväkielinen ascii kirjoitus :",p_ascii)
print("Selväkirjoitus integermuodossa:",p[0])
print("Selväkirjoitus heksamuodossa  :",hex(p[0]))
print("Selväkirjoitus binäärimuodossa: b'{}".format(binary_repr(p[0],8)))

Salaimen XOR-funktio käyttää avainta \(k\) tuottaakseen salakielen \(c\) selväkielen viestistä \(p\) . Suoritetaan enkoodaus Pythonin XOR-operaatiolla ^.

Inactive

Activate

import secrets
from numpy import binary_repr

# Luodaan 8-bittinen avain k, huomaa avain vaihtuu joka ajokerta
bittejä = 8
k = secrets.randbelow(2**bittejä)

# Luodaan selvätekstiviesti p, joka saa arvon '?'
p_ascii = "?"
p = bytes(p_ascii, encoding="utf-8")

# Enkoodataan selväkieli salakieleksi ^ on biteittäinen XOR operaatio
c = p[0]^k

print("Avain      k: b'{}".format(binary_repr(k,8)))
print("Selväkieli p: b'{}".format(binary_repr(p[0],8)))
print("Salakieli  c: b'{}".format(binary_repr(c,8)))

print("Salaus suoritettu!")

Huomaatko salakielestä \(c\), miten XOR-funktio on laskenut tuloksen avaimesta \(k\) ja selväkielestä \(p\)?

---

Dekryptaus - symmetrinen avain

Symmetrisissä menetelmissä samalla avaimella suoritetaan dekoodaus \(D\), jolloin voidaan tuottaa selväkieli \(p\) salakielestä \(c\).

Eli \(p=D(c,k)\) ja toisin sanoen \(p=k\oplus c\).

Koska seuraava koodisolu luo joka kerta uuden avaimen, suoritamme saman koodisolun sisällä ensin salauksen ja sen jälkeen salauksen purun.

Inactive

Activate

import secrets
from numpy import binary_repr

print("Aloitetaan salaus!!!")
print("Tuotetaan satunnainen avain k")
bittejä = 8
k = secrets.randbelow(2**bittejä)

print("Tehdään selväkieli p ja muutetaan se tavu-muotoon")
p_ascii = "?"
p = bytes(p_ascii, encoding="utf-8")

print("Salataan selväkieli p")
c = p[0]^k

print("Salakirjoitus c tuotettu, näytetään tuotettu informaatio bitteinä.\n")

print("Avain      k: b'{}".format(binary_repr(k,8)))
print("Selväkieli p: b'{}".format(binary_repr(p[0],8)))
print("Salakieli  c: b'{}".format(binary_repr(c,8)))
print("\nSalaus suoritettu!\n")

print("Seuraavaksi suoritamme purkamisen!")
# Enkoodataan selväkieli salakieleksi ^ on biteittäinen XOR operaatio
p_dekoodattu = c^k

print("Binäärimuodossa avain, salakieli ja dekoodattu selväkieli:")
print("Avain              :",binary_repr(k,8))
print("Salattu salakieli  :",binary_repr(c,8))
print("Purettu selväkieli :",binary_repr(p_dekoodattu,8))
print("Selväkieli merkkinä:",chr(p_dekoodattu))

if p[0] == p_dekoodattu:
    print("\n\nOnneksi olkoon, olet suorittanut ensimmäisen salauksen ja salauksen purkamisen XOR-funktiolla")
else:
    print("\nJotain meni pieleen, tarkista avain, selväkielinen viesti sekä millä purat salakielen.")

Onneksi olkoon! Olet suorittanut ensimmäisen oikean kryptografisen enkryptaus-dekryptaus-operaation satunnaisella avaimella.

Symmetrisen avaimen tapauksessa XOR-operaatio tuotti ensin avaimella salakielen ja purki sen jälkeen samalla avaimella salakielen selväkieleksi.

---

Riittääkö salaimeksi pelkkä XOR?

Edellä näimme, että XOR on näpprä tapa salata ja purkaa informaatiota. Mutta entä jos salakieli muodostetaan vain suorittamalla XOR-operaatio avaimen ja salattavan datan kanssa? Onko tässä jokin heikkous?

Kun olet ajanut seuraavan koodisolun, valitse oikeat väittämät.

Inactive

Activate

import secrets
from numpy import binary_repr

bittejä = 8
k = secrets.randbelow(2**bittejä)

p_ascii = "?"
p = bytes(p_ascii, encoding="utf-8")

c = p[0]^k

KPA = c^p[0]
print("Avain                 :",binary_repr(k,8))
print("Salattu salakieli     :",binary_repr(c,8))
print("Selväkielen merkki    :",binary_repr(p[0],8))

print("\nSuoritetaan KPA hyökkäys")
print("KPA = p \u2295 c:",binary_repr(KPA,8))

Kun olet ajanut edellisen koodilohkon valitse oikeat väittämät.

Kysymys 1

Mitkä väittämät pitävät paikkansa?

Muuttujan KPA arvo on sama kuin salaisen avaimen \(k\), eli avain on murrettu.

XOR ei yksinään tuota riittävää salausta, koska mm. esimerkkimme KPA-hyökkäys murtaa avaimen.

Salaus vaatii muutakin kuin pelkän XOR operaation, kuten esimerkiksi substituution ja permutaation.

---

Brute-force: Voinko kokeilla kaikki avaimet?

Palataan avaimen bittimäärän ja avainten laskennan pariin.

Tarkastellaan 128-bittistä avainta. Oletetaan, että kykenemme suorittamaan joko enkryptauksen tai dekryptauksen 1000 miljardilla (\(10^{12}\)) avaimella sekunnissa. Kuinka pitkään kestää laskea kaikki avaimet? Joka sekunti meillä on \(\frac{10^{12}}{2^{128}}\).

Jos meillä on edellä kuvattu laskentakapasiteetti, kuinka kauan kestää löytää oikea avain kokeilemalla, kun avain on 128-bittinen?

Inactive

Activate

from xip import avaimen_laskemiseen_kuluva_aika, vertaa_maailmankaikkeuden_ikään

bittejä = 128
avainta_sekunnissa = 10**12

aika_vuosina = avaimen_laskemiseen_kuluva_aika(bittejä=bittejä, avainta_sekunnissa=avainta_sekunnissa)
vertaa_maailmankaikkeuden_ikään(aika_vuosina)

Miltä vaikuttaa, pystymmekö kokeilemaan kaikki avaimet elinaikanamme?

---

8-bittisen avaimen murtaminen brute-forcella

Jos avain on 8-bittinen kuten aiemmassa esimerkissämme, on mahdollista laskea kaikki mahdolliset salaimen tuottamat tulokset. Avainvaihtoehtoja on \(2^8\), mikä on hyvin pieni luku. Tällä määrällä voimme silmämääräisesti poimia oikean avaimen TAI löytää riittävän hyvän vastauksen väärälläkin avaimella.

Enkoodaus: Käytetään samaa viestiä kuin aikaisemmassa opetusmoduulissa. Nyt pidempi viesti lohkotaan tavuihin (eli merkeittäin) ja jokainen lohko salataan 8-bittisellä avaimella käyttäen XOR-funktiota. Tässä käytetty menetelmä vastaa Caesar-salauksen toimintaa biteillä.

Tämä demo-algoritmi on tehty vain opetustarkoitukseen, eikä sitä pidä oikeasti käyttää missään muussa tarkoituksessa!

Brute-force dekoodaus: Arvataan, että viesti on suojattu 8-bittisellä avaimella. Meillä on mahdollisuus käyttää salainta (XOR) ja asettaa jopa avain. Hyökkäysmallimme on siis CPA. Nyt pystymme tuottamaaan kaikki mahdolliset 8-bittisellä avaimella tuotettavat salatekstit. Poimitaan avain, joka näyttää tuottavan ymmärrettävän tuloksen.

Inactive

Activate

import secrets
from numpy import binary_repr
from xip import salaa_merkeittäin

# Teemme 8-bittisen avaimen
bittejä = 8
k = secrets.randbelow(2**bittejä)
print("Salainen avain k on:"+str(k))

print("Suoritetaan salaus!")
mun_viesti = "Kahvi Charlotassa on hyvää ja vahvaa!"
salaviesti=salaa_merkeittäin(viesti=mun_viesti, avain=k)
print("Salaviesti on:","".join([chr(merkki) for merkki in salaviesti]))

print("\nSuoritetaan brute force hyökkäys, käydään kaikki avaimet läpi")

for i in range(2**8):
    p_ehdokas = []
    for tavu in salaviesti:
        p_ehdokas.append(tavu^i)

    mjono = "Avain: {} :: purettu teksti:".format(i)

    for tavu in p_ehdokas:
        mjono+=chr(tavu)
    print(mjono)

Kun olet ajanut edellisen koodilohkon, valitse oikeat väittämät.

Kysymys 1

Mitkä väittämät pitävät paikkansa?

Täsmälleen oikea purettu viesti löytyy avaimella k (desimaalisena)

Osittain ymmärrettävä viesti löytyy myös toisella avaimella, johtuen ascii-merkistön koodauksen isojen ja pienten merkkien erosta.

Tulosteissa on paljon ei-näkyviä merkkejä, jotka voi heti hylätä jos selväkieli tiedetään luonnolliseksi kieleksi.

Edellisessä tehtävässä avain vaihtuu joka kerta, kun solu ajetaan. Joka kerta voimme myös löytää sellaisen avaimen, joka tuottaa oikean lähtötekstin.

---

Oletettu turvallinen symmetrisen avaimen pituus

Salauksen ja suojauksen turvataso on yhdistelmä käytettyä menetelmää ja avaimen bittimäärää. Symmetrisissä salaimissa yksinkertaistamme tässä turvatason tarkoittamaan samaa kuin avaimen bittimäärä. Tämä ei siis pidä paikkaansa käytännössä, mutta keskitymme tähän koska tämä osio käsittelee vain avaimen bittimäärää.

Vakiintunut käytäntö 2020-luvulla on, että symmetrisessä salauksessa käytetyn avaimen pituus on tyypillisesti vähintään 128-bittiä.

Yhdysvaltain kauppaministeriön alainen National Institute of Standards and Technology NIST onkin antanut vuonna 2015 suosituksen, että alle 112-bittistä turvatasoa ei tulisi käyttää.

On myös olemassa käsite Mooren-laki, jonka mukaan teknologian edistymisen seurauksena laskentakyky ja siten laskentakapasiteetti kaksinkertaistuvat 18 kuukauden välein. Tämä tarkoittaa sitä, että 18 kuukautta tästä hetkestä pystytään murtamaan kryptografisia järjestelmiä, jossa on yksi bitti enemmän turvatasoa kuin tällä hetkellä.

Jos yksinkertaistamalla oletamme nyt, että turvataso on sama kuin avaimen bittimäärä, voimme tarkistaa mikä on turvalliseksi oletettu bittimäärä juuri tänä päivänä. Jos NIST pystyisi kohtuullisessa ajassa murtamaan 111-bittisen turvatason vuonna 2015, niin mikä turvataso ja avaimen pituus meillä pitäisi olla tällä hetkellä käytössä, jotta salaus olisi turvallinen?

Inactive

Activate

from xip import nist112bits_diff
from xip import avaimen_laskemiseen_kuluva_aika

lisaa_112bittiin = nist112bits_diff()
print("112 bittiin on lisättävä {}-bittiä, \njos oletamme laskentatehon tuplautuvan 18kk välein.".format(lisaa_112bittiin))

bittejä = 112+lisaa_112bittiin
avainta_sekunnissa = 10**27      # oletettu laskentakyky vuonna 2015

aika_vuosina = avaimen_laskemiseen_kuluva_aika(bittejä=bittejä, avainta_sekunnissa = avainta_sekunnissa)
print(aika_vuosina)

Edellinen koodi antoi vuonna 2021 tulokseksi että 116-bittien avain on tarpeen. Vuonna 2022 arvio on että tarvitaan 117-bittinen avain tiedon suojaamiseksi. Jos siis salaamme tai suojaamme tietoa kyseisen ajankohdan laskentakapasiteetin mukaisella minimi-turvatasolla, joudumme jatkuvasti päivittämään menetelmiä turvatason kohottamiseksi.

Esimerkkikoodi tulostaa myös tiedon kuinka kauan oletetulla laskentakapasiteetilla kulloisenkin hetken minimi-turvatason murtaminen kestää.

Onko informaation muuttuminen tai paljastuminen tuon ajan kuluttua haitallista?

Onko tuo se aika, ”minkä jälkeen ihminen ei ole enää kykenevä pahaan?”.

Aikaisemmin tässä osiossa turvatason bittimäärä yksinkertaistettiin tarkoittamaan samaa kuin avaimen bittimäärä. Nämä ovat yhdet tärkeimmistä asioista, joita opit tällä kurssilla.

Kysymys 1

Mitkä väittämät pitävät paikkansa?

Huolellisesti suunniteltu salain pyrkii olemaan niin vahva, että riittävän pituisen avaimen kanssa se takaa turvatason.

Vaikka käyttäisimme \(10^6\) bittistä avainta, turvataso voi olla alhainen jos käytetty kryptografinen algoritmi on heikko.

Turvataso bitteinä määritellään \((t, \frac{t}{2^{n}})\) -turvallisuuden kautta. \(n\) määrittää turvatason bitteinä.

---

Yhteenveto

Tässä osiossa olemme oppineet, että:

• Hyvä kryptografinen avain on tuotettu satunnaislukugeneraattorilla joka on aito satunnaisluku tai tuotettu vähintään kryptografisesti turvallisella satunnaislukugeneraattorilla.

• Hyvä kryptografinen symmetrinen avain on muodostettu riittävästä määrästä bittejä.

• N-bittinen turvataso on todellisuudessa yhdistelmä käytetyn avaimen bittimäärää ja käytettyä algoritmia.

• Osaamme käyttää XOR operaatiota enkryptaukseen ja decryptaukseen ja tiedämme, että XOR ei yksistään riitä salaimeksi.

• Ymmärrämme, että esimerkkinä käytetty leikki-kryptaus ei juuri poikkea Caesar-salauksesta, eikä sitä pidä ikinä käyttää oikeassa kryptografisessa sovelluksessa.

Seuraavassa osiossa perehdymme jonosalaimeen.

Palautusta lähetetään...

×

Identtinen palautus

Tämä palautus on identtinen aikaisemman palautuksen kanssa. Oletko varma, että haluat lähettää palautuksen?

Peruuta Lähetä