Στοιχεία Θεωρίας Αριθμών και Εφαρμογές στην Κρυπτογραφία (ΣΗΜΜΥ)
Κρυπτογραφία και Πολυπλοκότητα (ΣΕΜΦΕ, ΜΠΛΑ)
χειμερινό εξάμηνο 2012-2013

● Γενικά ● Ανακοινώσεις ● Υλικό ● Παρουσιάσεις εργασιών ●

Γενικά

Διδάσκοντες

  • Στάθης Ζάχος, Καθηγητής ()
  • Άρης Παγουρτζής, Eπίκουρος Καθηγητής ()

Βοηθοί διδασκαλίας

  • Δημήτρης Σακαβάλας, Υ.Δ. ()
  • Γιώργος Ζηρδέλης, Υ.Δ. ()

Ώρες - αίθουσα - ώρες γραφείου

  • Δευτέρα, 10:45-13:30 (Θεωρία)
  • Παρασκευή, 11:45-12:30 (ασκήσεις)
  • Αίθουσα 1.1.29 (κτ. Ηλεκτρολόγων)
  • Ώρες γραφείου: Τετάρτη 15:00-17:00, στο CoReLab (1.1.30)

Βαθμολογικό σχήμα

  • Ασκήσεις: 2 μονάδες.
  • Εργασία: 2 μονάδες.
  • Καταγραφή σημειώσεων μαθήματος (μίας εβδομάδας): 1 μονάδα.
  • Τελικό διαγώνισμα: 6 μονάδες. Προϋπόθεση για το "πέντε": 2/6 στο τελικό διαγώνισμα.

Βιβλιογραφία

  1. Σημειώσεις Ε. Ζάχου, ΕΜΠ, 2012.
  2. D. Stinson: Cryptography: Theory and Practice, 3rd edition, CRC Press, 2005.
  3. A. Menezes, P. van Oorschot, and C. Vanstone: Handbook of Applied Cryptography: http://www.cacr.math.uwaterloo.ca/hac.
  4. J. Katz and Y. Lindell: Introduction to Modern Cryptography, Chapman & Hall/CRC Press, 2007.
  5. V. Shoup: A Computational Introduction to Number Theory and Algebra: http://shoup.net/ntb/.
  6. B. Schneier: Applied Cryptography: http://www.schneier.com/book-applied.html.
  7. W.Trappe, L. Washington: Introduction to Cryptography with Coding Theory.
  8. A.Κιαγιάς: Τεχνικές Σύγχρονης Κρυπτογραφίας: σημειώσεις

Ανακοινώσεις

  • 26/05/2013: Βαθμολογία κανονικής περιόδου: pdf
  • 28/02/2013: Η εξέταση της 1/3/2013 θα πραγματοποιηθεί στην αίθουσα 1.1.29.
  • 14/2/2012: Η εξέταση του μαθήματος περιλαμβάνει ένα μέρος με κλειστά βιβλία (θεωρία και απλές ασκήσεις) και ένα με ανοιχτά (ασκήσεις, λίγο πιο δύσκολες).
    Ενδεικτικό διαγώνισμα (τα θέματα 1-6 ήταν με κλειστά βιβλία, τα υπόλοιπα με ανοιχτά): pdf
    Ύλη μαθήματος για την εξέταση: (i) Σημειώσεις διαλέξεων. (ii) Σημ. Ζάχου: κεφ. 1, 2 (συνοπτικά), 3, 6, 7 (AKS συνοπτικά), 8, 9 (έως και 9.4), 11 (συνοπτικά), 12, 13, 14, 15, 16, 17 (συνοπτικά).
  • 27/01/2013: Αναρτήθηκε το πρόγραμμα παρουσιάσεων της 28/1 και της 1/2 (δείτε παρακάτω).
  • 27/01/2013: Η εξέταση του μαθήματος μεταφέρεται για την 1/3/2013, ώρα 3μμ. Η αίθουσα θα ανακοινωθεί σύντομα.
  • 5/10/2012: Το πρώτο μάθημα θα γίνει στις 8/10/2012.

Ύλη Διαλέξεων και Σημειώσεις

