Jump to content

Krüptograafia

From Wikiversity

Indrek Surajev

Krüptograafia (kreeka keelest kryptòs - peidetud, gráphein - kirjutama) on informatsiooni muutmine loetamatuks ilma eriteadmiste ja -vahenditeta.

Krüptograafia lihstalt vaadatuna

Minevikus aitas krüptograafia tagada kommunikatsiooni salastatust. Alates elektronarvutite leiutamisega eelmise sajandi keskel on krüptograafia ainevald laienenud, hõlmates tänapäeval lisaks turvalisele sidele ka informatsiooni terviklikuse kontrolli, isikute tuvastamise ja muu säärase. Krüptograafia vältimist uurib krüptoanalüüs. Vahel seotakse krüptograafia ja krüptoanalüüs krüptoloogia ühise nimetaja alla. Krüptograafiaga on seotud ka steganograafia, mis tegeleb mitte sõnumi sisu vaid, sõnumi enda peitmisega. Krüptograafia on interdistsiplinaarne ala. Kui oma algusaegadel oli see seotud peamiselt lingvistikaga, siis tänapäeval on põhirõhk matemaatikal, täpsemalt arvuteoorial, informatsiooniteoorial, algoritmiteoorial ja diskreetsel matemaatikal. Samuti on krüptograafia seotud inseneritegevusega (niinimetatud security engineering).

Ajalugu

[edit]

Ajalooline (arvutieelne) krüptograafia

[edit]

Krüptograafia oli ajaloolises plaanis teadus, mis tegeles teabe (andmete sisu) peitmisega võõraste pilkude eest selle "kentsaka" üleskirjutamise teel. Krüptograafia pärineb arvatavasti antiikajast, kui hakati pruukima teadete ülesmärkimist ja tekkis kiri - vahel oli vaja märkida üles teavet nii, et kõik sellest aru ei saaks. Tähestik on mitu tuhat aastat vana (foiniiklased), hieroglüüfkiri veel palju vanem (vähemalt 5000 aastat). Sama vana on arvatavasti ka krüptograafia. Krüptograafia vanim teadaolev kasutusfakt - Egiptuse vaarao Khnumhotepi kaljuhaua hieroglüüfkirjad, mis erinesid tunduvalt teistest hieroglüüfidest. Vanus ligi 4000 aastat (~1900 e.Kr.).

Ajaloolise (arvutieelse) krüptograafia põhivõtted.

[edit]

Kaks põhivõtet: Substitutsioon (substition) - olemasolevate märkide asendamine teiste märkidega. Transpositsioon ehk permutatsioon (transposition, permutation) - olemasolevate märkide järjekorra muutmine.

Lihtsamad arvutieelsed krüptovõtted kujutas endast substitutsiooni voi transpositsiooni eri varianti; keerukamad võtted (keerukamad krüptosüsteemid) olid nende teatud kombinatsioonid.
Ka suur osa kaasaegseid (arvutite ajastu) krüptosüsteeme on üles ehitatud enam-vähem sama ideoloogia kohaselt, koosnedes substitutsioonidest ja transpositsioonidest.

Kuulsamaid arvutite eelseid krüptograafiaid.

[edit]

Polybiose ruut pärineb ajajärgust ca 200 a.e.Kr.

File:Polybios1.jpg
Polybiose ruut

Iga täht asendati kahekohalise numbriga, näiteks EESTI asendus järjendiga 5151344442. Võimalik oli tähestikku ka ümber järjestada.

Kreeka transpositsioonišiffer, tuntud ka nime Skytale all. Esmamainitud ca 500 a.e.Kr. Sisaldab linti (rihma), millele on kantud tähed ja õige jämedusega pulka. Linti pulgale kerides saab teksti lugeda ja kirjutada. (pilt)

Caesari šiffer oli lihtne substitutsioonišiffer: tähestiku iga täht asendati temast teatud arv positsioone edasi oleva tähega. Näiteks sõna KRYPTO teisendub sünaks CIOHKG. Kasutusele võttis Julius Gaius Caesar 50 a.e.Kr.

