2 of 49

ΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩΑΒΓΔΕΖΗΘΙΚ

ΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩΑΒΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡ

ΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩΑΒΓΔΕΖΗΘΙΚΛΜΝΞΟΠ

ΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩΑΒΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥ

ΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩΑΒΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤ

ΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩΑΒΓΔΕΖΗΘΙΚΛΜΝΞΟ

ΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩΑΒΓ

ΑΒΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩΑ

ΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩΑΒΓΔΕΖΗΘΙ

ΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩΑΒΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡ

ΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩΑΒΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦ

ΑΒΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩΑ

3 of 49

ΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩΑΒΓΔΕΖΗΘΙΚ

ΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩΑΒΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡ

ΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩΑΒΓΔΕΖΗΘΙΚΛΜΝΞΟΠ

ΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩΑΒΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥ

ΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩΑΒΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤ

ΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩΑΒΓΔΕΖΗΘΙΚΛΜΝΞΟ

ΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩΑΒΓ

ΑΒΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩΑ

ΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩΑΒΓΔΕΖΗΘΙ

ΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩΑΒΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡ

ΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩΑΒΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦ

ΑΒΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩΑ

4 of 49

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

Κρυπτολογία

Κρυπτογραφία

Κρυπτανάλυση

Βασικό αντικείμενο Κρυπτογραφίας

Η ασφάλεια των πληροφοριών και γενικώς η εξασφάλιση της επικοινωνίας μέσω μη ασφαλών διαύλων.

Βλέπουμε αρχικά με το τι ασχολείται η Κρυπτογραφία, δηλαδή με τον τομέα των επικοινωνιών και κυρίως με το πως μπορούμε να εξασφαλίσουμε την ασφάλεια των δεδομένων μας αν αυτά μεταφέρονται μέσα από ένα μη ασφαλή δίαυλο επικοινωνίας.
Εκτός από την ασφάλεια των δεδομένων βέβαια, θέλουμε με αυτή να εξασφαλίσουμε και μερικές ακόμη ιδιότητες της επικοινωνίας, όπως είναι για παράδειγμα η ιδιότητα της μη αποκήρυξης, σύμφωνα με την οποία ο αποστολέας ή ο παραλήπτης της πληροφορίας δεν μπορούν να αρνηθούν την αυθεντικότητα της μετάδοσης ή της δημιουργίας της, αντίστοιχα.

΄Έτσι, βλέπουμε στη βάση του διαγράμματος ταξινόμησης μας την Κρυπτογραφία, η οποία προσπαθεί να εξασφαλίσει κάποιες ιδιότητες της επικοινωνίας σαν αυτή που ανέφερα και στον αντίποδα αυτής, την Κρυπτανάλυση, που προσπαθεί να τις αναιρέσει.
Μαζί αυτές οι δύο αποτελούν την Κρυπτολογία.

5 of 49

Μη ασφαλής δίαυλος επικοινωνίας

Αποστολέας

Παραλήπτης

Αλίκη

Μπομπ

Μάλορι

Πως μπορεί η Αλίκη να στείλει ένα μήνυμα στον Μπομπ με ασφάλεια;

Κρυπτογράφηση

Κρυπτογραφικός αλγόριθμος

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

Σε αυτό το σημείο θα ήθελα να σας γνωρίσω τους βοηθούς μου για τις αναπαραστάσεις που θα ακολουθήσουν.
Έχουμε την Αλίκη, η οποία πάντα θα προσπαθεί να στείλει μηνύματα στον Μπομπ, ο οποίος μόνο θα λαμβάνει μηνύματα.
Και αυτό θα γίνεται συνήθως διαμέσου ενός μη ασφαλούς διαύλου επικοινωνίας, το οποίο σημαίνει ότι η πληροφορία που μεταφέρεται μπορεί να υποκλαπεί από κάποιον τρίτο, τον Μάλορι.
Οπότε, η ερώτηση η οποία καλούμαστε να απαντήσουμε είναι «Πως μπορεί η Αλίκη να στείλει ένα μήνυμα στον Μπομπ με ασφάλεια?», δηλαδή χωρίς να μπορεί ο Μάλορι να έχει πρόσβαση στο περιεχόμενο αυτών των μηνύματα.
Σχετική με την απάντηση σ΄ αυτήν την ερώτηση είναι η έννοια της Κρυπτογράφησης, μέσω της οποίας τα μηνύματα της Αλίκης μπορούν να μετασχηματιστούν σε μια άλλη μορφή την οποία δεν θα μπορεί να καταλάβει ο Μάλορι, αν υποκλέψει τα μηνύματα μέσω του μη ασφαλούς διαύλου.
Μαθηματικά, η κρυπτογράφηση γίνεται χρησιμοποιώντας έναν Κρυπτογραφικό Αλγόριθμο, δηλαδή έναν αλγόριθμο που μετασχηματίζει τα μηνύματα σε τέτοια μορφή που να μην μπορεί να αποκαλυφθεί το περιεχόμενο τους από μη εξουσιοδοτημένα άτομα, δηλαδή τον Μάλορι και τον κάθε Μάλορι.
Γενικά, όσον αφορά την μορφή του, ένας κρυπτογραφικός αλγόριθμος θα έχει ως είσοδο ένα αρχικό μήνυμα και ένα κλειδί, το οποίο χρησιμοποιείται στην κρυπτογράφηση και ως έξοδο ένα κρυπτογραφημένο κείμενο, δηλαδή το κείμενο που παράγεται από την διαδικασία της κρυπτογράφησης.
Γνωρίσαμε λοιπόν δύο έννοιες που σχετίζονται με την απάντηση αλλά ποια είναι η ακριβής απάντηση στην ερώτηση που θέσαμε? *Ν*

6 of 49

Καλούμε κρυπτοσύστημα ή κρυπτογραφικό σχήμα μια πεντάδα (P, C,K, E,D) , όπου :

・ P : ο χώρος των απλών κειμένων

・ C : ο χώρος των κρυπτογραφημένων κειμένων

・ K : ο χώρος των κλειδιών

・ E = {E_k : P → C| k ∈ K} : συναρτήσεις κρυπτογράφησης

・ D = {D_k : C → P| k ∈ K} : συναρτήσεις αποκρυπτογράφησης

Ισχύει ότι : ∀e ∈ K, ∃d ∈ K τέτοιο ώστε : D_d(E_e(m)) = m, ∀m ∈ P

Κρυπτογράφηση

Αποκρυπτογράφηση

Κλειδί Κρυπτογράφησης

Κλειδί Αποκρυπτογράφησης

E_e(m)

E_e

D_d(E_e(m))

D_d

Κρυπτοσύστημα

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

Θα είναι η έννοια του κρυπτοσυστήματος, το οποίο μαθηματικά ορίζεται όπως βλέπετε μπροστά σας, αλλά αντί απλά να κοιτάμε σύμβολα ας δούμε τι σημαίνει στη πράξη αυτό, πως δηλαδή δουλεύει ένα κρυπτοσύστημα :

Έχουμε για παράδειγμα την Αλίκη, η οποία προσπαθεί να στείλει ένα μήνυμα m και αυτό το μήνυμα θα αποτελεί ένα απλό κείμενο και άρα θα ανήκει στο χώρο P (plaintext).
Για να στείλει αυτό το μήνυμα με ασφάλεια θα πρέπει πρώτα να το κρυπτογραφήσει μέσω μιας συνάρτησης κρυπτογράφησης E_eτης οποίας η μορφή εξαρτάται από το κλειδί κρυπτογράφησης e μικρό (encryption), το οποίο θα δούμε από που προέρχεται στη συνέχεια.
Αφού κρυπτογραφηθεί, το μήνυμα αυτό περνάει σε αυτήν τη μορφή μέσα από τον μη ασφαλή δίαυλο επικοινωνίας και πριν φτάσει στα χέρια του Μπομπ πρέπει να γυρίσει πίσω σε μια κατανοητή μορφή, κάτι που γίνεται μέσω της διαδικασίας της αποκρυπτογράφησης, η οποία μαθηματικά είναι μια συνάρτηση D_d και εξαρτάται από το κλειδί αποκρυπτογράφησης d μικρό (decryption).

Σε αυτό το σημείο πρέπει να αναφέρω ότι η ασφάλεια ενός κρυπτοσυστήματος πρέπει να βασίζεται στην ασφάλεια του ή των κλειδιών και όχι στο να παραμείνει κρυφή η ίδια η διαδικασία κρυπτογράφησης, μια απαίτηση που περιέγραψε πρώτος ο Kerckhoffs, ένας Ολλανδός κρυπτογράφος.

7 of 49

Κρυπτογραφία - Ιστορική Αναδρομή

Κρυπτεία Σκυτάλη

500 π.Χ.

1500 μ.Χ.

1900 μ.Χ.

Παρόν

Όχι τόσο μακρινό μέλλον

Μηχανή Enigma

Σύγχρονη Κρυπτογραφία

Κρυπτοσύστημα Viginère

Κώδικας του Καίσαρα

Κρυπτογραφία στη Μετακβαντική Εποχή

50 μ.Χ.

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

Κ Ρ Υ Π Τ Ο Γ Ρ Α Φ Ι Α

Ν Υ Ψ Τ Χ Σ Ζ Υ Δ Ω Μ Δ

Έχουμε τώρα μια σύντομη ιστορική αναδρομή της Κρυπτογραφίας η οποία όπως βλέπουμε έχει τις απαρχές της στην Αρχαία Ελλάδα και ακόμη πιο πίσω.
Ας δούμε για παράδειγμα τον κώδικα του Καίσαρα, ο οποίος αποτελεί ένα εύκολο στη κατανόηση παράδειγμα ενός κρυπτοσυστήματος :

Το μόνο που χρειαζόμαστε για να κρύψουμε το μήνυμα μας, ας πούμε τη λέξη «Κρυπτογραφία» είναι να χρησιμοποιήσουμε για κάθε γράμμα της λέξης το γράμμα που βρίσκεται 3 θέσεις μπροστά.
Έτσι, τα Α της Κρυπτογραφίας γίνονται Δ και το Κ γίνεται Λ,Μ,Ν

Έπειτα βλέπουμε οι άνθρωποι σκέφτηκαν πιο πολύπλοκα σχήματα αλλά και κρυπτογραφικές μηχανές. Εμείς όμως ας εστιάσουμε τώρα στο παρόν, στη σύγχρονη κρυπτογραφία, η οποία γνώρισε τεράστια άνθιση μετά από την κατασκευή των ηλεκτρονικών υπολογιστών και από την οποία νομίζω θα ήταν χρήσιμο να δούμε μερικές εφαρμογές της στον κόσμο γύρω μας, ώστε να καταλάβουμε όλοι την σημαντικότητα της.

