Kertakäyttöavain

Kertakäyttösalaus, englanniksi one-time pad, on menetelmä:

• Jossa informaation jokaisen bitin tai bittikuvion korvaamiseen käytetään yksilöllistä korvaussääntöä eli substituutiota.

• Esimerkiksi luonnollisessa kielessä jokainen viestin merkki salataan omalla substituutiollaan.

• Käytettävän kertakäyttöavaimen on oltava vähintään yhtä pitkä kuin salattava tieto.

• Kutakin kertakäyttöavainta saa käyttää vain yhden kerran. Siitä siis nimi kertakäyttöavain.

Myöhemmin kurssilla pyrimme efektiivisesti saavuttamaan kaikilla oikeillakin salaimilla kertakäyttösalaimen ominaisuuksia. Seuraavassa tehtävässä on väittämiä kertakäyttöavaimesta.

Salaimilla pyritään kertakäyttösalaimen kaltaiseen toimintaan. Kertakäyttöavaimella suoritettu salaus on meille referenssi parhaasta salaustavasta.

Kysymys 1

Valitse oikeat väittämät:

Kertakäyttöavainta saa käyttää vain yhden kerran.

Kertakäyttöavain saa olla pidempi kuin salattava informaatio.

Kertakäyttösalainta saa käyttää vain luonnollisen kielen, eli teksti-informaation kanssa.

Kysymys 2

Kertakäyttösalaimella salattava ja suojattava tieto sisältää \(10^{12}\) merkkiä. Mitkä seuraavista voisivat olla kertakäyttöavaimen pituuksia?

\(10^{12}\)

\(10^{128}\)

\(12^{10}\)

Kysymys 3

Binäärinen salaus suoritetaan XOR operaatiolla \(\oplus\). XOR-funktio suorittaa biteittäin vertailun ja antaa arvoksi 1, jos ja vain jos toinen vertailtavista biteistä on 1. Tämän funktion toiminta on esitelty johdantomoduulin Bitit- ja Tavut -osioissa.

Meillä on seuraavat tekijät:

• Kaksi salaamatonta selväkielistä informaatiota bittimuodossa \(P_1\) ja \(P_2\)

• Kertakäyttöavain bittimuodossa \(K\)

• Kaksi salattua informaatiota bittimuodossa \(C_1\) ja \(C_2\)

Jos selväkieli \(P_1\) salataan kertakäyttöavaimella \(K\) saadaan tulokseksi salakielinen viesti \(C_1\) . Matemaattisesti ilmaistuna \(P_1 \oplus K = C_1\) . Mitä tapahtuu jos toinen selväkieli \(P_2\) salataan samalla avaimella, eli \(P_2 \oplus K = C_2\) ?

Emme saavuta mitään uutta tietoa, mikä auttaisi selvittämään avaimen.

Avain selviää helposti, koska voimme suorittaa XORin salakielen viesteille \((P_1 \oplus K) \oplus (P_2 \oplus K)\), joka paljastaa avaimen.

Saamme tietoa \(P_1\) ja \(P_2\) informaation samankaltaisuudesta, koska XOR-operaatiolla saamme salakielestä informaatiota \((P_1 \oplus K) \oplus (P_2 \oplus K) = P_1 \oplus P_2\) .

---

Kertakäyttöavaimen tapauksessa salaus suoritetaan samalla tavalla kuin aiemmin esitetyssä Vigenère-salauksessa, mutta siten että avaimen tulee aina olla yhtä pitkä kuin viesti ja täysin satunnaisesti valittu. Ohessa yksinkertaistettu esimerkki miten kertakäyttöavaimella salaus ja purkaminen voidaan suorittaa:

Salaus \(E(x) = (x_i + k_i) \pmod{m}\)

Purku \(D(x) = (x_i - k_i) \pmod{m}\) ,

jossa \(x_i\) ja \(k_i\) ovat viestin ja avaimen \(i\) :nnes merkki. Jos oletetaan, että viestin merkistö on jälleen suomen kielen aakkosto, tällöin \(m=29\) . Salataan esimerkiksi tuttu viestimme KAHVICHARLOTASSAONHYVÄÄJAVAHVAA käyttäen täysin satunnaisesti valittua avainta UWMXOPHHQDEVTRHSDDMQOÄCJKNEAIGA:

selväviesti

K

A

H

V

I

C

H

A

R

L

O

T

A

S

S

A

O

N

H

Y

V

Ä

Ä

J

A

V

A

H

V

A

A

avain

U

W

M

X

O

P

H

H

Q

D

E

V

T

R

H

S

D

D

M

Q

O