Jeffersoni silinder on esmamainitud 1790 aastal. Igal kettal on tähestik suvalises järjekorras. Ketaste järjekord on võti. Sõnum (avatekst) seatakse ketaste pööramisega ritta; mingist kindlaksmääratud teisest reast loetakse krüptogramm.

Krüpteerimismasin ENIGMA

[edit]

Kuni 1920-40ndate aastateni olid peamised abivahendid krüpteerimisel paber ja pliiats; ainult vähesel määral kasutatimuid abivahendeid. Pruugitavaim oli nn Vernami šiffer, kus võtmena kasutati näiteks mingit avalikku teost või muud kättesaadavat tekstimaterjali (märgijada). 1930-40ndatel ilmusid nende kõrvale ka esimesed mehaanilised või elektromehaanilised krüpteerimismasinad.

Sakslased konstrueerisid 1930ndatel aastatel elektromehaanilise krüpteerimismasina ENIGMA, mille šifrid pidid olema murdmatud.

ENIGMA

ENIGMA oli keerukas substitutsioon-permutatsioonšiffer, kus võtmena anti ette rootorite (3-8 tk)(substitutsiooni) nihked. Rootor oli mõlemalt küljelt 26 kontaktiga ketas, mis realiseeris tähestiku permutatsiooni.

Rootoreid oli kolm ja iga tähe šifreerimisel liigutati viimast rootorit ühe sammu võrra. Kui viimane rootor oli teinud 26 sammu (täisringi), liigutati eelviimast rootorit nagu auto kilomeetrilugejas. Niiviisi saavutati 26x26x26=17576 rootorite asendit ehk erinveat substitutsiooni. See võte arvati 1930-40ndatel olevat murdmatu.

ENIGMA murdmise lugu (arvutite võidukäigu algus)

[edit]

ENIGMA koodi murdis Poola krüptograaf Rejewski 1930-datel aastatel, aga seda käsitsi teha oli mahukas. 1943 konstrueeris Inglise matemaatik Alan Turing spetsiaalse elektronarvuti (maailma esimese) COLOSSUS, mille eesmärgiks oli ENIGMA šifrite murdmine. Kaua aega (1980. aastate lõpuni) hoiti seda fakti salajas.

Traditsioonilise krüptograafia lõpp

[edit]

Traditsioonilise krüptograafia lõpetas elektronarvuti ilmumine 1940. aastatel (COLOSSUS, ENIAC), mis tegi arvutamisvõimaluse sadu ja tuhandeid kordi kiiremaks. Sellega lõppes arvutieelsete krüptoalgoritmide ajastu ja lõppes traditsiooniline (arvutieelne) krüptograafia. Alates 1940-test kasutatakse nii šifreerimisel kui krüptoalgoritmide murdmisel elektronarvuti abi.

Elektronarvutite ilmumisega umbes samal ajal (1949) avaldas Shannon oma informatsiooniteooria, mis viis senise empiirilise teooria teaduslikule alusele. Alates 1949. aastast võib rääkida juba kaasaegsest (teaduslikust) krüptograafiast, mis on sisult matemaatika üks haru ja rakenduselt andmeturbe üks haru.

Krüptograafia ja arvutid

[edit]

Diplomaatide ja sõjardite käsutuses.

[edit]

Traditsioonilise krüptograafia (kuni 1940ndad) ajastul oli sellel väga kitsas kasutusvaldkond: diplomaatia ja sõjandus. Üleminek käsitsi krüpteerimiselt arvutipõhisele ei muutnud esialgu krüptograafia kasutusvaldkonda. Paljudes riikdes olid kuni 1970-80teni krüptoalgoritmid ja- seadmed oma käitumisreeglitelt võrdsustatud relvadega.

1980ndad - sõjardite pärusmaalt masskasutusse.

[edit]

Krüptograafia levik sõjardite ja diplomaatide mängumaast masspruukimisse algas seoses teabe liikumisega ülemaailmses arvutivõrgus - Interneti - ja selle kaitse vajadustega. See sai alguse 1980te lõpul ja 1990te algul. Täiendava tõuke andsid siin krüptoalgoritmid ja võtted, mida ei kasutatud enam teabe konfidentsiaalsuse, vaid tervikluse kaitseks.

Krüptograafia olemus ja roll kaasajal

[edit]