Επιστρέφοντας πίσω στην αναδρομή μας, έχω αφήσει για το τέλος τον στόχο μας, την Κρυπτογραφία μετά τους κβαντικούς υπολογιστές, στην οποία θα αναφερθούμε μετά και όπου θα μιλήσουμε για το πώς η σύγχρονη κρυπτογραφία απειλείται από τους κβαντικούς υπολογιστές και μαζί με αυτήν τα πάντα που προστατεύει, ελάχιστα από τα οποία είδαμε μόλις.

8 of 49

Αλγόριθμοι

Μέγεθος εισόδου (n)

Αριθμός πράξεων (N)

Χρονική πολυπλοκότητα - Χρόνος εκτέλεσης

Αποδοτικός αλγόριθμος

Πολυωνυμικός χρόνος

Εκθετικός χρόνος

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

Εδώ τώρα….μιλήσαμε πριν για κρυπτογραφικούς αλγορίθμους και αυτό που μας ενδιαφέρει κυρίως σε αυτό το σημείο σχετικά με αυτούς είναι η έννοια της χρονικής πολυπλοκότητας ενός αλγορίθμου η οποία αναφέρεται στο πόσο αργά ή γρήγορα εκτελείται ένας αλγόριθμος σαν συνάρτηση του μεγέθους της εισόδου.

Όπως βλέπετε τώρα στο διπλανό σχήμα όσο μεγαλώνει το μέγεθος της εισόδου του αλγορίθμου, τόσο επηρεάζεται και ο αριθμός των πράξεων που χρειάζεται να εκτελεστούν, ανάλογα την κάθε περίπτωση.

Στις συναρτήσεις εδώ κάτω βλέπουμε ότι αν και μεγαλώνει η είσοδος, ο αριθμός των πράξεων που χρειάζονται δεν αυξάνεται τόσο πολύ και άρα είναι πιο γρήγοροι οι αλγόριθμοι που έχουν τέτοια χρονική πολυπλοκότητα.
Ενώ, εδώ πάνω, βλέπουμε ότι ακόμη και για μικρά μεγέθη στην είσοδο χρειάζεται τεράστιο πλήθος πράξεων για την εκτέλεση του αλγορίθμου, και άρα αργοί αλγόριθμοι σχετίζονται με αυτές.

Έτσι, μπορούμε να κάνουμε έναν άτυπο διαχωρισμό των αλγορίθμων ανάλογα με την ταχύτητα τους – Πολυωνυμικού χρόνου οι γρήγοροι και Εκθετικού χρόνου οι αργοί.
Ξαναλέω όμως αυτός ο διαχωρισμός όπως τον κάνουμε τώρα δεν είναι αυστηρός αλλά είναι ιδανικός για τους σκοπούς μας.
Με αυτή τη λογική θα καλούμε και αποδοτικό έναν αλγόριθμο ο οποίος είναι γρήγορος, δηλαδή έναν αλγόριθμο πολυωνυμικού χρόνου.

Όσο αυξάνεται η είσοδος του αλγορίθμου ο απαιτούμενος χρόνος αυξάνεται πολυωνυμικά / εκθετικά.

Δηλαδή, σε διπλάσια είσοδο θα χρειαστούμε «διπλάσιο» χρόνο για γραμμικό πολυωνυμικό (n) αντί για τον προηγούμενο χρόνο εις το τετράγωνο αν είναι εκθετικός.

9 of 49

Ταξινόμηση Κρυπτολογίας

Κρυπτολογία

Κρυπτογραφία

Συμμετρική Κρυπτογραφία

Ασύμμετρη Κρυπτογραφία

Κρυπτανάλυση

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

Βλέπουμε τώρα πάλι το διάγραμμα ταξινόμησης και θα συνεχίσουμε με μια ανάλυση των δύο βασικών ειδών κρυπτογραφίας, οι οποίες διαφοροποιούνται ανάλογα με το πλήθος των κλειδιών που χρησιμοποιούνται στα κρυπτογραφικά σχήματα κάθε είδους και έτσι έχουμε
Την κρυπτογραφία των συμμετρικών κρυπτοσυστημάτων, στα οποία το κλειδί κρυπτογράφησης με το κλειδί αποκρυπτογράφησης ταυτίζονται και έχουμε ένα κοινό κλειδί για κάθε διεργασία.
Καθώς και την ασύμμετρη κρυπτογραφία..
*Ν*

10 of 49

Ασύμμετρο κρυπτοσύστημα

Χρησιμοποιούνται δύο διαφορετικά κλειδιά για τις διεργασίες της κρυπτογράφησης και της αποκρυπτογράφησης:

Ένα ιδιωτικό κλειδί
Ένα δημόσιο κλειδί

Κρυπτογράφηση

Αποκρυπτογράφηση

Δημόσιο Κλειδί (Μπομπ)

Ιδιωτικό Κλειδί (Μπομπ)

E_pk(m)

E_pk

D_sk(E_pk(m))

D_sk

Δημοσίευση pk

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

…στην οποία χρησιμοποιούνται δύο διαφορετικά κλειδιά για κάθε άτομο (και όχι ένα μόνο κοινό κλειδί).

*Ν0*

Έτσι, σ’ ένα σενάριο στο οποίο η Αλίκη θέλει να στείλει ένα μήνυμα στο Μπομπ, χρειάζονται μόνο τα δύο κλειδιά του Μπομπ. Το ένα από αυτά θα είναι ιδιωτικό και θα πρέπει να το κρατάει μυστικό ο Μπομπ ενώ το άλλο, το οποίο είναι δημόσιο, μπορεί να το ανακοινώνει σε όλους.
Τέλος, να αναφέρω ότι τα δύο κλειδιά, αν και διαφορετικά συνδέονται από κάποια μαθηματική σχέση.

11 of 49

Που βασίζεται η ασφάλεια των κρυπτοσυστημάτων δημοσίου κλειδιού ?

Πρέπει να είναι υπολογιστικά αδύνατο να βρεθεί το ιδιωτικό κλειδί από το δημόσιο κλειδί.

Υπολογιστική αδυναμία εύρεσης κλειδιού ⬄ Υπολογιστικά δύσκολο πρόβλημα

Πρόβλημα Παραγοντοποίησης Μεγάλων Ακεραίων

Έστω ότι έχουμε έναν ακέραιο n=p∙q, με q και p δύο αρκετά μεγάλους πρώτους. Γνωρίζοντας μόνο το n, να βρεθούν τα p και q.

Δεν έχει βρεθεί κλασσικός αλγόριθμος παραγοντοποίησης πολυωνυμικού χρόνου.

Κρυπτοσύστημα Δημοσίου Κλειδιού RSA

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

Πάνω σε αυτήν ακριβώς τη σχέση βασίζεται η ασφάλεια ενός ασύμμετρου κρυπτοσυστήματος και πιο συγκεκριμένα στο να είναι αυτή η σχέση δύσκολο να αντιστραφεί.

Δηλαδή, θα πρέπει να μην υπάρχει αποδοτικός αλγόριθμος ο οποίος να μπορεί να μας δώσει το ιδιωτικό κλειδί του Μπομπ πίσω, αν δεχτεί ως είσοδο το δημόσιο κλειδί.

Πηγαίνοντας ένα βήμα παρακάτω, η αδυναμία εύρεσης κλειδιών στα ασύμμετρα κρυπτοσυστήματα συνδέεται άμεσα με την ύπαρξη ενός προβλήματος το οποίο θεωρείται υπολογιστικά δύσκολο να λυθεί, δηλαδή ενός προβλήματος για το οποίο δεν έχει βρεθεί αποδοτικός αλγόριθμος που να το επιλύει.

Για παράδειγμα, στο κρυπτοσύστημα δημοσίου κλειδιού RSA, η ασφάλεια του…

σε 1^η φάση θα βασίζεται στη δυσκολία του να βρεθεί το μυστικό κλειδί του κρυπτοσυστήματος από το δημόσιο κλειδί
και σε 2^η φάση αποδεικνύεται ότι αυτή η δυσκολία εύρεσης του μυστικού κλειδιού θα ισοδυναμεί με τη δυσκολία επίλυσης ενός γνωστού προβλήματος των μαθηματικών , του Προβλήματος Παραγοντοποίησης Μεγάλων Ακεραίων, το οποίο είναι ακριβώς ότι ονομάζεται…

Δηλαδή, δοθέν ενός αριθμού n ο οποίος αποτελεί γινόμενο δύο μεγάλων πρώτων αριθμών q και p, ζητείται να βρεθούν αυτοί οι παράγοντες q και p που τον δημιούργησαν.

Καθώς, λοιπόν, δε έχει βρεθεί μέχρι στιγμής κάποιος αποδοτικός αλγόριθμος που να το επιλύει δηλαδή σε πολυωνυμικό χρόνο, μιλάμε για ένα υπολογιστικά δύσκολο πρόβλημα και έτσι τελικά μπορούμε να πούμε ότι η ασφάλεια του RSA βασίζεται σε αυτό το δύσκολο πρόβλημα.

Οπότε συνοψίζοντας, ανάλογα με το RSA, και τα υπόλοιπα ασύμμετρα κρυπτογραφικά σχήματα που έχουν δημιουργηθεί βασίζουν και αυτά την ασφάλεια τους σε κάποιο υπολογιστικά δύσκολο πρόβλημα.

12 of 49

Ψηφιακές Υπογραφές

Καλούμε σχήμα ψηφιακής υπογραφής μια πεντάδα (P,Y,K,S,V), όπου :

・ P : ο χώρος των μηνυμάτων

・ Y : ο χώρος των υπογραφών

・ K : ο χώρος των κλειδιών

・ S = {sig_k : P → Y | k ∈ K} : συναρτήσεις υπογραφής

・ V = {ver_k’ : P × Y → {0, 1}| k ∈ K} : συναρτήσεις επαλήθευσης

Ισχύει ότι ∀k,k΄ ∈ K και (x, y) ∈ P × Y, έχουμε:

(x,y)

0 ή 1

Ver_k’

Επαλήθευση

Υπογραφή

Sig_k

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

Αφήνουμε τώρα τα Κρυπτοσυστήματα για να δούμε τις ψηφιακές υπογραφές για το τέλος του κεφαλαίου, οι οποίες δουλεύουν παρόμοια με τα ασύμμετρα Κρυπτοσυστήματα.
Έχουμε πάλι τον αυστηρό μαθηματικό ορισμό στο κουτάκι αλλά εμάς μας ενδιαφέρει στη πράξη πως δουλεύει το σύστημα, κάτι που θα δούμε με τη βοήθεια της Αλίκης και του Μπομπ.