Ä

C

J

K

N

E

A

I

G

A

salaviesti

B

W

T

P

W

R

O

H

E

O

S

L

T

G

Z

S

R

Q

T

L

G

Z

A

S

K

F

E

H

A

G

A

Alla sama toimenpide suoritettuna Python-koodilla:

Inactive

Activate

# Tuodaan kirjastot
from xip import onetimepad, merkistot, esikasittele_teksti
# Käytetään kirjastoja luomaan suomenkielen isot ja pienet merkit.
isot, pienet = merkistot(suomi=True)

# Luodaan viesti
viesti                        = "Kahvi Charlotassa on hyvää ja vahvaa"
# Muunnetaan viesti esikäsittelyllä merkkijonomuotoon.
selväviesti                   = esikasittele_teksti(viesti, isot+pienet)

# Seuraava funktio palauttaa kertakäyttöavaimen sekä avaimella salatun viestin.
# Kertakäyttöavain vaihtuu jokaisella ajokerralla.
# Avain muodostetaan satunnaisella permutaatiolla aakkosista.

kertakäyttöavain, salaviesti  = onetimepad(selväviesti)

print("Alkuperäinen viesti :", viesti)
print("Esikäsitelty viesti :", selväviesti)
print("Salaviesti          :", salaviesti)

---

Tavallisesti salaus kertakäyttöavaimella suoritetaan kuitenkin vieläkin yksinkertaisemmalta vaikuttavalla tavalla käyttämällä binäärimerkistöä, jossa on vain kaksi merkkiä eli merkit 0 ja 1. Tällöin yllä esitetyt salaus ja sen purkaminen yksinkertaistuvat siten, että

• avainmerkin ollessa \(k_i=0\) , selväkielen merkki säilyy muuttumattomana salakielessä, koska \((x_i + 0) \pmod{2} = x_i\) ,

• avainmerkin ollessa \(k_i=1\) , se muuttuu nollasta ykköseksi ja ykkösestä nollaksi, koska \((x_i + 1) \pmod{2} = 1-x_i\) , kun \(x_i \in \{0,1\}\) .

Koska jokainen avainmerkki on valittu täysin satunnaisesti, ovat sekä avaimen että salakielen merkit yhtä todennäköisesti (50%/50%) nollia ja ykkösiä, eikä salakielestä voi saada mitään tietoa selväkielestä.

---

Käytännössä edellä kuvattua kertakäyttöavainta ei voida kuitenkaan käyttää juuri milloinkaan, koska avaimien pitäisi olla yhtä pitkiä kuin lähetettävät viestit, eikä avainta saisi milloinkaan käyttää uudelleen, mikä tekee avainten välittämisestä käytännössä hankalaa. Toisaalta vaatimus täysin satunnaisista avaimista on myös hankala toteuttaa käytännössä, ja tähän palataan myöhemmin kurssilla.

Näiden reaalimaailman haasteiden vuoksi kertakäyttöavaimeen perustuvien salainten käyttö onkin rajoittunut vain hyvin harvoihin valtiollisiin sovelluksiin (esim. Washingtonin ja Moskovan välisen kuuman linjan on kerrottu käyttäneen kertakäyttöavaimia). Yllä kuvattua kertakäyttöavaimella tapahtuvaa salausta \(\{0,1\}\)-merkistöllä käytetään kuitenkin osana moderneja salausmenetelmiä, ja/tai moderneilla salausmenetelmillä pyritään matkimaan kertakäyttöavaimella tapahtuvaa salausta, vaikka niissä avain onkin huomattavasti viestiä lyhyempi. Näistä asioista kerrotaan lisää lohko- ja jonosalaimia käsittelevässä moduulissa.

---

Esimerkki

Olemme saaneet käsiimme viestin, jonka sisältö on LP. Emme tunne miten selväkielen viesti on salattu. Yksi tapa yrittää selvittää selväkielen kaksimerkkinen viesti on tuottaa kaikki mahdolliset alkukuva-avaruuden yhdistelmät. Tällöin salaviestin viestin L-kirjaimelle suomalaisessa aakkostossa on 29 alkukuvavaihtoehtoa, koska on mahdollista, että merkki korvataan myös itsellään. Myös salatekstimme P-kirjaimella on 29 mahdollista alkukuvaa.

On mahdollista korvata merkki myös itsellään, vaikka se vaikuttaa aluksi omituiselta. Jos tiedettäisiin, että merkki korvataan kaikilla muilla kuin itsellään, se helpottaa kryptoanalyysin suorittamista. Vaikka bittikuvio tai merkki korvattaisiin itsellään ajoittain, ei tämä ole suuri ongelma kertakäyttöavaimella, koska substituutio vaihtuu jokaisen merkin tai bittikuvion kohdalla.