Kaasajal ei tegele krüptograafia küll enam pelgalt teabe salastuse tagamisega, vaid lisaks volitamata muutmise ärahoidmisega (tervikluse tagamisega), mida võib lugeda isegi tema põhifunktsiooniks. Nimetus krüptograafia (peidetud süna) on traditsioonide tõttu jäänud küll alles ja kasutusse,kuigi tihti pole salastusega selle rakendamisel mingit tegemist.

1990ndad: krüptograafia liberaliseerimine

[edit]

Viimased vanade tavade kantsid olid:

Prantsusmaa(oli veel 1990te keskel võrdsustatud relvadega).
USA(kuni 1999. aastani kehti praktikas murdmatute krüptograafiatoodete ekspordikeeld).

Kaasaja krüptograafia

[edit]

Tüüpvõttena IT ja andmeturbe teenistuses

[edit]

Kaasajal on krüptograafial põhinevad võtted muutunud (internetis) teabe kaitsmise tüüpvõteteks, ilma milleta ei ole teavet võimalik töödelda. Selle vaatlemine erivahendina on lõplikult ja jäädavalt ajalugu.

Kaasaja krüptograafia on oluline tööriist digiandmete turbe tagamisel. Konfidentsiaalsuse ja tervikluse juures on ta põhivahend, käideldavuse juures aga abivahend.

Ametlik definitsioon

[edit]

(Kaasaja) krüptograafia (cryptography) on distsipliin, mis hõlmab põhimõtteid, vahendeid ja meetodeid andmete teisendamiseks nende semantilise sisu peitmise, nende volitamata kasutamise või nende märkamata muutumise vältimise eesmärgil.

Kaasaja krüptoloogia

[edit]

Digiandmete vorming

[edit]

(Digi)andmete vorming (format) on kokkuleppeline viis, kuidas erinevat liiki teave andmetena (digimaailmas 1 ja 0 jadadena) kodeeritakse. Vorming annab andmetele tähenduse, st kokkuleppeline vorming seob andmed nende poolt kantava teabega. Järeldus: vormingut mitte teades omatakse küll andmeid, kuid ei omata nende poolt kantavat informatsiooni. See tõik on muuhulgas krüptograafia aluseks tema kasutamisel konfidentsiaalsuse kaitseks.

Kaasaja krüptograafia olemus

[edit]

(Kaasaja) krüptograafia (cryptography)on distsipliin, mis hõlmab põhimõtteid, vahendeid ja meetodeid, andmete teisendamiseks nende semantilise sisu peitmise, nende volitamata kasutamise või nende märkamata muutumise vältimise eesmärgil (ISO 7498-2).

Krüptograafia põhimõisted

[edit]
  • Krüpteeritavat (leotamatule või muutmatule kujule teisandatavat) teksti nimetatakse avatekstiks (plaintekst).
  • Krüpteeritud ehk loetamatule kujule viidud teksti nimetatakse krüptogrammiks (ciphertext).
  • Avateksti teisendamist loetamatul kujul olevaks krüptogrammiks nimetatakse krüpteerimiseks ehk šifreerimiseks (encryption, enciphering).
  • Krüptogrammi teisendamist avatekstiks normaalolukorras nimetatakse dešifreerimiseks (deciphering, decryption).
  • Nii šifreerimise kui ka dešifreerimise juures kasutatakse salajast võtit ((secret) key), ilma milleta on need tegevused praktikas võimatud.
  • Dešifreerimine on krüptogrammi teisendamine avatekstiks võtme kaasabil.
  • Krüptogrammist avateksti leidmist ilma salajast võtit teadmata nimetatakse krüptosüsteemi (krüptoalgoritmi) murdmiseks, millega tegeleb krüptoanalüüs.

Krüptograafia ja krüptoanalüüs

[edit]
  • Krüptograafia (cryptography) tegeleb teabe teisendusmeetodite väljatöötamisega, mis kaitsekid teabe konfidentsiaalsust või terviklust.
  • Krüptoanalüüs (cryptanalysis) tegeleb vastupidisega – nende meetodite ehk olemasolevate krüptosüsteemide või krüpteerimisvõtete murdmisega.
  • Krüptograafia ja krüptoanalüüs koos koos moodustavad krüptoloogia (cryptology).