Ημερομηνία Περιεχόμενο διάλεξης Σημειώσεις
8/10 Διοικητικά του μαθήματος. Εισαγωγή στην κρυπτογραφία και κρυπτολογία. Κλασικά συστήματα (Καίσαρα, ολίσθησης, αντικατάστασης. Vigenere cipher). Κρυπτανάλυση συστημάτων αντικατάστασης με στατιστικές συχνότητες. Κρυπτανάλυση Vigenere με Kasiski test, και χρήση δείκτη σύμπτωσης (Coincidence Index). pdf, tex
15/10 Περισσότερα κλασικά συστήματα (Affine cipher, Permutation cipher, κρυπτοσυστήματα γινομένου). One-time pad. Τέλεια μυστικότητα (perfect secrecy). pdf
26/10 Ασκήσεις: ισοδυναμία συνθηκών τέλειας μυστικότητας, τέλεια μυστικότητα με μη ισοπίθανα κλειδιά, επαναχρησιμοποίηση κλειδιού στο one-time pad, ιδέες για κρυπτανάλυση του Permutation Cipher, idempotency του Affine Cipher. pdf pending
29/10 Εισαγωγή στη Θεωρία Αριθμών. Διαιρετότητα, πρώτοι αριθμοί. Το Θεμελιώδες Θεώρημα της Αριθμητικής. Κρυπτογραφία Δημοσίου Κλειδιού. Το κρυπτοσύστημα Σακιδίου Merkle-Hellman. pdf (draft)
2/11 Ασκήσεις: απλός διαμοιρασμός μυστικού, επίλυση γραμμικής ισοτιμίας, ασκήσεις διαιρετότητας. pdf (draft)
5/11 Αποδοτικοί αριθμητικοί αλγόριθμοι: αλγόριθμος Ευκλείδη (απλός και επεκτεταμένος), υπολογισμός αντιστρόφου modulo n, επαναλαμβανόμενος τετραγωνισμός. Η συνάρτηση φ του Euler. Ομάδες, υποομάδες, κλειστότητα, κυκλικές ομάδες, γεννήτορας, τάξη ομάδας. Σύμπλοκα, τάξη υποομάδας, Θεωρήματα Lagrange, Fermat, Euler. Κινέζικο θεώρημα υπολοίπων (εισαγωγή). pdf (draft)
9/11 Ασκήσεις: Θεμελιώδες Θεώρημα κυκλικών ομάδων: κυκλικότητα υποοομάδων, μοναδικότητα τάξης. Αλγόριθμος ακέραιας διαίρεσης (επιγραμματικά). pdf (draft v2)
12/11 Κινέζικο Θεώρημα Υπολοίπων. Τετραγωνικά υπόλοιπα. Επίλυση τετραγωνικής ισοτιμίας. Σύμβολα Legendre και Jacobi: αποδοτικός υπολογισμός (κριτήριο Euler, νόμος τετραγωνικής αντιστροφής). Το κρυπτοσύστημα RSA: ορισμός, ορθότητα, σχέση με παραγοντοποίηση, επίθεση κοινού γινομένου. pdf (draft)
19/11 RSA: εύρεση ιδιωτικού κλειδιού => πιθανοτικός αλγόριθμος παραγοντοποίησης του modulus. Έλεγχοι πρώτων αριθμών: Fermat test, Miller-Rabin test. Ορθότητα ελέγχου Miller-Rabin.
Παραγοντοποίηση: η μέθοδος ρ και το παράδοξο των γενεθλίων.		 pdf (draft v2)
23/11 Ασκήσεις: ασφάλεια των bits του κρυπτοκειμένου στο RSA, επίθεση μικρού εκθέτη. Πιθανοτική κρυπτογράφηση με το RSA. pdf (draft v2)
26/11 Το πρόβλημα του διακριτού λογαρίθμου (DLP) και η ασφάλεια του τελευταίου bit στο DLP. Ανταλλαγή κλειδιού Diffie-Hellman. Το κρυπτοσύστημα δημοσίου κλειδιού ElGamal και μια επίθεση για αυτό υπό προυποθέσεις. pdf (draft)
30/11 Ασκήσεις: Το πρόβλημα απόφασης Diffie-Hellman (DDH). Το υπολογιστικό πρόβλημα Diffie-Hellman (CDH). Η σχέση των DDH, CDH και DLP. Αναγωγή από το πρόβλημα της εγκυρότητας κρυπτοκειμένων ElGamal στο DDH και το αντίστροφο.
Αλγόριθμοι επίλυσης του DLP. Εξαντλητικοί αλγόριθμοι και αλγόριθμοι ανταλλαγής μνήμης χρόνου. Ο αλγόριθμος του Shanks (Baby step - Giant step). 		pdf (draft v2)
7/12 Ασκήσεις: Διακριτός λογάριθμος στο Z*_p και οι πρώτοι Sophie Germain. pdf (draft)
14/12 Ψηφιακές υπογραφές. Το σχήμα υπογραφής RSA. Το σχήμα υπογραφής ElGamal, σενάρια πλαστογράφησης. pdf (draft)
17/12 Πρότυπο Ψηφιακής Υπογραφής (Digital Signature Standard). Υπογραφές μιας χρήσης: Lamport scheme, βελτίωση Bos-Chaum. Τυφλές υπογραφές (blind signatures): Chaum's scheme. Αδιαμφισβήτητες υπογραφές (undeniable signatures): Chaum-van Antwerpen scheme. pdf (draft)
21/12 Υπογραφές Fail-Stop: van Heyst-Pedersen scheme. Απόδειξη πλαστογράφησης: unconditional security.
Συναρτήσεις κατακερματισμού (hash functions): ορισμός, επιθυμητές ιδιότητες (ελευθερία συγκρούσεων, μονής κατεύθυνσης). Ιεράρχηση επιθυμητών ιδιοτήτων. Birthday attacks: το Παράδοξο των Γενεθλίων. 		pdf (draft)
11/1 Συνάρτηση κατακερματισμού Chaum-van Heisjt-Pfitzmann: ελευθερία συγκρούσεων ισοδύναμη με υπόθεση Διακριτού Λογαρίθμου. Μέθοδος Merkle-Damgard για επέκταση συναρτήσεων κατακερματισμού.

