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

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

Γενικά

Διδάσκοντες

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

Υπεύθυνος ασκήσεων

  • Πέτρος Ποτίκας, Ε.Δι.Π. ()

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

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

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

  • Έναρξη: 20/10/2014
  • Δευτέρα, 10:45-12:30 (θεωρία)
  • Παρασκευή, 12:45-14:30 (θεωρία - ασκήσεις)
  • Αίθουσα 1.1.29 (παλιό κτ. Ηλεκτρολόγων ΕΜΠ)
  • Ώρες γραφείου: Τετάρτη 14:00-15:00, στο CoReLab (1.1.30)

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

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

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

  • [5/11/2015]: Βαθμολογία επαναληπτικής περιόδου ακαδ. έτους 2014-15: pdf.
  • [18/9/2015]: Η επαναληπτική εξέταση του μαθήματος παραμένει για την 21/9/2015, ώρα 12:00 μμ. Η εξέταση θα γίνει στην αίθουσα 1.1.29 του Παλιού Κτ. Ηλεκτρολόγων ΕΜΠ.
  • [27/5/2015]: Βαθμολογία κανονικής περιόδου ακαδ. έτους 2014-15: pdf.
  • [2/3/2015]: Η παράδοση της 2ης σειράς ασκήσεων παρατείνεται μέχρι τις 6/3, 00:00.
  • [26/2/2015]: Κατόπιν συνεννόησης με τους σπουδαστές, η εξέταση του μαθήματος θα πραγματοποιηθεί στις 6/3, ώρα 15:00-18:00, στην αίθουσα 1.1.29.
  • [29/1/2015]: Αναρτήθηκε το πρόγραμμα παρουσιάσεων για τις 30/1/2015 (δείτε παρακάτω).
  • [27/1/2015]: To moodle είναι έτοιμο για να ανεβάσετε τις εργασίες σας.
  • [16/1/2015]: Αναρτήθηκε η δεύτερη σειρά ασκήσεων (δείτε παρακάτω).
  • [5/1/2015]: Έχουν αναρτηθεί τα θέματα για τη Μικρή και τη Μεγάλη Εργασία και δίπλα τα ονόματα των φοιτητών που έχουν αναλάβει τη συγκεκριμένη εργασία.
  • [19/12/2014]: Η υποβολή της 1ης σειράς παρατείνεται για 24 ώρες, ενώ για κάθε ημέρα καθυστέρησης αφαιρείται 10% από το βαθμό, με ανώτερο όριο τις πέντε ημέρες (-50%). Σε περίπτωση τμηματικής υποβολής η μείωση αφορά το μέρος που υποβάλλεται καθυστερημένα.
  • [18/12/2014]: Η υποβολή των ασκήσεων θα γίνει ηλεκτρονικά μέσω του moodle του Εργαστηρίου Λογικής και Υπολογισμών που βρίσκεται στη διεύθυνση

    https://www.corelab.ntua.gr/moodle

    Οδηγίες:
    Επιλέγετε το μάθημα Υπολογιστική Κρυπτογραφία και μετά Continue. Στη συνέχεια κάνετε κλικ στο Create New Account. Εκεί θα σας ζητηθούν τα στοιχεία σας, ενώ στο Other Fields επιλέξτε την Ιδιότητά σας (Προπτυχιακός/Μεταπτυχιακός), τη Σχολή στην οποία ανήκετε και συμπληρώστε τον Αριθμό Μητρώου σας. Στο τέλος κάνετε κλικ στο Create my new account.
    Στη συνέχεια θα λάβετε e-mail στη διεύθυνση που δηλώσατε για να επιβεβαιώσετε τον λογαριασμό σας. Σας ζητάει να εγγραφείτε στο μάθημα (Υπολογιστική Κρυπτογραφία). Κάνοντας κλικ στο Enrol me εγγράφεστε στο μάθημα. Στη συνέχεια σας εμφανίζει την 1η Σειρά Ασκήσεων και διάφορες πληροφορίες.
    Έχετε δικαίωμα να υποβάλετε μέχρι 5 φορές το αρχείο με τις λύσεις σας. Η προθεσμία υποβολής της 1ης Σειράς Ασκήσεων είναι Παρασκευή 19/12/2014, 23:59:59 (όπως φαίνεται και στη σελίδα). Μετά τη λήξη, καμία παράδοση ασκήσεων και με κανένα άλλο τρόπο δε θα γίνεται δεκτή.
  • [14/12/2014]: Η παράδοση των ασκήσεων παρατείνεται μέχρι τις 19/12/2014. Οδηγίες υποβολής θα δοθούν σε επόμενη ανακοίνωση.
  • [20/11/2014]: Αναρτήθηκε η πρώτη σειρά ασκήσεων (δείτε παρακάτω). Οδηγίες υποβολής θα δοθούν σε επόμενη ανακοίνωση.
  • [9/10/2014]: Το πρώτο μάθημα θα γίνει στις 20/10/2014.

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

    Η ύλη θα ενημερώνεται τακτικά. Για ενδεικτική ύλη και σημειώσεις του μαθήματος δείτε την σελίδα του ακ. έτους 2013-2014 καθώς και προηγούμενων ετών.