Krüptograafia erijooni

[edit]

I

[edit]

Tänapäeval on krüpteerimisalgoritmid (andmete teisendusreeglid) reeglina avalikud, kogu salastus põhineb turvalisus kasutataval salajasel võtmel (mis on lühike digitaalteabekogum). Säärane võte lubab sõltumatutel ekspertidel süsteemide turvalisust abstraktselt hinnata, pääsemata ligi kaitsmist vajavatele andmetele.

Praktikas tegelevad sellega küll kitsa eriharidusega inimesed – krüptoloogid –, kes on reeglina eriteadmistega matemaatikud.

II

[edit]

Kaasaja krüptograafia kasutab eranditult matemaatikute (krüptograafide) poolt koostatud tüüpalgoritme, ise oma kasutamiseks välja töötatatavad unikaalsed algoritmid on ajalugu. Nende algoritmide koostamine krüptograafia (matemaatika) alaseid eriteadmisi.

Mida kauem on krüptoalgoritm avalikus kasutuses olnud, seda väiksem on tõenäosus, et tal leidub efektiivseid murdrmisvõtteid.

III

[edit]

Kaasaja krüptograafia kasutab eranditult arvutustehnikat, käsitsi paberil arvutamine on jäädavalt ajalugu. Krüptoanalüüsil on oluline tehete kiirus: arvuti taktsagedus on GHZ-des, käsitsi arvutamisel heal juhul mõni Hz.

Krüptograafia (tegelikult kogu krüptoloogia) on praktilise poole pealt informaatika üks rakendusi.

IV

[edit]

Kaasaja krüptograafia kasutab suurt hulka standardeid, mida järgib kogu (virtuaal)maailm. Standardid on nagu ikka vabatahtlikud, kuid sünergeetilisel efektil põhinevas koostoimivas maailmas on mõistlik neid järgida.

Ilma ühtsete standarditeta ei teki ühtset infrastruktuuri, mille eri osad saaksid koos toimida.

Krüptoalgoritmide peamised liigid

[edit]
  1. Sümmeetrilised ehk salajase võtmega krüptoalgoritmid (on traditsioonilised e ajaloolised).
  1. Asümmeetrilised ehk avaliku võtmega krüptoalgoritmid (levinud viimase 20 aasta jooksul).
  1. Krüptograafilised sõnumilühendid jms sellesarnased funktsioonid.
  1. Eriotstarbega algoritmid tõestusteks, autentimisteks, ajatempli jaoks jm.

Salajase võtmega krüptoalgoritm

[edit]

Tuntuimad esindajad:

  • AES (128, 192 või 256 bitine võti)
  • IDEA (128 bitine võti)
  • Skipjack (80 bitine võti)
  • RC4 (40 kuni 256 bitine võti)
  • DES (56 bitine võti)

Võtme osa šifreerimises ja dešifreerimises

[edit]

Krüpteerimine ehk šifreerimine (encryption, encipherment) nõuab teatud salajase võtme (key) kasutamist. Vastupidine tegevus on dešifreerimine (decryption, decipherment), mille käigus taastatakse sama salajase võtme kaasabil algsed andmed. Ilma ühte sama võtit teadmata on mõlemad tegevused võimatud.

Salajase võtmega krüptoalgoritm: turvalisus

[edit]

Kaasajal loetakse piisavalt tugevaks tavaliselt 80 biti pikkuse (erijuhtumeil ka 128 biti pikkuse) salajase võtmega algoritme. DES on seega kaasajal nõrguke, kuna ei vasta sellele tingimusele. Hädalahendus oli 3kordse DESi kasutamine (kuni aastani 2005). Lisaks võtmepikkusele ei tohi algoritmil olla tuntavaid efekte andvaid krüptoanalüütilisi ehk murdmisvõtteid .

Salajase võtmega krüptoalgoritm: kasutusalad

[edit]

Neid on kaks:

  • konfidentsiaalse teabe edastamiseks üle (mitte pealtkuulamiskindlate) võrkude
  • konfidentsiaalsete teabekogumite salvestamine avalikus keskkonnas sooviga teabe saajate hulka piirata

Salajase võtmega krüptoalgoritm: tekkiv probleem

