Ανάλυση Συχνότητας Γλώσσας
Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
[Επεξεργασία] Κρυπτανάλυση Μονοαλφαβητικής Αντικατάστασης
Ο κρυπταναλυτής χρησιμοποιεί μία μέθοδο που λέγεται ανάλυση συχνότητας η οποία διασπά την μονοαλφαβητική αντικατάσταση τεχνική αυτή μελετάει την στατιστική δομή της γλώσσας του κρυπτομηνύματος σχ 2.2 πιν 2.2.Η ανάλυση συχνότητας βασίζεται στο γεγονός ότι οι περισσότερες γλώσσες παρουσιάζουν στην δομή (γράμματα ή συνδυασμούς γραμμάτων) τους κάποια ορισμένη κατανομή με μέγιστα και ελάχιστα. τα οποία μπορούν να χαρακτηρίσουν την γλώσσα αυτή. Με τον υπολογισμό της κατανομής των γραμμάτων μέσα στην γλώσσα βρίσκουμε ένα μέτρο που το ακολουθούν όλα τα κείμενα της γλώσσας αυτής. Για την αγγλική γλώσσα το Ε τείνει να είναι το πιο κοινό γράμμα (με της περισσότερες επαναλήψεις σε ένα οποιοδήποτε κείμενο) ενώ το Ζ τείνει να είναι το πιο σπάνια συναντούμενο γράμμα. Σε μερικά κρυπτοσυστήματα τέτοιες ιδιότητες της φυσικής γλώσσας συντηρούνται στο κρυπτογράφημα, και αυτά οι κατανομές δίνουν τη δυνατότητα μίας επίθεσης κρυπτοκειμένου. Χρησιμοποιώντας την κατανομή χαρακτήρων ψάχνουμε να βρούμε για τον πιο επαναλαμβανόμενο κρυπτοχαρακτήρα. και τον αντικαθιστούμε από τον πιο επαναλαμβανόμενο χαρακτήρα της φυσικής γλώσσας. και συνεχίζουμε την ανάλυση έως φθάσουμε σε μία μοναδική λύση(Το εξαγόμενο μήνυμα να έχει γλωσσικό νόημα).
Βοηθητικά εργαλεία είναι:
- Ν-γραμματική πιθανοτική ανάλυση
- Ανάλυση δομής Γλώσσας
- Ακολουθιακή Γραμματική Ανάλυση κατά Μαρκοφ
Πινακας 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
Ανάλυση Δομής Γλώσσας :
- Το πίο κοινό πρώτο γράμμα μέσα σε λέξεις 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
Η Τριγραμματική ανάλυση σε ένα Αγγλικό κείμενο 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
Συνεχίζει επιλέγοντας σαν ζευγάρι το Ζ να το αντικαταστήσει με το Τ ή το Α κλπ.. Μελετάει την διγραμματική κατανομή.