Seminar iz kriptografije in teorije kodiranja

Namen seminarja:

____Živimo v zanimivih časih, ko imamo priložnost slediti dinamičnemu razvoju kriptografije z javnimi ključi, posebej na področju eliptičnih krivulj. Kriptografija, bolj konkretno kriptografija javnih ključev, se je začela razvijati izredno pospešeno v zadnjih dvajsetih letih kot pomembna disciplina, ki ni samo predmet intenzivnega raziskovanja, temveč predstavlja osnovo informacijske družbe. Na vseh področjih komunikacij se pojavljajo standardi za kriptografsko zaščito. Kriptografske tehnike javnih ključev uporabljamo danes za zaščito elektronske pošte, pri pametnih karticah, digitalnem denarju, protokolih za internet, brezžičnih telefonih, kabelski televiziji, za zaščito proti virusom, če omenimo samo nekaj primerov uporabe.

Teorija kodiranja je matematična veja, ki se ukvarja s prenosom (ali hranjenjem) podatkov preko nezanesljivega kanala, ki na koncu povrne originalno sporočilo. Bistvo je torej v tem, da si olajšamo branje: ne mešajte te teorije s kriptografijo, ki želi otežiti branje sporočil. Različna področja sodelujejo pri premagovanju teh težav: tehnične vede kot so elektrotehnika in elektronika, računalništvo in matematika.
Sprva so se ljudje trudili narediti računalnike in pomnilnike, kateri bodo naredili oziroma vsebovali kar se da manj napak. Seveda so bile zato cene takih izdelkov vedno višje. Potem pa so se nekega dne domislil, da bi raje naučili računalnike iskati in odpravljati napake. Tako je postala proizvodnja veliko bolj učinkovita in cenejša. Pravzaprav smo dolgo časa uporabljali ``parity-check'' bite (kot npr. pri številki čeka), ki so služili za kontrolo ali je morda prišlo do napake, šele nato je Hamming nekega dne pomislil: ``če zna računalnik sam odkriti napako, potem jo bo moral znati sam tudi odpraviti.''
Od kar so računalniki začeli prevzemati večino dela na področju obdelovanja informaciji in telekomunikacij in od kar jih ljudje uporabljajo, jih zanima, kaj se da narediti v primeru, če mašina naredi napako? V pričetku so računalniki in programi, ki jih izvajajo, bili dovolj enostavni, da so tehnične napake (ponavadi je odpovedala vakumska žarnica) postale hitro očitne. Toda z razvojem hardwara (strojne opreme) so postali programi vse bolj zapleteni, s tem pa je postalo upanje, da odkrijemo mikroskopske napake, ki spremenijo delovanje naprave, zanemarljivo in s tem resna skrb. Elektronska vezja postajajo iz dneva v dan bolj minjaturna, računalniki pa vse hitrejši in tako je možnost, da se nam izmuzne kakšna napaka vse večja. Tudi če je ta možnost ena sama milijardinka, se bo računalnik s 2 GigaHetzi (tj. hitrost PC-ja), ki je prav dolgočasno počasen glede na standarde super-računalnikov (kot so Cray), zmotil 2-krat na sekundo. Kaj lahko naredimo? Odgovor, ki so ga raziskovalci našli, se nahaja v kodah za odpravljanje napak.
Matematična teorija teh kod, ki se je razvila v zadnjih 50-ih letih, je omogočila računalnikarjem in inžinjerjem, da sestavijo sisteme, ki so maksimalno zanesljivi (at the very edge of their physical capabilities). Tehnologija kod za popravljanje napak je danes tako razširjena kot zgoščenke; le-ta nam omogoča, da poslušamo priljubljen Mozartov ali Madonnin CD brez kakršnih koli motenj, četudi nam je mačka spraskala CD. Isto tehnologijo uporabljajo tudi (deep-space probes) vesoljske ladje, in tako omogočijo, da na zemljo pridejo kristalno jasni posnetki oddaljenih planetov, pri tem pa porabijo manj energije kot hladilnikova žarnica.

____ Namen tega seminarja je splošen uvod v kriptografijo in teorijo kodiranja ter osvetlitev njenih pomembnejših raziskovalnih dosežkov v zadnjih dvajsetih letih. Mnogi, ki Vas zanima kriptografija, prihajate z drugih področij, bodisi z elektrotehnike, računalništva ali matematike. Celo tistim, ki imajo za seboj formalno šolo kriptografije, primankuje trdnih osnov.
Matematično ozadje teorije kodiranja in kriptografije predstavlja predvsem algebraična kombinatorika (vključno s teorijo števil), ki se uporablja še na enem pomembne področju: v teoriji statističnega designa. Le-ta išče optimalne množice vzorcev in se uporablja na primer za design digitalnih komunikacij.
Naš cilj je razširiti osnovni nivo znanja kriptografije in teorije kodiranja ter se poglobiti v algebraično kombinatoriko. Prepričan sem, da se znanje pridobi z intenzivnim skupinskim študijem (kjer ima vsak posameznik priložnost testirati svoje predloge in vprašanja) ter najbolje utrdi z reševanjem večjega števila nalog. Zato na seminarju ne boste samo izmenično predavali, temveč boste tudi predstavljali izbrane rešitve domačih nalog.

Aleksandar Jurisic, ajurisic@valjhun.fmf.uni-lj.si, jan. 2012.