Έστω ότι θέλει η Αλίκη να στείλει ένα μήνυμα x στον Μπομπ, υπογεγραμμένο ώστε να ξέρει ότι το έστειλε η ίδια.
Για να γίνει αυτό χρειάζονται δύο διαφορετικά κλειδιά ένα ιδιωτικό κλειδί υπογραφής και ένα δημόσιο κλειδί επαλήθευσης με την βοήθεια του οποίου ο Μπομπ θα μπορέσει να επαληθεύσει την αυθεντικότητα της υπογραφής της Αλίκης.
Πριν ξεκινήσουμε την διαδικασία η Αλίκη επιλέγει τα αντίστοιχα κλειδιά και συναρτήσεις της, κρατά κρυφό το κλειδί υπογραφής και την συνάρτηση υπογραφής, ενώ δημοσιεύει το κλειδί επαλήθευσης και την συνάρτηση επαλήθευσης της.
Ξεκινώντας την διαδικασία, δημιουργεί μια υπογραφή y από το αρχικό μήνυμα της x, χρησιμοποιώντας μια συνάρτηση υπογραφής sig_k, και το ιδιωτικό κλειδί της k.
Έπειτα, παίρνει και το μήνυμα της και την υπογραφή του και τα στέλνει και τα δύο στον Μπομπ.
Ο Μπομπ τότε για να επαληθεύσει το μήνυμα θα χρησιμοποιήσει την συνάρτηση επαλήθευσης της ver_k’και το κλειδί επαλήθευσης k’, τα οποία γνωρίζει γιατί είναι δημόσια και παίρνει ως αποτέλεσμα της συνάρτησης 1, καθώς ξέρουμε ότι το έστειλε η Αλίκη. Αν λάμβανε ως αποτέλεσμα 0, θα σήμαινε ότι το x μήνυμα που έλαβε, δεν το έχει στείλει η Αλίκη.

Υπάρχουν ακόμη δύο όροι ώστε να έχουμε ένα ασφαλές σχήμα υπογραφής, θα πρέπει να είναι εύκολο να υπογράψει (δεξιά) και δύσκολο για κάποιον να πλαστογραφήσει την υπογραφή σου (αριστερά).
Τέλος απλά να πω ότι αν μας ενδιαφέρει να κρύψουμε τα υπογεγραμμένα μηνύματα μας από κάποιον κακόβουλο -> Υπογράφουμε πρώτα και κρυπτογραφούμε μετά.

13 of 49

Συναρτήσεις Κατακερματισμού – Ασφαλείς υπογραφές

Εύκολο

f^-1

Δύσκολο

x₁

x₂

h(x₁)

Συνάρτηση κατακερματισμού

h : X → Y τ.ω. το σύνολο Y να είναι πεπερασμένο και |X| > |Y|.

Έστω h : X → Y μια συνάρτηση κατακερματισμού.

Το (x1,x2) καλείται σύμπτωση της h αν ισχύει x₁ ≠ x₂ με h(x₁) = h(x₂).

Η h θα καλείται ελεύθερη σύμπτωσης αν είναι υπολογιστικά ανέφικτο να βρεθεί μια σύμπτωση της.

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

Τέλος, πολύ σημαντικές είναι και οι συναρτήσεις κατακερματισμού για τον τομέα των ψηφιακών υπογραφών.

Ονομάζουμε συνάρτηση κατακερματισμού μια συνάρτηση της οποίας το σύνολο τιμών είναι πεπερασμένο και μικρότερο πληθικά από το πεδίο ορισμού της. Όπως βλέπουμε και δίπλα, ουσιαστικά αντιστοιχίζει τα πολλά στοιχεία του X σε λιγότερα στοιχεία του Y.
Μας ενδιαφέρουν ακόμη μερικές ιδιότητες που πρέπει να έχει μια συνάρτηση κατακερματισμού ώστε να την θεωρούμε «ασφαλή, κρυπτογραφικά», δηλαδή αρκετά ασφαλή ώστε να χρησιμοποιηθεί σε σχήματα της κρυπτογραφίας.
Αρχικά θέλουμε να είναι επίσης μιας κατεύθυνσης, δηλαδή να είναι τέτοια, ώστε να πηγαίνουμε εύκολα απ’ το X στο Y, αλλά να είναι αδύνατο να πάμε από το Y στο X. Στη πράξη βέβαια δεν έχουν βρεθεί συναρτήσεις μιας κατεύθυνσης, οπότε συμβιβαζόμαστε με συναρτήσεις που είναι υπολογιστικά δύσκολο να πάμε απ’ το Y στο X, δλδ γνωρίζοντας την τιμή f(x), για κάποιο x \in X, να βρούμε με κάποια διαδικασία το x.
Τέλος, έχουμε την έννοια της σύμπτωσης, όπου ουσιαστικά είναι ζευγάρια (x₁,x₂) τα οποία μια συνάρτηση κατακερματισμού μεταφέρει στην ίδια τιμή στο σύνολο Y.
Έτσι, εμείς θέλουμε οι συναρτήσεις κατακερματισμού που χρησιμοποιούμε να είναι ελεύθερες σύμπτωσης, δηλαδή να είναι υπολογιστικά ανέφικτο να βρούμε μια σύμπτωση της – Υπολογιστικά ανέφικτο ξαναλέω σημαίνει να μην υπάρχει αλγόριθμος που να εκτελεί αυτή την αναζήτηση σε πολυωνυμικό χρόνο.

Και σε αυτό το σημείο έχουμε λοιπόν πει ότι χρειαζόμαστε για την κρυπτογραφία και ήρθε η ώρα να δούμε το πως θα επηρεάσουν οι κβαντικοί υπολογιστές τον κόσμο της.

14 of 49

ΚΒΑΝΤΙΚΟΙ ΥΠΟΛΟΓΙΣΤΕΣ ΚΑΙ ΚΡΥΠΤΟΓΡΑΦΙΑ

Οπότε, αρχικά ας δούμε τι έχουμε μπροστά μας…

Αριστερά βλέπετε σε επίπεδα τον τωρινό καλύτερο κβαντικό επεξεργαστή της IBM, με όνομα Eagle.
Δεξιά βλέπετε φωτογραφία ενός κβαντικού συστήματος της Rigetti Computing.

Η μεγάλη αυτή κατασκευή αποτελεί τον κρυοστάτη του κβαντικού επεξεργαστή, ο οποίος βρίσκεται τοποθετημένος τέρμα κάτω στη κατασκευή.
Η ιδέα είναι ότι σταδιακά με κάποιες χημικές διαδικασίες που ξεκινάνε από την κορυφή του κρυοστάτη και συνεχίζονται στο ενδιάμεσο, καταφέρνουν τελικά να ρίξουν την θερμοκρασία στα 0,1 kelvin για τον κβαντικό επεξεργαστή (η θερμοκρασία του σύμπαντος είναι περίπου 2.7 kelvin)

15 of 49

Κβαντικός υπολογιστής

Υπολογιστική συσκευή που εκμεταλλεύεται χαρακτηριστικές ιδιότητες της κβαντομηχανικής για την επεξεργασία δεδομένων και την εκτέλεση υπολογισμών.

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

Οπότε ξεκινώντας, αυτό που μας ενδιαφέρει εδώ είναι απλά να έχουμε στο μυαλό μας ότι ο κβαντικός υπολογιστής είναι μια ισχυρή υπολογιστική μηχανή που λειτουργεί αξιοποιώντας κάποιες παράξενες ιδιότητες της κβαντομηχανικής, καθώς και ότι δεν είναι απλά ένας καλύτερος υπολογιστής…
Μπορείτε να σκέφτεστε ότι ο κβαντικός υπολογιστής είναι για τον κλασσικό υπολογιστή, ότι είναι ο ηλεκτρικός λαμπτήρας για το κερί. Μια εντελώς καινούργια τεχνολογία..

16 of 49

Κβαντικός αλγόριθμος

Ένας αλγόριθμος ο οποίος εκτελείται σε ένα ρεαλιστικό μοντέλο κβαντικού υπολογισμού.

Αλγόριθμος του Grover

Αλγόριθμος του Shor

Κβαντικοί Αλγόριθμοι & Κρυπτογραφία

Κβαντικοί Αλγόριθμοι

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

Συνεχίζουμε τώρα με τους κβαντικούς αλγορίθμους οι οποίοι είναι αλγόριθμοι που χρησιμοποιούν κάποια από αυτές τις παράξενες ιδιότητες.
Συνήθως ο όρος χρησιμοποιείται για αλγορίθμους που μπορούν να εκτελεστούν μόνο σε κβαντικούς υπολογιστές.
Οι κβαντικοί αλγόριθμοι είναι πρακτικά ο σύνδεσμος κρυπτογραφίας και κβαντικών υπολογιστών, η πηγή της κβαντικής απειλής που ανέφερα στις αρχές της παρουσίασης.
Πιο συγκεκριμένα όμως, αναφερόμαστε σε δύο κβαντικούς αλγορίθμους, τους οποίους και θα δούμε περιληπτικά στη συνέχεια.

«όλοι οι κλασσικοί αλγόριθμοι μπορούν να εκτελεστούν και σε έναν κβαντικό υπολογιστή»

17 of 49

Αλγόριθμος του Grover Καταφέρνει να επιταχύνει (τετραγωνικά) την διαδικασία διερεύνησης μιας μη δομημένης βάσης δεδομένων.

Κβαντικός Αλγόριθμος του Grover

Πόσες προσπάθειες χρειάζονται για την εύρεση ενός στοιχείου σε μια μη δομημένη βάση N δεδομένων ?

Κλασσικός Υπολογιστής

Κατά μέσο όρο N/2 (τυχαία επιλογή)

Κβαντικός Υπολογιστής

Περίπου √N (αλγόριθμος του Grover)

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

Ξεκινάμε με τον αλγόριθμο που δημιούργησε ο Love Grover πριν από 26χρόνια και ο οποίος καταφέρνει να βρει πιο γρήγορα ένα στοιχείο σε μια ΜΗ ΔΟΜΗΜΕΝΗ βάση δεδομένων.
Και θα δείξουμε τι σημαίνει αυτό με το παράδειγμα του τηλεφωνικού καταλόγου :

Έστω λοιπόν ότι έχουμε έναν μεγάλο έντυπο κατάλογο στον οποίο περιέχεται ένας μεγάλος αριθμός ονομάτων, σε καθένα από τα οποία αντιστοιχεί ένας αριθμός τηλεφώνου.
Τότε, παρατηρούμε ότι, καθώς τα ονόματα είναι ταξινομημένα σε αλφαβητική σειρά, μας είναι πολύ εύκολο να βρούμε τον αριθμό τηλεφώνου που αντιστοιχεί σε κάποιο όνομα. Ο τηλεφωνικός κατάλογος δηλαδή αποτελεί μια δομημένη βάση, όσον αφορά τα ονόματα.
Από την άλλη μεριά, αν πάρουμε το αντίθετο πρόβλημα, αν υποθέσουμε δηλαδή ότι μας δίνεται ένας τηλεφωνικός αριθμός και μας ζητείται να βρούμε το όνομα που του αντιστοιχεί, τότε παρατηρούμε ότι μας είναι πολύ δύσκολο να το κάνουμε αυτό . Το πρόβλημα αυτό είναι τόσο δύσκολο γιατί ο τηλεφωνικός κατάλογος είναι μια μη δομημένη βάση δεδομένων, όσον αφορά τους τηλεφωνικούς αριθμούς.

