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.
- 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:
Loengute sisu on üldiselt sama, mis eelmisel
aastalgi. Loengukonspekti leiab Jani lehelt.
Loengute kiled:
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)(xazb)?
- Soovigu Alice saata Bobile ja Charliele teadet x. Bobi ja
Charlie avalikud võtmed on (n,eB) ning
(n,eC), kus eB ja
eC on ühistegurita (ning moodul n on sama). Kui
ründaja saab teada Bobile ja Charliele saadetud krüptotekstid
yB ja yC, 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 Zp*, kus p on
n-i mingi algarvuline tegur. Need arvutused on
peidetud arvutustega rühmas Zn*. Me
uurime, kas me jõuame rühmas Zp*
ühikelemendini.
- Rühma Zp* 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 p2 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
Zp* moodustaja. Kui h kuulub
sellesse rühma, siis kuidas leida, kas logg h on
paaris või paaritu?
- Olgu p ja g samad, mis eelmisel ülesandel. Olgu meil
oraakel O, mis sisendi h korral tagastab
logg 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 Zn*.
Olgu h:{1,...,n2} ->
Zn* defineeritud kui
h(x)=gx mod n. Näita, et
h on kollisioonikindel.
- Ülesanded 6 ja 7 15. detsembril 2005 toimunud kontrolltööst.
- Ül. 7 ka kompressioonifunktsiooni h'(x)=gh(x)
jaoks.
- DSA jaoks on meil tarvis Zp*
elementi, mis on algarvulist järku q. Loengus soovitati sellise elemendi
genereerimiseks tõsta mõni rühma Zp*
moodustaja astmesse (p-1)/q. Näita, et hakkama saab ka rühma
Zp* 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) ->
Ex(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)=Ex(y) xor y) seda tõepoolest on.