Поделюсь тогда и я результатом, не знаю на сколько у меня грамотный подход
суть в том что длинну ключа мы определяем более-менее устойчиво
потом просто берем случайный ключь, проверяем результат посимвольно, если абракадабра то сразу генерим новый ключь, если нет то считаем все пробели и оцениваем их частоту, если она близка к теоретической - ключь найден
C++ |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
| //code and decode if exist key
void code(ifstream &src, ofstream &result, const char * kodeTable){
size_t codeStackSize = strlen(kodeTable);
int i = 0;
char ch;
while ( src.good() ) {
src.get(ch);
if (src.good())
result << (char)(ch^kodeTable[i%codeStackSize]);
i++;
}
}
//find key and decode
void decode(ifstream &src, ofstream &result){
const int size_buf = 50000;
const int max_key_size = 15;
// const int iter_num = 1000000000;
char buffer_src[size_buf];
char buffer[size_buf];
char ch;
int frec_table[max_key_size];
//READ FILE
char * p = buffer_src;
char * pp = buffer;
while ( src.good() ) {
src.get(ch);
if (src.good()){
*p++ = ch;
*pp++ = ch;
}
}
*p = '\0';
*pp = '\0';
int text_size = strlen(buffer_src);
//DETERM LENGTH OF KEY WORD
for (int i=0; i<max_key_size; i++){
//left cycle shift of string!
ch = buffer[0];//char go to end of new buffer
for (int j=0; j<text_size-1; j++){
buffer[j] = buffer[j+1];
}
buffer[text_size-1] = ch;
buffer[text_size] = '\0';
//CALCULATE frec of ecuality src txt and shifted txt
frec_table[i]=0;
for (int j=0; j<text_size; j++){
if (buffer[j] == buffer_src[j])
frec_table[i]++;
}
result << "frec[" << i+1 << "]=" << frec_table[i] << endl;
}
//FIND local maximum
int key_len = 0;
float epsilon = 1.99f;
if ( frec_table[1]*epsilon < frec_table[0]){
key_len = 1;
} else {
for (int i=1; i<max_key_size; i++){
if ( frec_table[i+1] > frec_table[i]*epsilon){
key_len = i+2;
break;
}
}
}
result << "size of text = " << text_size << endl;
result << "calc key len = " << key_len << endl;
cout << "size of text = " << text_size << endl;
cout << "calc key len = " << key_len << endl;
// cout << (int)'А' << ' ' << (int)'Я' << ' ' << (int)'а' << ' ' << (int)'я' << endl;
// cout << (int)'A' << ' ' << (int)'Z' << ' ' << (int)'a' << ' ' << (int)'z' << endl;
// cout << (int)' ' << ' ' << (int)'\t' << ' ' << (int)'\n' << ' ' << (int)'\v' << endl;
//FIND KEY! (FROM FREC OF ' ' = 0.178609)
char key[max_key_size];
char key_tmp[max_key_size];
key_tmp[0] = '\0';
float sp_frec = 0.178609f;
//maching key
srand(time(NULL));
int mach_count=0;
float delta=0;
float delta_min=1;
// for (int i = 0; i<iter_num; i++){
long int i = 0;
while (delta_min > 0.01f){
if (i%(iter_num/100) == (iter_num/100-1))
cout << i/(iter_num/100) + 1 << '%' << endl;
//INIT KEY
for (int key_i = 0; key_i < key_len ; key_i++){
key[key_i] = rand()%64 + 'А';
}
key[key_len] = '\0';
mach_count=0;
//DECODE WITH CURRENT KEY
for (int j=0; j<text_size-1; j++){
buffer[j] = buffer_src[j]^key[j%key_len];
//IF IN TEXT INCORRECT SYMBOL
if ( (buffer[j] < -111 & buffer[j] != -123)
|| (buffer[j] > -105 & buffer[j] < 9)
|| (buffer[j] > 12 & buffer[j] < 32)
|| (buffer[j] > 126) ){
mach_count = 0;
break;
}
if (buffer[j] == ' ')
mach_count++;
}
//Exam result
if (mach_count != 0)
delta = sp_frec - (mach_count*1.0f)/(text_size*1.0f);
else
delta = 1;
if (delta<0) delta = -delta;
if (delta_min > delta) {
delta_min = delta;
strcpy(key_tmp, key);
result << "key = " << key_tmp << ' ' << mach_count << ' ' << i << ' ' << delta << endl;
}
i++;
}
result << "RES key = " << key_tmp << endl;
cout << "RES key = " << key_tmp << endl;
//DECODE WITH TRUE KEY
for (int j=0; j<text_size-1; j++){
result << (char)(buffer_src[j]^key_tmp[j%key_len]);
}
} |
|
Знаю что плохо с размером массивов намутил, но пока главное принцип,
ключевое слово из 3 букв ищет в среднем за 10-100 тыс случ итераций
а вот уже с 4 буквами не всегда хватает и миллиарда итераций
из 6 букв не находил вообще ни разу
Добавлено через 6 часов 4 минуты
Есть идеи как повысить эффективность алгоритма? Я так понял есть возможность статистически определять не только длину ключа но и наиболее вероятные буквы в ключе, может кто подскажет как?