Ανάλυση συχνότητας γλώσσας

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση
Ιστόγραμμα με τις σχετικές συχνότητες γραμμάτων της αγγλικής γλώσσας

Στην κρυπτανάλυση, με τον όρο ανάλυση συχνότητας γλώσσας περιγράφεται η μελέτη της συχνότητας των γραμμάτων (ή ομάδας γραμμάτων) σε ένα κρυπτογράφημα (ciphertext). Η τεχνική αυτή εφαρμόζεται σε περιπτώσεις όπου το πρωτότυπο κείμενο (plaintext) έχει κρυπτογραφηθεί με κάποια μέθοδο Μονοαλφαβητικής Αντικατάστασης, δηλαδή κάθε ένα γράμμα του πρωτότυπου αντικαθίσταται με μόνο έναν άλλο χαρακτήρα.

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

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

Κρυπτανάλυση Μονοαλφαβητικής Αντικατάστασης[Επεξεργασία | επεξεργασία κώδικα]

Σχετικές Συχνότητες Γραμμάτων Αγγλικής-Ελληνικής
A B C D E F G H I J K L M
8,2 1,4 2,8 3,8 12,7 2,9 2,0 5,3 6,3 0,1 0,4 3,4 2,3
N O P Q R S T U V W X Y Z
7,1 8,0 2,0 0,1 6,8 6,1 10,5 2,5 0,9 1,5 0,2 2,0 0,1
Α Β Γ Δ Ε Ζ Η Θ Ι Κ Λ Μ Ν
12 0,8 2 1,7 8 0.5 2,9 1,3 7,8 4,2 3,3 4,4 7,9
Ξ Ο Π Ρ Σ Τ Υ Φ Χ Ψ Ω
0,6 9,8 5,024 5,009 4,9 9,1 4,3 1,2 1,4 0,2 1,6

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

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

Ανάλυση Δομής Γλώσσας[Επεξεργασία | επεξεργασία κώδικα]

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

Ν-γραμματική πιθανοτική ανάλυση[Επεξεργασία | επεξεργασία κώδικα]

Η Τριγραμματική ανάλυση σε ένα Αγγλικό κείμενο 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 με όλους τους συνδυασμούς και τις πιθανότητες για κάθε συνδυασμό. Συμπεραίνουμε ότι το μήνυμα σαν ακολουθία περιέχει μνήμη την οποία μπορούμε να ποσοτικοποιήσουμε

Παράδειγμα[Επεξεργασία | επεξεργασία κώδικα]

Έστω ο κρυπταναλυτής έχει αποκτήσει πρόσβαση στο κρυπτοκείμενο. WSADSXDAONVOPDDZQCQSINYAKAOQCZNPUSSAZJOEDYZEDVUJZQDZNZNZJSFSIVPDXDJSUWDNYONMZXSASMYCDAOQCDVYUZAYSMYCDUSUIJZYOSNYCZYVYCDQIAADNYUASFA DVVSMCIWZNOYKVYZNPHDCONPZJJHJZHJZHJZAOQCFDYAOQCDAUSSAFDYUSSADAZNOQDVSQODYKONPDDPCDZPDPZYMIJJVUDDPZFZONVYZHAOQELZJJOZPXOQDKSIYSMZVYD NKSIAVDZYHDJYZNPYSVDZYNDBYYSZNDWDAFDNQKDBOYJOEDQAZQEONFLSAELDJJSAQ

Το πρώτο βήμα που κάνει ο κρυπταναλυτής είναι να μετρήσει την συχνότητα που εμφανίζονται τα γράμματα( πιν 2.3) στο κρυπτοκείμενο και μετά να τα συσχετίσει με το ιστόγραμμα 2.2 Το πιο εμφανιζόμενο γράμμα μέσα στο κρυπτοκείμενο είναι το γράμμα D το οποίο τείνει να είναι το γράμμα Ε αλλά αυτό δεν είναι σίγουρο. Ο κρυπταναλυτής οδηγείται σε διάφορους συσχετισμούς ανάλογα με την συχνότητα γραμμάτων.

Πίνακας 2.3 Μετρήσεις κατανομής γραμμάτων

Νούμερο. χαρακτήρας        Συχνότητες(%)   Μέτρηση Συχνότητας
   1              D             12.5000         41
   2              Z              9.7561         32
   3              Y              8.5366         28
   4              S              8.2317         27
   5              A              7.3171         24
   6              N              6.4024         21
   7              O              6.4024         21
   8              J              5.4878         18
   9              Q              4.8780         16
  10              V              4.2683         14
  11              C              3.6585         12
  12              P              3.6585         12
  13              U              3.0488         10
  14              I              2.4390         8
  15              F              2.1341         7
  16              E              1.8293         6
  17              H              1.8293         6
  18              K              1.8293         6
  19              M              1.8293         6
  20              W              1.2195         4
  21              X              1.2195         4
  22              L              0.9146         3
  23              B              0.6098         2

Διγραματική Ανάλυση

   1                ZN              2.4465         8
   2             OQ              2.1407         7
   3             SA              2.1407         7
   4             AO              1.8349         6
   5             CD              1.8349         6
   6             ON              1.8349         6
   7             DA              1.5291         5
   8             DZ              1.5291         5
   9             JZ              1.5291         5
  10             NP              1.5291         5
  11             QC              1.5291         5
  12             VY              1.5291         5
  13             ZY              1.5291         5
  14             AD              1.2232         4
  15             DN              1.2232         4
  16             DV              1.2232         4
  17             DY              1.2232         4
  18             JJ              1.2232         4
  19             NY              1.2232         4
  20             PD              1.2232         4
  21             SI              1.2232         4
  22             SM              1.2232         4
  23             US              1.2232         4
  24             YC              1.2232         4
  25             YS              1.2232         4
  26             YZ              1.2232         4


Αντικαθιστά μέσα στο κρυπτοκείμενο το D με το Ε

wsaEsxEaonvopEEzqcqsinyakaoqcznpussazjoeEyzeEvujzqEznznzjsfsivpExEjsuwEnyonmzxsasmycEaoqcEvyuzaysmycEusuijzyosnyczyvycEqiaaEnyuasfaEvvsmciwznoykvyznphEconpzjjhjzhjzhjzaoqcfEyaoqcEaussafEyussaEaznoqEvsqoEykonpEEpcEzpEpzymijjvuEEpzfzonvyzhaoqelzjjozpxoqEksiysmzvyEnksiavEzyhEjyznpysvEzynEbyysznEwEafEnqkEboyjoeEqazqeonflsaelEjjsaq

Συνεχίζει επιλέγοντας σαν ζευγάρι το Ζ να το αντικαταστήσει με το Τ ή το Α κλπ.. Μελετάει την διγραμματική κατανομή.

Πηγές[Επεξεργασία | επεξεργασία κώδικα]