Jos käytössämme ei ole kryptoanalyysin työkaluja, selvitämme alkukuva-avaruuden tuottamalla kaikki \(29 \cdot 29 = 841\) mahdollista kirjainyhdistelmää. Suoritetaan tämä alkukuvien tuottaminen alla olevalla Python-koodilla. Koodi tulostaa kaikki suomen aakkosista muodostettavat kahden kirjaimen yhdistelmät eli alkukuva-avaruuden kokonaisuudessaan. Tämä esimerkki näyttää sen, että jo kahden aakkosmerkin läpikäyminen käsin on iso työ.

---

Inactive

Activate

from xip import merkistot
isot, pienet = merkistot(suomi=True)
aakkoset = isot
print("Käytämme aakkosmerkistöä: "+ aakkoset)
print("Joista on mahdollista muodostaa "+str(len(aakkoset)**2)+" alkukuvaa\n")

# Kaksi sisäkkäistä for-silmukkaa on toimiva mutta varsin hidas tapa tehdä merkkiparit.
i = 1
for eka_merkki in aakkoset:
    for toka_merkki in aakkoset:
        print(eka_merkki+toka_merkki, end=',')
        if (i%29==0):
            print()
        i += 1

Aja koodi alla olevasta solusta ja etsi suomen kielessä esiintyvät sanat.

Kysymys 1

Kuinka monta suomalaista sanaa on kahden kirjaimen sanalistassa?

Alle 10

13 tai enemmän

Ei yhtään

---

Selväkirjoitusten avaruus

Tuotimme edellisessä esimerkissä kaikki kahden aakkoskirjaimen selvätekstiavaruuden alkukuvavaihtoehdot. Harjoituksena poimit syntyneestä selvätekstiavaruudesta paljon pienemmän selvätekstijoukon potentiaalisia suomenkielisiä sanoja. Käytettäessä kertakäyttöavainta tai -salainta menetelmän vahvuus perustuu siihen, ettei ole mahdollista tietää, mikä sana on oikea alkukuva josta salatekstin viesti on muodostettu.

Käytettäessä luonnollisen kielen merkistöä, viestin pituuden kasvaessa kasvavat myös selvätekstiavaruus ja mahdollisten suomen kielen sanojen selvätekstijoukko. Edellisessä kahden kirjaimen esimerkissä sanat EI ja OK ovat kumpikin yhtä mahdollisia alkuperäisiksi viesteiksi.

Kun salattava tai suojattava informaatio on yksi kirjain aakkostosta, todennäköisyys että se arvataan sattumalta oikein on \(\frac{1}{29}\) . Jos taas salattava tai suojattava informaatio on 128-bittinen symboli, niin 29 aakkosmerkin sijaan symboleita on \(2^{128} = 340282366920938463463374607431768211456\) kappaletta. Kahden tällaisen symbolin yhdistelmiä on \(2^{128} \cdot 2^{128} = 340282366920938463463374607431768211456^2\) kappaletta.

Edellä mainittuja suuria lukuja on varsin vaikea hahmottaa.

Helpommin voimme hahmottaa kolmesta suomen aakkosmerkistä muodostuvan merkkijono-avaruuden. Kuinka monta alkukuvaa on olemassa kolmen suomalaisen aakkosmerkin informaatiossa?

Kysymys 1

29!

24389

3^29

Ei yhtään

---

Esimerkki kertakäyttösalaimesta

Alla olevassa koodiesimerkissä käytämme luonnollisen kielen salaamiseen tuotettua kertakäyttösalainta. Python-funktio tuottaa viestiä salatessaan jokaisella ajokerralla eri avaimen käyttämällä tietokoneen satunnaislukuja. Tietokoneessa olevat satunnaisluvut eivät välttämättä ole oikeita satunnaislukuja. Näitä tarkistelemme tarkemmin seuraavassa opetusmoduulissa.

Meillä on nyt hyökkäysmalli, jossa voimme tuottaa selvätekstistä salatekstiä. Näin ainakin oletamme, mutta tutkitaan, mitä hyötyä tästä on.

Seuraava tehtävä vaatii koodin kirjoittamista.

Kirjoita funktioon selvitä_avain toiminnallisuus, joka laskee avaimen selväviestin ja salaviestin avulla. Funktioon on kirjoitettu valmiiksi for-silmukka, jota voi hyödyntää avaimen laskemisessa.

Inactive

Activate