Ημερομηνία Περιεχόμενο διάλεξης Διαφάνειες
20/10 Διοικητικά του μαθήματος. Εισαγωγή στην κρυπτογραφία και κρυπτολογία. Συμμετρική κρυπτογραφία vs κρυπτογραφία Δημοσίου Κλειδιού: μια πρώτη ματιά. Παραδείγματα κρυπτογραφικών πρωτοκόλλων. Στόχοι του μαθήματος.
pdf
24/10 Κλασικά συστήματα (αντικατάστασης, Καίσαρα, Vigenere cipher) και κρυπτανάλυσή τους. Δείκτης σύμπτωσης (Coincidence Index). pdf (1-18) handouts1
27/10 Τέλεια μυστικότητα (perfect secrecy). Ισοδύναμες συνθήκες. Μήκος κλειδιού. One-time pad. Random Shift cipher. pdf (19-31)
31/10 Γεννήτριες ψευδοτυχαιότητας. Ορισμός (t,ε)-ασφάλειας. Σχέση με μη διακρισιμότητα. Σημειώσεις L. Trevisan (σελ. 15-17)
3/11 Γεννήτριες ψευδοτυχαιότητας RC4, RSA-based, BBS. Κρυπτοσυστήματα ροής/ρεύματος. Κρυπτοσυστήματα γινομένου. Κρυπτοσύστημα σακιδίου. pdf (32-) Δείτε και Σημειώσεις L. Trevisan (σελ. 18-19)
7/11 Κρυπτοσυστήματα τμήματος. Τα δίκτυα Feistel. Aποκρυπτογράφηση με αντιστροφή κλειδιών. Εισαγωγή στο κρυπτοσύστημα DES. Ο ρόλος των S-boxes. Σύγχυση και διάχυση. Το πρόγραμμα παραγωγής κλειδιών. pdf (1-13)
handouts2
10/11 Επιθέσεις στο DES, MITM attack. Βελτιώσεις: 3-DES, DES-X. Τρόποι λειτουργίας block ciphers: ECB, CBC, CFB, OFB, CTR. Λάθη μετάδοσης, self-recovery. Χρήση για αυθεντικοποίηση (CBC-MAC). Authenticated encryption. Κρυπτοσυστήματα ροής από CFB/OFB/CTR. pdf (13-18)
24/11 Το κρυπτοσύστημα AES. Αλγεβρικός ορισμός των S-boxes και διαδικασίας Mixcolumns. Άλγεβρα πολυωνύμων. Αντιστρεψιμότητα του συστήματος. Σημειώσεις Ε. Ζάχου (σελ. 83-106)
Δείτε και: Laurie Brown's slides
28/11 Authenticated encryption. Τρόπος λειτουργίας CCM για κρυπτοσυστήματα τμήματος.
Εισαγωγή στη Θεωρία Αριθμών. Διαιρετότητα, Θεμελιώδες Θεώρημα της Αριθμητικής. Αλγόριθμος Ευκλείδη, υπολογισμός αντιστρόφου modulo n. 		pdf handoutsCCM

