Ανάλυση συχνότητας γλώσσας
 |
Το λήμμα περιέχει τεχνικές λεπτομέρειες που ενδεχομένως οι περισσότεροι αναγνώστες δεν είναι σε θέση να κατανοήσουν. Μπορείτε να το βελτιώσετε ώστε να είναι κατανοητό και από μη ειδικούς, χωρίς να αφαιρεθούν οι τεχνικές λεπτομέρειες, κλιμακώνοντας την εμβάθυνση προς το τέλος του λήμματος. |
 |
Το λήμμα παραθέτει τις πηγές του αόριστα, χωρίς παραπομπές. |
Στην κρυπτανάλυση, με τον όρο ανάλυση συχνότητας γλώσσας περιγράφεται η μελέτη της συχνότητας των γραμμάτων (ή ομάδας γραμμάτων) σε ένα κρυπτογράφημα (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. Χρησιμοποιώντας την κατανομή χαρακτήρων ψάχνουμε να βρούμε τον πιο επαναλαμβανόμενο κρυπτοχαρακτήρα και τον αντικαθιστούμε από τον πιο επαναλαμβανόμενο χαρακτήρα της φυσικής γλώσσας. Συνεχίζουμε την ανάλυση έως φθάσουμε σε μία μοναδική λύση (Το εξαγόμενο μήνυμα να έχει γλωσσικό νόημα).
Βοηθητικά εργαλεία είναι η ανάλυση δομής γλώσσας (δηλαδή η ανάλυση της συχνότητας εμφάνισης χαρακτήρων σε ένα οποιοδήποτε κείμενο μιας γλώσσας), η Ν-γραμματική πιθανοτική ανάλυση (δηλαδή η ανάλυση της κατανομής συχνότητας εμφάνισης λέξεων Ν χαρακτήρων μέσα σε κάποιο κείμενο της γλώσσας) και ακολουθιακή γραμματική ανάλυση κατά Μαρκόφ (αφορά σχέσεις που πιθανόν να έχουν μεταξύ τους τα γράμματα στις λέξεις της γλώσσας).
Ανάλυση Δομής Γλώσσας
[Επεξεργασία | επεξεργασία κώδικα]- Το πιο κοινό πρώτο γράμμα μέσα σε λέξεις: T, O, A, W, B, C, D, S, F, M, R, H, I, Y, E, G, L, N, 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
Ν-γραμματική πιθανοτική ανάλυση
[Επεξεργασία | επεξεργασία κώδικα]Η Τριγραμματική ανάλυση σε ένα Αγγλικό κείμενο 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.