# Tehtävänäsi on muuttaa yhtä kohtaa alla olevasta funktiosta.
# Tehtävä ei ole vaikea, mutta vaatii ymmärrystä.

def selvitä_avain(selväviesti, salaviesti):
  aakkoset, _ = merkistot(suomi=True)

  avaimet = []
  for i, merkki in enumerate(selväviesti):
      selväviestimerkin_indeksi = aakkoset.index(merkki)
      salaviestinmerkin_indeksi = aakkoset.index(salaviesti[i])

      # TODO: korvaa alla oleva i-muuttuja
      # Vihje: haluamme ehkä laskea salakielen ja selväkielen merkkien indeksien erotus

      avaimet.append(aakkoset[(i)%len(aakkoset)])

  return "".join(avaimet)

# Tuodaan kirjastot
from xip import onetimepad, merkistot, esikasittele_teksti
# Käytetään kirjastoja luomaan suomenkielen isot ja pienet merkit.
isot, pienet = merkistot(suomi=True)

# Luodaan viesti
viesti        = "Olipa kerran karhu, joka söi mansikoita!"
# Muunnetaan viesti esikäsittelyllä merkkijonomuotoon.
selväviesti   = esikasittele_teksti(viesti, isot+pienet)

# Seuraava funktio palauttaa kertakäyttöavaimen sekä avaimella salatun viestin.
# Kertakäyttöavain vaihtuu jokaisella ajokerralla.
# Avain muodostetaan satunnaisella permutaatiolla aakkosista.

kertakäyttöavain, salaviesti  = onetimepad(selväviesti)

print("Alkuperäinen viesti :", viesti)
print("Esikäsitelty viesti :", selväviesti)
print("Salaviesti          :", salaviesti)
print("")

# Tässä kutsutaan edellisessä koodi-solussa luotua funktioita,
# jonka oletetaan selvittävän kertakäyttöavaimen sala- ja selvätekstin pohjalta.
avain = selvitä_avain(selväviesti, salaviesti)

if avain == kertakäyttöavain:
  print("Hienoa! avain on tosiaan:",avain )
else:
  print("Avain ei ollut oikein :", avain)
  print("Sen olisi pitänyt olla:", kertakäyttöavain)

Sait ehkä selvitettyä kertakäyttöavaimen. Hienoa!

Mutta mitä siitä seuraa?

Kysymys 1

Kaikki salaisuudet on murrettu, voin avata muitakin salaisuuksia ja väärentää tietoa ja muuntaa allekirjoituksia!

Jos kyseessä on kertakäyttöavain, niin saan auki vain tämän viestin. Tämän jälkeen avaimella ei ole enää mitään käyttöä.

Yhteenveto

Käytännössä kertakäyttöavaimia ei aina käytetä tai voida käyttää. Valitettavasti useissa järjestelmissä samoja avaimia (tai salasanoja) käytetään joskus jopa vuosia.

Miksi avaimille halutaan kertakäyttöavaimen ominaisuuksia?

• Oletetaan, että olemme käyttäneet samaa avainta useasti ja joku onnistuu selvittämään tai murtamaan avaimen. Tällöin kaikki aiemmin salattu tieto pystytään avaamaan tällä salasanalla. Kaikki tuleva informaatio, jota suojataan samalla avaimella, on myös luettavissa

• Useat viimeisimmät salaustekniikat hyödyntävät käyttökertakohtaista avainta (englanniksi ephemeral key). Tällöin kyseisen avaimen selvittäminen ei avaa aiempaa informaatiota, koska käyttökertaa varten on luotu kertakäyttöinen salasana. Esimerkiksi tiedonsiirtoprotokolla TLS 1.3 tukee näitä käyttökertakohteisia avaimia.

• Jos nykyistä avainta käytetään tulevien avaimien muodostamisessa (englanniksi key derivation), johtaa yhdenkin aiemmin käytetyn avaimen murtaminen kaikkien sen jälkeen suojattujen informaatioiden avautumiseen.

Aidon kertakäyttöavaimen suurin etu on siinä, että jokaista avainta käytetään vain kerran. Tällöin yhden avaimen murtaminen ei johda muiden avaimien eikä uuden tai vanhan tiedon murtumiseen.

Näimme myös sen, että vaikka tuottaisimme kaikki mahdolliset selvätekstit joista salattu informaatio voisi olla mudostettu, emme kykene selvittämään oikeaa alkukuvaa.

Seuraavaksi opettelemme ensimmäisen klassisen kryptoanalyysin työkalun - frekvenssianalyysin.

Palautusta lähetetään...

×

Identtinen palautus

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

Peruuta Lähetä