Tedenski oris

  • 1. oktober - 7. oktober

    Uvod: Splošno o predmetu.  Nekaj malega o pametnih karticah. Kaj je kriptografija, cilji kriptografije, širši pogled na kriptografijo - varnost informacij, gradniki uporabne kriptografije.
    Ideja asimetrične kriptografije: DH-izmenjava ključev, koncept kriptografije javnih ključev.
    Introduction: Course outline. Short introduction to smart cards. What is cryptography, goals of crypography, information security, building blocks of applied cryptography.
    The idea of PKC:
    DH-Key Agreement, the Concept of Public Key Cryptography.

  • 8. oktober - 14. oktober

    1. Klasična kriptografija: uvod (enostavne šifre), zamenjalni tajnopis, Afina šifra, Vigenerjeva šifra, Hillova šifra, permutacijska šifra. kriptoanaliza, tokovne šifre in povezava z nalogo o PINih, LFSR, afin tajnopis, Vigenerjeva šifra, Hillova šifra, permutacijska šifra, kriptoanaliza. Tokovne šifre in povezava z nalogo o PIN-ih.
    Nekaj matematičnih osnov
    : modularna aritmetika, Zn={0,1,...,n-1} skupaj z operacijami +, * mod n kvadratni algoritem za množenje, deljenje ustreza množenju z inverznim elementom, Evklidov algoritem (EA), (Zn,+) je grupa z enoto 0, (Zn\{0},*) je grupa z enoto 1, kadar je n praštevilo, algoritem kvadriraj in zmnoži, kubični algoritem za potenciranje, 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.
    1. Classical cryptography: intoduction (simple ciphers), substitution cipher, Affine cipher, Vigenere cipher, Hill cipher, permutaton square algorithm for multiplication cipher. Cryptoanalysis, stream ciphers and connection to the problem about PINs, LFSR. Affine cipher, Vigenere cipher, Hill cipher, permutaton cipher, cryptoanalysis. Stream ciphers and the PIN problem.
    Some math background: modular arithmetics, Zn={0,1,...,n-1} together with the operations +, * mod n,, division corresponds to multiplication with the inverse element, Euclidean algorithm (EA), (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 powers, there exists an element a of Zp that 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.


  • 15. oktober - 21. oktober

    Tokovne šifre in povezava z nalogo o PIN-ih (za DN: porabite Kitajski izrek o ostankih (KIO)), LFSR.
    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).
    Stream ciphers and connection to the problem about PINs (for HW: use Chinese Remainder Theorem (CRT)), LFSR.
    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).

  • 22. oktober - 28. oktober

    Razširjen Evklidov algoritem za polinome, Feistelova šifra, opisa AES in 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 (napad na sredini), DESX, diferencialna kriptoanaliza.
    Extended Euclidean Algorithm (EEA) for polynomials, Fiestel cipher, descriptions of AES and 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 (Meet In the Middle Attack), DESX, differential cryptanalysis.

  • 29. oktober - 4. november

     4. RSA kriptosistem in faktorizacija: simetrična kriptografija (prednosti in pomanjkljivosti), hibridne sheme, upravljanje ključev, center zaupanja in distribucija, zdravstvena kartica, protokol izziv-odgovor, Evklidov algoritem in reševanje linearnih Diofantskih enačb (razširjeni EA), binarni EA, Lehmerjev algoritem.

    4. RSA cryptosysytem and factorization: symmetric cryptography (pros and cons), hybrid schemes, key management, TA and distribution, Slovenian health card, challenge-response protocol, Euclidean Algorithm and solving a linear Diophantine Equation (Extended EA), Binary EA, Lehmer algorithm, Fermat's little theorem.

  • 5. november - 11. november

    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.
      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.

  • 12. november - 18. november

    Odločitveni problem praštevilo, Legendrov in Jacobijev simbol, DA-naklonjen Monte Carlo algoritem, Solovay-Strassen algoritem, Gaussov izrek o kvadratni recipročnosti praštevil, Miler-Rabinov test za testiranje praštevilskosti, naključne napake in uporaba KIO.
    Še nekaj matematičnih osnov: Eulerjev kriterij in popolni kvadrati.

    The decision problem Composites, Legendre and Jacobi symbols, YES-biased Monte Carlo algorithm, 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.
    More math background: Euler's criterion and quadratic residues.
  • 19. november - 25. november

    Predebatirali smo prvo vprašanje s kolokvija.
    Napadi na RSA - odšifrirni eksponent kriptosistema RSA in Las Vegas algoritem. 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).
    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.

    We discussed the first question from the midterm.
    Attacks on RSA - decrypting exponent of the RSA cryptosystem and Las Vegas algorithm. Factoring algorithms (trial division up to 1012, Pollard p-1 algorithm, Dixon's random squares algorithm, practice, Vidav's question - factoring 1064+1).
    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.

  • 26. november - 2. december

    Pohlig-Hellmanov algoritem, metoda index calculus), 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). 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).
    Pohlig-Hellman algorithm, Index calculus method, 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). 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)
  • 3. december - 9. december

    DH na EC in DLP na EC, 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. Merkle-Hellmanov sistem z nahrbtnikom.
    6. Sheme za digitalne podpise: koncept in zahteve-možnosti, primerjava lastnoročnega in digitalnega podpisa, primer RSA. 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.
    DH on EC, DLP on EC, brute force attack, computer capacity and attacks on DSA, ECDSA and comparison with RSA and AES; comparison of signatures in prime fields and in a group on the elliptic curve, Certicom SigGen smart card, 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. 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.


  • 10. december - 16. december

    Slepi podpisi, ideja skupinskega podpisa, podpisi brez možnosti zanikanja, enosmerne funkcije in enkratni podpisi.
    Blind signatures, an idea of group signatures, undeniable signatures, oneway functions and one time signatures.

  • 17. december - 23. december

    7. Zgoščevalne funkcije: Definicije in terminologija, 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, uporaba zgoščevalnih funkcij, generični napadi, iterativne zgoščevalne funkcije, MDx-družina zgoščevalnih funkcij, RIPEMD, SHA-1, HMAC,... časovni žigi, digitalna potrdila.
    8. Upravljanje ključev: distribucija ključev, uskladitev ključev, certifikati, infrastruktura javnih ključev.

    eng.jpg 7. Hash functions: Definitions and Terminology, collision free , one-way, collision attacks (based on birthday paradox), hash function based on security of DLP, from simetric block ciphers, e.g. DES, applications of hash functions, generic attacks, iterated hash functions, MDx-family of hash functions, RIPEMD, SHA-1, HMAC,... timestamping, digital certificates.
    8. Key management
    :
    key distribution, key agreement, certificates, infrastucture of public keys.


  • 7. januar - 13. januar

    Blomova shema (posplošitev), Avtentikacijska drevesa, Diffie-Hellmanov distribucija ključev, Certifikati (CA), Infrastruktura javnih ključev (PKI), Modeli zaupanja, Secure Electronic Transaction (SET), Lista preklicanih certifikatov (CRL), Kerberos, Diffie-Hellmanova uskladitev ključev, Overjena uskladitev ključev (AKA, primer station-to-station protokol STS), MTI Protokoli za dogovor o ključu, Uskladitev ključev s ključi, ki se sami overijo (Giraultova shema), Internet (napadi na TCP/IP), Internet Engineering Task Force (IETF), IPsec: Virtual Private Networks (VPNs), Secure Sockets Layer (SSL), Google in ECC.

      Blom's scheme (generalization), Authentication trees, Diffie-Hellman Key Predistribution, Certification Authorities (CAs), Public-Key Infrastructure (PKI), Trust models, Secure Electronic Transaction (SET), Certificate revocation lists, Kerberos, Diffie-Hellman Key Exchange, Authenticated Key Agreement (AKA, an example station-to-station protocol STS), MTI Key Agreement Protocols, Key Agreement Using Self-certifying Keys (Girault scheme), Internet (attacks on TCP/IP), Internet Engineering Task Force (IETF), IPsec: Virtual Private Networks (VPNs), Secure Sockets Layer (SSL), Google and ECC.


  • 14. januar - 20. 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*
    11. Sheme za deljenje skrivnosti*
    12. Psevdno naključna zaporedja

    13. Dokazi brez razkritja znanja*
    14. Računalniška varnost

    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*
    11. Secret Sharing Schemes*

    12. Pseudo-random number generators
    ;

    13. Zero-Knowledge Proofs*

    14. Computer Security
    Digital cash
    (main actors: payer, payee, bank; online/offline, anonymous).