[edit]

Probleem: enne teabe edastamist üle võrgu on vaja kuidagi tagada, et mõlemas otspunktis (mõlemal osapoolel) oleks olemas vaid neile teadaolev salajane võti. Võtme säärane edastamine vajab turvalist (pealtkuulamiskindlat) kanalit, mida salajase võtmega krüptosüsteem ei paku. Võtme kohaletoimetamine nt kulleriga on esiteks kohmakas ja teiseks ei pruugi olla turvaline.

Avaliku võtmega krüptoalgoritm

[edit]

Avaliku võtmega krüptoalgoritm (public key cryptoalgorithm) ehk asümmeetriline krüptoalgoritm (asymmetric cryptoalgorithm) kasutab kahte võtit – esimese võtmega šifreeritud teave on dešifreeritav vaid teise võtmega ja vastupidi. Ühest võtmest teist ei ole võimalik praktikas leida.

Avaliku võtmega krüptoalgoritm: võtmed

[edit]

Avaliku võtmega krüptoalgoritmi võtmeid nimetatakse reeglina avalikuks võtmeks ja privaatvõtmeks (public and private key).

  • Avalik võti on tavaliselt kõigile soovijaile teada.
  • Privaatvõti on reeglina aga subjekti (inimese, tehnilise süsteemi, programmi vms) ainuvalduses.

Avaliku võtmega krüptoalgoritm: RSA

[edit]

Tuntuim avaliku võtmega krüptoalgoritm on RSA. Seda loetakse turvaliseks alates 1024 biti pikkusest võtmest. RSA korral on tingimused veidi pehmemad: privaatvõtmest avalikku võtit saab leida, kuid avalikust võtmest privaatvõtit mitte. Nad on omavahel matemaatilisel seotud, kuid avalikust võtmest privaatvõtme leidmine võtab aega miljoneid aastaid.

Avaliku võtmega krüptoalgoritmi kasutamine

[edit]
  • Avaliku võtmega krüptoalgoritme saab kasutada salajaste võtmete turvalisel edastamisel üle liinide ilma füüsilise kokkusaamiseta. Ainus tingimus on siin avaliku võtme avalikkus.
  • Avaliku võtmega krüptoalgoritme saab lisaks andmete konfidentsiaalsuse tagamisele kasutada ka nende tervikluse tagamisel. See ongi nende peamine kasutusvaldkond.
  • Avaliku võtmega krüptoalgoritmidel põhineb digitaalallkirja (digitaalsignatuuri) idee.
    File:Avalikvoti.png
    Avaliku võtmega krüptoalgoritmi kasutamine šifreerimisel

Krüptograafiline sõnumilühend

[edit]

Krüprograafiline sõnumilühend ehk krüptoräsi (cryptographic message digest, hash, fingerprint) on ükskõik kui pikast sõnumist (failist) teatud matemaatiliste eeskirjade järgi arvutatav lühike (paarsada bitti) teabekogum. See seos on ühesuunaline (one-way): etteantud sõnumilühendi korral ei ole võimalik tuletada faili, millele see sõnuimilühend vastab.

Krüptograafiline sõnumilühend: kasutusala

[edit]

Kui meil on olemas sõnum/sõnumilühend paar, kus sõnumilühend vastab failile, võime olla igal juhul kindlad, et lühend on arvutatud kindlasti sellest failist ega mitte millestki muust. Sõnumilühendite peamine kasutusala on autentimisel ja tervikluse tagamisel digitaalallkirja juures ja mujal. Praktikas turvalised sõnumilkühendid on vähemalt 160 bitti pikad (veelgi parem, kui nad oleks 256 bitised).

Teoreetiline ja praktiline turvalisus

[edit]

Teoreetiline turvalisus – krüptoalgoritmi ei ole võimalik teoreetiliselt murda, st ka siis, kui meie käsutuses oleks lõpmatult võimsaid arvutusressursse ja/või lõpmatult palju aega. Praktiline turvalisus – krüptoalgoritmi ei ole võimalik murda mõistliku aja jooksul (päevade, kuude, aastate, aastatuhandete vms jooksul). Reeglina siiski ei ole murdmisaeg väiksem kui aastatuhanded.

