diff options
Diffstat (limited to 'mat/predstavitev/osnutek.md')
| -rw-r--r-- | mat/predstavitev/osnutek.md | 99 |
1 files changed, 99 insertions, 0 deletions
diff --git a/mat/predstavitev/osnutek.md b/mat/predstavitev/osnutek.md new file mode 100644 index 0000000..d8c9200 --- /dev/null +++ b/mat/predstavitev/osnutek.md @@ -0,0 +1,99 @@ +Drobljanci o kriptografiji in RSA +================================= + +Moderna kriptografija +--------------------- + +Kriptografija je veda o matematičnih tehnikah za dosego informacijske varnosti, torej zaupnosti, celovitosti podatkov, overjanja identitete in podatkov in konec koncev tudi ekonomičnosti prenosa (da podpisi in sporočila niso predolga -- med drugim v tem ECDSA premaga RSA. stiskanje podatkov je pa že nekaj drugega, vendar vseeno pazimo na BREACH napade (glej diplomsko delo spodaj)). Ker močno temelji na matematičnih algoritmih, jo štejemo kot vejo matematike. Pri moderni kriptografiji govorimo o poznanih in razumljivih algoritmih, ki na podlagi nekih skrivnosti, torej skrivnih ključev, delujejo in dosegajo prej opisano (Kerckhoffovo načelo). Glavna težnja po razvoju moderne kriptografije je bila v času tekmovanja velesil. + +Izpostavimo lahko šifrirni stroj Enigma, ki so ga v drugi svetovni vojni uporabljale nemške oborožene sile. Predstavljal je skupno skrivnost med oddajnikom in prejemnikom informacij, saj je overil vsak posredovan čistopis -- izdelanega tajnopisa namreč med posredovanjem ni moč spreminjati ali brati. + +V osnovi algoritme grobo delimo na simetrično šifriranje in kriptografijo z uporabo javnega ključa. Simetrična kriptografija je bila do leta 1976 edina javno poznana metoda šifriranja, tedaj so na MIT iznašli in patentirali prvi nesimetrični algoritem -- RSA. + +Če se vrnemo nazaj k Enigmi: delovala je simetrično. Vsako sporočilo (oziroma čistopis) je bilo pred pošiljanjem pretvorjeno v šifrirano sporočilo (oziroma tajnopis) tako, da je bil vsak znak čistopisa nadomeščen z nekim drugim znakom. Ker pa bi bilo zgolj šifriranje na podlagi menjave znakov lahko razlomiti, je Enigma pri zamenjavi upoštevala tudi trenutno pozicijo znaka v besedilu. S tem je brez poznanega zaporedja znakov zelo težko dobiti izvirno besedilo, prav tako pa bi vsak poseg v tajnopis vidno pokvaril rezultate pri osebi, ki besedilo dešifrira. Čeprav je tak sistem daleč od perfektnosti, je predstavljal nek znan algoritem, ki ga je lahko vojni nasprotnik poznal, pa brez pripadajočih kolutov za dešifracijo, kot jih je imel tisti, ki je sporočilo šifriral, ni mogel preprosto dešifrirati ali kako drugače posegati v sporočilo. + +V matematično utemeljenih šifrirnih algoritmih so šifrirni ključi ponavadi neka dolga števila, tukaj pa se pri simetričnem šifriranju pojavi problem. Isti ključ se namreč uporablja tako za šifriranje čistopisa, kot tudi za dešifriranje tajnopisa, zategadelj se mora ta ključ prenesti po komunikacijskem kanalu, ki ni berljiv nikomur, razen članom komunikacije. Temu rečemo vnaprej deljen ključ. Enigma je bila poleg tega še celo samopovratna, kajti z dvojnim šifriranjem spet pridemo do izvornega čistopisa, prav tako pa črke čistopisa nikoli ni zamenjala ista črka. Te sprva uporabne funkcije so kriptologi takoj spoznali za kritične napake, ki so zgolj olajšale kriptoanalizo oziroma lomljenje -- pridobivanje izvornega čistopisa brez dostopa do šifrirnega ključa. Poljaki so na tem področju dosegli velik napredek, z uporabo prvih programabilnih računalnikov Colossus Tommyja Flowersa, ki jih je programiral Alan Turing, so ob porabi dragocene elektrike za gretje triod proti koncu vojne z uporabo lingvističnih karakteristik nemščine, napak v algoritmu Enigme in izredno računalniško močjo poskušanja razlomili šifriranje vseh znanih tajnopisov, poslanih po radijskih zvezah med vojno. + +Pri praktični uporabi Enigme v drugi svetovni vojni so nemci uporabljali mesečne tajne kodne knjige z vnaprej določenimi povezavami med koluti in zaporedji kolutov za vsak dan posebej. Tako so bila razkrita zgolj sporočila nekega dne, v kolikor so bile povezave med koluti za nek dan razkrite -- vsaj takšen je bil načrt. Pri Enigmi so torej kot ključ štele povezave med znaki in razporeditve kolutov, le-tega pa je moč zapisati tudi v obliki števila. + +V vsakdanjem svetu se s kriptografijo pogosto srečamo na medmrežju. Le-ta nam omogoča izdelavo tajnih komunikacijskih kanalov po komunikacijskih kanalih, ki drugače sami po sebi niso tajni, kot na primer radijsko sevanje ali medmrežne povezave med tisočimi mrežnimi operaterji, ki lahko prestrezajo podatke po njih. Vendar pa bi bila vsakodnevna šifrirana komunikacija nepraktična, če bi uporabljali zgolj simetrične algoritme, saj bi morali za komunikacijo z vsakomer najprej tajno izmenjati deljen ključ, recimo osebno. + +Kriptografija javnega ključa pa leta 1977 reši problem izmenjave ključev. Tu z matematično operacijo, ki jo bom kasneje opisal, vsak udeleženec v komunikaciji izdela par ključev (števil), zasebnega in javnega. Šifriranje je enosmerna funkcija, ki ob podanem javnem ključu naslovnika in čistopisu izdela tajnopis, ki ga lahko preprosto nazaj pretvorimo v čistopis samo z dešifrirno funkcijo, za uporabo katere potrebujemo zasebni ključ naslovnika. Izmenjuje se seveda samo javni ključ, prednost izmenjave tukaj pa je, da za izmenjavo potrebujemo le zaupan in preverljiv komunikacijski kanal, ne pa nujno tajnega. Z drugimi besedami, poskrbeti moramo le, da zaupamo, da zasebni del ključa pozna le oseba, s katero komuniciramo, in ključ med prenosom ni bil zamenjan, vseeno pa nam je, če je še kdo na poti prebral ta ključ. + +Kriptografija javnega ključa ima ponavadi tudi sistem overjanja sporočil, kjer oseba overi oziroma podpiše neko sporočilo in s tem dokaže njegovo veljavnost. Vsak, ki ima dostop do javnega ključa in podpisanega sporočila, lahko matematično preveri, da je lahko sporočilo podpisal le imetnik pripadajočega zasebnega ključa. Pri RSA, kot bom razložil, to deluje tako, da oseba neko sporočilo šifrira, vendar v šifrirno funkcijo namesto javnega ključa poda svoj zasebni ključ. To ne velja pri vseh asimetričnih šifrirnih algoritmih, ampak vsakdo lahko z dešifrirno funkcijo, v katero poda tajnopis in pošiljateljev javni ključ, odšifrira veljaven čistopis in s tem potrdi lastništvo zasebnega ključa, kajti le lastnik pripadajočega zasebnega ključa lahko zašifrira sporočilo, ki se ga odšifrirati z javnim ključem (če izključimo poskušanje vseh možnih kombinacij zasebnega ključa). + +Varnost modernih kriptosistemov: +* razpršitev: tajnopis mora izgledati kot naključni podatki +* zmeda: zveza med ključem in tajnopisom mora biti zapletena, iz tajnopisa ne moremo preprosto izvedeti ključa, če tudi imamo veliko tajnopisov +* velikost ključev: ključi naj bodo čim manjši, a ne toliko, da bi jih lahko z grobo silo zdaj ali v bližnji prihodnosti odkrili. + +Napadi na kriptosisteme: +* groba sila, kriptoanaliza, algebraični napadi (reševanje sistemov enačb). +* na implementacijo: stranski kanali (merjenje porabljenega časa in energije stroja), povzročanje napak pri računanju (s sevanjem, s kratkim padcem napetosti) + +Po kratkem uvodu pa še groba predstavitev koncepta delovanja RSA. + +Kaj pa je bilo prej -- zgodovina +-------------------------------- +* Antika: Histius sužnju na golo glavo vtetovira sporočilo za Aristagorasa, ki ni vidno, ko glava ni obrita. Primer nekreckoffovskega sistema. +* 475 pr. n. š.: Skital, uporabljen v šparti, je koncept pisanja sporočila na okoli valja z enakim polmerom kot valj prejemnika ovit trak po geometrijski višini. Primer paddinga, kajti valj mora biti popisan v celoti (tudi v novo vrsto gremo) (semkaj prilepi slikico). +* 100 pr. n. š.: Cezarjeva šifra, ROTn, recimo ROT13 je pri ameriški abecedi samopovraten +* Gaj Julij Cezar prelomi palico in del da vojščaku. Sklenitev palice kasneje dokaže, da je to res vojščak, ki ga je Cezar prej srečal. +* Srednji vek: Papež Clerment VII naroči Gabrielu di Lavinda, da ustvari nomenclator, šifro, ki je zamenjevala besede in črke sporočil. +* 1518: Johannes Trithemius spiše prvo knjigo o kriptografiji +* 1790: Thomas Jefferson z matematikom Robertom Pattersonom izdela pripravo za šifriranje besedila na podlagi 26 vrtečih koles s pomešanimi črkami. Nastavimo kolesa na izbran čistopis, tajnopis pa je besedilo eno vrstico pod čistopisom. (semkaj prilepi slikico) +* Frekvenčna analiza: razbijanje šifriranja, ko se nek del ponovi v čistopisu in tajnopisu večkrat. +* 2003: Microsoft uporablja povsem neumno metodo XORanja Word dokumenta z geslom. + +Oseba A generira + +za narediti +----------- +* RSA algoritem +* napadi na RSA algoritem +* RSA padding kot rešitev +* forward secrecy +* (diffie-hellman) key exchange (tista slikica mešanja barv mi je zelo všeč) +* teorija grup (ne znamo tega, vse spodaj je zato dokaj brez zveze) + - diskretni logaritem + + težko izračunljiv pri praštevilih (RSA) in eliptičnih krivuljah (ECDSA) + - Shorov kvantni algoritem za evektivno računanje diskretnega logaritma - iskanje d, če so nam v formuli (m^e)^d%n=m%n znani e, n in m + - algoritmi za faktorizacijo zmnožka dveh praštevil +* zgoščevalne funkcije + https://ucilnica1213.fmf.uni-lj.si/course/view.php?id=32 + +izrazi +------ +* napad z grobo silo - bruteforce - poizkušanje vseh možnosti, recimo vseh ključev +* čistopis - izvorno razumljivo besedilo +* tajnopis - kriptogram - šifrirano nerazumljivo besedilo +* šifriranje - funkcija (čistopis, šifrirni ključ)=>tajnopis +* dešifriranje - funkcija (tajnopis, dešifrirni ključ)=>čistopis +* podpisovanje - funkcija (čistopis, zasebni ključ)=>podpis +* kriptoanaliza - iskanje pomanjkljivosti v kriptografskem algoritmu in zmanjševanje števila poskusov, potrebnih za pridobitev čistopisa, to so delali Zavezniki proti algoritmu Enigme v II. SV +* kriptosistem - končna implementacija osnovnega algoritma, padding sheme in vsega ostalega, ki od uporabnika ne zahteva dodatnega znanja +* padding - spreminjanje čistopisa v bolj komplicirano obliko pred operaciji s ključi, kar prepreči razkritje ključev + +zanimiva literatura +------------------- +* https://dk.um.si/IzpisGradiva.php?id=75135 + - napadi na SSL: POODLE, BREACH, SSL Strip - 2019 +* https://dk.um.si/IzpisGradiva.php?id=14056 + - diplomska naloga o diskretnem logaritmu - 2010 + - strani 6 in 7 kot uvod +* https://ucilnica1213.fmf.uni-lj.si/course/view.php?id=32 + - FMF predmet kriptografija - 2012/13 + - in, oh, kako ironično, preusmeri na zastarel TLS + - povezave do zanimivih člankov v preseku + + http://lkrv.fri.uni-lj.si/popularizacija/presek/klasicne.sifre.in.zdravstvena.kartica.1.pdf + + http://lkrv.fri.uni-lj.si/popularizacija/presek/diffie-hellmanov.dogovor.o.kljucu.2.pdf + + http://lkrv.fri.uni-lj.si/popularizacija/presek/postni.nabiralnik.in.kriptografski.protokoli.3.pdf + + http://lkrv.fri.uni-lj.si/popularizacija/presek/Jurisic_Zaupati_ali_ne_zaupati_Digitalni_podpis_v_kriptografiji_4.pdf + + http://lkrv.fri.uni-lj.si/popularizacija/presek/kako.deliti.skrivnosti.pdf + - ... v monitorju + + http://lkrv.fri.uni-lj.si/popularizacija/monitor_pametne.kartice.2.zasebno.zivljenje.javnih.kljucev.pdf + + http://lkrv.fri.uni-lj.si/popularizacija/monitor_pametne.kartice.3.napadi.in.obrambe.-.velike.skrivnosti.malih.kartic.pdf +* https://ucilnica.fri.uni-lj.si/pluginfile.php/32408/mod_resource/content/0/drugi_del.pdf + - zgodovina kriptografije, tokrat FRI, manj matematično +* http://www.cs.bc.edu/~straubin/crypto2017/Assignment1.pdf + - kratek opis neumnosti microsoftovskega XOR "šifriranja" študentom neke ameriške fakultete |