Krüptograafia 2002/2003 1Turingi masinad 1 2Arvuteooria: Algarvud, Euleri phi funktsioon, SÜT, Eukleidese algoritm 3 3Arvuteooria: lõplikud korpused 4 4Matemaatiline loogika 5 5Ühesuunalised funktsioonid 5 5.1DLA 6 5.2Rabini funktsioon 6 5.3RSA 6 6Andmeturbe alused 6 7Krüptograafia ajalugu ja alused 8 8Sümmeetrilise võtmega krüptograafilised algoritmid 11 8.1DES 12 8.23DES 12 8.3IDEA 13 8.4AES 13 9Asümmeetrilised krüptoalgoritmid 13 9.1El-Gamal 13 9.2RSA 13 9.3ECC 13 10Räsifunktsioonid 13 10.1SHA1 13 10.2MD5 13 11Bit-commitment 13 12Võtmevahetusprotokollid 13 13Digitaalsed allkirjad 13 14Ajatemplid 13 15PKI 13 16Standardid (SSL/https, PKIX – x509, PKCS) 13 17Kvantkrüptograafia 13 1Turingi masinad Turingi masinad Turingi masinal (TM, nimetuse saanud inglise matemaatiku A.M. Turingi järgi) on 1) juhtseade, mis igal ajahetkel on ühes lõplikust arvust seisunditest, 2) sisendlint, mis on jaotatud ruutudeks (igas ruudus asub üks sümbol), ja 3) lugemispea, mis igal ajahetkel “vaatab” sisendlindi ühte ruutu. TM saab sisendlindilt lugeda ja sinna kirjutada, liigutada oma lugemispead vasakule või paremale. Lähteseisundis on lugemispea sisendstringi vasakpoolseima sümboli kohal. Sisendlint on vasakult ja paremalt lõpmatu pikkusega; ruudud, kus ei ole sisendsümbolit, on tähistatud sümboliga #. TM tööd juhitakse lõpliku hulga instruktsioonidega - nelikutega kujul (qi,aj,qk,X), kus qi, qk on seisundid, aj alfabeedi sümbol ja X on kas alfabeedi sümbol või üks nn spetsiaalsümbolitest L või R. Tõlgendus: kui TM asub seisundis qi ja loeb aj, siis ta läheb üle seisundisse qk ning kui X on alfabeedi sümbol, asendab aj sellega; kui aga X on L või R, siis jätab aj muutmata, aga lugemispea liigub ühe ruudu võrra kas vasakule või paremale. See on nn deterministlik TM. Kui TM saavutab seisundi, milles ükski instruktsioon pole rakendatav, siis ta peatub. TM vaadeldakse tavaliselt kui arvutavaid seadmeid (funktsioone), mitte kui keelte aktseptoreid. Seejuures loetakse funktsiooni argumendiks sisendstringi ja funktsiooni väärtuseks lõppkonfiguratsioon lindil, kui masin peatub. Kodeerides naturaalarve kui stringe, võime lasta TM-il arvutada naturaalarvuliste argumentidega ja naturaalarvuliste väärtustega funktsioone. Võime püstitada näiteks küsimuse, kas funktsioonid f(x)=x2 või f(x)=x! on arvutatavad TM-ga. Seda lähenemisviisi võib üldistada k argumendiga funktsioonidele, eeldades, et lähtestring esitatakse k plokina, mis on eraldatud sümboliga #. Näiteks TM, mis arvutab kahe naturaalarvu m ja n summa, võiks lähtuda stringist Funktsioone, mis on arvutatavad TM abil, nimetatakse osaliselt rekursiivseteks funktsioonideks (partial recursive function); osaliselt – sest TM võib mitte peatuda kõigi argumentide korral ja seega jäävad mõned funktsiooni väärtused defineerimata. Turingi mõttes arvutatavaid funktsioone, mis osutuvad kõikjal määratuiks, nimetatakse rekursiivseteks funktsioonideks. Seega on rekursiivne funktsioon selline funktsioon, mida võib arvutada TM-ga, mis peatub kõigi sisendite korral funktsiooni määramispiirkonnas. TM-i võib vaadelda ka stringihulkade genereerimise seadmena, kui TM-le anda sisendina mingi naturaalarvu kood ja lasta tal arvutada, kuni ta peatub. Lindi sisu #-de vahel on TM-i poolt genereeritud string. Kõikide selliste stringide hulka, mis genereeritakse kõikvõimalike naturaalarvuliste sisendite puhul, nimetatakse selle TM-i poolt rekursiivselt loetletavaks hulgaks (recursively enumerable set). Hulka nimetatakse rekursiivselt loetletavaks, kui leidub TM, mis selle hulga rekursiivselt loetleb. Järgmised kolm väidet on samaväärsed: (i)(stringide hulk) A on aktsepteeritav mingi TM poolt (ii)A on mingi osaliselt rekursiivse funktsiooni väärtuste hulk (iii)A on rekursiivselt loetletav mingi TM poolt. Piiramata grammatikad ja Turingi masinad Piiramata grammatikad e 0-tüüpi grammatikad genereerivad parajasti selliseid keeli, mida aktsepteerivad TM-d, st rekursiivselt loetletavaid hulki. (iv)A on genereeritav mingi 0-tüüpi grammatika poolt Churchi hüpotees Algoritmiks nimetatakse fikseeritud, deterministlikku protseduuri, mida mehaaniliselt rakendades on võimalik lõpliku aja jooksul saavutada tulemus. Tavaliselt töötatakse algoritmid välja terve probleemide klassi jaoks. 1930ndatel aastatel tehti rida katseid algoritmi mõiste täpsustamiseks. Turingi masin on üks selline algoritmi mõiste täpsustus. Alonzo Church: kõik, mida me intuitiivselt nimetame algoritmideks, võib formuleerida Turingi masinatena. (See pole teoreem, sest seob intuitiivse algoritmi mõiste matemaatiliselt täpse Turingi masina mõistega.) Algoritmi mõistet on täpsustanud veel Kleene, Post, Markov, Church jt. Rekursiivsete funktsioonide teooria põhitulemus: osaliste funktsioonide (ja ka kõikjal määratud funktsioonide) klassid, mida kasutatakse Turingi, Kleene’, Churchi, Posti, Markovi jt poolt, on identsed, st on üks ja sama klass. (v)Leidub algoritm, mis tuvastab hulka A kuuluvad stringid. Rekursiivsed ja rekursiivselt loetletavad hulgad Turingi masin, mis aktsepteerib hulka A, peatub alati, kui saab sisendina hulga A elemendi, ning ei peatu, kui saab sisendina hulka A mittekuuluva elemendi. Kui me tunnustame Churchi hüpoteesi, siis see tähendab, et algoritm võib töötada sellisel viisil, et annab lõpliku aja jooksul vastuse teatava klassi kõigi elementide jaoks, aga ei anna resultaati, kui tegu ei ole selle klassi elemendiga. Võib osutuda, et eksisteerib algoritm nii hulga A kui ka tema täiendi ?*-A elementide tuvastamiseks. Kui see on nii, siis öeldakse, et A on rekursiivne hulk. Seega: A on rekursiivne, kui A ja tema täiend A’ on mõlemad rekursiivselt loetletavad (Turingi mõttes aktsepteeritavad). Järelikult on rekursiivsed hulgad parajasti Turingi mõttes lahenduvad keeled. Funktsioonid, mis on algoritmiliselt arvutatavad, on Churchi hüpoteesi kohaselt parajasti osaliselt rekursiivsed funktsioonid. Kui funktsioon on osaline ega ole täielikult määratud, siis algoritm ei tagasta väärtust nende argumentide korral, kus funktsioon pole määratud. Kui aga funktsioon on kõikjal määratud, siis algoritm tagastab väärtuse iga argumendi korral. TM, mis lahendab keele, arvutab tegelikult selle keele karakteristliku funktsiooni1. Rekursiivsed hulgad on seega parajasti need hulgad, mille karakteristlik funktsioon on rekursiivne. Rekursiivselt loetletavate hulkade karakteristlikud funktsioonid on osaliselt rekursiivsed funktsioonid. Järgmised väited on samaväärsed: (i)A on rekursiivne hulk (ii)A on Turingi mõttes lahenduv (iii)A ja tema täiend A’ on rekursiivselt loetletavad (iv)A karakteristlik funktsioon on rekursiivne Universaalne Turingi masin Kuna Turingi masin on defineeritud kui lõplik nelikute hulk koos väljaeraldatud lähteseisundiga, siis on võimalik nummerdada kõik Turingi masinad. Me võime kodeerida seisundeid ja alfabeedi sümboleid 1-de järjenditena, mida eraldame 0-ga. Samuti võime kokku leppida kõigi nelikute loetlemise fikseeritud järjekorra, nii et igal TM-l on unikaalne esitus. Nüüd võime nummerdada TM-d nii, et väikseima neliku numbriga (2-ndsüsteemis) masin on esimesel kohal jne kasvavas järjekorras. Nii saame üksühese vastavuse naturaalarvude ja TM-te vahel. Oletame veel, et sisendstringid on mingil viisil kodeeritud 1 ja 0 abil. Tähistame E(M) Turingi masina M koodi ja E(x) sisendstringi x koodi. Osutub, et leidub Turingi masin U – universaalne TM -, mille sisend on E(M)E(x) ning mis modelleerib M käitumist sisendil x. Seega: kui M peatub sisendil x, siis U peatub sisendil E(M)E(x) ja saab lindil M väljundi. Kui M ei peatu sisendil x, siis U ei peatu sisendil E(M)E(x). U on kolme lindiga masin: 1) M instruktsioonide kood, 2) M lindi mittetühja osa kood igal arvutamise momendil, 3) jooksva seisundi kood. U kontrollib 3. lindilt jooksvat seisundit, 2. lindilt sümbolit, mis asub M lugemispea all ja 1. lindilt instruktsiooni, mis algab selle seisundi ja sümboliga. Kui sobivat instruktsiooni ei leidu, siis M peatuks ja samuti peatub U. Kui aga leidub, siis teeb U vastavad muudatused 2. lindil, muudab seisundit 3. lindil ja kordab tsüklit. Turingi masina peatumise probleem Keel L={E(M)E(x) | M aktsepteerib x} on Turingi mõttes aktsepteeritav. Et määrata, kas M peatub antud x korral, tuleks anda U-le M kood ja x kood. Kui M peatub, siis teeb seda ka U. Kui aga M ei peatu, siis ei peatu ka U. Me soovime teada, kas eksisteerib mingi viis otsustamaks, kas M ei peatu etteantud x korral, st kas L on Turingi mõttes lahenduv. Kas on mingi TM, mis peatub ja ütleb ‘jah’, kui M peatub x korral, ning peatub ja ütleb ‘ei’, kui M ei peatu x korral? Osutub, et ei ole! Teoreem 1. On hulki, mis pole rekursiivselt loetletavad. Teoreem 2. On hulki, mis on rekursiivselt loetletavad, kuid pole rekursiivsed. Ei leidu algoritmi, mis määraks suvalise 0-tüüpi grammatika G puhul, kas G genereerib teatava stringi, kas G genereerib tühistringi, kas G genereerib antud alfabeedi kõik stringid. 4Matemaatiline loogika XOR exclusive OR, on tõene kui üks ja ainult üks kahest sisendist on tõene. Krüptograafiliste rakenduste jaoks on sellel tehtel tohutu väärtus, kuna teades ainult üht sisendit on 50% tõenäosus, et väärtus on tõene ja 50% tõenäosus, et väärtus on väär. Huvitav on tähele panna, et kui A XOR B=C siis C XOR B=A 5Ühesuunalised funktsioonid Ühesuunalised funktsioonid on funktsioonid, mida on lihtne arvutada, kuid mille pöördfunktsiooni arvutus on keeruline. Definitsioon: Funktsiooni f:{0,1}*->{0,1}* nimetatakse ühesuunaliseks, kui: 1)eksisteerib determineeritud polünomiaalses ajas töötav algoritm A, mis sisendi x korral annab väljundi f(x) 2)iga tõenäosusliku polünomiaalses ajas töötava algoritm A’, iga positiivse polünoomi p(*) ja piisavalt suure n korral: Prob(A’(f(Un),1n)?f-1(f(Un)))<1/p(n), kus Un tähistab juhuslikku suurust ühtlase jaotusega üle {0,1}n. 1n on soovitud väljundi pikkus – see on lisatud, et ei oleks võimalik lugeda funktsiooni ühesuunaliseks lihtsalt sellepärast, et ei ole piisavalt aega väljundit trükkida. Mitteformaalselt tähendab see siis, et ainult ebaolulise tõenäosusega on lubatud pöördoperatsioonil õnnestuda. Tegelikkuses ei huvita meid aga üks funktsioon vaid pigem funktsioonide hulgad, ehk kollektsioonid. Funktsioonide kollektsioon koosneb funktsioonidest, millest igaüks töötab eraldi lõplikul lähtehulgal(piirkonnas), jagab sama arvutusalgoritmi, mis saadud sisendi peale oma lähtehulgast tagastab funktsiooni väärtuse antud punktis. Definitsioon: Funktsioonide kollektsioon koosneb lõpmatust hulgast indeksitest I, lõplikust hulgast Di iga i?I jaoks ja funktsioonist fi, mis on defineeritud üle Di. Definitsiooni järgi seega algoritmide kolmik (I,D,F) moodustavad ühesuunaliste funktsioonide kollektsiooni. ärgnevalt vaatame ühesuunaliste funktsioonide kandidaate. 5.1DLA Discrete Logarithm Assumption. Põhineb DLP’l ehk diskreetse logaritmi probleemil, mis on defineeritud kolme algoritmiga: 1)I sisendi 1n korral väljastab indeksi valimise algoritm algarvu P 2n-1<=P<2n ja ühikelemendi g multiplikatiivsest rühmast modulo P, ehk selle tsüklilise rühma generaatori. 2)Lähtehulga leidmise algoritm D annab sisendi (P,g) peale väljundiks x hulgast ZP-1 ehk jäägi modulo P-1. 3)F arvutab y=gxmod P Pöördtehe tähendaks, et sisendite P,g,y korral saame väljundiks x elik (loggy) mod P=x DLA väidab, et ükski polünomiaalses ajas töötav Turingi Masin ei suuda sellise sisendi korral väljastada x’i oluliselt paremini kui juhusliku arvamise teel. 5.2Rabini funktsioon Tegelikkuses huvitavad meid ühesuunalised funktsioonid millel on olemas nn tagauks.See tähendab, et pöördfunktsioon on võimalik kui on teada mingisugune sala informatsioon “tagaukse võti”. Nendest lähemalt kui räägime avaliku võtmega krüptograafiast. Kandidaadid tagauksega funktsioonide jaoks on väikese modifikatsiooniga RSA funktsioonide kollektsioon. Mida tegelikult kaitstakse? Informatsioon on teadmine, mis puudutab objekte või ideid ning millel on mingis kontekstis eritähendus. Elik keegi teab millestki midagi või keegi arvab millestki midagi. Informatsioonil iseenesest puudub täielikult vorm, informatsioon omandab (rünnatava) vormi läbi mistahes informatsiooni esituse. Meie kaitsemegi informatsiooni mingit esitust, ehk andmeid. Andmeteks nimetame me siis informatsiooni esitust kokkulepitud kujul, mille abil on võimalik selle informatsiooni taasesitamine. Tavaliselt on andmete kujul informatsiooni esitus seotud informatsiooni edastuse, tõlgenduse või töötlusega. Samas andmete tõlgendamine informatsiooniks ei ole ühene – see sõltub kokkuleppest ja kontekstist. Levinumad andmeesitused: paberkandja ja digitaalkujul informatsioon Paberkandjaga võrdseks loeme foto, filmi, riide jms füüsiliselt kompaktselt ja lahutamatult seotud informatsiooni Digitaalkujul andmed on kõik, mis on esitatav bitijadana ehk kahendarvude abil, elik arvuti abil töödeldava andmed. Andmetele ja nendest väljaloetavale informatsioonile saab alati mingi väärtuse omistada mingi subjekti jaoks (ei pruugi olla omanik) – tegelikult tegeleb andmeturve mingite väärtuste tagamisega. Ekslik arvamus on seejuures, et turvalisus tähendab salastatust elik konfidentsiaalsust. Nende kolme omaduse omavahelise tasakaalu leidmine ongi tüüpiline andmeturbe ülesanne: seejuures mõistlike süsteemide korral konstantse rahasumma juures tähendab käideldavuse tõstmine tihti loobumist mõnest terviklust või konfidentsiaalsust tagavast elemendist jms Kõige esmalt on enamasti vaja tagada siiski andmete käideldavus. Käideldavad andmed on kättesaadavad selleks volitatud isikutele. See ongi see milleks need andmed üldse üles tekitatakse. Järgnevalt vaadeldakse tavaliselt terviklust, mis tähendab siis seda, et saadud andmed on korrektsed (muutmata volitamata isikute poolt, sisestatud volitatud isikute poolt jne.) Konfidentsiaalsus on tänapäeval rõhutatult viimane kuid kaugelt mitte kõige tähtsusetum osa. Konfidentsiaalsus on omadus, mille kohaselt ei saa volitamata subjektid andmetele ligi. Enamasti tuleb aga andmeturbe asemel tegemist teha infovarade kaitsmisega elik turbega. Infovarade hulka kuuluvad aga lisaks andmetele ka IT aparatuur, andmesidekanalid ja tarkvara. Üldiselt siis eksisteerivad infovarade jaoks mingid ohud (threats), ohtude realiseerumiseks peavad eksisteerima mingisugused turvaaugud (need alati esinevad 100% turvalist süsteemi pole olemas) Ohtude realiseerumise tõenäosus määrab infovarade riski. Riskide alandamine tähendab tegelikult ohtude realiseerumise tõenäosust. Tüüpiliselt eksisteerib inovarade jaoks mingi aksepteeritav turvarisk, ehk mille realiseerumise vastu ehk turvakao vastu turvameetmeid ei rakendata. Siinjuures saab määravaks tavaliselt raha, mis tüüpiliselt on konstantne. Üldiselt saab seda aga illustreeridalda graafiliselt Kahjude ja kulude kõverad on tüüpiliselt eksponentsiaalsed. Kogu turbe probleemi saab aga veelgi laiemalt vaadelda, elik tervikuna organistsioponi turvet, riigi turvet, globaalset turvet jne – me ei tegele sellega. Pisut praktikast. Tegelikult ei tule riskide all näha väliseid ettekavatsetud ründeid sest praktikas suuremad kulud on tingitud stiihiliste ohtude (loodusõnnetus, tehnilise praak, rike) realiseerumisest. Ründeid tasub lähtuvalt allikast – volitatud kasutaja, majandus jms luure, kräkkerid, muud Rünnete jaotus: füüsillised ründed ressursside väärkasutus ressursside blokeerimine infopüük võltsing süsteemi manipuleerimine ründed turvamehhanismidele ründetarkvara Kreeka keeles seega tähendab krüptograafia peidetud kirja. Krüptograafia tegelesandmete peitmisega viies need loetamatule kujule Krüptoanalüüs tegeleb salastatud teksti või salastamis mehhanismi avamisega – murdmisega Krüptograafia ja krüptoanalüüs kokku moodustavadki teaduse mida Valdo Praust jt. nimetavad krüptoloogiaks. Ajalooliselt tegeles ta andmete peaitmisega volitamatute isikute eest. Tegeles sellega suuresti luureteenistus ja seda võis võrdsustada slakirjade koostamise ja murdmise kunstiga. Tänapäeval on krüptograafia mõiste tänu arvutite laialdasele levikule seda eelkõige terviklust tagava ülesande lisandumise läbi. Terminid: Krüpteeritavat (loetamatule kujule teisendatavat) teksti nimetatakse avatekstiks (plaintext) Krüpteeritud ehk loetamatule kujule viidud teksti nimetatakse krüptogrammiks (ciphertext) Krüptogrammist avateksti leidmist ilma salajast võtit teadmata nimetatakse krüptosüsteemi (krüptoalgoritmi) murdmiseks, millega tegeleb krüptoanalüüs