Κρυπτανάλυση κλασικών κρυπτοσυστημάτων

Εξαντλητικές ΜέθοδοιΕπεξεργασία

Η πιο κοινή μέθοδος επίθεσης σε ένα κρυπτοσύστημα είναι η εξεύρεση του κλειδιού, δοκιμάζοντας όλους τους πιθανούς συνδυασμούς κλειδιών (brute force Attack). Για την υλοποίηση της επίθεσης ο αντίπαλος δοκιμάζει όλο τον κλειδοχώρο, έως ότου καταλήξει σε μία λύση. Ο χώρος κλειδιών του κάθε κρυπτοσυστήματος καθόριζε τη δυσκολία ανεύρεσης του σωστού κλειδιού. Ο κρυπταλγόριθμος μετατόπισης μπορεί να σπαστεί μετά από 26 δοκιμές. Ο αφινικός κρυπταλγόριθμος μετά από 312 δοκιμές. Ο κρυπταλγόριθμος τετραγώνου με μήκος κλειδιού 6 μετά από 321.272.406 δοκιμές. Όταν οι πρώτες υπολογιστικές μηχανές πρωτοεμφανίστηκαν επηρέασαν το κατώτο όριο κλειδιού που χρειαζόταν για να διατηρηθεί η ασφάλεια.

Μία επιπλέον θεωρητική προσέγγιση της κρυπτανάλυσης του συστήµατος RSA, αλλά και των παρόµοιων συστηµάτων που αναπτύχθηκαν μετά από αυτό, όπως το πρωτόκολλο των Diffie-Hellman και το DSS, είναι η Timing Attack (Επίθεση Χρόνου). Η επίθεση αυτή στηρίζεται στο brute force attack αλλά τα επιπρόσθετα στοιχεία τα οποία εισάγει και χρησιµοποιεί, την καθιστούν λιγότερο τυχαιοκρατική. Είναι µια νέα µέθοδος κρυπτανάλυσης την οποία και οφείλουµε να αναλύσουµε, ώστε να δούµε πώς τόσο δυνατά συστήµατα όπως το RSA, το Diffie- Hellman και DSS, βρίσκονται σε κίνδυνο, αλλά και τους τρόπους που ο κίνδυνος αυτός µπορεί να αποφευχθεί.

Ανάλυση ΣυχνότηταςΕπεξεργασία

Η ανάλυση συχνότητας βασίζεται στο γεγονός ότι οι περισσότερες γλώσσες παρουσιάζουν στη δομή (γράμματα ή συνδυασμούς γραμμάτων) τους κάποια ορισμένη κατανομή με μέγιστα και ελάχιστα. τα οποία μπορούν να χαρακτηρίσουν τη γλώσσα αυτή. Με τον υπολογισμό της κατανομής των γραμμάτων μέσα στη γλώσσα βρίσκουμε ένα μέτρο που το ακολουθούν όλα τα κείμενα της γλώσσας αυτής. Για την αγγλική γλώσσα το Ε τείνει να είναι το πιο κοινό γράμμα (με τις περισσότερες επαναλήψεις σε ένα οποιοδήποτε κείμενο) ενώ το Ζ τείνει να είναι το πιο σπάνια συναντούμενο γράμμα. Το ιστιόγραμμα σχ. 3.2 δείχνει ποσοστιαία την εμφάνιση του αγγλικού αλφάβητου σε ένα λογοτεχνικό κείμενο.

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

  1. Ν-γραμματική πιθανοτική ανάλυση
  2. Ανάλυση δομής Γλώσσας
  3. Ακολουθιακή Γραμματική Ανάλυση κατά Μαρκοφ
Πίνακας Εμφάνισης Συχνοτήτων Ελληνικής Γλώσσας
Γράμμα Συχνότητα Εμφανισης Γράμμα Συχνότητα Εμφανισης
Α 12 Ν 7,9
Β 0.8 Ξ 0.6
Γ 2 Ο 9.8
Δ 1.7 Π 5.024
Ε 8 Ρ 5.009
Ζ 0.5 Σ 4.9
Η 2.9 Τ 9.1
Θ 1.3 Υ 4.3
Ι 7.8 Φ 1.2
Κ 4.2 Χ 1.4
Λ 3.3 Ψ 0.2
Μ 4.4 Ω 1,6

Πίνακας 3.1 Αγγλικά Γλωσσικά Μοτίβα

