Συχνότητα εμφάνισης γραμμάτων

[Re4cTiV3]

Σκέφτομαι να υλοποιήσω ένα πρόγραμμα που θα κάνει κάποια αποκωδικοποίηση με επίθεση συχνόττας γραμμάτων.

 

Έστω ότι κάποιος μου δίνει αυτό το ciphertext: (παρμένο απο εδώ)

 

LIVITCSWPIYVEWHEVSRIQMXLEYVEOIEWHRXEXIPFEMVEWHKVSTYLXZIXLIKIIXPIJVSZEYPERRGERIM

WQLMGLMXQERIWGPSRIHMXQEREKIETXMJTPRGEVEKEITREWHEXXLEXXMZITWAWSQWXSWEXTVEPMRXRSJ

GSTVRIEYVIEXCVMUIMWERGMIWXMJMGCSMWXSJOMIQXLIVIQIVIXQSVSTWHKPEGARCSXRWIEVSWIIBXV

IZMXFSJXLIKEGAEWHEPSWYSWIWIEVXLISXLIVXLIRGEPIRQIVIIBGIIHMWYPFLEVHEWHYPSRRFQMXLE

PPXLIECCIEVEWGISJKTVWMRLIHYSPHXLIQIMYLXSJXLIMWRIGXQEROIVFVIZEVAEKPIEWHXEAMWYEPP

XLMWYRMWXSGSWRMHIVEXMSWMGSTPHLEVHPFKPEZINTCMXIVJSVLMRSCMWMSWVIRCIGXMWYMX

 

 

με βάση αυτήν την συχνότητα γραμμάτων:

 

private final double[] probOfLetters = {

//John Hershey. Cryptography Demystified. McGraw-Hill, 2003

//Order by letter

0.0642, 0.0127, 0.0218, 0.0317,

0.1031, 0.0208, 0.0152, 0.0467,

0.0575, 0.0008, 0.0049, 0.0321,

0.0198, 0.0574, 0.0632, 0.0152,

0.0008, 0.0484, 0.0514, 0.0796,

0.0228, 0.0083, 0.0175, 0.0013,

0.0164, 0.0005, 0.1859

};

 

 

Βρίσκω ότι την συχνότητα εμφάνισης των γραμμάτων του cipher και αποθηκεύω τις θέσεις τους για πιο γρήγορο υπολογισμό μετά. το θέμα μου είναι πως θα συσχετίσω τις συχνότητες που βρίσκω με αυτές που δίνω παραπάνω. Η σύγκριση με floating point είναι λίγο δύσκολη..

 

Εγώ βρίσκω ότι για το ciphertext οι συχνότητες είναι αυτές....

 

Letter 'A' : 0.010706638115631691

Letter 'B' : 0.004282655246252677

Letter 'C' : 0.019271948608137045

Letter 'D' : 0.0

Letter 'E' : 0.10278372591006424

Letter 'F' : 0.01284796573875803

Letter 'G' : 0.034261241970021415

Letter 'H' : 0.034261241970021415

Letter 'I' : 0.12419700214132762

Letter 'J' : 0.019271948608137045

Letter 'K' : 0.019271948608137045

Letter 'L' : 0.047109207708779445

Letter 'M' : 0.0728051391862955

Letter 'N' : 0.0021413276231263384

Letter 'O' : 0.006423982869379015

Letter 'P' : 0.044967880085653104

Letter 'Q' : 0.02569593147751606

Letter 'R' : 0.057815845824411134

Letter 'S' : 0.06423982869379015

Letter 'T' : 0.02569593147751606

Letter 'U' : 0.0021413276231263384

Letter 'V' : 0.06638115631691649

Letter 'W' : 0.07494646680942184

Letter 'X' : 0.08779443254817987

Letter 'Y' : 0.027837259100642397

Letter 'Z' : 0.01284796573875803

Letter space(?) : 0.0

 

 

Επεξ/σία 21 Νοεμβρίου 2012 από Re4cTiV3

