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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια

Πίνακας περιεχομένων

[Επεξεργασία] Εξαντλητικές Μέθοδοι ή Μέθοδοι Ωμής βίας

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

Μια επιπλέον θεωρητική προσέγγιση της κρυπτανάλυσης του συστήµατος 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. Επιλέγουμε τον παράγοντα που εμφανίζεται πίο συχνά