Tečaj iz kriptografije in računalniške varnosti - 11. aprila 2006

Povzetek predavanja:

Drugi javni kriptosistemi (pričetek 5. poglavja)

• Diffie-Hellmanov dogovor o ključu
  • nekaj zgodovine
  • učinkovitost potenciranja
  • varnost
• ElGamalovi protokoli in shema Massey-Omura
• problem diskretnega logaritma
• algoritmi za računanje diskretnega logaritma:
  • metoda velikega koraka malega koraka,
  • Pohlig-Hellmanov algoritem,

Vse postscript (ps) datoteke si lahko ogladate z Ghostscript in GSview, ki so na voljo za večino računalnikov in brskalnikov.

Dodatna gradiva:

Obvezno branje: rokopis za Presek ( pdf 137 Kb).

Domače naloge

Rešite vse naloge iz rokopisa o DH-protokolu. Najbolj primerne sem prenesel v html obliko:

1. Ali se lahko domisliš še kakšne zanimive zgodbe, ki bi nazorno ponazorila hitro rast eksponentne funkcije?
   Pomisli, npr. koliko prednikov bi imel v času, ko je bila zgrajena arena v Puli (pred približno 2000 leti) če si med njimi nobena dva iz iste generacije ne bi bila v sorodu?
2. Oceni, koliko riža potrebujemo, da pokrijemo cel svet (vključno z oceani), če meri polmer zemlje 6400 km? (Še ena varianta zgodbe iz antične Indije.)
3. Oceni, koliko besed lahko "obdela" tvoj ali pa fakultetni PC v eni uri? Kolikšna je velikost največjega števila, ki bi ga še lahko zapisal v spomin svojega ali fakultetnega računalnika?
4. Kolikšna je dolžina produkta dveh binarnih števil, katerih zapisa sta dolga m in n?
5. Koliko operacij potrebuješ za izračun produkta dveh 100-bitnih binarnih števil s procesorjem/vodilom svojega ali fakultetnega računalnika?
6. Pri učinkovitem algoritmu računanja potence aⁿ, kjer je n naravno število, smo vnaprej izračunali potence a², a^{2^2}, a^{2^3}, ... Poišči učinkovit algoritem za potenciranje, ki potrebuje bistveno manj spomina. (Namig: en tak algoritem je znan pod imenom kvadriraj in zmnoži, njegov spomin pa je neodvisen od števila n.)
7. Poišči čim več parov funkcij, za katere velja pravilo o zamenjavi. Ali znaš s takim parom sestaviti digitalno različico protokola Massey-Omura, ki bo varna?
8. Ni se težko prepričati, da je ciklična grupa z n elementi izomorfna grupi (Z_n,+_n). Kaj lahko poveš o relaciji med zahtevnostjo problema diskretnega logaritma v poljubni ciklični grupi G z n elementi in problema iskanja izomorfizma med grupo G in aditivno grupo (Z_n,+_n)?