(Προσπ.)Γενικά στη κλασσική περίπτωση μπορούμε να πούμε ότι για να βρούμε ένα στοιχείο μιας μη δομημένης βάσης N δεδομένων θα χρειαστούμε κατά μέσο όρο N/2 προσπάθειες. Αυτό όμως δεν ισχύει για τους κβαντικούς υπολογιστές οι οποίοι, χρησιμοποιώντας τον αλγόριθμο του Grover, μπορούν να εκτελέσουν πια αυτή την αναζήτηση σε περίπου √N προσπάθειες.

18 of 49

Κβαντικός Αλγόριθμος του Shor

Προβλήματος Παραγοντοποίησης Μεγάλων Ακεραίων

Πρόβλημα Διακριτού Λογαρίθμου

Κρυπτοσύστημα Δημοσίου Κλειδιού RSA
Σχήμα Ψηφιακής Υπογραφής RSA
Κρυπτοσύστημα Δημοσίου Κλειδιού Rabin
Σχήμα Ψηφιακής Υπογραφής Rabin

Πρωτόκολλο Ανταλλαγής Κλειδιού Diffie-Hellman
Κρυπτοσύστημα Δημοσίου Κλειδιού ElGamal
Αλγόριθμος Ψηφιακής Υπογραφής (DSA)
Αλγόριθμος Ψηφιακής Υπογραφής Ελλειπτικών Καμπυλών (ECDSA)

(2042μ.Χ.) Παραγοντοποίηση ενός αριθμού 2048bits

300.000.000 χρόνια

36 λεπτά

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

Συνεχίζουμε με τον αλγόριθμο του Shor, ο οποίος είναι ένας αποδοτικός αλγόριθμος εύρεσης της περιόδου μιας συνάρτησης της μορφής που βλέπετε και ουσιαστικά μας ενδιαφέρει γιατί η επίλυση αυτού του προβλήματος σε πολυωνυμικό χρόνο μας δίνει και την επίλυση των δύο παρακάτω προβλημάτων σε πολυωνυμικό χρόνο.
Ωστόσο, σε αυτά τα προβλήματα βάσιζαν την ασφάλεια τους αρκετά σχήματα κρυπτογράφησης και υπογραφής, τα οποία βλέπουμε σιγά σιγά στις οθόνες μας και άρα ο αλγόριθμος Shor ουσιαστικά καταφέρνει να σπάσει όλα αυτά τα σχήματα και πρωτόκολλα, καθώς και άλλα παρόμοια.
Δηλαδή, για κάποιον που δεν γνωρίζει αυτά τα σχήματα, αυτό σημαίνει ότι η ασφάλεια του διαδικτύου κινδυνεύει γιατί ας πούμε το RSA ακόμη χρησιμοποιείται κατά κόρον σε browsers, chats, ακόμη και μέιλ
Και οι αλγόριθμοι ψηφιακής υπογραφής, παρόμοια.
Βέβαια, να τονίσω σε αυτό το σημείο ότι για να μπορέσουν να εκτελεστούν και ο αλγόριθμος του Grover και ο αλγόριθμος του Shor σωστά χρειάζονται κβαντικοί υπολογιστές πολλών qubit τους οποίους δεν έχουμε κατασκευάσει ακόμη, αλλά πολλοί επιστήμονες πιστεύουν ότι είναι κάτι που μπορεί να γίνει στα επόμενα χρόνια.

Ακόμη, ενδιαφέρον είναι να δούμε την διαφορά στην ταχύτητα του αλγόριθμου του Shor σε έναν εκτιμώμενο κβαντικό υπολογιστή σε σύγκριση με τον τωρινό καλύτερο κλασσικό αλγόριθμο, αν τον τρέξουμε υποθετικά σε έναν κλασσικό υπολογιστή του 2042 με σκοπό την παραγοντοποίηση ενός αριθμού μήκους 2048bits.
Εκεί που ο κλασσικός υπολογιστής θα χρειαστεί 300 εκατομμύρια χρόνια ο κβαντικός υπολογιστής θα χρειαστεί 36, όχι χρόνια, λεπτά!

19 of 49

Οι κβαντικοί υπολογιστές θα «ΣΠΑΣΟΥΝ» το ίντερνετ

Peter Shor

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

Οπότε, όπως μπορείτε να καταλάβετε και με τα προηγούμενα, ο Shor καταφέρνει να σπάει απίστευτα γρήγορα σχήματα κρυπτογραφίας στα οποία βασίζεται η ασφάλεια του διαδικτύου και άρα καταλήγουμε στο συμπέρασμα ότι ένας αρκετά μεγάλος κβαντικός υπολογιστής τα επόμενα χρόνια θα ήταν καταστροφικός για το ίντερνετ, η λεγόμενη κβαντική απειλή.
Και αυτό είναι κάτι που δεν το διαπιστώσαμε εμείς πρώτοι *N*
Από κβαντικούς χάκερ, μέχρι την απειλή του σπασίματος των σημερινών κρυπτογραφημένων μηνυμάτων και την πτώση του bitcoin το μέλλον που χάραξε ο Shor πραγματικά φαίνεται δυσοίωνο, ακόμη και αν τεχνολογικά δεν είμαστε ακόμη εκεί.

20 of 49

Κβαντική Κρυπτογραφία

Επιστήμη που χρησιμοποιεί τις ιδιότητες της κβαντομηχανικής σε κρυπτογραφικές εφαρμογές.

Μετακβαντική Κρυπτογραφία

Οικογένεια κρυπτογραφικών αλγορίθμων οι οποίοι (εικάζεται ότι) εξασφαλίζουν ένα υψηλό επίπεδο ασφάλειας, ακόμη και ενάντια σε έναν επιτιθέμενο που διαθέτει έναν κβαντικό υπολογιστή.

Κβαντική διαχείριση κλειδιών
Κβαντικές ψηφιακές υπογραφές
Quantum commitment
Oblivious transfer
Quantum fingerprinting

Κρυπτογραφία Συναρτήσεων Κατακερματισμού
Κρυπτογραφία Κωδίκων
Κρυπτογραφία Δικτυωτών
Κρυπτογραφία Πολυμετάβλητων Τετραγωνικών Εξισώσεων

Οι κβαντικοί υπολογιστές ΔΕΝ θα «ΣΠΑΣΟΥΝ» το ίντερνετ

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

Η τουλάχιστον έτσι φαίνεται να πιστεύουν άνθρωποι οι οποίοι κάνανε μισή την έρευνα τους στο θέμα..
Στη πραγματικότητα καθώς οι επιστήμονες γνώριζαν γι’ αυτήν την απειλή εδώ και αρκετά χρόνια, έγιναν βήματα προς την εύρεση λύσεων για την αντιμετώπιση της απειλής.
Αυτές οι λύσεις είναι δύο νέοι τομείς τις κρυπτογραφίας, με πρώτη την Κβαντική Κρυπτογραφία η οποία ουσιαστικά εκμεταλλεύεται κάποιες ιδιότητες της κβαντομηχανικής για την υλοποίηση κρυπτογραφικών εφαρμογών με πιο κύρια την κβαντική διαχείριση κλειδιών, η οποία αποτελεί την τέλεια, θεωρητικά, ασφάλεια και άλλες πιο σύγχρονες και λιγότερο εξελιγμένες.
Και ακόμη, η 2^η λύση στη κβαντική απειλή και ίσως και η πιο προσιτή για το παρόν είναι η Μετακβαντική Κρυπτογραφία, η οποία είναι μια οικογένεια διαφόρων κρυπτογραφικών αλγορίθμων οι οποίοι, αν και χρησιμοποιούν κλασσικά μαθηματικά και φυσική, και όχι την δύναμη του κβαντικού κόσμου, εικάζεται ότι δεν μπορούν να σπάσουν από κβαντικούς υπολογιστές.
Και παρακάτω παραθέτω τις 4 πιο σημαντικές από αυτές τις οικογένειες, 3 από τις οποίες θα αναλύσω στη συνέχεια…

21 of 49

ΚΡΥΠΤΟΓΡΑΦΙΑ ΚΩΔΙΚΩΝ

22 of 49

Θεωρία Κωδίκων

Βασικό αντικείμενο Θεωρίας Κωδίκων

Κωδικοποίηση της πληροφορίας με τέτοιον τρόπο, ώστε αν μικρό πλήθος αλλοιώσεων έχει εισχωρήσει σ’ ένα μήνυμα, η αποκωδικοποίηση του να τις διορθώνει.

Παράδειγμα (ASCII) :

Υπολογιστές χρησιμοποιούν μόνο 0 και 1.
Αδύνατη η αποφυγή λαθών στους υπολογιστές.

Γράμματα	Λέξεις ASCII
A	10000010
B	10000100
C	10000111

1+1=0

1+1+1=1

Κωδικοποιητής

Αποκωδικοποιητής

Πομπός

Δέκτης

Θόρυβος

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

Θα ξεκινήσουμε αυτό το κεφάλαιο βλέποντας κάποια βασικές έννοιες από Θεωρία Κωδίκων, η οποία για όσους δεν γνωρίζουν είναι ακόμη μια επιστήμη που ασχολείται με τον τομέα της επικοινωνίας, όπως η Κρυπτογραφία, αλλά πιο συγκεκριμένα αυτή δεν ασχολείται με το να εξασφαλίσει την ασφάλεια των πληροφοριών αλλά ασχολείται με την ανίχνευση και την διόρθωση αλλοιώσεων που μπορούν να εισχωρήσουν σε ένα μήνυμα.
Αυτό το πετυχαίνει με τις διαδικασίες τις κωδικοποίησης και αποκωδικοποίησης, οι οποίες θα προσπαθήσουμε διαισθητικά να καταλάβουμε πως δουλεύουν βλέποντας το βασικό μοντέλο επικοινωνίας μας.
Έχουμε έναν πομπό λοιπόν, ο οποίος θέλει να στείλει ένα μήνυμα σε έναν δέκτη μέσα από έναν δίαυλο αλλά μέσα από αυτόν το δίαυλο γνωρίζει ότι μπορεί η πληροφορία να αλλοιωθεί και να εισχωρήσουν κάποια λάθη, όπως λέμε λόγω του θορύβου από το περιβάλλον.
Έτσι, ο πομπός πρώτα κωδικοποιεί το μήνυμα, το στέλνει μέσα από το δίαυλο σε κωδικοποιημένη μορφή και ο δέκτης πριν το λάβει ολοκληρώνει την διαδικασία αποκωδικοποιώντας το μήνυμα.
Κατά την αποκωδικοποίηση μπορεί εκτός από την βασική αντιστροφή της πληροφορίας στην βασική της μορφή, να ανιχνευθούν και λάθη καθώς και να διορθωθούν ανάλογα τον κώδικα τον οποίο έχουμε.

