Toimumisaeg ja -koht:

Üritus	Aeg	Koht	Läbiviija
Loengud	T 10:15	Liivi 2-404	Peeter Laud
Praktikumid	N 12:15	Liivi 2-403	Peeter Laud

Loengute ja praktikumide jaotus pole väga range.

Teadmiste kontroll: kodused ülesanded semestri jooksul ning mingi suurusega eksam sessi ajal.

• Eksamisse tulevad ülesanded ja ka teooriaküsimused, mida koduste ülesannetena nii hästi kontrollida ei saa.
• Eksam on avatud materjalidega.
• Koduste ülesannete ja eksami tulemused liidetakse kokku. Kodused ülesanded moodustavad kaks kolmandikku koguhindest. Kõigi ülesannete kaal on sama.
• Koduseid ülesandeid võtan vastu kuni eksamini. Aga palun jätke mulle mingi aeg kontrollimiseks ikka ka.
• Eksamiajad ja -kohad on 4. jaanuaril kell 12 ruumis 402 ja 29. jaanuaril kell 9 ruumis 111 (samaaegselt Algoritmide ja andmestruktuuride eksamiga). Ruum on reserveeritud neljaks tunniks, aga eksam on planeeritud vähem aega võtma.
  • 29. jaanuari eksami ülesanded (pdf).
• Alternatiivina kirjalikule eksamile on võimalik (ja isegi soovitav) teha sessi ajal või enne seda suuline eksam. Aega võtab see umbes tunni, toimumisaeg ja -koht on kokkuleppel õppejõuga (viibin üldiselt Tartus, aga 22.-30./31. detsembril olen Tallinnas ning 16.-18. jaanuaril Kurgjärvel). Aga ka juhul, kui te valite suulise eksami, palun registreeruge ÕIS-is ühele eksamiaegadest. Muidu ei satu teie nimi eksamiprotokolli.

Uudised:

• 9. novembril alustame praktikumiga kell 13:00.
• 31. oktoobril loengut ei ole.
• 26. oktoobril lahendame kõigepealt veel mõned ülesanded RSA ja Rabini krüptosüsteemide kohta (vaata altpoolt) ning seejärel jätkame loenguga. Ma lihtsalt ei suutnud rohkem ülesandeid leida.

Kodused ülesanded:

• Tähtajaga 21. september
• Tähtajaga 5. oktoober
• Tähtajaga 12. oktoober
• Tähtajaga 26. oktoober
• Tähtajaga 16. november
• Tähtajaga 30. november
• Tähtajaga 23. november enne praktikumi: ülesanne 8.104 (alapunktid 1 ja 3) loengukonspektist. Kui mingi alapunkti vastuseks on "nii ja naa", siis tuua näide mõlemast juhust.

Loengute sisu on üldiselt sama, mis eelmisel aastalgi. Loengukonspekti leiab Jani lehelt.

Loengute kiled:

• 5. september (sama pdf-formaadis)
• 12. september (sama pdf-formaadis)
• 19. september (sama pdf-formaadis)
• 26. septembril räägime veel natuke blokkšifrite töörežiimidest (pdf) ning jätkame jadašifritega (pdf).
• 3. oktoobril räägime veel pikkade perioodidega LTNR-idest ning jätkame DES-i ja diferentsiaalse krüptoanalüüsiga (pdf). Siin on DES-i ning loengukiledel olevate krüptoanalüütiliste funktsioonide mingi implementatsioon.
• 10. oktoobril alustame asümmeetriliste krüptosüsteemidega. Loengukiled on siin (pdf) ja siin (pdf).
• 17. oktoobril jätkame RSA-ga.
• 24. oktoobril jätkame sealt, kus pooleli jäi.
• 26. oktoobril alustame diskreetse logaritmi keerukusel põhinevate krüptosüsteemidega (pdf).
• 6. novembril jätkame sealt, kus pooleli jäi. Slaidid on täienenud.
• 14. novembril räägime signeerimisest ja räsifunktsioonidest (pdf).
• 21. novembril jätkame. Slaidid on täienenud.
• 28. novembril räägime identifitseerimisskeemidest ja nullteadmusest (pdf).
• 5. detsembril jätkame. Samuti räägime avalike võtmete levitamisest (pdf)
• 12. detsembril räägime Krüptoprimitiivide turvaomaduste formaalsest defineerimisest (pdf).