Ανταλλαγή κλειδιού Diffie-Hellman. Σχήματα αναγνώρισης: μέθοδος κατασκευής από κρυπτοσυστήματα (κλασσικά και δημοσίου κλειδιού). Σχήμα του Schnorr: πληρότητα (completeness) και ορθότητα (soundness). 		pdf1 pdf2 (draft)
14/1 Σχήματα αναγνώρισης μηδενικής γνώσης: σχήματα Fiat-Shamir και Feige-Fiat-Shamir. Πιθανοτική κρυπτογράφηση: μέθοδοι Goldwasser-Micali (1-bit) και Blum-Goldwasser. Γεννήτρια ψευδοτυχαίων BBS (Blum-Blum-Shub). Μέθοδος παραγοντοποίησης Dixon (βάσεις παραγοντοποίησης). pdf
18/1 Σχήμα προκατανομής κλειδιών (key predistribution) του Blom. Σχήμα κατανομής απορρήτων (secret sharing) του Shamir.

Εισαγωγή στα κρυπτοσυστήματα πακέτου, Δίκτυα Feistel, αποκρυπτογράφηση με αντιστροφή κλειδιών. 		pdf (draft v2)
21/1 Θεωρία υπολογιστικής πολυπλοκότητας. Μη-ντετερμινιστικοί και πιθανοτικοί αλγόριθμοι. Κλάσεις P, NP, BPP, RP, ZPP. Δένδρα υπολογισμού. Τεχνικές ενίσχυσης της πιθανότητας σωστής απάντησης στους πιθανοτικούς αλγόριθμους. Πλειοψηφικοί ποσοδείκτες. Παίγνια Arthur-Merlin και συστήματα διαλογικών αποδείξεων. Αποδείξεις μηδενικής γνώσης. (Σημ. Ζάχου: κεφ. 16, 17),
pdf pending
28/1 Η κλάση UP. Η απόδειξη ότι UP γνήσιο υπερσύνολο της P ισοδυναμεί με ύπαρξη συναρτήσεων μονής κατεύθυνσης.
Περιγραφή του κρυπτοσυστήματος DES, S-boxes. Aποκρυπτογράφηση με αντιστροφή κλειδιών. Η ιδιότητα της συμπληρωματικότητας. Επιθέσεις στο DES.

Παρουσιάσεις σπουδαστών. 		pdf (draft)
1/2 Κρυπτοσυστήματα πακέτου (block ciphers): τρόποι λειτουργίας (ECB, CBC, CFB, OFB). Επίδραση λαθών μετάδοσης στους διάφορους τρόπους λειτουργίας, self-recovery. Χρήση CBC για ακεραιότητα, αυθεντικοποίηση (MAC). Παραγωγή key stream από CFB/OFB. Κρυπτοσυστήματα ρεύματος (stream ciphers): περίοδος κλειδιού, linear feedback shift registers.

Παρουσιάσεις σπουδαστών. 		pdf (draft)

Ασκήσεις

Εργασία (project)

Κείμενα για συμπληρωματική μελέτη

  • Ε. Ζάχος, Α. Παγουρτζής, Δ. Φωτάκης: "Σύντομη Εισαγωγή στη Θεωρία Πολυπλοκότητας":pdf
  • Ε. Ζάχος: "Computational Complexity Notes (in English)":pdf
  • V. Shoup: "A Primer on Algebra and Number Theory for Computer Scientists":pdf
  • R. Rivest, A. Shamir, L. Adleman: "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems": ps (gzipped), pdf.
  • W. Diffie, M. Hellman: "New Directions in Cryptography": ps (gzipped), pdf.
  • S. Goldwasser, M. Belare: Lecture Notes on Cryptography: pdf.
  • M. Agrawal, N. Kayal, N. Saxena: Primality is in P: pdf.

Links

Τελευταία ανανέωση: 26/5/2013