Ας δούμε 1-2 παραδείγματα πάνω σε αυτό.
Αξιοσημείωτο είναι πρώτα πρώτα το παράδειγμα εφαρμογής ενός τέτοιου κώδικα κατά την μεταφορά εικόνας της εικόνας της Μόνα Λίζας από τους επιστήμονες της NASA μέσω λέιζερ από την γη σε διαστημικό σκάφος που βρισκόταν περίπου 400χιλιάδες χλμ. μακριά με τροχιά γύρω από το φεγγάρι.

Οι αναταράξεις στην ατμόσφαιρα της Γης προκάλεσαν σφάλματα μετάδοσης ακόμη και όταν ο ουρανός ήταν καθαρός και ουσιαστικά αποτελούν το θόρυβο σε αυτήν την περίπτωση.
Για να ξεπεράσουν αυτό το πρόβλημα, χρησιμοποιήθηκε η κωδικοποίηση Reed-Solomon με ρυθμό 2/3*.
Στην αριστερά εικόνα βλέπετε κάποια τυπικά σφάλματα στα οποία περιλαμβάνονται ελλείποντα pixel (λευκά) και ψευδή σήματα (μαύρο), ενώ η λευκή λωρίδα υποδεικνύει μια σύντομη περίοδο κατά την οποία διακόπηκε η μετάδοση. Σφάλματα τα οποία διόρθωσε η κωδικοποίηση μας.

Σε αυτό το σημείο κανονικά είχα μερικές πληροφορίες για το ASCII αλλά ας το αφήσουμε για να κερδίσουμε χρόνο.

\για όποιον διαβάασει\

Δεύτερον ας δούμε και τον κώδικα ASCII, έναν πολύ απλό λειτουργικά κώδικα.

Ουσιαστικά τα αίτια δημιουργίας του ASCII είναι δύο
1. ότι οι υπολογιστές καταλαβαίνουν μόνο 0 και 1 αντί των δικών μας αλφαβήτων και 2. ότι καθώς οι υπολογιστές αποτελούν ένα φυσικό σύστημα, είναι επόμενο ότι θα εισχωρήσουν κάποια λάθη.

Τέλος, η μορφή μερικών κωδικοποιημένων λέξεων με ASCII φαίνεται στο διπλανό σχήμα.
Ουσιαστικά κάθε λέξη και σύμβολο μπορεί να αναπαρασταθεί ξεχωριστά από μια ακολουθία 7 ψηφίων, ενώ το τελευταίο ψηφίο είναι για τον έλεγχο και είναι το άθροισμα των υπόλοιπων ψηφίων.

*΄Ένας κώδικας με ρυθμό 2/3 είναι ένας κώδικας που για κάθε 2 bits χρήσιμης πληροφορίας παράγει 3 bits δεδομένων.

23 of 49

Γραμμικοί Κώδικες

m ∙ G

m’ ∙ G^-1

m’

Κωδικοποιητής

Αποκωδικοποιητής

Δίαυλος

Πομπός

Δέκτης

3 bits

7 bits

2-bit διορθώνονται

4-bit προστέθηκαν

Πως ?

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

Συνεχίζουμε βλέποντας το πως λειτουργεί μια πολύ σημαντική οικογένεια κωδίκων, οι γραμμικοί κώδικες.
Σε αυτούς ουσιαστικά η κωδικοποίηση γίνεται πολλαπλασιάζοντας με έναν πίνακα G, ενώ η αποκωδικοποίηση γίνεται με τον πολλαπλασιασμό με τον αντίστροφο G^-1, στην περίπτωση που δεν έχουμε θόρυβο.
Και αυτό μπορούμε να το δούμε και στο παρακάτω παράδειγμα όπου έχουμε ένα μήνυμα m μήκους 3 bits το οποίο πολλαπλασιαζόμενο με έναν πίνακα G μας δίνει ένα διάνυσμα 7 bits στο οποίο μπορούν να διορθωθούν, αν εισχωρήσουν μέχρι και 2 λάθη.

24 of 49

Γραμμικοί Κώδικες

m ∙ G

m’ ∙ G^-1

m’

Κωδικοποιητής

Αποκωδικοποιητής

Πομπός

Δέκτης

Θόρυβος

D_G(m’’)=m’

m’’

3 bits

7 bits

m’

2 Λάθη

m’’

m’

D_G

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

25 of 49

Κρυπτοσύστημα McEliece

Δυαδικοί Κώδικες Goppa

Μπορούν να διορθωθούν λάθη σε πολυωνυμικό χρόνο. (Αλγόριθμος Patterson)

E_(G^pub_,t)

D _(S,D_G_,P)

Κρυπτογράφηση

Αποκρυπτογράφηση

Δημόσιο κλειδί (Μπομπ)

E_(G^pub_,t)(m)

D_(S,D_G_,P)(E_(G^pub_,t)(m))

Ιδιωτικό κλειδί (Μπομπ)

Δημοσίευση pk= (G^pub, t)

Παραγωγή κλειδιών:

Επιλογή τριών πινάκων G,S,P
Υπολογισμός G^pub=S∙G∙P

Δημόσιο κλειδί: (G^pub, t) , όπου t ο αριθμός των λαθών
Ιδιωτικό κλειδί: (S,D_G,P)
Κρυπτογράφηση: Πολ/σμός m∙G^pubκαι έπειτα εισαγωγή t λαθών.
Αποκρυπτογράφηση: Διόρθωση λαθών με D_Gκαι έπειτα πολ/σμός με (G^pub)^-1.

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

Και έτσι φτάνουμε στο κυρίως σημείο ενδιαφέροντος αυτού του κεφαλαίου που είναι ένα κρυπτοσύστημα που χρησιμοποιεί την Θεωρία Κωδίκων για την κρυπτογράφηση κ αποκρυπτογράφηση της πληροφορίας.
Αυτό το κρυπτοσύστημα παρουσίασε πρώτος ο McEliece το 1978 και αποτελεί ένα ασύμμετρο κρυπτοσύστημα.
Έτσι γρήγορα γρήγορα βλέπουμε ότι για την παραγωγή του ζεύγους κλειδιών κρυπτογράφησης-αποκρυπτογράφησης επιλέγουμε πρώτα τρεις πίνακες G,S και P με σκοπό τον υπολογισμό του πίνακα G^pub.
Το δημόσιο κλειδί θα είναι της μορφής (G^pub,t), όπου t αποτελεί το πλήθος των λαθών, ενώ το ιδιωτικό κλειδί θα είναι της μορφής (S,D_G,P) ,όπου με D_Gσυμβολίζουμε τον αλγόριθμο διόρθωσης λαθών.
Και γενικά η διαδικασία της κρυπτογράφησης γίνεται σε δύο βήματα, πρώτα τον πολλαπλασιασμό ενός μηνύματος με τον δημόσιο πίνακα G^pubκαι έπειτα μ την εισαγωγή t λαθών.
Ενώ η αποκρυπτογράφηση ουσιαστικά αντιστρέφει την προηγούμενη διαδικασία, πρώτα διορθώνοντας τα λάθη με τη βοήθεια του D_Gκαι έπειτα πολλαπλασιάζοντας με τον αντίστροφο πίνακα. (Η διαδικασία αποκρυπτογράφησης δε μπορεί να γίνει χωρίς γνώση των πινάκων που περιέχονται στο δημόσιο κλειδί)
Καταλαβαίνω πως μπορεί σε αυτό το σημείο να έχετε απορίες για το πως μπορεί να γίνει μαθηματικά κάτι τέτοιο αλλά καθώς τα μαθηματικά που χρησιμοποιούμε είναι αρκετά δύσκολα και χρησιμοποιούν θεωρία πεπερασμένων σωμάτων δεν μπορώ σε αυτή την παρουσίαση να αναφέρω περισσότερες λεπτομέρειες εκτός ίσως απ’ το ότι συνήθως χρησιμοποιούνται γι’ αυτή τη διαδικασία οι λεγόμενοι δυαδικοί κώδικες Goppa και ως αλγόριθμος διόρθωσης λαθών ο Αλγόριθμος του Patterson, ο οποίος είναι αποδοτικός.

26 of 49

Κρυπτογραφικά Σχήματα Κωδίκων

Ασφάλεια

Κβαντικός Αλγόριθμος Grover

Προσφέρει παρόμοιες ταχύτητες με ήδη γνωστούς αλγορίθμους.

Κβαντικός Αλγόριθμος Shor

Δεν έχει βρεθεί κάποιος τρόπος χρήσης του.

Μειονεκτήματα

Μεγάλες απαιτήσεις μνήμης

Κρυπτοσύστημα McEliece

Άλλα Σχήματα:

Σχήμα ταυτοποίησης του Stern
Συναρτήσεις κατακερματισμού
Γεννήτριες τυχαίων αριθμών
Σχήματα υπογραφής (γίνονται προσπάθειες)

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

Τέλος, μερικά γενικά σχόλια για το κρυπτοσύστημα που είδαμε και άλλα παρόμοια που χρησιμοποιούν τις ίδιες αρχές είναι ότι ….
Όσον αφορά την ασφάλεια, δεν φαίνεται να είναι χρήσιμος κανένας από τους κβαντικούς μας αλγορίθμους και άρα εικάζεται ότι επιτυγχάνεται η κβαντική ασφάλεια.
Ωστόσο, αυτού του είδους τα κρυπτοσυστήματα έχουν ένα μεγάλο μειονέκτημα το οποίο είναι οι τεράστιες απαιτήσεις σε χώρο, ειδικά σε σχέση και με το μέγεθος του δημοσίου κλειδιού το οποίο θα είναι στη πράξη ένας τεράστιος πίνακας μαζί με έναν ακέραιο.
Τέλος, στην οικογένεια της κρυπτογραφίας κωδίκων ανήκουν και άλλα σχήματα και πρωτόκολλα όπως το Σχήμα ταυτοποίησης του Stern, οι Συναρτήσεις κατακερματισμού, οι Γεννήτριες τυχαίων αριθμών και κάποια Σχήματα υπογραφής.

27 of 49