Kaasaja praktikas pruugitavate krüptoalgoritmite korral pruugitakse reeglina vaid praktilist turvalisust. Teoreetiliselt on kõik need murtavad tuhandete, miljonite ja/või miljardite aastate jooksul.

Nõuded kaasaja krüptotoodetele (ranguse kasvamise järjekorras)

[edit]

1. Algoritmi kogu turvalisus baseerub salajasel võtmel, algoritmi enda teadmine ei vähenda süsteemi turvalisust (traditsiooniline e Kerckhoffi eeldus, sõnastati 19. sajandi lõpul).

2. Krüptogrammi teades ei ole võimalik leida ei salajast võtit ega ka avateksti. Teiste sõnadega: ei ole võimalik teha teadaoleva krüptogrammi rünnet (known ciphertext attack).

3. Avatekst-krüptogramm paari teades ei ole võimalik leida salajast võtit. Teiste sõnadega: ei ole võimalik teostada teadaoleva avateksti rünnet (known plaintext attack).

4. Etteantud avateksti ette andes ja vastavat krüptogrammi teada saades ei ole võimalik leida salajast võtit. Teiste sõnadega: ei ole võimalik teostada valitud avateksti rünnet (chosen plaintext attack).

5. Tervet hulka avatekste ette andes ja vastavat krüptogrammi teada saades, millest lähtuvalt valitakse järgmine etteantav avatekst, ei ole võimalik leida salajast võtit. Teiste sõnadega: ei ole võimalik teostada adaptiivse valitud avateksti rünnet (adaptive chosen plaintext attack).

Kaasaja praktiliselt turvalisteks peetavad krüptoalgoritmid rahuldavad tavaliselt kõiki toodud 5 omadust.

Krüptoanalüüsi alused

[edit]

Triviaalseim võte on kõikide võimalike võtmete (bitikombinatsioonide) proovimine: seda nimetatakse ammendavaks otsinguks (exhaustive search). N biti pikkuse võtme korral eeldab ammendav otsing 2N variandi läbivaatamist – see on suure N korra väga suur arv, mistõttu ei ole teatud N väärtusest alates ammendav otsing võte praktikas teostatav. Kõiki selliseid võtteid, mis võimaldavad N biti pikkuse võtmega krüptoalgoritmi murda vähema kui 2N operatsiooni jooksul, nimetatakse krüptoanalüütilisteks võteteks. Rääkides krüptoanalüütilistest võtetest, ei mõelda selle all reeglina selle lihtsaimat vormi: ammendavat otsingut. Reeglina on praktikas krüptoalgoritmidel lubatud vaid säärased krüptoanalüütilised võtted, mis vähendavad tööd 2, 4 või 8 korda, kuid ei anna ammendava otsinguga võrreldes olulist võitu.

Algoritmide praktiline turvalisus

[edit]

Praktiliselt turvaline on selline krüptoalgoritm, mille korral ei ole teada efektiivseid krüptoanalüütilisi võtteid ühegi eelnimetatud viie ründetüübi puhul ega praktikas mõistliku ajaga realiseeritava ammendava otsingu võimalust. Mida rohkem on krüptoalgoritmid kasutusel olnud, seda väiksemaks muutub efektiivse krüptoanalüütilise võtte konstrueerimise tõenäosus – kogu maailma krüptograafid püüavad neid pidevalt leida.

Praktilise turvalisuse saavutamise teed

[edit]

Põhitõde: suurendades võtmepikkust mõne biti võrra, kasvab krüptoalgoritmi turvalisus üldkujul sama arv korda.

Põhjus: eksponentfunktsiooni y = 2**x hea omadus. See võimaldab lineaarse kulutuste (algoritmi lahendusaja, protsessori maksumuse vm) kasvuga saavutada turvalisuse (murdmiseks kuluva aja) eksponentsiaalset kasvu.

Sel põhjusel on küllalt tugev praktiline turvalisus krüptograafias saavutatav.

Kasutatud kirjandus

[edit]
http://enos.itcollege.ee/~valdo/turve/
http://www.para-web.org/viewthread.php?tid=4969
http://et.wikipedia.org/wiki/Krüptograafia
http://en.wikipedia.org/wiki/File:Crypto.png