pdf (1-10)
handouts3
1/12 Η συνάρτηση φ του Euler. Αριθμητική modulo. Ο δακτύλιος Ζm. Θεωρία ομάδων, η ομάδα των units του Zm, κυκλικές ομάδες, γεννήτορας, τάξη ομάδας, δακτύλιοι, σώματα. Μικρό Θεώρημα Fermat, Θεώρημα Euler. Σύμπλοκα, τάξη υποομάδας, Θεώρημα Lagrange. pdf (11-22)
5/12 Έλεγχος πρώτων αριθμών Fermat. Αριθμοί Carmichael. Κινέζικο Θεώρημα Υπολοίπων. Ισομορφισμοί: Zm x Zn με Ζmn και U(Zm) x U(Zn) με U(Ζmn). pdf (23-29)
8/12 Η δομή της ομάδας Zp*. Η δομή της ομάδας U(Zn). Τετραγωνικά υπόλοιπα. Επίλυση τετραγωνικής ισοτιμίας. Σύμβολο Legendre. pdf (32-39)
12/12 Σύμβολα Legendre και Jacobi: αποδοτικός υπολογισμός (κριτήριο Euler, νόμος τετραγωνικής αντιστροφής). Ο έλεγχος πρώτων αριθμών Miller-Rabin και η απόδειξη ορθότητάς του. Ευεπίλυτα και δυσεπίλυτα αριθμοθεωρητικά προβλήματα. pdf (40-46)
15/12 Το κρυπτοσύστημα RSA: ορισμός, ορθότητα, σχέση με παραγοντοποίηση. Επιθέσεις στο RSA: επίθεση κοινού γινομένου pdf (1-7)
handouts4 (1-7)
19/12 RSA: μερική ανάκτηση πληροφοριών, semantic security, κριτήρια επιλογής παραμέτρων. Το κρυπτοσύστημα Rabin, ισοδυναμία με παραγοντοποίηση. pdf (8-14)
22/12 Το πρόβλημα του διακριτού λογαρίθμου (DLP). Αλγόριθμος Shanks. Ανταλλαγή κλειδιού Diffie-Hellman. Το πρόβλημα απόφασης Diffie-Hellman (DDH). Το υπολογιστικό πρόβλημα Diffie-Hellman (CDH). Η σχέση των προβλημάτων DDH, CDH και DLP. Το κρυπτοσύστημα δημοσίου κλειδιού ElGamal. Άσκηση: υπολογισμός διακριτού λογαρίθμου σε ομάδα τάξης 2^m. pdf (15-27)
9/1 Κρυπτογραφικές αναγωγές και υποθέσεις. Είδη ασφάλειας: IND-CPA, IND-CCA, IND-CCA2. Malleability. pdf
12/1 Απόδειξη μη διακρισιμότητας (IND-CPA) του κρυπτοσυστήματος ElGamal κάτω από την υπόθεση DDH. pdf
16/1 Ψηφιακές υπογραφές. Το σχήμα υπογραφής RSA. Το σχήμα υπογραφής ElGamal, σενάρια πλαστογράφησης. pdf (διαφ. 1-13)
handouts5 (διαφ. 1-13)
19/1 To Πρότυπο Ψηφιακής Υπογραφής (Digital Signature Standard). Υπογραφές μιας χρήσης: Lamport scheme, βελτίωση Bos-Chaum. Τυφλές υπογραφές (blind signatures): Chaum's scheme. Αδιαμφισβήτητες υπογραφές (undeniable signatures): Chaum-van Antwerpen scheme. Ασφάλεια έναντι πλαστογράφησης και αποποίησης: unconditional security. pdf (διαφ. 14-31)
23/1 Υπογραφές Fail-Stop: van Heyst-Pedersen scheme. Απόδειξη πλαστογράφησης: unconditional security.
Hash functions: ορισμός, επιθυμητές ιδιότητες (ελευθερία συγκρούσεων, μονής κατεύθυνσης). Ιεράρχηση επιθυμητών ιδιοτήτων. Συνάρτηση Chaum-van Heijst-Pfitzman. 		pdf (διαφ. 32-39)
26/1 Συναρτήσεις σύνοψης: μέθοδος επέκτασης Merkle-Damgård. Παράδοξο Γενεθλίων. Χρήσεις συναρτήσεων σύνοψης. Κρυπτογραφικά πρωτόκολλα. Πρωτόκολλα ταυτοποίησης Schnorr, διαμοιρασμού απορρήτων Shamir. Θέματα πολυπλοκότητας. Αποδείξεις γνώσης και αποδείξεις μηδενικής γνώσης. Επισκόπηση μαθήματος. pdf (διαφ. 40-49)
30/1 Παρουσιάσεις εργασιών σπουδαστών.

Ασκήσεις

Μεγάλη εργασία (project)

Μικρή εργασία

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

  1. Σημειώσεις Ε. Ζάχου - Α. Παγουρτζή, ΕΜΠ, 2014.
  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.Κιαγιάς: Τεχνικές Σύγχρονης Κρυπτογραφίας: σημειώσεις

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

  • Ε. Ζάχος, Α. Παγουρτζής, Δ. Φωτάκης: "Σύντομη Εισαγωγή στη Θεωρία Πολυπλοκότητας":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