ΚΡΥΠΤΟΓΡΑΦΙΑ ΣΥΝΑΡΤΗΣΕΩΝ ΚΑΤΑΚΕΡΜΑΤΙΣΜΟΥ

28 of 49

Σχήματα Ψηφιακών Υπογραφών

Σύγχρονα σχήματα υπογραφής

RSA

DSA

ECDSA

Αντικαταστάτες ?

Σχήματα Υπογραφής Συναρτήσεων Κατακερματισμού (Hash-based)

Σχήματα Υπογραφής Μιας Φοράς (OTS)

Συνάρτηση μιας κατεύθυνσης

Συνάρτηση Κατακερματισμού

Η ασφάλεια ενός OTS βασίζεται μόνο στην ιδιότητα «ελεύθερης σύμπτωσης».
Κάθε ζεύγος κλειδιών που παράγεται μπορεί να χρησιμοποιηθεί μόνο μια φορά.

Πρέπει να είναι ελεύθερη σύμπτωσης.

Σχήμα Υπογραφής Merkle – Δέντρο Merkle (MSS)

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

Ας ξεκινήσουμε βλέποντας πάλι κάποια βασικά σύγχρονα σχήματα υπογραφής, αυτά λοιπόν όπως έδειξα, σπάνε απ’ τον Shor άρα φύγανε και στόχος μας είναι να βρούμε τους υποψήφιους για αντικαταστάτες τους.
Έτσι, ερχόμαστε στα σχήματα υπογραφής συναρτήσεων κατακερματισμού, όπου πρώτα έχουμε τα λεγόμενα OTS, δηλαδή σχήματα υπογραφής μιας φοράς.
Αυτά χρησιμοποιούν ουσιαστικά δύο συναρτήσεις στον κορμό τους, μια συνάρτηση μιας κατεύθυνσης και μια συνάρτηση κατακερματισμού.
Οι συναρτήσεις μιας κατεύθυνσης έχει ήδη αποδειχθεί από τον Rompel ότι είναι ικανές και αναγκαίες για την ύπαρξη ασφαλών ψηφιακών υπογραφώ και έτσι ουσιαστικά η ασφάλεια ενός σχήματος μιας φοράς βασίζεται στην συνάρτηση κατακερματισμού που χρησιμοποιεί και, πιο συγκεκριμένα, στο βαθμό ελευθερίας σύμπτωσης που έχει αυτή.
Ωστόσο, δεν τελειώνουμε εδώ… τα OTS έχουν ένα μεγάλο μειονέκτημα που είναι και φανερό από την ονομασία τους και είναι ότι κάθε ζεύγος κλειδιών υπογραφής και επαλήθευσης που παράγουν μπορεί να χρησιμοποιηθεί μόνο μια φορά, για την υπογραφή ενός μόνο αρχείου.
Ένα μειονέκτημα το οποίο δεν κράτησε πίσω τον Ralph Merkle, ο οποίος πήρε τα OTS και τα χρησιμοποίησε ως δομικό λίθο για το δικό του σχήμα υπογραφής..

29 of 49

*OTS – One Time Signature

Σχήμα Υπογραφής Μιας Φοράς Lamport-Diffie (L-D OTS)

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

Παραγωγή Ζεύγους Κλειδιών (X,Y)
Η Αλίκη διαλέγει τα f, g και το ιδιωτικό κλειδί υπογραφής της X (π.χ. X=(1 0 0 1 0 1))
Η Αλίκη υπολογίζει το δημόσιο κλειδί επαλήθευσης Y (π.χ. Y = f(X)=(0 0 0 1 1 1)) και το δημοσιεύει.

Παραγωγή Υπογραφής σ

Η Αλίκη υπολογίζει το g(M) και το χρησιμοποιεί για να παράξει την σ.

Επαλήθευση Υπογραφής σ

Ο Μπομπ γνωρίζει τις f, g, το Y, την σ και το M και τα χρησιμοποιεί για την διαδικασία.

Οπότε, ας μιλήσουμε πρώτα για το πως δουλεύει ένα από τα πρώτα OTS, το σχήμα υπογραφής μιας φοράς των Lamport και Diffie.
Έχουμε την επιστροφή των Αλίκη και Μπομπ και η Αλίκη για ακόμη μια φορά θέλει να στείλει ένα μήνυμα στον Μπομπ, υπογεγραμμένο με το L-D OTS

