Υπολογιστική Κρυπτογραφία
Section outline
-
Χειμερινό Εξάμηνο 2020-2021
Διδάσκοντες:
- Στάθης Ζάχος, Καθηγητής (zachos@cs.ntua.gr)
- Άρης Παγουρτζής, Καθηγητής (pagour@cs.ntua.gr)
- Πέτρος Ποτίκας, Ε.Δι.Π. (ppotik@cs.ntua.gr)
Βοηθοί Διδασκαλίας:
- Παναγιώτης Γροντάς, Υ.Δ. (pgrontas@gmail.com)
- Γιάννης Παπαϊωάννου, Υ.Δ. (ipap@corelab.ntua.gr)
- Θωμάς Σουλιώτης, Υ.Δ.
- Ιάσων Μηλιώνης (jasonmili DOT cs AT gmail DOT com)
Διαλέξεις:
- Τρίτη 12:00-14:30 [ΑΛΜΑ: 12:00-14:00]
- Παρασκευή 18:00-19:15 [ΑΛΜΑ: 17:45-19:45]
(ΠΡΟΣΟΧΗ: οι ώρες έχουν τροποποιηθεί)
Έναρξη: Τρίτη, 6 Οκτωβρίου 2020
Σύνδεσμος webex: δείτε τις ανακοινώσεις
Βασική βιβλιογραφία:
[ΖΠΓ]: Ε. Ζάχος, Α. Παγουρτζής, Π. Γροντάς: Υπολογιστική Κρυπτογραφία, Κάλλιπος, 2015.
[LK2]: Jonathan Katz and Yehuda Lindell: Introduction to Modern Cryptography (2nd edition).
[BoSh]: D. Boneh and V. Shoup: A Graduate Course in Applied Cryptography (free draft, κατεβάστε την τελευταία έκδοση) -
ΤΡΙΤΗ 6/10
- Διαδικαστικά.
- Εισαγωγή.
- Στόχοι της Κρυπτογραφίας.
- Επισκόπηση βασικών λειτουργιών και πρωτοκόλλων.
- Βίντεο της διάλεξης (password: θα σταλεί με email)
- (ΠΡΟΣΟΧΗ: Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο.)
ΠΑΡΑΣΚΕΥΗ 9/10
- Κλασικά συστήματα (αντικατάστασης, Καίσαρα, Vigenere cipher) και κρυπτανάλυσή τους.
- Δείκτης σύμπτωσης (Coincidence Index).
Slides: Lec1 (1-19) (προσωρινά)
Βίντεο της διάλεξης (password: θα σταλεί με email)
[Ισχύουν οι περιορισμοί χρήσης που αναφέρονται παραπάνω]
Προτεινόμενη μελέτη:
- [ΖΠΓ]: κεφ. 1 (1.1 & 1.2)
- [LK2]: κεφ. 1.2, 1.3
- Διαδικαστικά.
-
ΤΡΙΤΗ 13/10
- Τέλεια μυστικότητα (perfect secrecy). Ισοδύναμες συνθήκες. Random Shift cipher. One-time pad. Unicity distance.
- Ορισμοί ασφάλειας, υπολογιστική ασφάλεια.
- Κρυπτοσυστήματα ρεύματος, μετάθεσης και γινομένου.
- Ασύμμετρη κρυπτογραφία: κρυπτοσύστημα "σακιδίου" Merkle-Hellman, επίθεση Shamir.
Slides: Lec1 (20-42) (προσωρινά)
Βίντεο της διάλεξης (password: θα σταλεί με email)
[Ισχύουν οι περιορισμοί χρήσης που αναφέρονται παραπάνω]
Προτεινόμενη μελέτη:
- [ΖΠΓ]: κεφ. 1.4, 5.7 (έως 5.7.3, συνοπτικά), 6.3
- [BoSh]: κεφ. 2.2
- [LK2]: κεφ. 2
ΠΑΡΑΣΚΕΥΗ 16/10
- Εισαγωγή στη θεωρία αριθμών, διαιρετότητα, ΜΚΔ, αλγόριθμος Ευκλείδη
- Εύρεση αντιστρόφου σε αριθμητική υπολοίπων
- Συζήτηση 1ης σειράς ασκήσεων
Βίντεο της διάλεξης [Ισχύουν οι περιορισμοί χρήσης που αναφέρονται παραπάνω]
-
ΤΡΙΤΗ 20/10
- Αριθμητική υπολοίπων. Θεώρημα Fermat και Euler.
- Κινέζικο Θεώρημα Υπολοίπων (CRT).
- Θεωρία ομάδων, τάξη στοιχείου και ομάδας, κυκλικές ομάδες, γεννήτορες.
- Σύμπλοκα, ομάδα πηλίκο, Θεώρημα Lagrange.
Βίντεο της διάλεξης [Ισχύουν οι περιορισμοί χρήσης που αναφέρονται παραπάνω]
Προτεινόμενη μελέτη: [ΖΠΓ] 2.1, 2.2, 2.3 και [LK2] 7.1, 7.3 [7.3.1, 7.3.3] (συμπληρωματικά)
ΠΑΡΑΣΚΕΥΗ 23/10- Έλεγχος πρώτων με θεώρημα του Fermat
- Η δομή των ομάδων Z*p και U(Zpq)
- Τετραγωνικά Υπόλοιπα, τετραγωνικές ισοτιμίες, κριτήριο Euler
Βίντεο της διάλεξης [Ισχύουν οι περιορισμοί χρήσης που αναφέρονται παραπάνω]
Προτεινόμενη μελέτη: [ΖΠΓ] 2.4, [LK2] 7.1-7.3 (συμπληρωματικά)
- Αριθμητική υπολοίπων. Θεώρημα Fermat και Euler.
-
ΤΡΙΤΗ 27/10
- Σύμβολα Legendre και Jacobi
- Ευεπίλυτα και δυσεπίλυτα αριθμοθεωρητικά προβλήματα
Προτεινόμενη μελέτη: [ΖΠΓ] 2.4, [LK2] 7.1-7.3 (συμπληρωματικά)
- Εισαγωγή στην ψευδοτυχαιότητα, γεννήτριες ψευδοτυχαιότητας
Προτεινόμενη μελέτη: [LK2] 3.3, [BoSh] 3.1 [ΖΠΓ] 5.7ΠΑΡΑΣΚΕΥΗ 30/10
- Η γεννήτρια ψευδοτυχαιότητας Blum-Blum-Shub
- Κρυπτοσυστήματα ροής
- Η γεννήτρια RC4
Προτεινόμενη μελέτη: [LK2] 3.3, 3.6 [BoSh] 3.2, 3.9, 3.10, [ΖΠΓ] 5.7Βίντεο της διάλεξης [Ισχύουν οι περιορισμοί χρήσης που αναφέρονται παραπάνω] - Σύμβολα Legendre και Jacobi
-
ΤΡΙΤΗ 03/11
- Καταχωρητές γραμμικής ανάδρασης (LFSR)
Προτεινόμενη μελέτη: [ΖΠΓ] 5.7 (έως και 5.7.3)
- Κρυπτοσυστήματα τμήματος.
- Δίκτυα Feistel.
- Κρυπτοσύστημα DES, S-boxes, MITM attack.
- Βελτιώσεις: 3-DES, DES-X.
Προτεινόμενη μελέτη: [ΖΠΓ] 5.1-5.3Βίντεο της διάλεξης [ισχύουν περιορισμοί - δείτε παραπάνω]ΠΑΡΑΣΚΕΥΗ 06/11
Συζήτηση για την 2η σειρά ασκήσεων
Βίντεο της διάλεξης [ισχύουν περιορισμοί - δείτε παραπάνω]
- Καταχωρητές γραμμικής ανάδρασης (LFSR)
-
ΤΡΙΤΗ 10/11Slides: Lec4 (22-25)
Προτεινόμενη μελέτη: [ΖΠΓ] 5.3.4
- AES
Προτεινόμενη μελέτη: [ΖΠΓ] 5.4-5.6
- Block ciphers: σύνοψη
Βίντεο της διάλεξης [Ισχύουν περιορισμοί - δείτε παραπάνω]ΠΑΡΑΣΚΕΥΗ 13/11- AES
https://en.wikipedia.org/wiki/Advanced_Encryption_StandardΠροτεινόμενη μελέτη: [ΖΠΓ] κεφ. 6.1Βίντεο της διάλεξης [Ισχύουν περιορισμοί - δείτε παραπάνω] -
ΠΑΡΑΣΚΕΥΗ 20/11
-
ΤΡΙΤΗ 24/11
- Επιθέσεις γενεθλίων
- Επέκταση συναρτήσεων κατακερματισμού Merkle-Damgard
- Δέντρα Merkle
Προτεινόμενη μελέτη: [ΖΠΓ] κεφ. 8.2-8.3Βίντεο της διάλεξης [Ισχύουν περιορισμοί - δείτε παραπάνω]ΠΑΡΑΣΚΕΥΗ 27/11- Εφαρμογές συναρτήσεων κατακερματισμού
Βίντεο της διάλεξης [Ισχύουν περιορισμοί - δείτε παραπάνω] -
ΤΡΙΤΗ 1/12 - RSA
- Κρυπτογραφία Δημοσίου Κλειδιού
- Ορισμός RSA, επιλογή παραμέτρων
- Ασφάλεια RSA και αριθμοθεωρητικά προβλήματα
Διαφάνειες (1-22)Βίντεο της διάλεξης [ισχύουν περιορισμοί, βλ. παραπάνω]ΠΑΡΑΣΚΕΥΗ 4/12
- RSA: επίθεση μικρού ιδιωτικού εκθέτη
- RSA: ισοδυναμία αποκάλυψης ιδιωτικού εκθέτη με παραγοντοποίηση
- Συζήτηση για την 3η σειρά ασκήσεων
Βίντεο της διάλεξης [ισχύουν περιορισμοί, βλ. παραπάνω]
Προτεινόμενη μελέτη εβδομάδας[ΖΠΓ]: Ενότητες 6.1, 6.2, 6.4
[LK2]: Ενότητες 11.1, 11.2, 11.5.1, 11.5.2, 11.5.4, 11.5.6
-
ΤΡΙΤΗ 8/12
- RSA: ασφάλεια ιδ. εκθέτη σε σχέση με παραγοντοποίηση (επανάληψη),
oμοιότητες με έλεγχο πρώτων αριθμών Miller-Rabin - Επίθεση κοινού γινομένου
- Μοντελοποίηση ασφάλειας
- Έλλειψη ασφάλειας IND-CPA, IND-CCA, malleability στο κλασικό RSA
- Παραλλαγές για IND-CPA, IND-CCA. Padded RSA, RSA-OAEP
Διαφάνειες (21-22, 30-35, 41-51)Βίντεο της διάλεξης [ισχύουν περιορισμοί, βλ. παραπάνω]ΠΑΡΑΣΚΕΥΗ 11/12
- RSA: δυσκολία διαρροής ενός bit (location, parity)
Διαφάνειες (36-40)- Εισαγωγή στον Διακριτό Λογάριθμο: ανταλλαγή κλειδιού Diffie-Hellman.
- Αλγόριθμος Shanks
- RSA: ασφάλεια ιδ. εκθέτη σε σχέση με παραγοντοποίηση (επανάληψη),
-
ΤΡΙΤΗ 15/12
- Διακριτός Λογάριθμος: αλγόριθμος Pohlig-Hellman
- Το κρυπτοσύστημα ElGamal (ορισμός, ασφάλεια, σχέση με CDHP)
Βίντεο της διάλεξης [ισχύουν περιορισμοί, βλ. παραπάνω]
ΠΑΡΑΣΚΕΥΗ 18/12
- Κρυπτοσύστημα ElGamal: Ασφάλεια IND-CPA, malleability
- Εκθετικό ElGamal
- Σχήμα Δέσμευσης Pedersen
Βίντεο της διάλεξης [ισχύουν περιορισμοί, βλ. παραπάνω]
Προτεινόμενη μελέτη εβδομάδας
[ΖΠΓ]: Ενότητες 6.5, 9.2, 9.3
[LK2]: Ενότητες 9.2.1, 9.2.2, 11.4.1, 11.4.2, 11.4.4, 13.3
- Διακριτός Λογάριθμος: αλγόριθμος Pohlig-Hellman
-
ΤΡΙΤΗ 22/12
- Ψηφιακές υπογραφές: ορισμός - μοντελοποίηση ασφάλειας
- Ψηφιακές υπογραφές RSA, καθολική πλαστογράφηση
- Full Domain Hash RSA, random oracle model
- Ψηφιακές υπογραφές ElGamal και DSA
Βίντεο της διάλεξης [ισχύουν περιορισμοί, βλ. παραπάνω]
Προτεινόμενη μελέτη: [ΖΠΓ] Κεφ. 7 (έως και 7.6.2)
-
ΠΑΡΑΣΚΕΥΗ 8/1
- Διαλογικές αποδείξεις μηδενικής γνώσης
- Σ-πρωτόκολλα
- Μη διαλογικές αποδείξεις μηδενικής γνώσης
- Ηλεκτρονικές ψηφοφορίες
Βίντεο της διάλεξης [ισχύουν περιορισμοί, βλ. παραπάνω]
Προτεινόμενη μελέτη εβδομάδας
[ΖΠΓ]: Κεφ. 10, 11.1 (11.1.1 έως 11.1.3)
[BoSh]: Κεφ. 19.4, 19.7 [προαιρετικά: 19.5, 19.6, 19.8]
-
ΤΡΙΤΗ 12/1
- Εισαγωγή σε Blockchain & Consensus
- Εισαγωγή στο Bitcoin (transactions, blocks, proof-of-work)
Βίντεο της διάλεξης [ισχύουν περιορισμοί, βλ. παραπάνω]
ΠΑΡΑΣΚΕΥΗ 15/1
- Τυφλές Υπογραφές και εφαρμογές
Υπογραφές μιας χρήσης. Αδιαμφισβήτητες υπογραφές, υπογραφές Fail-Stop
Διαφάνειες (19-20, 23-31)
- Εισαγωγή σε Blockchain & Consensus