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

Στην κρυπτανάλυση, με τον όρο ανάλυση συχνότητας γλώσσας περιγράφεται η μελέτη της συχνότητας των γραμμάτων (ή ομάδας γραμμάτων) σε ένα κρυπτογράφημα (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

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

Πηγές

• Π., Αμπατζόγλου, Κρυπτογράφηση και Ποιότητα Υπηρεσιών (Qos) σε Ad-hoc ασύρματα δίκτυα^{[νεκρός σύνδεσμος]}, Μεταπτυχιακή Εργασία, 2009.