Έτσι, ξεκινώντας με την παραγωγή των κλειδιών της, η Αλίκη διαλέγει μια συνάρτηση μιας κατεύθυνσης f και μια συνάρτηση κατακερματισμού g, τις οποίες και δημοσιοποιεί.
Οπότε, έχοντας αυτά επιλέγει το ιδιωτικό κλειδί υπογραφής της X και μέσω της f υπολογίζει το κλειδί επαλήθευσης της Y, το οποίο και δημοσιοποιεί.
(Σε αυτό το σημείο να υπενθυμίσω ότι ως συνάρτηση μιας κατεύθυνσης είναι μια συνάρτηση η οποία μας πάει εύκολα απ’ το X στο Y αλλά είναι σχεδόν αδύνατο να γίνει το αντίθετο, έτσι κάποιος που έχει στην κατοχή του την f και το Y δε μπορεί να το χρησιμοποιήσει για να βρει το X.

Και σχετικά με τις διαδικασίες της παραγωγής και της επαλήθευσης υπογραφής σε αυτό το σημείο μόνο μας ενδιαφέρει ότι

- Για την υπογραφή η Αλίκη χρησιμοποιεί την συνάρτηση κατακερματισμού για να υπολογίσει το g(M) και το χρησιμοποιεί για να παράξει την υπογραφή σ με κάποιο τρόπο.
Για την επαλήθευση ο Μπομπ χρησιμοποιεί παρόμοια, ότι έχει δημοσιεύσει η Αλίκη και το μήνυμα M για να γίνει η επαλήθευση, πάλι με κάποιο τρόπο που δε χρειάζεται να αναλύσουμε τώρα.

30 of 49

Σχήμα Υπογραφής Merkle (MSS)

*MSS – Merkle Signature Signature

Παραγωγή Ζεύγους Κλειδιών (X,Y)

*OTS – One Time Signature

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

ν₀[0]

ν₀[1]

ν₀[2]

ν₀[3]

ν₁[1]

ν₁[0]

ν₂[0]

Υ₀

Χ₀

Υ₁

Χ₁

Υ₂

Χ₂

Υ₃

Χ₃

(Ιδιωτικό) Κλειδί Υπογραφής: Η ακολουθία των X_i.

(Δημόσιο) Κλειδί Επαλήθευσης: H ρίζα του δέντρου Merkle (ν_H[0]).

4. Υπολογισμός ρίζας δέντρου Merkle.

3. Δημιουργία του δέντρου Merkle.

2. Παραγωγή 2^H ζεύγη κλειδιών μιας φοράς (X_i,Y_i).

Το Σχήμα Merkle είναι το σχήμα το οποίο θα μας απασχολήσει τώρα και είναι αρκετά απαιτητικό οπότε θα σας παρουσιάσω μόνο το κομμάτι σχετικά με την παραγωγή των κλειδιών υπογραφής κ επαλήθευσης, καθώς και της γενικής ιδέας πίσω από το σχήμα.
,Ξεκινάμε επιλέγοντας έναν θετικό ακέραιο n, μια συνάρτηση κατακερματισμού, ένα σχήμα υπογραφής μιας φοράς, για παράδειγμα το L-D OTS και επιλέγουμε έναν H (από το Height – ύψος) αριθμό φυσικό, μεγαλύτερο του 2.
Έπειτα, χρησιμοποιούμε το OTS που έχουμε διαλέξει για την παραγωγή 2^Hζευγών (Xi,Yi), όπου Xi συμβολίζουμε τα ιδιωτικά κλειδιά υπογραφής μιας φοράς, ενώ Yi τα δημόσια κλειδιά επαλήθευσης μιας φοράς. Σας έχω και ένα αριθμητικό παράδειγμα από κάτω που θα μπορείτε να δείτε ταυτόχρονα με την εξήγηση.

Και τώρα ξεκινάνε το πιο ενδιαφέροντα πράγματα, με την δημιουργία αυτού που αποκαλούμε δέντρο Merkle το οποίο δημιουργείται ως εξής :

Κατακερματίζοντας τα κλειδιά επαλήθευσης Yi παίρνουμε το τελευταίο επίπεδο του δέντρου.
Και στη συνέχεια, οι κόμβοι του προτελευταίου επιπέδου υπολογίζονται κάθε φορά παίρνοντας τα αμέσως από κάτω αριστερά και δεξιά φύλλα, βάζοντας τα ψηφία τους σε σειρά και κατακερματίζοντας αυτή την παράθεση τους.
Αυτό το συνεχίζουμε και για τους υπόλοιπους εσωτερικούς κόμβους μέχρι να φτάσουμε στο ανώτερο επίπεδο, στη ρίζα του δέντρου.

Ο υπολογισμός αυτής της ρίζας αποτελεί το 4^ο και τελευταίο βήμα και έχουμε πια τα κλειδιά μας για το MSS.
Ιδιωτικό κλειδί θα θεωρηθεί η ακολουθία των κλειδιών υπογραφής μιας φοράς Xi και δημόσιο κλειδί η ρίζα του δέντρου.

Αυτό το δέντρο είναι που χρησιμοποιούν και οι διαδικασίες τις υπογραφής και της επαλήθευσης, χρησιμοποιώντας μονοπάτια που δημιουργούνται μέσα σε αυτό.

31 of 49

Μειονεκτήματα

Τεράστιες απαιτήσεις χώρου.
Χρόνος κ χώρος που χρειάζονται οι επιμέρους διαδικασίες.

CMSS (Chained MSS)

GMSS (Generalized MSS)

XMSS (eXtended MSS)

Ασφάλεια

Κβαντικός Αλγόριθμος Grover

Επιταχύνει κάποιες γενικευμένες επιθέσεις, αλλά όχι αρκετά.

Κβαντικός Αλγόριθμος Shor

Δεν έχει βρεθεί κάποιος τρόπος χρήσης του.

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

Σχήμα Υπογραφής Merkle (MSS)

Είδαμε λοιπόν περιληπτικά πως λειτουργεί το MSS, οπότε το μόνο που μένει είναι να πω μερικά σχόλια γύρω από αυτό και προχωράμε στο επόμενο κεφάλαιο.
Αρχικά ας ξεκινήσουμε αναφέροντας τα δύο μεγάλα μειονεκτήματα του MSS, τα οποία είναι οι τεράστιες απαιτήσεις μνήμης σε κάθε βήμα της διαδικασίας καθώς και ο χρόνος κ ο χώρος που χρειάζεται για την δημιουργία των δέντρων και μετά τον υπολογισμό των λεγόμενων μονοπατιών των δέντρων για την υπογραφή και την επαλήθευση ενός κειμένου.
Αυτά τα μειονεκτήματα είναι που προσπάθησαν να αντιμετωπίσουν νεότερα σχήματα που βασίζονται στο MSS, μερικά από τα οποία βλέπετε δεξία.
Τέλος, ας πούμε και δύο λόγια για την ασφάλεια των σχημάτων υπογραφής συναρτήσεων κατακερματισμού από την κβαντική απειλή.
Και ουσιαστικά αυτό που ισχύει είναι ότι ο Grover επιταχύνει κάποιες πιο γενικευμένες επιθέσεις σε αυτά τα σχήματα αλλά και πάλι όχι αρκετά, δηλαδή όχι σε πολυωνυμικό χρόνο, ενώ όσον αφορά τον αλγόριθμο του Shor, δεν έχει βρεθεί κάποια χρήση του για την κρυπτανάλυση αυτών των σχημάτων

32 of 49

ΚΡΥΠΤΟΓΡΑΦΙΑ

ΔΙΚΤΥΩΤΩΝ

x₁

x₂

y₁

y₂

33 of 49

Βάση Δικτυωτού

«Καλή» Βάση

«Κακή» Βάση

x₁

x₂

y₂

y₁

Βασικές Έννοιες Δικτυωτών

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

Αλγόριθμοι Αναγωγής Βάσης (Gauss, LLL, ...)

Έστω λοιπόν ότι έχουμε n διανύσματα v1,v2,...,vn που ανήκουν στον R^n τα οποία είναι γραμμικά ανεξάρτητα.
Τότε, το σύνολο των γραμμικών συνδυασμών τους με συντελεστές από το Z θα καλείται δικτυωτό.

Αυτός είναι ο αυστηρός ορισμός ενός δικτυωτού και μπορείτε και στο σχήμα δίπλα να δείτε ένα δικτυωτό που παράγεται από 2 διανύσματα, τα x1 και x2 στον R^2.

Ακόμη, κάθε σύνολο γραμμικά ανεξάρτητων διανυσμάτων που παράγουν ένα δικτυωτό L θα αποτελούν βάση του.

Γενικά ένα δικτυωτό μπορεί να έχει πολλές βάσεις, τις οποίες μπορούμε κάπως άτυπα να τις χαρακτηρίσουμε ως καλές ή κακές.
Έτσι, στο σχήμα μας βλέπουμε ότι η βάση x1,x2 είναι μια καλή βάση, ενώ η y1,y2 είναι μια κακή βάση.
Η x1,x2 μπορούμε να πούμε, άτυπα ξαναλέω, ότι είναι καλύτερη λόγω ότι 1. το μέτρο των διανυσμάτων τους είναι πολύ μικρό και 2. ότι τα x1,x2 έχουν σχεδόν ορθή γωνία μεταξύ τους.

Τέλος, να αναφέρω ότι υπάρχουν κάποιοι αλγόριθμοι οι οποίοι μπορούν να μας δώσουνε μια καλή βάση αν τους δώσουμε ως είσοδο μια κακή βάση, όπως αυτός του Gauss και αυτός των Lenstra, Lenstra και Lovász (ο 2^ος από αυτούς συγκεκριμένα σε πολυωνυμικό χρόνο)

34 of 49

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

Βασικές Έννοιες Δικτυωτών

Ακόμη, μια σημαντική έννοια που πρέπει να αναφερθεί πριν προχωρήσουμε είναι αυτή του Θεμελιώδους χωρίου, όπου είναι ακριβώς αυτό που βλέπετε στο διπλανό σχήμα για την περίπτωση των 2 διαστάσεων παίρνοντας διανύσματα της βάσης του δικτυωτού.
Αυτό συνοδεύεται από την εξής πολύ σημαντική πρόταση, που μας λέει πρακτικά ότι μπορούμε να πάρουμε οποιαδήποτε διάνυσμα του χώρου συνδυάζοντας ένα διάνυσμα του θεμελιώδους χωρίου και ένα του δικτυωτού.
Ισοδύναμα, μπορούμε να πούμε ότι η ένωση μετασχηματισμένων θεμελιωδών χωρίων F+v, για v \in L καλύπτει ακριβώς όλο τον R^n

35 of 49

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

Προβλήματα στα Δικτυωτά

Αλγόριθμος του Babai

Τέλος, πριν πάμε στα κρυπτοσυστήματα ας αναφέρουμε τα δύο βασικά προβλήματα των δικτυωτών. Πάνω σε αυτά αλλά και σε παραλλαγές αυτών βασίζονται τα κρυπτογραφικά σχήματα δικτυωτών.
Πρώτα πρώτα βλέπουμε το Πρόβλημα του μικρότερου διανύσματος, το οποίο είναι ακριβώς ότι λέει το όνομα του.

Για παράδειγμα, βλέπουμε στο διπλανό δικτυωτό 2 διαστάσεων 3 διανύσματα ζωγραφισμένα και μπορούμε να φανταστούμε και άλλα.. Εε το μικρότερο διάνυσμα σε αυτή την περίπτωση θα είναι το x καθώς έχει το μικρότερο μέτρο.

Έπειτα, προχωράμε στο Πρόβλημα του Πλησιέστερου Διανύσματος, το οποίο δεν είναι και τόσο διαφορετικό.

Σε αυτό ψάχνουμε ουσιαστικά πάλι το διάνυσμα του δικτυωτού που βρίσκεται πιο κοντά σε ένα διάνυσμα t το οποίο είναι εκτός του δικτυωτού.
Μαθηματικά δηλαδή λέμε ότι σκοπός μας είναι να βρούμε το v που ελαχιστοποιεί την ευκλείδεια νόρμα t-v για την διάσταση που βρισκόμαστε.
Σχηματικά στις 2 διαστάσεις αυτό το βλέπετε δίπλα όπου με κόκκινο έχω χρωματίσει τον στόχο t και με μπλε το πιο κοντινό v.

Τέλος, να αναφέρω απλά την ύπαρξη του αλγορίθμου του babai ο οποίος δεν λύνει το CVP αλλά μας δίνει κάποια προσέγγιση του CVP σε πολυωνυμικό χρόνο. Αυτή η προσέγγιση μπορεί να είναι καλή μόνο αν η βάση του δικτυωτού που χρησιμοποιούμε για τον αλγόριθμο είναι καλή.
Γενικά, δε θα αναφερθώ σε πολυπλοκότητες με P NP κτλ αλλά θα πω απλά ότι αυτά τα προβλήματα ίσως μας φαίνονται εύκολα όπως τα είδαμε σχηματικά σε 2 διαστάσεις αλλά φανταστείτε πόσο η δυσκολία του προβλήματος αυξάνει όσο αυξάνεται ο αριθμός των διαστάσεων.

*(είναι NP hard και NP complete αλλά…)

36 of 49

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

Κρυπτοσύστημα GGH

E_{w1,...,wn}

D _{v1,...,vn}

Κρυπτογράφηση

Αποκρυπτογράφηση

Δημόσιο κλειδί (Μπομπ)

E_{w1,...,wn}(m)

D_{v1,...,vn}(E_{w1,...,wn}(m))

Ιδιωτικό κλειδί (Μπομπ)

Με λεπτομέρεια θα αναφερθώ μόνο σε ένα από τα πρώτα κρυπτοσύστημα δικτυωτών, αυτό των Goldreich, Goldwasser και Halevi, το οποίο βασίζεται στο πρόβλημα κοντινότερου διανύσματος CVP και ίσως μας θυμίσει λίγο και το κρυπτοσύστημα του McEliece από τον τρόπο που γίνεται η κρυπτογράφηση.
Σε αυτό όπως βλέπουμε κλειδιά θα είναι μια ιδιωτική καλή βάση και μια δημόσια κακή βάση αντίστοιχα. Ενώ ακόμη, η κρυπτογράφηση για να στείλει ας πούμε ένα μήνυμα η Αλίκη γίνεται πολλαπλασιάζοντας την κακή βάση του Μπομπ με το διάνυσμα του μηνύματος m και έπειτα προσθέτοντας σε αυτό ένα διάνυσμα λάθους r το οποίο έχει επιλέγεται τυχαία.
Ενώ μετά ο Μπομπ για να διαβάσει το κρυπτογραφημένο μήνυμα θα πρέπει πρώτα να αναιρέσει το λάθος που έχει προσθέσει η Αλίκη, κάτι που γίνεται βρίσκοντας το σωστό v \in L δηλαδή αυτό που βρίσκεται πιο κοντά στο e, χρησιμοποιώντας τον αλγόριθμο του Babai και την καλή της βάση
και μετά να πολλαπλασιάσει αυτό το αποτέλεσμα με τον αντίστροφο του πίνακα της κακής βάσης, ώστε να πάρει το αρχικό μήνυμα.

Ας υποθέσουμε τώρα, ότι κάποιος 3^ος προσπαθεί να αποκρυπτογραφήσει το μήνυμα τότε δε θα μπορεί να το κάνει γιατί δεν θα έχει στα χέρια του το ιδιωτικό κλειδί, δηλαδή την καλή βάση του Μπομπ, ώστε να χρησιμοποιήσει τον αλγόριθμο του Babai και να πάρει το σωστό αποτέλεσμα.

37 of 49

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

Κρυπτογραφικά Σχήματα Δικτυωτών

Άλλα Σχήματα:

Σχήματα κρυπτογράφησης (NTRUEcrypt, CRYSTALS-Kyber...)
Σχήματα υπογραφής (NTRUSign, CRYSTALS-Dilithium,...)
Σχήματα ανταλλαγής κλειδιού (RLWE-KEX,...)
Συναρτήσεις κατακερματισμού (SWIFFT,...)
Πλήρης ομομορφική κρυπτογράφηση

Βασικά χαρακτηριστικά:

Υψηλή ασφάλεια
Μεγαλύτερα κλειδιά αλλά πιο γρήγορες ταχύτητες
Εύκολα υλοποιήσιμα

Συνοψίζοντας λοιπόν, στα γρήγορα έχουμε τα βασικά χαρακτηριστικά των κρυπτογραφικών σχημάτων που χρησιμοποιούν δικτυωτά, τα οποία με λίγα λόγια είναι ότι :

είναι πολύ ασφαλή επειδή βασίζονται σε δύσκολα προβλήματα, αποδεδειγμένα πιο δύσκολα δηλαδή.
Είναι πιο γρήγορα όσον αφορά τις ταχύτητες τους στις διαδικασίες κρυπτογράφησης και αποκρυπτογράφησης, αν και χρησιμοποιούν μεγαλύτερα κλειδιά.
Τέλος, είναι πιο απλά και άρα πιο εύκολα υλοποιήσιμα, σε αντίθεση για παράδειγμα με αυτά της κρυπτογραφίας συναρτήσεων κατακερματισμού που είδαμε πριν.

Επίσης, αναφέρω εδώ μερικά ακόμη γνωστά κρυπτογραφικά σχήματα, τα δύο crystal συγκεκριμένα είναι νικητές ενός διαγωνισμού που τελείωσε τώρα το 2022 και θα σας αναφέρω περισσότερα σχετικά με αυτό στο μικρό κεφάλαιο με το οποίο θα τελειώσει η παρουσίαση.

38 of 49

ΜΙΑ ΜΑΤΙΑ ΣΤΟ ΜΕΛΛΟΝ

						P
						O				N
				A	N	S	S	I		I	B	M
						T				S
			P	R	E	Q	U	A	N	T	U	M
						U
H	Y	B	R	I	D	A	T	I	O	N
						N
		C	R	Y	P	T	O	G	R	A	P	H	Y
						U
						M

39 of 49

Έφτασε η εποχή των κβαντικών υπολογιστών?

Γιατί να μας νοιάζει από τώρα ?

STORE NOW, DECRYPT LATER

Wired

Scientific

American

Forbes

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

Σχετικά με το πόσο κοντά είμαστε στην κατασκευή ενός κβαντικού υπολογιστή αρκετά δυνατού ώστε να τρέχει τους κβαντικούς αλγορίθμους που αναφέραμε
στην ερευνητική κοινότητα κυριαρχεί η ιδέα ότι είμαστε κοντά αλλά και μακριά ταυτόχρονα, όπως μπορείτε να δείτε και σε αυτά τα άρθρα τα οποία έχουν γραφτεί τα τελευταία 2-3 χρόνια.
Αυτό σημαίνει ότι η πλειοψηφία των επιστημόνων πιστεύει ότι, αν και γίνονται τεράστια βήματα καθημερινά, ακόμα δεν έχουν ξεπεραστεί διάφορα σημαντικά προβλήματα και άρα ίσως είμαστε ακόμη μερικές δεκαετίες μακριά από τον στόχο μας.
Οπότε, γιατί μας ενδιαφέρει από τώρα αυτό το θέμα και ασχολούμαστε???
Λόγω της τεχνικής STORE NOW, DECRYPT LATER, σύμφωνα με την οποία μπορεί κάποιος να υποκλέψει και να αποθηκεύσει μηνύματα σημαντικής αξίας σήμερα, ώστε να τα αποκρυπτογραφήσει με την βοήθεια ενός μεγάλου κβαντικού υπολογιστή στο μέλλον.

40 of 49

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

41 of 49

ΗΝΩΜΕΝΕΣ ΠΟΛΙΤΕΙΕΣ ΤΗΣ ΑΜΕΡΙΚΗΣ

National Institute of Standards and Technology (NIST)

ΔΙΑΓΩΝΙΣΜΟΣ NIST (2016)

«Μετακβαντικοί» Αλγόριθμοι που να μπορούν με ασφάλεια να εκτελούν κάποιες διαδικασίες.

(2022) 4 φιναλίστ

(2024) «Τυποποίηση» ;

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

Στην Αμερική πρώτα έχουμε να αναφέρουμε το Εθνικό Ινστιτούτο Προτύπων και Τεχνολογίας και τον διαγωνισμό που ξεκίνησε το 2016 με σκοπό να βρει κάποιους αρκετά ασφαλείς μετακβαντικούς αλγορίθμους τους οποίους να τροποποιήσει και τυποποιήσει ώστε να μπορούν να χρησιμοποιηθούν από το ευρύτερο κοινό τα επόμενα χρόνια.
Οι υποψήφιοι αυτού του διαγωνισμού ανήκαν κυρίως στις 4 κατηγορίες της Μετακβαντικής Κρυπτογραφίας που ανέφερα προηγουμένως, με την κρυπτογραφία δικτυωτών να αποδεικνύεται η πιο πολλά υποσχόμενη από αυτές.
Τέλος να αναφέρω επίσης ότι τώρα ο διαγωνισμός βρίσκεται πλέον έχει τελειώσει με 4 φιναλίστ (2 από τους οποίους είδαμε πριν) και εκτιμάται ότι περίπου το 2024 θα δημοσιευτούν πλήρως τα πρώτα τυποποιημένα σχήματα.

42 of 49

ΓΑΛΛΙΑ (ΕΥΡΩΠΗ)

Agence Nationale de la Securité des Systèmes d’ Information (ANSSI)*

Μετακβαντική Μετάβαση (Άρθρο 2022)

Χρήση υβριδικών μηχανισμών

*BSI (Bundesamt für Sicherheit in der Informationstechnik)

Φλωριάς Παπαδόπουλος

Κρυπτογραφία Στη Μετακβαντική Εποχή

Το κλείσιμο της παρουσίασης θα δοθεί με μια αναφορά στην Ευρώπη έχοντας ως αντιπρόσωπο τον Εθνικό Οργανισμό Ασφάλειας Πληροφοριακών Συστημάτων της Γαλλίας ANSSI καθώς οι απόψεις του συνάδουν με αυτές από οργανισμούς άλλων ευρωπαϊκών χωρών όπως ο BSI της Γερμανίας.
Αυτό που φαίνεται το πιο ενδιαφέρον από τις απόψεις και τα σχέδια του ANSSI είναι το μελλοντικό του σχέδιο για την λεγόμενη Μετακβαντική μετάβαση, όπως μπορούμε να διαβάσουμε σε φετινό άρθρο του ANSSI.
Το ANSSI έχει χωρίσει το σχέδιο του σε 3 φάσεις με την έννοια του υβριδισμού, δηλαδή του συνδυασμού ενός κλασσικού και ενός μετακβαντικού αλγορίθμου στις διεργασίες, να παίζει σημαντικό ρόλο σε κάθε φάση.

Και έτσι φτάσαμε στο τέλος της παρουσίασης.
*N*

43 of 49

Σας ευχαριστώ για την προσοχή σας

44 of 49

Σας ευχαριστώ για την προσοχή σας

45 of 49

Ασφάλεια

Αρχείων

Ασφάλεια Διαδικτύου

Ασφάλεια

Συναλλαγών

Ψηφιακές Υπογραφές

Ανταλλαγή Μηνυμάτων/Μέιλ

Ασφάλεια

Συναλλαγών

Εφαρμογές Σύγχρονης Κρυπτογραφίας

Φλωριάς Παπαδόπουλος

Παύλος Μαραντίδης

Κρυπτογραφία Στη Μετακβαντική Εποχή

46 of 49

Ψηφιακές Υπογραφές

Ασφάλεια

Αρχείων

Ασφάλεια

Διαδικτύου

Ανταλλαγή Μηνυμάτων/Μέιλ

Ασφάλεια

Συναλλαγών

Ασφάλεια

Συναλλαγών

Ασφάλεια

Διαδικτύου

Εφαρμογές Σύγχρονης Κρυπτογραφίας

Φλωριάς Παπαδόπουλος

Παύλος Μαραντίδης

Κρυπτογραφία Στη Μετακβαντική Εποχή

47 of 49

Ανταλλαγή Μηνυμάτων/Μέιλ

Ψηφιακές Υπογραφές

Ασφάλεια

Αρχείων

Ασφάλεια

Συναλλαγών

Ασφάλεια

Διαδικτύου

Ασφάλεια

Διαδικτύου

Ασφάλεια

Αρχείων

Εφαρμογές Σύγχρονης Κρυπτογραφίας

Φλωριάς Παπαδόπουλος

Παύλος Μαραντίδης

Κρυπτογραφία Στη Μετακβαντική Εποχή

Συνεχίζοντας ας σκεφτούμε τα μηνύματα μας, τα μέιλ μας αλλά ακόμη και τις κλήσεις μας από κινητό.
Χωρίς την κρυπτογραφία θα ήταν αδύνατο να στείλουμε ένα μήνυμα ή ένα μέιλ και να είμαστε σίγουροι ότι μόνο εμείς και οι παραλήπτες των μηνυμάτων έχουμε πρόσβαση σε αυτά, ..
Βέβαια για να είμαστε και ειλικρινείς μεταξύ μας, αυτό εξαρτάται και από το μέσο μέσα από το οποίο συζητάμε.
Για παράδειγμα αν μιλάμε μέσω Facebook τα μηνύματα μας αποθηκεύονται και στους σέρβερ του κ. Facebook, οπότε ανάλογα με την εμπιστοσύνη που του έχετε ο καθένας, μπορείτε να καταλάβετε τι σημαίνει αυτό….

48 of 49

Ασφάλεια

Συναλλαγών

Ανταλλαγή Μηνυμάτων/Μέιλ

Ψηφιακές

Υπογραφές

Ασφάλεια Διαδικτύου

Ασφάλεια

Αρχείων

Ασφάλεια

Αρχείων

Ψηφιακές

Υπογραφές

Εφαρμογές Σύγχρονης Κρυπτογραφίας

Φλωριάς Παπαδόπουλος

Παύλος Μαραντίδης

Κρυπτογραφία Στη Μετακβαντική Εποχή

Όσον αφορά τις συναλλαγές μας τώρα, αρχικά να ξεκαθαρίσω (αν δεν έχει γίνει ήδη ξεκάθαρο) ότι κρυπτογραφία δεν είναι μόνο bitcoin και άλλα κρυπτονομίσματα που μπορεί να είναι η μόδα τελευταία.
Στην πράξη χωρίς την κρυπτογραφία το τραπεζικό σύστημα στη τωρινή του μορφή θα κατέρρεε, αφήστε κωδικούς σε τράπεζες και ευαίσθητες πληροφορίες χρηστών και συναλλαγές ονλάιν, οι ίδιες οι πιστωτικές κάρτες και τα συστήματα pos χρησιμοποιούν κρυπτογραφία, καθώς, αν το σκεφτείτε΄με τις πιστωτικές έχουμε κάποιες πληροφορίες οι οποίες ξεκλειδώνονται βάζοντας το pin μας σε ένα P.O.S., όπως είδαμε και πριν στην Ασφάλεια Αρχείων.

49 of 49

Ασφάλεια Διαδικτύου

Ασφάλεια

Συναλλαγών

Ανταλλαγή Μηνυμάτων/Μέιλ

Ασφάλεια

Αρχείων

Ψηφιακές

Υπογραφές

Ψηφιακές

Υπογραφές

Ανταλλαγή Μηνυμάτων/Μέιλ

Εφαρμογές Σύγχρονης Κρυπτογραφίας

Φλωριάς Παπαδόπουλος

Παύλος Μαραντίδης

Κρυπτογραφία Στη Μετακβαντική Εποχή