Ανάλυση Δομής Γλώσσας Γράμματα Το πιο κοινό πρώτο γράμμα μέσα σε λέξεις T, O, A, W, B, C, D, S, F, M, R, H, I, Y, E, G, L, N, O, U, J, K Το πιο κοινό δεύτερο γράμμα μέσα σε λέξεις H, O, E, I, A, U, N, R, T Το πιο κοινό τρίτο γράμμα μέσα σε λέξεις E, S, A, R, N, I Το πιο κοινό τελευταίο γράμμα μέσα σε λέξεις E, S, T, D, N, R, Y, F, L, O, G, H, A, K, M, P, U, W Οι περισσότερες λέξεις τελειώνουν με E ,T, D, S Τα γράμματα που ακολουθούν το Ε R,S,N,D Τα πιο κοινά διπλά γράμματα SS, EE, TT, FF, LL, MM, OO

Πινακας 3.2Η Τριγραμματική ανάλυση σε ένα Αγγλικό κείμενο 763 λέξεων Λεξεις Εμφάνιση Συχνότητα The 91 11.9% And 27 3.5% Had 19 2.5% Was 15 2% That 13 1.7%

Διακριτή Στατιστική πηγή ΜαρκόφΕπεξεργασία

Μπορούμε να παραστήσουμε το μήνυμα σαν μία ακολουθία γραμμάτων. Αυτές οι ακολουθίες γραμμάτων δεν είναι τυχαίες αλλά έχουν μία στατιστική εξάρτηση δηλαδή η εμφάνιση ενός γράμματος επηρεάζει την εμφάνιση ένος άλλου γράμματος.Π.χ. η εμφάνιση του του Q συνεπάγει ότι το αμέσως πιθανότερο γράμμα είναι το U. Η πηγή εκπέμπει γράμματα από ένα πεπερασμένο αλφάβητο, έστω το Αγγλικό, σύμφωνα με κάποιες πιθανότητες που εξαρτώνται από το τρέχων γράμμα και από τα προηγούμενα γράμματα. Η πιθανότητα εμφάνισης ενός γράμματος εξαρτάται από το συγκεκριμένο γράμμα και από το αμέσως προηγούμενο πχ P(Xj=b,Xj-1=a) = 0.0228302. Σχηματίζεται επομένως ένας πίνακας 26x26 με όλους τους συνδυασμούς και τις πιθανότητες για κάθε συνδυασμό.

 

Μέθοδος KasiskiΕπεξεργασία

Η εξέταση Kasiski ή αλλιώς τεστ kasiski είναι μια μέθοδος για τη διάσπαση πολυαλφαβητικών κρυπτοσυστημάτων. Η βασική ιδέα είναι η παρατήρηση ότι λόγω της επανάληψης κάποιων λέξεων μέσα στο μήνυμα κρυπτογραφούνται και παράγουν ίδια κρυπτοκείμενα όταν είναι ευθυγραμισμένα με το κλειδί. Τα επαναλαμβανόμενα συμπλέγματα θα πρέπει να είναι τουλάχιστον τρία. Μετρώντας την απόσταση ανάμεσα στα επαναλαμβανόμενα μοτίβα δημιουργείται μια λίστα από αποστάσεις και ο ΜΚΔ όλων αυτών είναι συνήθως το μήκος του κλειδιού. Αν ο κρυπταναλυτής βρει το μήκος του κλειδιού, έστω 5, τότε σε ένα κρυπτογραφημένο κείμενο τα γράμματα στη θέση [1,1+n*5] όπου δημιουργούν μία λίστα μιας μονοαλφαβητικής αντικατάστασης η οποία αναλύεται εύκολα με την ανάλυση συχνότητας γραμμάτων. Καταλήγουμε με τόσες λίστες όσα είναι τα στοιχεία του κλειδιού και αντιμετωπίζουμε πλέον την πολυαλφαβητική αντικατάσταση σαν πολλές απλές μονοαλφαβητικές αντικαταστάσεις.

Τα βήματα για τον έλεγχο kasiski είναι

  1. Αναγνώριση των επαναλαμβανόμενων μοτίβων τριών ή περισσότερων χαρακτήρων.
  2. Για κάθε μοτίβο γράφουμε τη διευθύνση που ξεκινάνε τα μοτίβα.
  3. Υπολογίζουμε την απόσταση μεταξύ των μοτίβων
  4. Προσδιορίζουμε όλους τους παράγοντες των αποστάσεων
  5. Επιλέγουμε τον παράγοντα που εμφανίζεται πιο συχνά