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

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

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

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

Βοηθητικά εργαλεία είναι:

  1. Ν-γραμματική πιθανοτική ανάλυση
  2. Ανάλυση δομής Γλώσσας
  3. Ακολουθιακή Γραμματική Ανάλυση κατά Μαρκοφ


Πινακας 2.2 Σχετικές Συχνότητες Γραμμάτων Αγγλικής-Ελληνικής

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


Ιστόγραμμα με τις σχετικές συχνότητες της Αγγλικής γλώσσας



Ανάλυση Δομής Γλώσσας :

  1. Το πίο κοινό πρώτο γράμμα μέσα σε λέξεις T, O, A, W, B, C, D, S, F, M, R, H, I, Y, E, G, L, N, O, 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

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