Tedenski oris

  • 3. oktober - 9. oktober

    Splošno o predmetu.  Nekaj malega o pametnih karticah.

    Course outline. Short introduction to smart cards.

  • 10. oktober - 16. oktober

    Nekaj matematičnih osnov: modularna aritmetika, uporabimo Kitajski izrek o ostankih (KIO) ter tokovne šifre in naloga o PIN-ih za motivacijo, Zn={0,1,...,n-1} skupaj z operacijami +, * mod n, kvadratni algoritem za množenje, deljenje Evklidov algoritem (EA), razširjen Evklidov algoritm (EEA) (še ne: binarni EA, Lehmerjev algoritem), (Zn,+) ja grupa z enoto 0, (Zn\{0},*) je grupa z enoto, kadar je n praštevilo, algoritem kvadriraj in zmnoži, kubični algoritem za potenciranje.
    Ideja asimetrične kriptografije:
    DH-izmenjava ključev, koncept kriptografije javnih ključev.

    Some math background: modular arithmetics, using Chinese Reminder Theorem (CRT) and Stream ciphers and the problem about PINs for motivation, Zn={0,1,...,n-1} together with the operations +, * mod n, square algorithm for multiplication, division, Euclidean algorithm (EA), Extended Euclidean algorithm (EEA) (not yet: binary EA, Lehmer algorithm), (Zn,+) is a group with unity 0, (Zn\{0},*) is a group with unity 1, when n is a prime, algorithm square and multiply, cubic algorithm to calculate power.
    The idea of PKC:
    DH-Key Agreement, the Concept of Public Key Cryptography.

  • 17. oktober - 23. oktober

    Nadaljevanje uvoda: kaj je kriptografija, cilji kriptografije, širši pogled na kriptografijo - varnost informacij, gradniki uporabne kriptografije.
    1. Klasična kriptografija: uvod (enostavne šifre), zamenjalni tajnopis (premešalka), afin tajnopis, Vigenerjeva šifra, Hillova šifra, permuticijska šifra, kriptoanaliza.Tokovne šifre in povezava z nalogo o PIN-ih, LFSR.

    Introduction (cont.): what is cryptography, goals of crypography, information security, building blocks of applied cryptography.
    1. Classical cryptography:
    intoduction (simple ciphers), substitution cipher, Affine cipher, Vigenere cipher, Hill cipher, permutaton cipher, cryptoanalysis. Stream ciphers and connection to the problem about PINs, LFSR.

  • 24. oktober - 30. oktober

    2. Shannonova teorija: popolna varnost na splošno (računska varnost, brezpogojna varnost, dokazljiva varnost, Vernamov enkratni ščit, produktne šifre.
    3. Simetrični kriptosistemi: bločne šifre, nekaj zgodovine (DES, AES), iterativne šifre, zamenjalno-permutacijske mreže (SPN), Feistelova šifra, opis DES. Načini delovanja (ECB, CBC, CFB, OFB, CRT - nekatere preučite sami oz. jih boste delali še na vajah), napadi na šifro DES, 3-DES, problem z 2-DESom.

    2. Shannon theory: perfect security in general (computational security, unconditional security, provable security), Vernam one time pad, product ciphers.
    3. Symmetric cryptosystems: block ciphers, some history (DES, AES), iterated ciphers, substitution-permutation network (SPN), Fiestel cipher, description of DES. Modes of operation (ECB, CBC, CFB, OFB, CRT - the last one study on your own), attacks on DES, 3-DES, problem with  2-DES,
  • 7. november - 13. november

    Zgoščevalne funkcije: Definicije in terminologija, uporaba zgoščevalnih funkcij, generični napadi, iterativne zgoščevalne funkcije, MDx-družina zgoščevalnih funkcij.
    Še nekaj matematičnih osnov: v Zp obstaja element a, ki generira multiplikativno grupo, tj.Zp *={a0,a1 ,...,ap-2}, in je zato le-ta izomorfna (Zp-1,+), Lagrangov izrek (moč podgrupe deli moč grupe),  red elementa iz grupe deli moč grupe, Fermatov mali izrek, Eulerjev kriterij in popolni kvadrati.

    Hash functions: Definitions and Terminology, Applications of Hash Functions, Generic Attacks, Iterated Hash Functions, MDx-Family of Hash Functions.
    More math background: there exists an element a of Zpthat generates the multiplicative group, i.e.,  Zp *={a0,a1 ,...,ap-2}, and it is thus isomorphic to (Zp-1,+), Lagrange theorem, the order of a group element divides the order of the group, Fermat little theorem, Euler's criterion and quadratic residues.

  • 14. november - 20. november

    Binarni EA, Lehmerjev algoritem, Fermatov izrek, Eulerjeva funkcija, Eulerjev izrek. Opis in implementacija RSA (časovna zahtevnost: algoritem kvadriraj in zmnoži, pohitritev RSA - izbira majhnega eksponenta in uporaba KIO, nekaj lažjih nalog, izrek o gostoti praštevil (od Gaussa in Jurija Vega pa do Poussina in Hadamarda), asimptotična velikost n-tega praštevila je n*log n, odločitveni problem praštevilo, Legendrov in Jacobijev simbol, DA-naklonjen Monte Carlo algoritem.

    Binary EA, Lehmer algorithm, Fermat's little theorem, Euler function,  Euler theorem. Description and implementation of RSA (time complexity: square and multiply algorithm, speed up of RSA - the choice of small exponent and use of CRT, some easy problems. prime number theorem (PNT) - from Gauss and Vega to Poussin and Hadamard), asymptotic size of the n-th prime number is n*log n, the decision problem Composites, Legendre and Jacobi symbols, YES-biased Monte Carlo algorithm.

  • 21. november - 27. november

    Solovay-Strassen algoritem, Gaussov izrek o kvadratni recipročnosti praštevil, Miler-Rabinov test za testiranje praštevilskosti, napadi na RSA - odšifrirni eksponent kriptosistema RSA in Las Vegas algoritem, naključne napake in uporaba KIO. Algoritmi za faktorizacijo (požrešna metoda, Pollardova p-1metoda, Dixonov algoritem in kvadratno rešeto, praksa, vprašanje prof. I. Vidava: faktorizacija števila 1064+1).
      Solovay-Strassen algorithm, the law of quadratic reciprocity (Gauss), Miler-Rabin algorithm for primality testing, attacks on RSA - decrypting exponent of the RSA cryptosystem and Las Vegas algorithm, random errors and an application of CRT. Factoring algorithms (trial division up to 1012, Pollard p-1 algorithm, Dixon's random squares algorithm, practice, Vidav's question - factoring 1064+1).
  • 28. november - 4. december

    5. Drugi kriptosistemi z javnimi ključi: ElGamalovi protokoli in shema Massey-Omura, problem diskretnega logaritma, algoritmi za računanje diskretnega logaritma (log in antilog tabele, Shankova metoda veliki korak - mali korak, Pohlig-Hellmanov algoritem, metoda index calculus).
      5. Other Public Key Cryptosistems: ElGamal protocols and Massey-Omura scheme, Discrete Logarithm Problem (DLP), Algorithms for DLP (log and antilog tables, Shanks' Algorithm giant step - baby step, Pohlig-Hellman algorithm, Index calculus method).
  • 5. december - 11. december

    Varnost bitov pri diskretnem logaritmu (računanje kvadratnega korena) (ponovitev), računanje v končnih obsegih (karakteristika je praštevilo, končni obseg ima pn elementov, kjer je p karakteristika, n pa razsežnost vektorskega prostora, nerazcepni polinomi - iščemo nerazcepen polinom 4. stopnje nad binarnim obsegom, trinomi/pentonomi/heptonomi, polinomska baza, normalna baza, optimalna normalna baza).
    Bit security of DLP (calculating a square root) (one more time), calculating in finite fields (the characteristic is prime, a finite field has pn elements, where p is the characteristic and n the dimension of the vector space, polynomial basis, irreducible polynomials - searching for an irreducible polynomial of degree 4 over the binary field, trinomials/pentonomials/heptonomials, normal basis NB, optimal NB).
  • 12. december - 18. december

    Grupa na eliptični krivulji (pravilo za seštevanje in točka neskončnost, grafična predstavitev grupe na eliptični krivulji, trije primeri eliptičnih krivulj, Hassejev izrek in štetje točk z uporabo KIO), DH na EC in DLP na EC, Merkle-Hellmanov sistem z nahrbtnikom.
    6. Sheme za digitalne podpise: koncept in zahteve-možnosti, primerjava lastnoročnega in digitalnega podpisa, primer RSA.
    Group on elliptic curve (addition rule and the point at infinity, graphical representation of EC, three examples of elliptic curves, Hasse theorem and point counting with CRT), DH on EC, DLP on EC, Merkle-Hellman knapsac public-key system.

     6. Digital Signature Schemes: introduction - idea and requirements/possibilities, comparison of handwritten and digital signatures, RSA example, ElGamal system for digital signature, order for encryption and signing, reblocking problem.

  • 19. december - 25. december

    ElGamalov sistem za digitalno podpisovanje, vrstni red šifriranja in podpisovanja, ElGamalov sistem za digitalno podpisovanje, Digital Signature Standard/Algorithm: opis algoritma, prikrit kanal pri DSA.Napadi z grobo silo na gesla, računalniške zmogljivosti, napadi na DSA, ECDSA in primerjava z RSA, DH in AES; primerjava podpisov v praštevilskih obsegih in v grupi na eliptični krivulji, Certicomova SigGen pametna kartica.

    ElGamal system for digital signature, order for encryption and signing, reblocking problem, ElGamal system for digital signature. Digital Signature Standard/Algorithm: algorithm description, hidden chanell in DSA. Brute force attack, computer capacity and attacks on DSA, ECDSA and comparisson with RSA and AES; comparison of signatures in prime fields and in a group on the elliptic curve, Certicom SigGen smart card.
  • 26. december - 1. januar

    Predavanja in vaje odpadejo zavoljo praznikov/Lectures and Tutorials are canceled due to hollidays.
    • 2. januar - 8. januar

      Slepi podpisi, ideja skupinskega podpisa, podpisi brez možnosti zanikanja, enosmerne funkcije in enkratni podpisi.
      7. Zgoščevalne funkcije: brez trčenj, enosmerne, verjetnost trčenja, napad s paradoksom rojstnih dnevov, zgoščevalna funkcija zasnovana na varnosti DLP, iz simetričnih kriptosistemov, npr. DES, na osnovi on DLP, MD4, MD5, RIPEMD, SHA-1, HMAC,... časovni žigi, digitalna potrdila.
      Blind signatures, an idea of group signatures, undeniable signatures, oneway functions and one time signatures.
      7. Hash functions: no colision, one-way, collision attacks (based on birthday paradox), hash function based on security of DLP, from simetric block ciphers, e.g. DES, based on DLP, MD4, MD5, RIPEMD, SHA-1, HMAC,... timestamping, digital certificates.
    • 9. januar - 15. januar

      8. Upravljanje ključev: distribucija ključev, uskladitev ključev, certifikati, infrastruktura javnih ključev.
      8. Key management: key distribution, key agreement, certificates, infrastucture of public keys.
    • 16. januar - 22. januar

      14. Računalniška varnost: Uvod v računalniško varnost (pomembnejše grožnje za varnost, pregled varnostnih ukrepov, izbira varnih gesel, upravljanje s ključi).
      12. Psevdno naključna zaporedja;

      11. Sheme za deljenje skrivnosti;

       14. Computer security: Introduction to computer security (more important security threats, survey of counter measures, how to choose a safe passwords, key management).
      12. Pseudo-random number generators
      ;
      11. Secret Sharing schemes;

    • 23. januar - 29. januar

      9. Identifikacijske sheme: uporaba in cilji identifikacijskih shem, protokol z izzivom in odgovorom, Schnorrova identifikacijska shema, Okomotova identifikacijska shema Guillou-Quisquater identifikacijska shema, pretvarjanje identifikacijske sheme v shemo za digitalni podpis
       (10. Kode za overjanje; 12. Dokazi brez razkritja znanja)
      Digitalni denar (glavni igralci: stranka, prodajalec, banka; online/offline, anonimen).
      9. Identification schemes: application and goals of identification schemes, protocols with challenge-response, Schnorr identification scheme, Okomoto identification scheme, Guillou-Quisquater identification scheme*, modifying an identification scheme into a digital signature scheme*; (10. Authentication schemes; 12. Zero-Knowledge Proofs)
      Digital cash (main actors: payer, payee, bank; online/offline, anonymous).