Praktikumide materjale:

• 7. ja 14. september
• Võimalikke ülesandeid 21. septembri praktikumiks. Kõiki ilmselt ei jõua ja osad ülesanded puudutavad materjali 19. septembri loengukilede lõpuosast, millest me veel ei rääkinud, aga eks me vaatame, mis järjekorras teeme.
• 28. septembri praktikumis jätkame nendesamade ülesannetega (uurime krüptosüsteemide kompositsiooni ning võtmeruumi tõenäosusjaotust. Samuti uurime LTNR-i väljundjada järgi LTNR-i ehituse leidmist.
• 5. oktoobri praktikumis otsime pika perioodiga LTNR-e ning teeme diferentsiaalset krüptoanalüüsi. See kood võib ehk kasulikuks osutuda.
  • Näita, et ~DES(K,X) = DES(~K,~X), kus ~x tähistab bitijada x bitikaupa täiendit, s.t. biti 0 asemele kirjutatakse 1 ja vastupidi. Kuidas lihtsustab see omadus brute-force rünnakuid?
  • Näita et DES-il on duaalsete võtmete paare ning eneseduaalseid võtmeid (vaata loengukilesid, need on täienenud).
  • Miks kasutatakse praktikas kolmekordset DES-i, aga ei kasutata kahekordset?
• Ülesandeid RSA-st 12. ja ... oktoobri praktikumiks:
  • Loengus näitasime, et RSA töötab, kui avatekst on mooduliga ühistegurita või kui avatekst on 0. Näita, et RSA töötab kõigi avatekstide jaoks.
  • Olgu meil antud mingi RSA-ga loodud krüptotekst ning olgu teada, et talle vastav avatekst oli mooduliga ühisteguriga. Kas ja mida saab murda?
  • Jani konspektist ülesanded (61), 66, (74, 75), 76, 77, (78), 80.
  • Kui E_(n,e)(x)=y ja E_(n,e)(z)=w, siis millega võrdub E_(n,e)(x^az^b)?
  • Soovigu Alice saata Bobile ja Charliele teadet x. Bobi ja Charlie avalikud võtmed on (n,e_B) ning (n,e_C), kus e_B ja e_C on ühistegurita (ning moodul n on sama). Kui ründaja saab teada Bobile ja Charliele saadetud krüptotekstid y_B ja y_C, siis kuidas saab ta leida x-i?
  • Kui RSA avalik astendaja on 3 ning meil on teada teadetele m ja am+b vastavad krüptotekstid (me teame konstante a ja b), siis kuidas leida teadet m?
  • Olgu n RSA moodul. Kui me teame mingile arvule x kahte ruutjuurt modulo n, kusjuures need ruutjuured ei ole võrdsed ega ka teineteise vastandarvud, kuidas me siis n-i tegurdada saame?
    • Miller-Rabini algarvulisuse testimise algoritm üritab leida mittetriviaalset ruutjuurt arvule 1 modulo n. Kas siia on kuidagi (efektiivne) tegurdamisalgoritm peidetud? Miks ei ole?
  • Suure arvu n algarvulisuse kontrollil tasub enne tõenäosusliku ja kalli algarvulisuse testi kasutamist proovida n-i läbi jagada 3-ga, 5-ga, 7-ga, 11-ga, jne. Tõenäosus, et jagub, on küllaltki suur ja siis pole seda kallist testi vaja teha. Kui mitme esimese algarvuga on mõtet jagamist proovida?
  • Olgu meil ligipääs mingile oraaklile, mis on nõus dekrüptima teatud mittekaduvväikese proportsiooni kõigist RSA krüptotekstidest (avalik võti on fikseeritud, peale selle on algoritm deterministlik, muuhulgas otsustamisel, kas ta mingit konkreetset krüptoteksti dekrüptib või ei). Kuidas seda oraaklit kasutades dekrüptida?
  • Sellist sorti algoritme, nagu me eelmise ülesande lahenduseks konstrueerisime, nimetatakse Las Vegase algoritmideks.
    • Milline on neis algoritmides keskmine katsete arv?
    • Kui suur peab olema katsete arv, kui tahame, et ebaõnnestumise tõenäosus pole suurem kui delta, kuid ühe katse ebaõnnestumise tõenäosus on epsilon?
  • Rabini krüptosüsteemi esitatakse tihti ka kujul:
    • Salajane võti: algarvud p ja q.
    • Avalik võti: n=pq ja juhuslikult valitud arv B vahemikust 0,...,n-1.
    • Teatele x vastav krüptotekst on x(x+B) mod n.
    Kuidas käib dekrüptimine, kuidas on lood turvalisusega?
• 9. november:
  • Ül. 7.93 (ja 7.92 lõpp ehk ka) Jani konspektist.
  • Menezes-Vanstone'i krüptosüsteemi dešifreerimine ja turvalisus.
  • Pollardi p-1 tegurdamisalgoritm. Millal ta töötab ja millal mitte? Tegurda 44023.
    • Tegurdades n-i, teeme me arvutusi (loodetavasti siledat järku) alamrühmas Z_p^*, kus p on n-i mingi algarvuline tegur. Need arvutused on peidetud arvutustega rühmas Z_n^*. Me uurime, kas me jõuame rühmas Z_p^* ühikelemendini.
    • Rühma Z_p^* asemel võiks kasutada teisi rühmasid. Näiteks elliptilisi kõveraid.
    • Olgu n-il selline algtegur p, et p+1 on sile. Kuidas tegurdada?
      • Vihje: varjatud rühmana kasuta p² elemendiga lõpliku korpuse multiplikatiivset rühma.
      • Siin on alternatiivne meetod, mis astendamise asemel kasutab natuke teistsuguseid tehteid.
  • Olgu p=3 (mod 4) mingi suur algarv, olgu g rühma Z_p^* moodustaja. Kui h kuulub sellesse rühma, siis kuidas leida, kas log_g h on paaris või paaritu?
  • Olgu p ja g samad, mis eelmisel ülesandel. Olgu meil oraakel O, mis sisendi h korral tagastab log_g h paremalt teise biti. Kuidas leida diskreetseid logaritme?
• 16. ja 23. november:
  • Jani konspekt, peatükid 8-10
  • ElGamal-i signatuuris s-i erinevad definitsioonid.
  • Räsipuude turvalisus.
  • Olgu n RSA moodul (kahe tugeva algarvu korrutis). Olgu g maksimaalset järku element rühmas Z_n^*. Olgu h:{1,...,n²} -> Z_n^* defineeritud kui h(x)=g^x mod n. Näita, et h on kollisioonikindel.
  • Ülesanded 6 ja 7 15. detsembril 2005 toimunud kontrolltööst.
    • Ül. 7 ka kompressioonifunktsiooni h'(x)=g^h(x) jaoks.
  • DSA jaoks on meil tarvis Z_p^* elementi, mis on algarvulist järku q. Loengus soovitati sellise elemendi genereerimiseks tõsta mõni rühma Z_p^* moodustaja astmesse (p-1)/q. Näita, et hakkama saab ka rühma Z_p^* moodustajat teadmata.
  • Ülesanded E.8.3 ja E.8.4 siit. E.8.4 kohta vaata ka seda.
  • Vaatame sümmeetrilise krüptosüsteemi abil defineeritud kompressioonifunktsiooni (x,y) -> E_x(y) xor y. Leia sellele kollisioon(e), kui E-ks on DES.
• 30. november ja 7. detsember
• 14. detsember
  • real-or-random turvadefinitsioon, seosed definitsioonide vahel.
  • PRF on hea MAC.
  • [viimane blokk CBC-režiimist (blokkšiffer on PRF) fikseeritud IV-ga on PRF, kui sisendi pikkus on fikseeritud.]
  • CCA CTR- ja CBC-režiimide vastu.
  • CPA CBC-režiimi vastu, kui IV on etteennustatav.
  • Ideaalne blokkšiffer. Näita, et mõni ideaalsest blokkšifrist konstrueeritud kollisioonikindlatest räsifunktsioonidest (näiteks h(x,y)=E_x(y) xor y) seda tõepoolest on.