Αρχαία Κρυπτοσυστήματα
Διαβάστε εδώ πώς μπορεί κανείς να επιτεθεί στο σύστημα μονοαλφαβητικής αντικατάστασης με ένα αλγόριθμο τύπου Monte Carlo. Μπορείτε να δείτε μία προσπάθεια υλοποίησης της μεθόδου του Persi Diaconis.
Το one-time-pad (OTP) είναι ασφαλές εφόσον κάθε κλειδί χρησιμοποιείται μία φορά. Σε αυτή την εργασία θα αποκρυπτογραφήσετε μηνύματα που έχουν κρυπτογραφηθεί με το OTP χρησιμοποιώντας το ίδιο κλειδί. Για μία πραγματική ιστορία "αποτυχίας" του OTP, λόγω επανειλλημένης χρήσης του κλειδιού, ψάξτε για το project Venona.
Το OTP είναι ασφαλές εναντίον παθητικών αντιπάλων, δηλαδή αντιπάλων που παρακολουθούν την επικοινωνία, αλλά δεν παρεμβαίνουν. Είναι όμως ανεπαρκές όταν ο αντίπαλος είναι ενεργητικός. Στην εργασία αυτή θα δούμε ένα παράδειγμα μίας τέτοιας επίθεσης.
Συμμετρική Κρυπτογραφία
Όπως είδαμε, το βασικό μειωνέκτημα της τέλειας ασφάλειας είναι ότι κάθε κλειδί μπορεί να χρησιμοποιηθεί μόνο μία φορά και πρέπει να έχει μέγεθος ίσο με το μέγεθος του μηνύματος. Για να μπορούμε να κατασκευάσουμε και να μελετήσουμε κρυπτοσυστήματα τα οποία θα είναι πιο πρακτικά, πρέπει να χαλαρώσουμε τις απαιτήσεις μας για το τι σημαίνει ασφαλές κρυπτοσύστημα. Αυτή η χαλάρωση γίνεται σε δύο άξονες:
- περιορίζουμε τις δυνατότητες του αντιπάλου, απαιτώντας να είναι αποτελεσματικός αλγόριθμος (πολυωνυμικού χρόνου αλγόριθμος) και
- επιτρέπουμε η πιθανότητα ο αντίπαλος να μπορεί να αναγνωρίσει ποιό μήνυμα έχει κρυπτογραφηθεί (μεταξύ δύο οποιονδήποτε μηνυμάτων της επιλογής του) να είναι μεγαλύτερη από 1/2 (που είναι τετριμμένο να επιτευχθεί), αλλά μεγαλύτερη κατά αμελητέα ποσότητα.
Αυτό μας οδηγεί στην έννοια της σημασιολογικής ασφάλειας (semantic security).
Μία κατασκευή ένος κρυπτοσυστήματος που ικανοποιεί τον ορισμό της σημασιολογικής ασφάλειας είναι ουσιαστικά το OTP, όπου όμως το κλειδί πλέον δεν είναι πραγματικά τυχαία ακολουθία ψηφίων, αλλά παράγεται ντετερμινιστικά από ένα αλγόριθμο με είσοδο μία αρχική τιμή (seed), η οποία έχει επιλεγεί τυχαία. Για να είναι ασφαλές το κρυπτοσύστημα, η ακολουθία θα πρέπει να μοιαζει τυχαία (ενώ δεν είναι!) σε κάθε επιτιθέμενο. Αυτό μας οδηγεί στον ορισμό της ψευδοτυχαίας γεννήτρια αριθμών (Pseudorandom Number Generator, PRG).
"Ψευδοτυχαίες γεννήτριες" όπως ο Linear Congruencial Generator (LCG) χρησιμοποιούνται ευρέως για επιστημονικούς υπολογισμούς, αλλά δεν είναι ασφαλείς με την έννοια που απαιτεί η κρυπτογραφία. Στην εργασία αυτή θα το δείξετε! Ο stream cipher που προκύπτει αν χρησιμοποιήσουμε ένα LCG, φυσιολογικά, δεν είναι σημασιολογικά ασφαλής. Δείξτε το σε αυτή την εργασία!