[albNik]

Μια στρατηγική είναι να ταξινομήσεις τις συχνότητες (γενικές και του cipher) κατά φθίνουσα σειρά και να τις ζευγαρώσεις.

Αν δεν ταιριάξουν να πάρεις το επόμενο permutation των συχνοτήτων του cipher που προκαλούν το μικρότερο derangement μέχρι να πετύχει.

Δηλαδή μια σειρά από permutations με αύξοντα derangement.

Στη χειρότερη περίπτωση (δλδ εντελώς ανάποδα οι συχνότητες) θα χρειαστείς 27! (=10*28 ) συνδυασμούς αλλά πιστεύω θα βρεθεί πολύ πιο γρήγορα.

 

[defacer]

Το σημαντικό ερώτημα που τίθεται εδώ είναι: μιλάμε για πρόγραμμα που θα σε βοηθάει να βρεις τη λύση (αλλά το τελικό OK το δίνεις εσύ) ή για πρόγραμμα που κάνει ο,τι καλύτερο μπορεί χωρίς άλλο input εκτός από το ciphertext?

 

Προφανώς το δεύτερο είναι απείρως δυσκολότερο και αν σ' ενδιαφέρει θα πρέπει να το ρίξεις στη μελέτη ακαδημαϊκών papers για να έχεις αποτέλεσμα -- το ίδιο ισχύει για πολλά ενδιαφέροντα προβλήματα στο computer science.

 

Οπότε, which of the two?

[Re4cTiV3]

Φυσικά και θα ήθελα το δεύτερο αλλά δεν υπάρχει ο χρόνος αυτήν την στιγμή.. άρα πάμε στο πρώτο...

 

Με κάτι τέτοιο θα ήμουν ψιλο οκ νομίζω...

 

τι εννοείς derangement; albNik ;

[Directx]

Πριν αρκετά χρόνια είχε συζητηθεί ένα παραπλήσιο ερώτημα εδώ και εδώ, τότε είχαμε γράψει μερικά προγραμματάκια που έλυναν μερικά προβλήματα που σχετιζόντουσαν με συχνότητες λέξεων, brute-force, XOR ciphers κλπ. Ίσως σου φανούν χρήσιμα (γενικά το νήμα είχε αρκετό ενδιαφέρον από την αρχή ως την λήξη του).

 

 

Ήταν η εποχή που είχα πρόσφατη την ανάγνωση του βιβλίου "Κώδικες & Μυστικά" του SIMON SINGH και αδημονούσα να εφαρμόσω μερικές από τις περιγραφόμενες τεχνικές του

 

Ένας απλός κώδικας σε C++ που μετρά την συχνότητα εμφάνισης χαρακτήρων γραμμένος σε C++ Builder.

 

>
/* Letter frequency, xdir. */

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <functional>
#include <iomanip>

using namespace std;

int main(void)
{
   const string strIn = // Not to be empty!
       "LIVITCSWPIYVEWHEVSRIQMXLEYVEOIEWHRXEXIPFEMVEWHKVSTYLXZIXLIKIIXPIJVSZEYPERRGERIM"
       "WQLMGLMXQERIWGPSRIHMXQEREKIETXMJTPRGEVEKEITREWHEXXLEXXMZITWAWSQWXSWEXTVEPMRXRSJ"
       "GSTVRIEYVIEXCVMUIMWERGMIWXMJMGCSMWXSJOMIQXLIVIQIVIXQSVSTWHKPEGARCSXRWIEVSWIIBXV"
       "IZMXFSJXLIKEGAEWHEPSWYSWIWIEVXLISXLIVXLIRGEPIRQIVIIBGIIHMWYPFLEVHEWHYPSRRFQMXLE"
       "PPXLIECCIEVEWGISJKTVWMRLIHYSPHXLIQIMYLXSJXLIMWRIGXQEROIVFVIZEVAEKPIEWHXEAMWYEPP"
       "XLMWYRMWXSGSWRMHIVEXMSWMGSTPHLEVHPFKPEZINTCMXIVJSVLMRSCMWMSWVIRCIGXMWYMX";

   vector<pair<double, char> > LetterFreq;

   for(char C = 'A'; C < 'Z'; C++)
       LetterFreq.push_back(make_pair(
           (count(strIn.begin(), strIn.end(), C) / (double)strIn.size()) * 100.0,
           C));

   sort(LetterFreq.begin(), LetterFreq.end(), greater<pair<double, char> >());

   for(int F = 0; F < LetterFreq.size(); F++)
       cout << setw(8) << setprecision(4) << LetterFreq.at(F).first << "% = " << LetterFreq.at(F).second <<endl;

   cout << "\nPress Enter to exit..";
   cin.get();

   return 0;
}

ΕΞΟΔΟΣ:

>
  12.42% = I
  10.28% = E
  8.779% = X
  7.495% = W
  7.281% = M
  6.638% = V
  6.424% = S
  5.782% = R
  4.711% = L
  4.497% = P
  3.426% = H
  3.426% = G
  2.784% = Y
   2.57% = T
   2.57% = Q
  1.927% = K
  1.927% = J
  1.927% = C
  1.285% = F
  1.071% = A
 0.6424% = O
 0.4283% = B
 0.2141% = U
 0.2141% = N
      0% = D

Press Enter to exit..

Ο κώδικας μπορεί να περιέχει bugs ή άλλες αβλεψίες.

 

 

Επεξ/σία 22 Νοεμβρίου 2012 από Directx

[albNik]

Partial derangment (n,k) είναι ο αριθμός των συνδυασμών n αντικειμένων όπου k βρίσκονται εκτός αρχικής θέσης.

http://mathworld.wolfram.com/PartialDerangement.html

Δηλαδή να ξεκινούσες με k=0,1,2...

 

Η καλύτερα να τα συνδύαζες με βάση μια συνάρτηση που μεγιστοποιεί τη συσχέτιση τους

F=probOfLetters[0]*prob[a0] + probOfLetters[1]*prob[a1] + ...

 

 

 

 

[Re4cTiV3]

το αντίστοιχο vector θέλω να το βρώ στην java... τώρα την μαθαίνω..ξέρει κανείς;

[defacer]

Φυσικά και θα ήθελα το δεύτερο αλλά δεν υπάρχει ο χρόνος αυτήν την στιγμή.. άρα πάμε στο πρώτο...

 

Με κάτι τέτοιο θα ήμουν ψιλο οκ νομίζω...

 

ΟΚ, σ' αυτή την περίπτωση και μιας που αναφέρθηκε o Singh, δες εδώ. Γενικά η ιδέα είναι πως θέλεις να δοκιμάσεις με κάποια heuristics να βρεις "γρήγορα" κάτι κοντά στη σωστή λύση, μιας και οι πιθανότητες δεν είναι με το μέρος σου οπότε με brute forcing δε θα πας μακριά.

 

Αυτό που κάνεις link δεν είναι αντιπροσωπευτικό γιατί ο Caesar cipher είναι μια πολύ απλή υποπερίπτωση της μοναλφαβητικής αντικατάστασης -- οι πιθανές περιπτώσεις είναι συνολικά 26 αντί για 26! που είναι στη γενική περίπτωση.

[Re4cTiV3]

Λοιπόν βρήκα την λύση αλλιως. Απλός αφαίρεσα απο την μεγαλύτερη πιθανότητα του ciphertext το 'e' ώστε να βρω το "key" αν δεν είναι αυτό ο χρήστης πατάει next και προχωράει...

 

τώρα όταν χρόνο θα δοκιμάσω και αυτό που λες...

[chdeal]

Βέβαια, αν κωδικοποιούνται και οι μη αλφαβητικοί χαρακτήρες, τη μεγαλύτερη συχνότητα θα την έχει το ' ' (κενό) και όχι το 'e'.